CS Colloquia: Computing Equilibria in Games

Title: Computing Equilibria in GamesSpeaker: Constantinos Daskalakis (UC Berkeley)ABSTRACT:
Game Theory is important for the study of large competitive environments, such
as the Internet, the market, and even social and biological systems. A key
tool in analyzing such systems (games) is the study of their stable states,
that is, their equilibria. Understanding the properties of equilibria can give
insights into the effectiveness of economic policies, engineering decisions,
etc. However, due to the large scale of most interesting games, the problem of
computing equilibria cannot be separated from complexity considerations.
Motivated by this challenge, I will discuss the problem of computing
equilibria in games.I will show first that computing a Nash equilibrium is an intractable problem.
It is not NP-complete, since, by Nash's theorem, an equilibrium is always
guaranteed to exist, but it is at least as hard as solving any fixed point
computation problem, in a precise complexity-theoretic sense.In view of this hardness result, I will present algorithms for computing
approximate equilibria. In particular, I will describe algorithms that achieve
constant factor approximations for 2-player games, and give a quasi-polynomial
time approximation scheme for the multi-player setting.Finally, I will consider a very natural and important class of games termed
anonymous games. In these games every player is oblivious to the identities of
the other players; examples arise in auction settings, congestion games, and
social phenomena. I will introduce a polynomial time approximation scheme for
the anonymous setting and provide surprising connections to Stein's method in
probability theory.BIO:
Constantinos (or Costis) Daskalakis grew up in Athens, Greece, where he
received his undergraduate degree in Electrical and Computer Engineering from
the National Technical University of Athens. In 2004 he moved to California to
pursue a Ph.D. in Computer Science at U.C. Berkeley under the supervision of
Professor Christos H. Papadimitriou. Costis¡¦s work has focused on
computational game theory and applied probability, in particular the
computation of equilibria in games, the study of social networks, and
computational problems in biology. His research is motivated by two questions:
"How does the algorithmic perspective influence economics, biology, physics,
and the social sciences?" And, "how does the study of computational problems
arising from areas outside computer science transform the theory of
computation?"

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia