Black-box reductions in mechanism design

Abstract

A central question in algorithmic mechanism design is to understand the additional difficulty introduced by truthfulness requirements in the design of approximation algorithms for social welfare maximization. In this paper, by studying the problem of single-parameter combinatorial auctions, we obtain the first black-box reduction that converts any approximation algorithm to a truthful mechanism with essentially the same approximation factor in a prior-free setting. In fact, our reduction works for the more general class of symmetric single-parameter problems. Here, a problem is symmetric if its allocation space is closed under permutations. As extensions, we also take an initial step towards exploring the power of black-box reductions for general single-parameter and multi-parameter problems by showing several positive and negative results. We believe that the algorithmic and game theoretic insights gained from our approach will help better understand the tradeoff between approximability and the incentive compatibility. © 2011 Springer-Verlag.