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

__
TR06-031
| 27th February 2006
__

Li-Sha Huang, Shang-Hua Teng#### On the Approximation and Smoothed Complexity of Leontief Market Equilibria

__
TR06-023
| 7th February 2006
__

Xi Chen, Xiaotie Deng, Shang-Hua Teng#### Computing Nash Equilibria: Approximation and Smoothed Complexity

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

"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 >>>

Li-Sha Huang, Shang-Hua Teng

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 >>>

Xi Chen, Xiaotie Deng, Shang-Hua Teng

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 >>>