
CS Colloquium
Tue, Nov 09, 2010 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
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 polynomialtime 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 multiunit auctions and variants of combinatorial auctions, and (2) Showing how a blackbox reduction can transforms any FPTAS for a socialwelfare 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 welfaremaximization 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 metaquestion 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