@article{ECP1100,
author = {Johan Jonasson},
title = {On the optimal strategy in a random game},
journal = {Electron. Commun. Probab.},
fjournal = {Electronic Communications in Probability},
volume = {9},
year = {2004},
keywords = {two-person game, mixed strategy, equalizing strategy, saddle point},
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.},
pages = {no. 14, 132-139},
issn = {1083-589X},
doi = {10.1214/ECP.v9-1100},
url = {http://ecp.ejpecp.org/article/view/1100}}