25 citations · 246 across the 55 of their papers we have counts for
3 papers · 1 filter
Large Supports are required for Well-Supported Nash Equilibria
Yogesh Anbalagan, Hao Huang, Shachar Lovett +3
We prove that for any constant and any , there exist bimatrix win-lose games for which every -WSNE requires supports of cardinality greater than . To do this, we pro…
A Near-Optimal Mechanism for Impartial Selection
Nicolas Bousquet, Sergey Norin, Adrian Vetta
We examine strategy-proof elections to select a winner amongst a set of agents, each of whom cares only about winning. This impartial selection problem was introduced independently…
Polylogarithmic Supports are required for Approximate Well-Supported Nash Equilibria below 2/3
Yogesh Anbalagan, Sergey Norin, Rahul Savani +1
In an epsilon-approximate Nash equilibrium, a player can gain at most epsilon in expectation by unilateral deviation. An epsilon well-supported approximate Nash equilibrium has the…