Introduction
In the field of algorithmic game theory, the search for Nash Equilibria (NE) in two-player bimatrix games is a foundational challenge. While John Nash proved that every finite game has at least one equilibrium, finding it computationally is a different matter. The problem is known to be PPAD-complete, suggesting that a polynomial-time algorithm for exact equilibria is unlikely to exist. This has led researchers to focus on approximation schemes.
Approximate Equilibria: $\epsilon$-Nash vs. $\epsilon$-WSNE
There are two primary ways to define an approximate equilibrium:
- $\epsilon$-Nash Equilibrium: A strategy profile where no player can improve their payoff by more than $\epsilon$ by unilaterally changing their strategy.
- $\epsilon$-Well-Supported Nash Equilibrium ($\epsilon$-WSNE): A more stringent condition where every pure strategy played with positive probability must be an $\epsilon$-best response. That is, no player puts any weight on a strategy that is more than $\epsilon$ worse than their best possible response.
While polynomial-time algorithms exist for $\epsilon$-Nash equilibria for $\epsilon \approx 0.3393$, $\epsilon$-WSNE is significantly harder to compute. The best known polynomial-time algorithm for WSNE only achieves $\epsilon \approx 0.6528$. For smaller values of $\epsilon$, the community has relied on quasi-polynomial time algorithms, typically with a complexity of $n^{O(\log n)}$.
The $1/2$ Threshold and Support Size
The work by Michail Fasoulakis and Evangelos Markakis, presented at AAAI-19, addresses the gap between these two complexity classes. They focus on the $(1/2 + \epsilon)$-WSNE and provide a new algorithm that operates in $n^{O(\log \log n)}$ time.
The core of their contribution lies in a sophisticated case analysis of player payoffs. They categorize games based on whether players receive payoffs above or below $1/2$ in an exact Nash equilibrium:
- Symmetric Payoffs: If both players receive payoffs either $> 1/2$ or $\le 1/2$, the problem can be solved using existing polynomial-time techniques.
- Asymmetric Payoffs: The "hard" case occurs when one player receives a payoff $> 1/2$ and the other receives $\le 1/2$.
Technical Innovation: Reducing the Support
The authors' key technical breakthrough is proving that in these asymmetric cases, there exists an approximate equilibrium where one player utilizes a strategy with a very small support size—specifically $O(\log \log n)$.
Previously, the standard approach for quasi-polynomial approximation (the Lipton-Markakis-Mehta framework) relied on the fact that there exist $\epsilon$-equilibria with support size $O(\log n / \epsilon^2)$. By proving that one player's support can be reduced to $O(\log \log n)$ for the $(1/2 + \epsilon)$ threshold, Fasoulakis and Markakis effectively reduce the exponent of the search space.
The algorithm proceeds as follows:
- It first attempts to find an equilibrium using the polynomial-time algorithm for symmetric payoff cases.
- If unsuccessful, it assumes the game falls into the asymmetric payoff category.
- It then exhaustively searches (brute-forces) all possible strategies for one player that have a support size of $O(\log \log n)$.
- For each candidate strategy, it uses a system of linear inequalities to determine if there is a corresponding strategy for the second player that satisfies the $(1/2 + \epsilon)$-WSNE conditions.
Theoretical Foundations
The proof of existence for this small-support strategy relies on the probabilistic method. By applying Hoeffding’s inequality, the authors demonstrate that a random sampling of strategies from an exact equilibrium will, with high probability, yield a strategy that satisfies the required approximation properties while maintaining a very small support. This allows the deterministic algorithm to succeed by searching the reduced space.
Significance and Limitations
The transition from $O(\log n)$ to $O(\log \log n)$ is a major theoretical milestone. While $n^{O(\log \log n)}$ is still technically quasi-polynomial, the function $\log \log n$ grows so slowly that the algorithm is asymptotically much closer to polynomial time than its predecessors. This represents the first time a quasi-polynomial algorithm has broken the standard $O(\log n)$ barrier for approximation values below the $0.6528$ threshold.
However, the "1/2 barrier" remains. The current techniques are specifically calibrated for the $1/2$ payoff threshold. It remains an open question whether similar $O(\log \log n)$ support arguments can be applied to achieve tighter approximations, such as $1/3$ or $1/4$-WSNE. Furthermore, while the theoretical complexity is improved, the constant factors involved in the exponent may still pose challenges for practical implementation in large-scale games.
Conclusion
Fasoulakis and Markakis have narrowed the gap between polynomial and quasi-polynomial solvability for well-supported Nash equilibria. By identifying the specific conditions under which support sizes can be drastically reduced, they provide a faster path toward approximating equilibria in complex two-player games, setting a new benchmark for future research in algorithmic game theory.
Summary updated