03-05

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