| Título: | On the optimal strategy in a random game |
| Autores: | Jonasson, Johan; Chalmers University of Technology |
| Fecha: | 2004-01-01 |
| Publicador: | Electronic communications in probability |
| Fuente: |
 |
| Tipo: |
Peer-reviewed Article |
| Tema: | two-person game, mixed strategy, equalizing strategy, saddle point |
| Descripción: | 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. |
| Idioma: | No aplica |
1 On the Non-Convexity of the Time Constant in First-Passage Percolation por Kesten, Harry; Cornell University | 6 Simulations and Conjectures for Disconnection Exponents por Puckette, Emily E.; Occidental College,Werner, Wendelin; Université Paris-Sud and IUF |
2 A Proof of a Conjecture of Bobkov and Houdré por Kwapien, S.; Warsaw University,Pycia, M.; Warsaw University,Schachermayer, W.; University of Vienna | 7 Excursions Into a New Duality Relation for Diffusion Processes por Jansons, Kalvis M.; University College London |
3 Moderate Deviations for Martingales with Bounded Jumps por Dembo, Amir; Stanford University | 8 Percolation Beyond $Z^d$, Many Questions And a Few Answers por Benjamini, Itai; Weizmann Institute of Science,Schramm, Oded; Microsoft Research |
4 Bounds for Disconnection Exponents por Werner, Wendelin; Université Paris-Sud and IUF | 9 Transportation Approach to Some Concentration Inequalities in Product Spaces por Dembo, Amir; Stanford University,Zeitouni, Ofer; Technion - Israel Institute of Technology |
5 The Dimension of the Frontier of Planar Brownian Motion por Lawler, Gregory F.; Duke University | 10 Surface Stretching for Ornstein Uhlenbeck Velocity Fields por Carmona, Rene; Princeton University,Grishin, Stanislav; Princeton University,Xu, Lin; Princeton University,Molchanov, Stanislav; University of North Carolina at Charlotte |