4 citations · 15 across the 17 of their papers we have counts for
Showing 2020 · cs.GTShow all
3 papers · 2 filters
cs.GT2020
Exponential Communication Separations between Notions of Selfishness
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas +2
We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type from each player and outputs an outcome $f(t_…
cs.GT2020★ 1 cited
Communication complexity of Nash equilibrium in potential games
Yakov Babichenko, Aviad Rubinstein
We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires c…
cs.GT2020
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…