Shaddin Dughmi talk, Thursday, 3:30
David Kempe
our next theory faculty candidate is just around the corner. Shaddin
Dughmi from Stanford will give a talk this coming Thursday at 3:30.
All key information is below.
I'm looking forward to seeing many of you there.
Time: Thursday, 03/10, 3:30pm
Location: SSL 150
Speaker: Shaddin Dughmi, Stanford University
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.
--------------------
Bio:
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.