From Games to Markets: On the Computation of Equilibria
In the past decade, models and approaches from Game Theory and Economics have been widely applied in the study of large-scale competitive environments such as the Internet and e-commerce. The concept of equilibria, i.e., that of stable states, serves as one of the key tools in such studies, and its computation has attracted great attention. In this talk, we will focus on the problem of computing equilibria in two of the most fundamental models of competitions in Game Theory and Economics: games and markets.
Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. In 1954, Arrow and Debreu showed that under very mild conditions, every market has an equilibrium. While games and Nash equilibria are used to predict the behavior of selfish agents in conflicting situations, the study of markets and market equilibria laid down the foundation of competitive pricing. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other.
In this talk, we will review the recent characterizations of how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show that these results also significantly advanced our understanding about equilibria in the market setting.
No prior knowledge of Game Theory will be assumed for this talk.
Xi Chen received his B.S. degree in Physics in 2003 and his Ph.D. in Computer Science in 2007, both from Tsinghua University, China. He then became a postdoctoral researcher at the Institute for Advanced Study, and at Princeton University, hosted by Avi Wigderson and Sanjeev Arora. This year he has been at the University of Southern California, hosted by Shang-Hua Teng.
The research interests of Dr. Chen lie mainly in Algorithmic Game Theory and Theoretical Computer Science in general. He is particularly interested in characterizing the intrinsic difficulties of natural and fundamental problems that arise in the game-theoretic study of Internet and e-commerce. He won the best paper awards of the 47th IEEE Symposium on Foundations of Computer Science (FOCS) in 2006 (for his work on the computation of Nash equilibria) and the 20th International Symposium on Algorithms and Computation in 2009 (for his work on the computation of market equilibria).