@inproceedings{chawla2011on,
author = {Chawla, Shuchi and Immorlica, Nicole and Lucier, Brendan},
title = {On the Impossibility of Black-Box Transformations in Mechanism Design},
booktitle = {Symposium on Theory of Computing 2012},
year = {2011},
month = {September},
abstract = {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. Such a reduction is known to be possible, for example, for the social welfare objective when the goal is to achieve Bayesian truthfulness and preserve social welfare in expectation. 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/impossibility-black-box-transformations-mechanism-design/},
edition = {Symposium on Theory of Computing 2012},
}