From Algorithms to Auctions

An auction designer faces an optimization problem with a twist. The designer’s goal is to allocate resources effectively, but the input to this allocation problem is held by rational participants who may misrepresent their private values for personal gain. To combat this manipulation one might ask for allocation rules that are incentive compatible, so that it is in the best interest of each participant to report truthfully. In general, however, it can be difficult to design auctions that are both truthful and computationally tractable, especially in complex settings where many related items are to be sold simultaneously.

One possible solution to these issues would be a general method for converting approximation algorithms into truthful mechanisms. Such a transformation would allow designers to separate the computational and economic aspects of auction design. In this talk I will describe a line of work aimed at finding such black-box reductions, for single-parameter problems. I will present a reduction that applies in Bayesian settings, as well as a strong negative result on the power of black-box reductions in non-Bayesian settings. I will then describe a natural subclass of auction problems – those that are downward-closed – that admits non-Bayesian black-box reductions with small (but unavoidable) loss.