On the Power of Randomization in Algorithmic Mechanism Design

Abstract

In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem. In particular, we construct an FPTAS for multi-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We also show for the first time that truthful in expectation polynomial-time mechanisms are \emph{provably} stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting in which: (1) there is a non-polynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.

Cited by in corpus (12)

• Truthfulness via Proxies
• Mechanisms for Risk Averse Agents, Without Loss
• Combinatorial Auctions with Restricted Complements
• Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions
• A Note on the Power of Truthful Approximation Mechanisms
• Fast Convex Decomposition for Truthful Social Welfare Approximation
• Interdependent Values without Single-Crossing
• Truthful Mechanisms with Implicit Payment Computation
• A Note on Relaxation and Rounding in Algorithmic Mechanism Design
• Truthfulness with Value-Maximizing Bidders
• Mechanism Design via Dantzig-Wolfe Decomposition
• Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design