|
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? |
|||||||||||
|
|
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. |
||||
|
|
