Convexity Seminar

The value of random zero-sum games

Location: Warren Weaver Hall 1302

Date: Tuesday, February 24, 2026, 11 a.m.

Synopsis:

In this talk, I will present new results on the value of a two-player zero-sum game when the payoff matrix M is random. This work is motivated by algorithm analysis (my main area of study) and relies on techniques from convex geometry. The presentation will be based on this preprint, which is joint work with Laurent Massoulié.

Abstract: We study the value of a two-player zero-sum game on a random matrix $M \in R^{n \times m}$, defined by $v(M) = \min_{x \in \Delta_n}\ \max_{y \in \Delta_m}\ x^T M y$. In the setting where $n = m$ and $M$ has i.i.d. standard Gaussian entries, we show that the standard deviation of $v(M)$ is of order $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 + \lambda \sqrt{n}$, showing that the expected value of the game is of order $\lambda/n$, as well as the case where $M$ is a random orthogonal matrix. Our techniques are based on probabilistic arguments and convex geometry.