TIME: 1:30-2:20 pm,  May 29, 2007


SPEAKER: Shang-Hua Teng
         Boston University

TITLE:  Game and Market Equilibria

I will present some recent advances in algorithmic game theory especally
about 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.

In particular, I will cover the recent results in settling several
open questions about Nash equilibria with focus on the approximation
and 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 (City
University of Hong Kong). Also with Li-Sha Huang (Tsinghua University)
and Paul Valiant (MIT).