Events Calendar

CS Colloquium

Speaker: Shaddin Dughmi, Stanford University

Talk Title: How to Compute in a Selfish Society: Randomness May be the Key

Abstract: 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.


Biography: Shaddin Dughmi is a PhD student in the computer science theory group at Stanford University, advised by Professor Tim Roughgarden. His interests include algorithms, game theory, and combinatorial optimization. Recently, Shaddin has focused on the following meta-question in algorithmic mechanism
design: When and how can we efficiently compute a desirable solution to a resource allocation problem despite the presence of selfish behavior? Shaddin graduated from Cornell University in 2004 with a B.S. in computer science and a minor in applied mathematics. From 2004 to 2006, he was an Information Security Engineer at the MITRE Corporation, where he worked on cryptographic protocol analysis. He enrolled in the Stanford computer science PhD program in the Fall of 2006, with an expected graduation date of June 2011.


Host: Dr. David Kempe

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal