20 citations · 95 across the 39 of their papers we have counts for
Showing 2014 · cs.GTShow all
3 papers · 2 filters
cs.GT2014
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…
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.GT2014
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…