Harvard Theory of Computation Seminar
Game and Market Equilibria
Shanghua Teng, Boston University and Akamai Technologies
Place and Time: Monday, February 26, Maxwell Dworkin 221
Refreshments at 2:30pm, talk at 2:45pm
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
complexities 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).