The value of random zero-sum games

Romain Cosson, Laurent MassouliéarXiv 2026 · arXiv

TL;DR

This paper resolves a decades-old conjecture in game theory by proving that the value of a square random zero-sum game with Gaussian payoffs has a standard deviation of exactly $\Theta(1/n)$. Using modern tools from probability theory and convex geometry, the authors also map out the behavior of rectangular and orthogonal random games, offering a fresh mathematical lens on randomized algorithms and computational complexity.

What Problem Does This Paper Address?

John von Neumann’s famous minimax theorem (1928) established that every two-player zero-sum game has a well-defined "value" ($v(M)$), representing the expected outcome if both players play optimally. While this value is easy to calculate for a specific matrix, understanding its distribution when the payoff matrix $M$ is random has remained an open problem since the 1960s.

In the 1980s, numerical experiments led researchers to conjecture that for an $n \times n$ matrix with standard Gaussian entries, the game's value fluctuates tightly around zero with a standard deviation of $\Theta(1/n)$. However, proving this mathematically turned out to be incredibly difficult; the best proven upper bound prior to this work was a much looser $O(1/\sqrt{n})$. This paper closes that gap and extends the analysis to rectangular and orthogonal random matrices.

Methods

The authors bypass traditional, loose combinatorial approaches by leveraging two sophisticated mathematical frameworks:

  1. Gaussian Comparison Principles (Gordon's Inequality): For Gaussian matrices, the authors use Gordon's inequality to simplify the complex minimax optimization problem. This technique decouples the interaction between the two players, reducing the game's value to a simpler stochastic optimization problem that can be analyzed using standard concentration inequalities.
  2. Convex Geometry (Conic Kinematic Formulas): For random orthogonal matrices, the authors reframe the game geometrically. A positive game value corresponds to the non-trivial intersection of the positive orthant cone with a randomly rotated version of itself. They apply the conic kinematic formula to bound how "wide" this intersection typically is, which directly translates to bounds on the game's value.

Datasets

No real-world datasets are used in this paper. The research relies entirely on synthetic data generated by simulating random matrices. To validate their theoretical results, the authors ran numerical simulations on square matrices of sizes ranging from $n = 5$ to $200$ with independent and identically distributed (i.i.d.) entries drawn from Gaussian, Rademacher ($\pm 1$), and Laplace distributions.

Key Insights and Ideas

  • The Advantage of Rationality: If a player chooses a completely uniform random strategy, the game's value is of the order $\sqrt{\log n}/n$. By playing optimally, the player sharpens this to $1/n$. This quantifies the exact mathematical "advantage of rationality" over naive random guessing.
  • Geometric Equivalence: The paper highlights a beautiful connection between game theory and geometry: determining the probability that a random orthogonal game has a positive value is mathematically identical to calculating the probability that two randomly rotated orthants intersect in space.
  • Implications for Complexity Theory: Through Yao’s minimax principle, zero-sum games can model the complexity of algorithms against worst-case inputs. The authors note that because random games strongly favor mixed (randomized) strategies over pure (deterministic) ones, the widely believed computer science conjecture that $P = RP$ (that randomness doesn't fundamentally speed up polynomial-time algorithms) implies that real-world algorithmic cost matrices must be highly structured, rather than random.

Key Results

  • Square Gaussian Matrices: Successfully proved that the standard deviation of the game value is $\sigma(v(M)) = \Theta(1/n)$, confirming the 1987 experimental conjecture by Faris and Maier.
  • Rectangular Gaussian Matrices: For matrices of size $n \times m$ where $m = n + \lambda\sqrt{n}$, they showed that the expected value of the game scales as $\lambda/n$, demonstrating how the aspect ratio competes with random noise.
  • Orthogonal Matrices: For $n \times n$ random orthogonal matrices, they proved tail bounds showing the game value is at most $O(1/n^{3/2})$ with high probability.
  • Universality: Numerical experiments (shown in the paper's appendix) demonstrate that the $1/n$ scaling behavior holds true not just for Gaussian payoffs, but also for discrete Rademacher and Laplace distributions.

Limitations and Future Work

  • Non-Constructive Proofs: While the mathematical techniques successfully prove the bounds of the optimal strategies, they are non-constructive—meaning they do not provide a computationally efficient, closed-form algorithm to actually find or calculate these strategies.
  • Extension to Discrete Settings: The Gaussian comparison tools used in the paper are notoriously difficult to apply to discrete settings. Extending these tight bounds rigorously to Bernoulli or Rademacher matrices remains an open theoretical challenge.
  • Sparse Regimes: The authors suggest that future work should investigate sparse random games (where most matrix entries are zero, representing sparse bipartite graphs), potentially using local tree-like graph approximations.

Summary updated

Abstract

We study the value of a two-player zero-sum game on a random matrix $M\in \mathbb{R}^{n\times m}$, defined by $v(M) = \min_{x\inΔ_n}\max_{y\in Δ_m}x^T M y$. In the setting where $n=m$ and $M$ has i.i.d. standard Gaussian entries, we prove that the standard deviation of $v(M)$ is of order $\frac{1}{n}$. This confirms an experimental conjecture dating back to the 1980s. We also investigate the case where $M$ is a rectangular Gaussian matrix with $m = n+λ\sqrt{n}$, showing that the expected value of the game is of order $\fracλ{n}$, as well as the case where $M$ is a random orthogonal matrix. Our techniques are based on probabilistic arguments and convex geometry. We argue that the study of random games could shed new light on various problems in theoretical computer science.
BibTeX
@misc{cosson2026value,
  author = {Romain Cosson and Laurent Massoulié},
  title = {{The value of random zero-sum games}},
  year = {2026},
  eprint = {2601.07759},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.07759},
}
Figure