CCS Seminar

Friday, December 8, 2006
12:00 noon
PRB 593  at 3 Cummington Street

Game and Market Equilibria

Shanghua Teng
Department of 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 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). 

Created for the Boston University/SCV Projects Page.

Created by The CoCoBoard.