2
$\begingroup$

Please consider the following exercise:

Consider the following non-cooperative bimatrix game: $$ \begin{pmatrix}(3,4) & (2,3) & (3,2)\\ (6,2) & (0,2) & (3,3)\\ (4,6) & (3,4) & (4,5) \end{pmatrix} $$ Find the safety levels and the maxmin strategies for both players.

This matrix represents the payoffs to the players in a two player game. For example, if player I chooses row $2$ and player II chooses column $2$ then player I receives a payoff of $0$ and player II receives a payoff of $2$.

The apparent solution: We can split up the bimatrix game into two matrices, $A$ and $B$, representing the payoffs to player I and player II respectively. $$ A = \begin{pmatrix}3 & 2 & 3\\ 6 & 0 & 3\\4 & 3 & 4 \end{pmatrix}, \,B =\begin{pmatrix} 4 & 3 & 2\\ 1 & 2& 3 \\ 6 & 4 & 5\end{pmatrix} $$ In $A$, the element in the third row and second column is a saddle point. So the third row is a maxmin strategy for player I and the safety level for player I is $v_I = 3$. In $B$, the third row is dominated by the first row, and the second column is an equal probability mixture of column one and column three. We can therefore remove the third row and the second column. The resulting $2$ by $2$ matrix has a value of $2.5$. The maxmin strategy for player II is $(1/4,0,3/4)$.

My questions:

  • In matrix $B$, why would the last row be dominated by the first row? I know that in a zero-sum two player game you can delete rows from the game matrix that are dominated by another row. Consider for example the game matrix corresponding to a zero-sum two player game: $$ G = \begin{pmatrix} 3 & 4 & -3\\ 1 &8 &2\\ 2 & 1 & -4 \end{pmatrix} $$ In this game the third row is dominated by the first row, because no matter what strategy player II chooses, choosing the first row guarantees a higher payoff for player I. However, the game in the exercise is not a zero sum game, so the payoff in matrix $B$ should not affect the choices that player I makes, right? Also, row and column domination does not work as in the usual way. In this case it is dominated because it is bigger than the first row

  • Given that the way the rows are being deleted is legitimate, why is the value of the game $2.5$ and the maxmin strategy for player II $(1/4,0,3/4)$? The maxmin strategy for player II satisfies $$ v_{II} = \max_q\min_i \sum_{j=1}^m b_{ij} q_j = val(B^T) $$ After deleting the third row and the second column we are left with the matrix $$ \begin{pmatrix}4&3\\1&2\end{pmatrix} $$ This matrix has a value of $2.5$ and optimal strategy $(1/4,3/4)$, but shouldn't we be looking at the value of the inverse of this matrix, to find the safety level of player II?

$\endgroup$
1
$\begingroup$

To find the maxmin strategy for player $2$ you have to treat his payoff matrix as being effectively one for a zero-sum game in which he or she chooses the column of the payoff matrix and an imaginary opponent chooses the row. Since the role of the imaginary opponent is to minimise the payoff to player $2$, and all the entries of the first row of the payoff matrix are strictly less than the corresponding entries in the third, the former dominates the latter for the purposes of finding the maxmin value and strategy.

There is currently a discrepancy between the value of player $2$'s payoff in the second row and first column of the bimatrix, where it is $2$, and the corresponding row and column of $\ B\ $, where it is $1$. For the rest of the answer I'll assume the latter value is correct.

The matrix you get from $\ B\ $ by deleting the third row and second column is then $$ \pmatrix{4&2\\1&3}\ ,\text{ not }\ \pmatrix{4&3\\1&2}\ . $$ The second matrix is what you get by deleting the third row and third (not the second) column of $\ B\ $. It has a pure strategy saddle-point, with the optimal strategy for player $2$ being $\ \left(0, 1\right)\ $, not $\ \left(\frac{1}{4}, \frac{3}{4}\right)\ $, and its value is $2$, not $\ 2.5\ $. It's the first of these matrices whose saddle-point is $\ \left(\frac{1}{4}, \frac{3}{4}\right)\ $, and whose value is $\ 2.5\ $, since \begin{align} \pmatrix{4&2\\1&3}\pmatrix{\frac{1}{4}\\\frac{3}{4}}&=\pmatrix{\frac{5}{2}\\\frac{5}{2}}\ . \end{align}

$\endgroup$
  • $\begingroup$ Thank you for your elaborate answer! Could you explain why the role of the imaginary opponent is to minimise the payoff to player 2? There is an actual opponent, called player I and he doesn't care about player 2's payoff right? $\endgroup$ – titusAdam Oct 21 '19 at 5:42
  • $\begingroup$ The actual problem is to find $\ V=\max_\limits{\mu}\min_\limits{\nu} \nu^\top B\mu\ $ and the strategy $\ \mu^*\ $ for player $2$ such that $\ \min_\limits{\nu} \nu^\top B\mu^*=V\ $. This is just a mathematical problem which you can solve without bothering whether it has anything to do with this or any other game. $\endgroup$ – lonza leggiera Oct 21 '19 at 7:10
  • $\begingroup$ However, Von Neumann's minimax theorem tells us that the function $\ \nu^\top B\mu \ $ has a saddle-point, $\ (\nu^*,\mu^*)\ $, which is the solution to the zero-sum game with payoff matrix $\ B\ $ for the player who has to choose the column, and the second element of which is the solution to the maxmin problem we're trying to solve. Thus one way to solve the maxmin problem is to treat it as a two-player zero-sum game, and find the solution of that game. $\endgroup$ – lonza leggiera Oct 21 '19 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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