The Limits of Black-Box Transformations in Mechanism Design
Speaker: Brendan Lucier , Microsoft Research, NE
Date: November 29 2011
Time: 4:15PM to 5:15PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, be@csail.mit.edu
A single-parameter mechanism design problem is an optimization problem with a game-theoretic twist: the input values are held by rational agents, who may misrepresent the input for their own gain. To combat this manipulation one might ask for an algorithm that is truthful, meaning that it is in the best interest of each agent to report its value truthfully. In general, however, the impact of the truthfulness requirement on the approximation factors achievable by polynomial-time algorithms for single-parameter problems is unknown.
We consider the problem of converting an arbitrary approximation algorithm for a single-parameter optimization problem into a computationally efficient truthful mechanism. We ask for reductions that are "black-box", meaning that they require only oracle access to the given algorithm and in particular do not require explicit knowledge of the problem constraints.
We show that no such general black-box reduction exists, even for single-parameter problems. Specifically, we show that a black-box reduction for the social welfare objective is not possible if the resulting mechanism is required to be truthful in expectation and to preserve the worst-case approximation ratio of the algorithm to within a subpolynomial factor. Further, we prove that for other objectives such as makespan, no black-box reduction is possible even if we only require Bayesian truthfulness and an average-case performance guarantee.
Joint work with Shuchi Chawla and Nicole Immorlica
See other events that are part of Theory Colloquium 2011/2012
See other events happening in November 2011
