# Optimal Mixed Strategy for matrixes of size NxN

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?

-
This is a zero-sum game? – Kinnisal Mountain Chicken 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)$. – Kinnisal Mountain Chicken 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. – Kinnisal Mountain Chicken 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

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.