Introduction
In the study of zero-sum games, "patience" serves as a critical metric for the complexity of a strategy. Formally defined as the reciprocal of the smallest nonzero probability used in an optimal strategy, patience represents the expected number of trials required to observe the rarest move or, equivalently, the number of random bits needed to simulate the strategy. While it is well-established that $\epsilon$-optimal strategies—those that are "close enough" to perfect—require only low patience ($O(\ln n / \epsilon^2)$), the requirements for truly optimal play are far more demanding.
This paper investigates the patience of $n \times n$ "win-lose-draw" games, where payoffs are restricted to $\{-1, 0, 1\}$. The authors demonstrate that perfect play can necessitate exponentially small probabilities, specifically $n^{-\Omega(n)}$, and provide a fully-explicit matrix construction that forces this extreme level of precision.
Theoretical Foundations and Methodology
The research bridges game theory and linear algebra by relating optimal strategies to the properties of ill-conditioned matrices. An ill-conditioned matrix is one that is nearly singular, where the inverse contains very large entries relative to the original matrix.
The Shapley-Snow Theorem
The authors utilize the Shapley-Snow Theorem, a classical result that connects the optimal strategies of a matrix game to the inverse and adjugate of its square submatrices. This theorem allows the problem of finding high-patience games to be reframed as a search for matrices whose inverses exhibit a large ratio between their largest and smallest entries, provided the inverse remains non-negative to represent a valid probability distribution.
Explicit Constructions
To achieve high patience, the authors build upon Alon-Vu constructions—(0,1)-matrices known for having large determinants. They extend this work by making the construction "fully-explicit," meaning any entry $(i, j)$ of the $n \times n$ game matrix can be computed in polynomial time relative to $\log n$.
The methodology incorporates several key techniques:
- Matrix Switching Games: Using the Gale-Berlekamp switching game to transform ill-conditioned matrices into game matrices while preserving high patience.
- Combinatorial Ordering: A specific ordering of subsets based on symmetric differences is developed to ensure the matrix inverse has non-negative entries, a necessary condition for the resulting vector to constitute a valid strategy.
Key Results and Bounds
The paper establishes tight bounds on the patience required for win-lose-draw games, effectively settling the order of magnitude for the worst-case scenario.
Upper and Lower Bounds
The authors prove that for any $n \times n$ win-lose-draw game, the maximum patience required is bounded by: $$P \leq (n+1)^{(n+1)/2}$$ This implies that players never need probabilities smaller than approximately $n^{-n/2}$.
Conversely, the authors provide a lower bound through an explicit construction of a win-lose game where the unique optimal strategy requires a probability as small as: $$p_{min} \approx n^{-n/2} \cdot 2^{n(1+o(1))}$$ Because the upper and lower bounds match in the exponent, the research provides a definitive characterization of the "precision gap" in matrix games.
Discussion: The Precision Gap and Complexity
A central insight of this work is the massive disparity between playing "nearly perfectly" and "perfectly." The transition from an $\epsilon$-optimal strategy to a truly optimal one triggers a jump from logarithmic precision to exponential precision.
Furthermore, the paper links the existence of high-patience games to computational hardness. The authors suggest that finding these optimal strategies is related to PLS-complete (Polynomial Local Search) problems, such as Bipartite MaxCut. This implies that while these strategies exist and can be explicitly constructed, identifying them through standard search mechanisms may be computationally intensive.
Conclusion and Future Work
The findings of this paper provide a rigorous bound on the complexity of optimal strategies in discrete zero-sum games. By providing a fully-explicit construction, the authors move beyond existential proofs to provide concrete examples of games requiring extreme precision.
Future research may address the limitations of the current construction, such as its reliance on dimensions that are powers of two ($n = 2^m$). Additionally, exploring how patience scales with arbitrary real-valued payoffs or different restricted sets of payoffs remains an open and promising area of inquiry.
Summary updated