68 citations · 163 across the 20 of their papers we have counts for
7 papers · 1 filter
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
Xi Chen, Shang-Hua Teng
It is a common belief that computing a market equilibrium in Fisher's spending model is easier than computing a market equilibrium in Arrow-Debreu's exchange model. This belief is…
Preference Games and Personalized Equilibria, with Applications to Fractional BGP
Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram +1
We study the complexity of computing equilibria in two classes of network games based on flows - fractional BGP (Border Gateway Protocol) games and fractional BBC (Bounded Budget C…
Bounded Budget Connection (BBC) Games or How to make friends and influence people, on a budget
Nikolaos Laoutaris, Laura J. Poplawski, Rajmohan Rajaraman +2
Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or…
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…
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…
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…