Finding the optimal mixed strategy of a 3x3 matrix game.

Question

Consider a two player matrix game with payoff matrix :

$$\begin{pmatrix}0 & 2 & -1\\ -2 & 0 & 1\ \\ 1 & -1 & 0\end{pmatrix}$$

I need to show that the game has no saddle point solution and find an optimal mixed strategy.

If simultaneously have a row minimum and a column maximum this is an example of a saddle point solution. As max(col1) = 1 , max(col2) = 2 , max(col3) = 1, min(row1) = -1 , min(row2) = 0 , min(row3) = -1 there is not a simultaneous row min and row max a saddle point does not exist.

How to find an optimal mixed strategy ?

From http://www.iun.edu/~mathiho/mathpol/fall00/chapter15.htm

An optimal mixed strategy for the row player is a mixed strategy for which the lowest expected payoff (over all possible column player mixed strategies) is as large as possible. An optimal mixed strategy for the column player is a mixed strategy for which the highest expected payoff (over all possible row player mixed strategies) is as small as possible.

Do I just need to find the min of all rows and min of all cols ?

Answer 1

Add $3$ to the payoff matrix so that the value of the new game, $V$, is positive. Let $A$ be the player whose pure strategies are arranged row-wise, and $B$ be the one whose strategies are arranged column-wise.$$P=\begin{bmatrix}3 & 5 & 2\\1 & 3 & 4\ \\ 4 & 2 & 3\end{bmatrix}$$

Let the optimal mixed strategy of player $B$ be $[p_1~p_2~p_3]$ with $p_i\ge0,\sum p_i=1$. Since $B$ is the minimizing player, for each strategy of $A$, $B$'s expected payoff is $\le V$.

For $A$'s first strategy, $B$'s expected payoff is$$3p_1+5p_2+2p_3\le V\Leftrightarrow3x_1+5x_2+2x_3\le1$$ For $A$'s second strategy, $B$'s expected payoff is$$1p_1+3p_2+4p_3\le V\Leftrightarrow1x_1+3x_2+4x_3\le1$$ For $A$'s third strategy, $B$'s expected payoff is$$4p_1+2p_2+3p_3\le V\Leftrightarrow4x_1+2x_2+3x_3\le1$$where $x_i=p_i/V\ge0$. Since $\sum p_i=1,\sum x_i=1/V$. This gives the following linear program:$$\begin{align}\max&:&\frac1V=x_1+x_2+x_3\\\text{subject to}&:&\begin{bmatrix}3 & 5 & 2\\1 & 3 & 4\ \\ 4 & 2 & 3\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}\le\begin{bmatrix}1\\1\\1\end{bmatrix}\\&&x_i\ge0\end{align}$$The optimal solution is $1/V=1/3$ at $[x_1~x_2~x_3]=\frac1V[p_1~p_2~p_3]=\left[\frac1{12}~\frac1{12}~\frac16\right]$ giving $V=3$ and $[p_1~p_2~p_3]=\left[\frac14~\frac14~\frac12\right]$. $A$'s optimal strategy is given by the solution of the dual of this linear program, which turns out to be identical to that of $B$.

The value of the original game is $V-3=0$.

Answer 2

$A$ is antisymmetric so the game itself is symmetric. Thus if player 1 can guarantee at least $v$, then player 2 can guarantee at most $-v$. Therefore, $v=0$ so you just have to find strategies $x$ and $y$ such that $x^TA=(0,0,0)$ and $Ay=(0,0,0)^T$. You get $x=y=(1/4,1/4,1/2)^T$.