Truthful mechanisms with implicit payment computation

DOI10.1145/2724705MaRDI QIDQ2796397zbMATH OpenOpenAlexFDO

Authors Moshe Babaioff, Aleksandrs Slivkins, Robert D. Kleinberg

Publication date 24 March 2016

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.3630

zbMATH Keywords

algorithmic mechanism designmulti-armed banditsmultiparameter mechanismsregretsingle-parameter mechanisms

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Applications of statistics to economics (62P20) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating a randomized truthful mechanism is essentially as easy as a single call to a monotone allocation rule. Our main result is a general procedure to take a monotone allocation rule for a single-parameter domain and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. The mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once. We also provide an extension of this result to multi-parameter domains and cycle-monotone allocation rules, under mild star-convexity and non-negativity hypotheses on the type space and allocation rule, respectively. Because our reduction is simple, versatile, and general, it has many applications to mechanism design problems in which re-evaluating the allocation rule is either burdensome or informationally impossible. Applying our result to the multi-armed bandit problem, we obtain truthful randomized mechanisms whose regret matches the information-theoretic lower bound up to logarithmic factors, even though prior work showed this is impossible for truthful deterministic mechanisms. We also present applications to offline mechanism design, showing that randomization can circumvent a communication complexity lower bound for deterministic payments computation, and that it can also be used to create truthful shortest path auctions that approximate the welfare of the VCG allocation arbitrarily well, while having the same running time complexity as Dijkstra's algorithm.

Recommendations

• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• scientific article; zbMATH DE number 2079341
• Two Randomized Mechanisms for Combinatorial Auctions
• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions

Cites work

• A necessary and sufficient condition for rationalizability in a quasilinear context
• A truthful mechanism for value-based scheduling in cloud computing
• Algorithmic mechanism design
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• An efficient dynamic mechanism
• Asymptotically efficient adaptive allocation rules
• Bayesian algorithmic mechanism design
• Bayesian incentive compatibility via fractional assignments
• Bayesian incentive compatibility via matchings
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Bundling as an optimal selling mechanism for a multiple-good monopolist
• Characterizing Truthful Multi-armed Bandit Mechanisms
• Contextual bandits with similarity information
• Finite-time analysis of the multiarmed bandit problem
• Haggling over substitutes
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485582 (Why is no real title available?)
• scientific article; zbMATH DE number 6253908 (Why is no real title available?)
• Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
• Monotonicity and implementability
• On the limits of black-box reductions in mechanism design
• On the Power of Randomization in Algorithmic Mechanism Design
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Optimal Auction Design
• Optimal auctions with correlated bidders are easy
• Pricing lotteries
• Regret bounds and minimax policies under partial monitoring
• Regret bounds for sleeping experts and bandits
• The communication burden of payment determination
• The dynamic pivot mechanism
• The Nonstochastic Multiarmed Bandit Problem
• Truthful germs are contagious: a local-to-global characterization of truthfulness
• Truthful learning mechanisms for multi-slot sponsored search auctions with externalities
• Truthful mechanisms with implicit payment computation

Cited in

(13)

• A truthful mechanism for value-based scheduling in cloud computing
• An optimal bidimensional multi-armed bandit auction for multi-unit procurement
• Mechanisms with learning for stochastic multi-armed bandit problems
• Truthful mechanisms with implicit payment computation
• Bayesian Incentive-Compatible Bandit Exploration
• Mechanisms with monitoring for truthful RAM allocation
• Algorithms as mechanisms: the price of anarchy of relax and round
• Competing bandits: learning under competition
• Fast Core Pricing for Rich Advertising Auctions
• Bayesian exploration: incentivizing exploration in Bayesian games
• Multi-scale online learning: theory and applications to online auctions and pricing
• On the power of randomization in algorithmic mechanism design
• Explicitly simple near-tie auctions

This page was built for publication: Truthful mechanisms with implicit payment computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796397)