Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/3

In an

ε

-approximate Nash equilibrium, a player can gain at most

ε

in expectation

by unilateral deviation. An

ε

-

well-supported

approximate Nash equilibrium has the stronger requirement that every pure strategy used with positive probability must have payoff within

ε

of the best response payoff. Daskalakis, Mehta and Papadimitriou [8] conjectured that every win-lose bimatrix game has a

$\frac{2}{3}$

-well-supported Nash equilibrium that uses supports of cardinality at most three. Indeed, they showed that such an equilibrium will exist

subject to

the correctness of a graph-theoretic conjecture. Regardless of the correctness of this conjecture, we show that the barrier of a

$\frac23$

payoff guarantee cannot be broken with constant size supports; we construct win-lose games that require supports of cardinality at least

$\Omega(\sqrt[3]{\log n})$

in any

ε

-well supported equilibrium with

$\epsilon < \frac23$

. The key tool in showing the validity of the construction is a proof of a bipartite digraph variant of the well-known Caccetta-Häggkvist conjecture [4]. A probabilistic argument [13] shows that there exist

ε

-well-supported equilibria with supports of cardinality

$O(\frac{1}{\epsilon^2}\cdot \log n)$

, for any

ε

 > 0; thus, the polylogarithmic cardinality bound presented cannot be greatly improved. We also show that for any

δ

 > 0, there exist win-lose games for which no pair of strategies with support sizes at most two is a (1 − 

δ

)-well-supported Nash equilibrium. In contrast, every bimatrix game with payoffs in [0,1] has a

$\frac{1}{2}$

-approximate Nash equilibrium where the supports of the players have cardinality at most two [8].