From Algorithms to Auctions


November 5, 2012


Brendan Lucier


Microsoft Research New England


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.


Brendan Lucier

Brendan Lucier is a Postdoctoral Researcher at Microsoft Research New England. He received his PhD in Computer Science at the University of Toronto under the supervision of Allan Borodin and Mike Molloy. His research interests lie in theoretical computer science and game theory. He is particularly interested in algorithmic mechanism design and the theory of social networks.