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.
E. Balder, On the existence of maximum likelihood Nash equilibria.
Stochastic equilibrium problems in economics and game theory,
em Ann. Oper. Res.114 (2002), 57-70.
Math.Review 2004c:91021
J. E. Cohen, Cooperation and self-interest: Pareto-inefficiency
of Nash equilibria in finite random games, Proc. Natl. Acad. Sci. USA95 (1998), 9724-9731.
Math.Review 99k:90214
W. G. Faris and R. S. Maier, The value of a random game; the
advantage of rationality, Complex Systems1 (1987), 235-244.
Math.Review 88i:90176
G. Owen, ``Game Theory,'' 3rd edition, Academic Press,
San Diego, 2001.
Math.Review 96i:90003
Y. Rinott and M. Scarsini, On the number of pure strategy
Nash equilibria in random games, Games Econom. Behav.33
(2000), 274-293.
Math.Review 2001i:91041
W. Stanford, A note on the probability of k pure Nash
equilibria in matrix games, Games Econom. Behav.9 (1995),
238-246.
Math.Review 96a:90046