Large Supports are required for Well-Supported Nash Equilibria

Abstract

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 provide a graph-theoretic characterization of win-lose games that possess $\epsilon$-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou, and Myers.

References in corpus (1)

• Polylogarithmic Supports are required for Approximate Well-Supported Nash Equilibria below 2/3

Cited by in corpus (1)

• Domination in 3-tournaments