Title: Game and Market Equilibria
Abstract:
I will present some recent advances in Algorithmic Game Theory and
particularly in computing and approximating game and market
equilibria. As you may have already known, the notion of the Nash
equilibrium 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 deep and fundamental
mathematical structures. As the scale of typical internet applications
increases, the problem of efficiently analyzing their game-theoretic
properties become more pointed. I will discuss the recent results in
settling several open questions about Nash equilibria. I will focus on
the approximation and smoothed complexity of equilibrium computation
in noncooperative two-player games. I will also address 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).
Biography:
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 more than ten US Patents for his work on compiler
optimization and Internet technology.
