Boston University | Center for Computational Science
HomeNews and EventsResearchEducationPeopleSeminarsFacilitiesContact Us

CCS Seminar
Friday - December 8, 2006
12:00 noon
PRB 595 - 3 Cummington Street

Professor Shang-Hua Teng - Computer Science, Boston University

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 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 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 the 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).

Page last updated on November 28, 2006. Please send comments to Cheryl Endicott.

copyright © 2006, Center for Computational Science | Boston Unversity , MA, 02215