×

On the optimal strategy in a random game. (English) Zbl 1080.91010

Summary: Consider a two-person zero-sum game played on a random \(n \times 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.) W. G. Faris and R. S. Maier [Complex Syst. 1, No. 2, 235–244 (1987; Zbl 0654.90100)] 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) \leq 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)\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^{-1}\), 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.

MSC:

91A15 Stochastic games, stochastic differential games
91A05 2-person games
60G10 Stationary stochastic processes

Citations:

Zbl 0654.90100