[talks] Talk on Wed. 3/5/2008 4:15PM

[Ginny Hogan]

Konstantinos Daskalakis, UC Berkeley, 
will present his talk "Computing Equilibria in Games" 
Wed 3/5/2008 at 4:15pm Computer Science Room 105 -

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?"