Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I have a Game Matrix of size $(N+1) \times (N+1)$, alike this one below \begin{array}{cccccc} 0 & 1 & 2 & \ldots & N-2 & N-1 & N \\ 1 & 0 & 1 & \ldots & N-3 & N-2 & N-1 \\ 2 & 1 & 0 & \ldots & N-4 & N-3 & N-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ N-2 & N-3 & N-4 & \ldots & 0 & 1 & 2 \\ N-1 & N-2 & N-3 & \ldots & 1 & 0 & 1 \\ N & N-1 & N-2 & \ldots & 2 & 1 & 0 \\ \end{array}

How would one go about finding the optimal mixed strategy for the row and for the column player?

share|cite|improve this question
This is a zero-sum game? – Keep these mind Feb 28 '13 at 16:09
Is it a game involving 2 players? Why not each entry of the payoff matrex is a 2-tuple? – Metta World Peace Feb 28 '13 at 16:11
Note that your matrix is $(N+1)\times(N+1)$. – Keep these mind Feb 28 '13 at 16:12
Well, whatever your question becomes, look at the NE for $N=2$, $N=3$, and $N=4$. A pattern might emerge. – Keep these mind Feb 28 '13 at 16:29
The game has value 1, and it's a two players game, also why would there be a two tuple in the payoff matrix, one players gain is the other ones loss, and I've tried to find a pattern without any luck. – Skeen Feb 28 '13 at 17:23
up vote 1 down vote accepted

It seems that the $(N+1) \times (N+1)$ game you have given is a two-player zero-sum game. From now on I assume it is so. As @Gugg suggests it is always useful to check what happens for small $N$'s. If you check it is easy to see that there is the following pattern.

We can claim that the $n+1$ tuple strategy $p=(\frac{1}{2},0,...,0,\frac{1}{2})$ is an optimal strategy. It is left to check whether this strategy guarantees the value of the game $\frac{1}{2}n$ (one can show this by showing that the upper value equals the lower value). That is for all strategies $q$, $pMq\geq \frac{1}{2}n$. Calculate $pM=\frac{1}{2}(1,...,1)$, now the matrix multiplication $\frac{1}{2}(1,...,1)q=\frac{1}{2}n\sum^{n}_{i=0}q_i=\frac{1}{2}n$. Hence whatever strategy player 2 plays player 1 guarantees the value $\frac{1}{2}n$ so $p=(\frac{1}{2},0,...,0,\frac{1}{2})$ is indeed an optimal mixed strategy. Similarly one can show that it is an optimal for player 2 as well. Therefore $(\frac{1}{2},0,...,0,\frac{1}{2}),(\frac{1}{2},0,...,0,\frac{1}{2})$ is a mixed equilibrium of the game, note that it does not mean it is unique.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.