Bernoulli Factories and Black-Box Reductions in Mechanism Design
Authors:
- Shaddin DughmiSDShaddin Dughmi
- Jason HartlineJHJason Hartline
- Robert KleinbergRKRobert Kleinberg
- Rad NiazadehRNRad Niazadeh
Preprint
Abstract
We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism's output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on $\textit{Bernoulli factories}$. In a Bernoulli factory problem, one is given a function mapping the bias of an "input coin" to that of an "output coin", and the challenge is to efficiently simulate the output coin given only sample access to the input coin. This is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline et al. (2015) exactly incentive compatible.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Optimal Linear Bernoulli Factories for Small Mean ProblemsMethodology and Computing in Applied Probability, 2016
- Introduction to Online Convex OptimizationFoundations and Trends® in Optimization, 2016
- Non-Optimal Mechanism DesignAmerican Economic Review, 2015
- Bayesian incentive compatibility via matchingsGames and Economic Behavior, 2015
- A Dynamic Near-Optimal Algorithm for Online Linear ProgrammingOperations Research, 2014
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- Efficient algorithms for online decision problemsJournal of Computer and System Sciences, 2005
- Fast simulation of new coins from oldThe Annals of Applied Probability, 2005
- An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter AgentsInternet Mathematics, 2004
- Algorithmic Mechanism DesignGames and Economic Behavior, 2001