On the optimal strategy in a random game

Abstract

Consider a two-person zero-sum game played on a random $n$ by $n$ matrix where the entries are iid normal random variables. Let $Z$ be the number of rows in the support of the optimal strategy for player I given the realization of the matrix. (The optimal strategy is a.s. unique and $Z$ a.s. coincides with the number of columns of the support of the optimal strategy for player II.) Faris an Maier (see the references) make simulations that suggest that as $n$ gets large $Z$ has a distribution close to binomial with parameters $n$ and 1/2 and prove that $P(Z=n) < 2^{-(k-1)}$. In this paper a few more theoretically rigorous steps are taken towards the limiting distribution of $Z$: It is shown that there exists $a < 1/2$ (indeed $a< 0.4$) such that $P((1/2-a)n < Z < (1/2+a)n)$ tends to 1 as $n$ increases. It is also shown that the expectation of $Z$ is $(1/2+o(1))n$. We also prove that the value of the game with probability $1-o(1)$ is at most $Cn^{-1/2}$ for some finite $C$ independent of $n$. The proof suggests that an upper bound is in fact given by $f(n)/n$, where $f(n)$ is any sequence tending to infinity as $n$ increases, and it is pointed out that if this is true, then the variance of $Z$ is $o(n^2)$ so that any $a >0$ will do in the bound on $Z$ above.