CS Colloquium

Speaker: Shaddin Dughmi, Stanford University

Talk Title: Randomization and Computation in Strategic Settings

Abstract: In resource allocation problems, a centralized agency allocates resources to
recipients: an Internet Service Provider allocates bandwidth to consumers; the Federal Communications Commission auctions radio spectra to telecommunications companies; and a content distribution company designs an overlay network to satisfy its customers' routing needs. Often, the agency's goal is to find an allocation that maximizes the social good. This goal is complicated by the fact that the recipients are self-interested, and their actions influence the allocation.

Economists cope with self-interested behavior by designing mechanisms that align individual incentives with the social good. This requires finding an optimal solution to the -- often intractable -- resource allocation problem.
Computer scientists cope with intractability by designing approximation algorithms. Until recently, it appeared difficult to unify these techniques and design incentive-compatible computationally-efficient mechanisms for computing approximately optimal allocations. Impossibility results regarding deterministic mechanisms suggest that this difficulty is fundamental.

My work harnesses the power of randomization to reconcile economic and computational requirements in settings where deterministic mechanisms provably can not. My colleagues and I (1) developed general techniques for the design of randomized mechanisms, (2) applied these techniques to solve some of the paradigmatic problems in this area, and (3) developed a black box reduction that, for a large class of problems, generically converts an approximation algorithm to an incentive compatible mechanism without degrading its approximation guarantee.

Biography: Shaddin Dughmi is a PhD student in the computer science theory group at Stanford University, advised by Professor Tim Roughgarden. His main research interests are in algorithms, game theory, and combinatorial optimization. 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: Prof. David Kempe

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal