Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shang-Hua Teng:

TR09-041 | 9th April 2009
Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

Reducibility Among Fractional Stability Problems

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

TR06-031 | 27th February 2006
Li-Sha Huang, Shang-Hua Teng

On the Approximation and Smoothed Complexity of Leontief Market Equilibria

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

Computing Nash Equilibria: Approximation and Smoothed Complexity

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

ISSN 1433-8092 | Imprint