20 citations · 95 across the 39 of their papers we have counts for
4 papers · 1 filter
On the Complexity of Dynamic Mechanism Design
Christos Papadimitriou, George Pierrakos, Christos-Alexandros Psomas +1
We introduce a dynamic mechanism design problem in which the designer wants to offer for sale an item to an agent, and another item to the same agent at some point in the future. T…
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…
Inapproximability of Nash Equilibrium
Aviad Rubinstein
We prove that finding an -approximate Nash equilibrium is PPAD-complete for constant and a particularly simple class of games: polymatrix, degree 3 graphical games, in which…
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…