8 citations · 34 across the 9 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.GT2014★ 6 cited
Computational Complexity of Approximate Nash Equilibrium in Large Games
Aviad Rubinstein
We prove that finding an epsilon-Nash equilibrium in a succinctly representable game with many players is PPAD-hard for constant epsilon. Our proof uses succinct games, i.e. games…
cs.CC2014★ 7 cited
On Simplex Pivoting Rules and Complexity Theory
Ilan Adler, Christos Papadimitriou, Aviad Rubinstein
We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm's path. Such rules cannot be the basis of a…