From Algorithms to Auctions

Speaker  Brendan Lucier

Host  Jennifer Chayes

Affiliation  Microsoft Research New England

Duration  01:25:33

Date recorded  5 November 2012

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.

©2012 Microsoft Corporation. All rights reserved.
> From Algorithms to Auctions