How to Compute in a Selfish Society: Randomness May be the Key
Shaddin Dughmi
Nov 17, 2010
Algorithmic Mechanism Design is concerned with solving computational problems in situations where essential problem data is being held privately by selfish agents. Techniques from economics have long existed for aligning the incentives of the agents with the social good, yet they often require solving a hard optimization problem exactly. On the other hand, computer scientists have coped with intractability by designing approximation algorithms. Unfortunately, recent results have demonstrated that these two approaches are fundamentally at odds for deterministic mechanisms: combining truthfulness and polynomial-time computation results in an inevitable deterioration of the approximation ratio for many important problems.

Fortunately, there is hope: randomized mechanisms are emerging that reconcile computational and economic constraints, yielding optimal approximate mechanisms for problems where deterministic mechanisms provably fail. In this talk, I will advocate randomized mechanism design by taking a tour through a sequence of our recent results. I will illustrate the power of randomized mechanisms by: (1) Overviewing recent positive results for paradigmatic problems such as multi-unit auctions and variants of combinatorial auctions, and (2) Showing how a black-box reduction can transforms any FPTAS for a social-welfare maximization problem into a truthful FPTAS , and (3) Arguing that, in the future, there is hope for more powerful black box reductions that would yield sweeping positive results for welfare-maximization problems in general.