Konstantinos Daskalakis
University of California,
Berkeley
"Computing Equilibria in Games"
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.
Monday, May 5, 2008
3:00 - 4:15
Wu & Chen
101 Levine Hall