An Extension Theorem for the Price of Anarchy in Games of Incomplete Information
Speaker: Tim Roughgarden , Stanford University
Date: April 24 2012
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Costis Daskalakis, Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Pure-strategy Nash equilibria --- where each player deterministically
picks a single action --- are often easier to analyze than their more
general cousins like mixed-strategy Nash equilibria (where players can
randomize) and Bayes-Nash equilibria (where players don't even know
with certainty what game they're playing in).
For this reason, the price of anarchy of a game --- the worst-case
ratio between the objective function value of an equilibrium and of an
optimal outcome --- is often analyzed, at least initially, only for
the game's pure-strategy Nash equilibria. But as much as he or she
might want to, the conscientious researcher cannot stop there. For
example, the Nash equilibrium concept fundamentally assumes that all
players' preferences are common knowledge, which is inappropriate for
most auction and mechanism design contexts, where participants have
private information.
Can we obtain price of anarchy bounds for more general equilibrium
concepts without working any harder than we already do to analyze
pure-strategy Nash equilibria? Ideal would be an "extension theorem"
that could be used in the following ``black-box'' way: (1) prove a
bound on the price of anarchy of pure-strategy Nash equilibria of a
game; (2) invoke the extension theorem to conclude immediately that
the exact same approximation bound applies to some more general
equilibrium concept. Such an extension theorem would dodge the
obvious deterrents from generalizing price of anarchy bounds beyond
pure Nash equilibria --- no extra work, and no loss in the
approximation guarantee.
In this talk, I'll describe a new extension theorem for games of
incomplete information, along with some applications.
Bio:
Tim Roughgarden received his Ph.D. from Cornell University in
2002 and joined the Stanford CS department in 2004, where he is
currently an associate professor. His research interests are in
theoretical computer science, especially its interfaces with game
theory and networks. He wrote the book "Selfish Routing and the Price
of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game
Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007).
His awards include the 2002 ACM Doctoral Dissertation Award (Honorable
Mention), the 2003 Tucker Prize, the 2003 INFORMS Optimization Prize
for Young Researchers, speaking at the 2006 International Congress of
Mathematicians, a 2007 PECASE Award, the 2008 Shapley Lectureship of
the Game Theory Society, and the 2009 ACM Grace Murray Hopper Award.
He recently developed a free online course on the design and analysis
of algorithms, which has tens of thousands of students.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in April 2012
