Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 9 (2004) > Paper 14 open journal systems 


On the optimal strategy in a random game

Johan Jonasson, Chalmers University of Technology


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.


Full text: PDF

Pages: 132-139

Published on: October 13, 2004


Bibliography

    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. USA 95 (1998), 9724-9731. Math.Review 99k:90214

    T. Cover, The probability that a random game is unfair, Ann. Math. Statist. 37 (1966), 1796-1799. Math.Review 34#4011

    W. G. Faris and R. S. Maier, The value of a random game; the advantage of rationality, Complex Systems 1 (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















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X