Events Calendar

CS Colloq: Dr. Xi Chen

Talk Title: From Two-Player Games to Markets: On the Computation of Equilibria
Speaker: Xi Chen
Host: Prof. David KempeAbstract:
Recently, there has been tremendous interest in the study of Algorithmic Game Theory. This is a rapidly growing area that lies at the intersection of Computer Science, Game Theory, and Mathematical Economics, mainly due to the presence of selfish agents in highly decentralized systems, the Internet in particular. The computation of Nash equilibria in games and the computation of Market equilibria in exchange markets have received great attention.
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 some of the results that characterize how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show how these results also advanced our understanding about market equilibria.
No prior knowledge of Game Theory will be assumed for this talk.Bio:
Dr. Xi Chen received his B.S. degree in Physics from Tsinghua University in 2003 and his Ph.D. in Computer Science from Professor Andrew Chi-Chih Yao's Institute for Theoretical Computer Science at Tsinghua University in 2007. He then became a postdoctoral researcher at the Institute for Advanced Study, hosted by Professor Avi Wigderson. Last year, he was a postdoctoral researcher at Princeton University, hosted by Professor Sanjeev Arora, and this year he is hosted by Professor Shang-Hua Teng at University of Southern California.The research interests of Dr. Chen lie mainly in Algorithmic
Game Theory and Complexity Theory. 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. His Ph.D. thesis titled "The Complexity of Two-Player Nash Equilibria" won the Silver prize of the New World Mathematics Award, presented by the International Congress of Chinese Mathematicians every three years. He also won the best paper awards of the 47th IEEE Symposium on Foundations of Computer Science and the 20th International Symposium on Algorithms and Computation.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Front Desk