Oct 5, 2006: Game and Market Equilibria: Approximation and Smoothed Complexity
Filed in: Colloquium
Dr. Shang-Hua Teng, Boston University
We will present some recent advances in Computational Game Theory and particularly in computing and approximating Nash equilibria. In the recent years, 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 deep and fundamental mathematical structures. As the complexity and scale of typical internet applications increase, the problem of efficiently analyzing their game-theoretic properties becomes more crucial.
We will cover the recent results on settling several open questions about Nash equilibria. We 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, we 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)
Dr. Shang-Hua Teng is currently 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 member 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 the Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received the NSF Faculty Early Career Development Award.
Dr. Teng received a B.S. degree in computer science and a B.A. degree in electrical engineering from Shanghai Jiao Tong University in 1985, an 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.
Abstract
We will present some recent advances in Computational Game Theory and particularly in computing and approximating Nash equilibria. In the recent years, 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 deep and fundamental mathematical structures. As the complexity and scale of typical internet applications increase, the problem of efficiently analyzing their game-theoretic properties becomes more crucial.
We will cover the recent results on settling several open questions about Nash equilibria. We 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, we 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
Dr. Shang-Hua Teng is currently 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 member 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 the Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received the NSF Faculty Early Career Development Award.
Dr. Teng received a B.S. degree in computer science and a B.A. degree in electrical engineering from Shanghai Jiao Tong University in 1985, an 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.