Skip to main content
1 of 2
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

Do random asymmetric games have more complicated strategies than random symmetric games?

Let $\Delta \subset \mathbb R^n$ be the locus of vectors whose entries are nonnegative and sum to $1$.

For $M$ an $n\times n$ matrix over $\mathbb R$, let $x_M \in \Delta$ be the vector $x$ that maximizes $\min_{ y \in \Delta} x^T M y$. (For generic $M$, this vector will be unique.)

Let $|\operatorname{supp}(x_M)|$ be the number of entries of $x_M$ are nonzero.

Is the expectation of $|\operatorname{supp}(x_M)|$ for $M$ a random matrix with all entries independent and identically distributed with the uniform distribution on $[-1,1]$, greater than the expectation of $|\operatorname{supp}(x_M)|$ for $M$ a random skew-symmetric matrix with all entries above the diagonal independent and identically distributed with the uniform distribution on $[-1,1]$?


I'm happy to consider variants of the problem, like using the entropy instead of the size of the support and using Gaussian instead of uniform distributions.


The only thing I know about this problem is that for $n=2$, the answer is yes, because for $M$ a skew-symmetric $2\times 2$ matrix, $x_M$ is always $(1,0)$ or $(0,1)$ depending on if the upper-right entry of $M$ is positive or negative, so $|\operatorname{supp}(x_M)|$ is always $1$, whereas if $M$ is not skew-symmetric, $|\operatorname{supp}(x_M)|=2$ with positive probability, for instance if $M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ with $a > b < d > c < a$.

Will Sawin
  • 148.7k
  • 9
  • 324
  • 563