68 citations · 128 across the 9 of their papers we have counts for
Showing 2007Show all
3 papers · 1 filter
cs.GT2007★ 4 cited
Settling the Complexity of Computing Two-Player Nash Equilibria
Xi Chen, Xiaotie Deng, Shang-Hua Teng
We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the comp…
cs.GT2007
Games on the Sperner Triangle
Kyle Burke, Shang-Hua Teng
We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to h…
cs.GT2007★ 2 cited
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
Xi Chen, Shang-Hua Teng
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d…