The value of random zero-sum games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914248688402432 |
|---|---|
| author | Cosson, Romain Massoulié, Laurent |
| author_facet | Cosson, Romain Massoulié, Laurent |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07759 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The value of random zero-sum games Cosson, Romain Massoulié, Laurent Probability Computer Science and Game Theory 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. |
| title | The value of random zero-sum games |
| topic | Probability Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.07759 |