Game and Market Equilibria: Approximation and Smoothed Complexity
Shanghua Teng
Department of Computer Science
Boston University
Friday, October 20, 2006
4:00 - 5:00 PM
Terman Engineering Center, Room 453
Abstract:
I will present some recent advances in Computational Game Theory and
particularly in computing and approximating Nash equilibria. As you may
have already known, the notion of Nash equilibria has captured the
imagination of much of the computer science theory community,
both for its many applications in the growing domain of online interactions
and for its deeps and fundamental mathematical structures. As the
complexity and scale of typical internet applications increase,
the problem of efficiently analyzing their game-theoretic properties
become more pointed.
I will cover the recent results in settling several open questions
about Nash equilibria. I will particularly focus on the complexity
of approximation in, as well as the smoothed complexity of,
non-cooperative two-player games. Those results link the
computational complexity of Nash equilibria to Brower's fixed point,
Sperner's lemma, and to Papadimitriou's complexity class, PPAD,
characterized by the end-of-line problem.
If time permits, I will also cover the extensions of these results
to other equilibrium problems such as in trading and market
economies.
Joint work with Xi Chen (Tsinghua University), Xiaotie Deng
(The City University of Hong Kong). Also with Li-Sha Huang (Tsinghua
University) and Paul Valiant (MIT).
Bio:
Shang-Hua Teng is now a full professor in the Computer Science
Department at Boston University and also a senior research scientist
at Akamai Technologies Inc. He taught as a faculty in the Department
of Mathematics of MIT and in the Computer Science Departments of the
University of Minnesota and UIUC.
He has worked and consulted for IBM Almaden Research Center, Intel
Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine
Corporation, and NASA Ames Research Center. He is an Alfred P. Sloan
Fellow, winner of Senior Xerox Award for Outstanding Faculty Research
(UIUC), and has received NSF Faculty Early Career Development Award.
Teng received a B.S. degree in computer science and a B.A. degree
in electrical engineering from Shanghai Jiao Tong University in 1985,
a M.S. degree in computer science from University of Southern
California (USC) in 1988, and a Ph.D. degree in computer science
from Carnegie Mellon University (CMU) in 1991.
With Dan Spielman of MIT, he developed the theory of Smoothed Analysis
for modeling and analyzing practical algorithms, and had demonstrated
that the simplex method for linear programming has a polynomial
smoothed complexity. This joint work was cited by National Science
Foundation in its FY'03 budget request to Congress. His research
centers on the design and analysis of efficient algorithms. His recent
interests include computational game theory, spectral graph theory
and its applications in optimization and information processing,
parallel scientific computing, computational geometry, graph partitioning
and clustering, and cryptography. He has also received 8 US Patents
for his work on compiler optimization and Internet technology.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html