Large Supports are required for Well-Supported Nash Equilibria

Yogesh Anbalagan, Hao Huang, Shachar Lovett +3

We prove that for any constant $k$ and any $\epsilon <1$, there exist bimatrix win-lose games for which every $\epsilon$-WSNE requires supports of cardinality greater than $k$. To do this, we pro…