From Games to Markets: On the Computation of Equilibria

Speaker:	Dr. Xi CHEN
		University of Southern California

Title:		"From Games to Markets: On the Computation of Equilibria"

Date:		Monday, 29 March 2010

Time:		4:00pm - 5:00pm

Venue:		Lecture Theater F (near lifts 25/26) HKUST

Abstract:

Recently, there has been tremendous interest in the study of Algorithmic
Game Theory. This 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 games. We will then show how these results also
significantly advanced our understanding about market equilibria.

No prior knowledge of Game Theory will be assumed for this talk

********************
Biography:

Dr. Xi Chen received his B.S. degree in Physics from Tsinghua University
in 2003 and his Ph.D. in Computer Science from the Institute for
Theoretical Computer Science at Tsinghua University in 2007.  He then
became a postdoctoral researcher at the Institute for Advanced Study, and
at Princeton University. He is currently a postdoctoral researcher at the
University of Southern California.

Dr. Chen's research interests 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 the Internet and
e-commerce. His Ph.D. thesis, "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 (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).