Computing
Equilibria in Large Games
By

Dr.
Constantinos Daskalakis
Postdoctoral
Researcher, Microsoft ResearchNew England

Date:
Dec 15, 2008 (Monday) 
Time:
2:30pm  3:30pm 
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK 
Abstract
:
How
long does it take a market or, more broadly, a game
to reach an equilibrium state? I will present joint
work with Paul Goldberg and Christos Papadimitriou,
showing that convergence to a Nash equilibrium may
take prohibitively long. Since a Nash equilibrium
is guaranteed to exist in every gameby Nash's seminal
result, NPcompleteness does not seem appropriate
for characterizing its complexity. Our result is that
the Nash equilibrium is as hard computationally as
the general Brouwer fixedpoint computation problem,
in a precise technical sense. The existence of the
Nash equilibrium is established via Brouwer fixedpoint
theorem; hence our result is the computational converse
of Nash's theorem.
To
alleviate the negative implications of this hardness
result for the predictive power of the Nash equilibrium,
it is important to study the computation of approximate
equilibria: an efficient approximation scheme would
imply that games can in principle come arbitrarily
close to a Nash equilibrium in a sufficiently large
number of gameplays. I will discuss such polynomialtime
approximation schemes for special classes of twoplayer
games and describe obstacles towards obtaining a polynomialtime
approximation scheme for the general twoplayer case.
I will then turn to a large and important class of
multiplayer games, called anonymous, in which the
players's utilities, although potentially different,
do not differentiate among the identities of the other
players; examples arise in congestion, social interactions,
and certain auction settings. I will present several
approaches for approximating multiplayer anonymous
games with two strategies, culminating in an efficient
PTAS with quasipolynomial dependence on the approximation.
Biography
:
Constantinos
(or Costis) Daskalakis grew up in Athens, Greece,
where he received an undergraduate degree in Electrical
and Computer Engineering from the National Technical
University of Athens. In 2004 he moved to California
where he completed his doctorate studies in Computer
Science at UC Berkeley under the supervision of Professor
Christos Papadimitriou. His research interests lie
in Algorithmic Game Theory and Applied Probability,
particularly in computational aspects of markets and
the Internet, in social networks, and in computational
problems in Biology. The Game Theory Society honored
Costis and his collaborators, Paul Goldberg and Christos
Papadimitriou, with the first Game Theory and Computer
Science Prize for their work on the Computational
Complexity of the Nash equilibrium. Costis was also
the recipient of a Microsoft Research Fellowship in
honor of Dean Richard Newton, and a UC Regents Fellowship.
Costis will join the EECS faculty at MIT as an Assistant
Professor in fall 2009, while spending this year at
Microsoft ResearchNew England. 