Maximin-Minimax Principle
Consider a game with two players $A$ and $B$ in which player $A$ has $m$ strategies (moves) and player $B$ has $n$ strategies (moves). The game can be described in the form of a payoff matrix such that the cell entry $a_{ij}$ is the payment to $A$ in $A$’s payoff matrix when $A$ chooses the $i^{th}$ strategy and $B$ chooses the $j^{th}$ strategy.
The maximin-minimax principle is used for the selection of optimal strategies by two players. This method is also known as a calculus method.
The Minimax Theorem
For every finite two-person zero-sum game,
- there is a number $v$, called the value of the game
- there is a mixed strategy for Player $A$ such that $A$’s average gain is at least $v$ no matter what Player $B$ does, and
- there is a mixed strategy for Player $B$ such that $B$’s average loss is at most $v$ no matter what Player $A$ does.
Player $A$ wishes to maximize his gain while player $B$ wishes to minimize his loss. Since player $A$ would like to maximize his minimum gain, we obtain the maximin value for player $A$ and the corresponding strategy is called the maximin strategy. Player $A$’s corresponding gain is called the maximin value or lower value ($\underline{v}$) of the game.
At the same time, player $B$ wishes to minimize his maximum loss, we obtain the minimax value for player $B$ and the corresponding strategy is called the minimax strategy. Player $B$’s corresponding loss is called the minimax value or upper value ($\overline{v}$) of the game.
Usually the minimax value is greater than or equal to the maximin value. If the equality holds, i.e., $\max_{i}\min_{j} a_{ij}=\min_{j}\max_{i} a_{ij}=v$ then the corresponding pure strategies are called optimal strategies and the game is said to have a saddle point.
When these two values (miximin and minimax) are equal, the corresponding strategies are called optimal strategies.
The player $A$’s selection is called the maximin strategy. Player $B$’s selection is called the minimax value or upper value ($\overline{v}$) of the game.
Payoff Matrix for Player $A$ is as follows:
| Player A \ Player B | $1$ | $2$ | $\cdots$ | $j$ | $\cdots$ | $n$ |
|---|---|---|---|---|---|---|
| $1$ | $a_{11}$ | $a_{12}$ | $\dots$ | $a_{1j}$ | $\cdots$ | $a_{1n}$ |
| $2$ | $a_{21}$ | $a_{22}$ | $\cdots$ | $a_{2j}$ | $\cdots$ | $a_{2n}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $i$ | $a_{i1}$ | $a_{i2}$ | $\cdots$ | $a_{ij}$ | $\cdots$ | $a_{in}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $m$ | $a_{m1}$ | $a_{m2}$ | $\cdots$ | $a_{mj}$ | $\cdots$ | $a_{mn}$ |
Here the payoff matrix is given for player $A$. The player $A$ is called the maximizing player and $B$ is called the minimizing player.
Step by step procedure of Maximin-minimax principle
Step 1
Select the minimum element of each row of the payoff matrix,
$$ \begin{equation*} \text{i.e., } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{equation*} $$
Step 2
Select the maximum element of each column of the payoff matrix,
$$ \begin{equation*} \text{i.e., } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$
Step 3
Obtain the maximum value of each row minimum,
$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$
Step 4
Obtain the minimum value of each column maximum,
$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$
Step 5
If $\min_{j}\max_{i} a_{ij}=\max_{i}\min_{j} a_{ij}=v$, i.e., $\max (\min) = \min (\max)$ then the position of that element is a saddle point of the payoff matrix. And the corresponding strategy is called optimal strategy.
Some Important Terms in Game Theory
Saddle Point
A saddle point of a payoff matrix is that position where the maximum of row minima coincides with the minimum of column maxima. That is, if some entry $a_{ij}$ of the pay-off matrix has the property that
- $a_{ij}$ is the minimum of the $i^{th}$ row, and
- $a_{ij}$ is the maximum of the $j^{th}$ column,
then $a_{ij}$ is the saddle point of the game. In such a situation, player $A$ can win at least $a_{ij}$ by choosing $i^{th}$ strategy and Player $B$ can loss at most $a_{ij}$ by choosing $j^{th}$ strategy.
The pay-off at the saddle point $a_{ij}$ is called the value of the game and is equal to the maximin and minimax value of the game. Saddle point is also called an equilibrium point.
The saddle point provides the optimum strategies for both the players and value of the game (i.e. gain for player $A$ and loss for player $B$).
Value of Game
The payoff at the saddle point is called the value of the game and is equal to maximin and minimax value of the game.
Fair Game
A game is said to be fair game if $maximin = minimax = 0$.
Strictly Determinable
A game is said to be strictly determinable game if $maximin=minimax = v$.
Maximin-Minimax Principle Example 1
Solve the game with the following payoff for player $A$.
| Player $A$ / Player $B$ | $B_1$ | $B_2$ | $B_3$ | $B_4$ |
|---|---|---|---|---|
| $A_1$ | 8 | 10 | 9 | 14 |
| $A_2$ | 10 | 11 | 8 | 12 |
| $A_3$ | 13 | 12 | 14 | 13 |
Solution
We have two players $A$ and $B$. Player $A$ has three strategies namely $A_1$, $A_2$ and $A_3$ while player $B$ has four strategies namely $B_1$, $B_2$, $B_3$ and $B_4$.
| B1 | B2 | B3 | B4 | |
|---|---|---|---|---|
| A1 | 8 | 10 | 9 | 14 |
| A2 | 10 | 11 | 8 | 12 |
| A3 | 13 | 12 | 14 | 13 |
Step 1
For each row of the payoff matrix, select the minimum element and call it RowMin.
$$ \begin{equation*} \text{i.e., } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{equation*} $$
| B1 | B2 | B3 | B4 | RowMin | |
|---|---|---|---|---|---|
| A1 | 8 | 10 | 9 | 14 | 8 |
| A2 | 10 | 11 | 8 | 12 | 8 |
| A3 | 13 | 12 | 14 | 13 | 12 |
Step 2
For each column of the payoff matrix, select the maximum element and call it ColMax.
$$ \begin{equation*} \text{i.e., } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$
| B1 | B2 | B3 | B4 | RowMin | |
|---|---|---|---|---|---|
| A1 | 8 | 10 | 9 | 14 | 8 |
| A2 | 10 | 11 | 8 | 12 | 8 |
| A3 | 13 | 12 | 14 | 13 | 12 |
| ColMax | 13 | 12 | 14 | 14 |
Step 3
From each RowMin, obtain the maximum value, i.e., $Max(RowMin)$.
$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$
Thus $Max(min) = Max(8, 8, 12)=12$
Step 4
For each ColMax, obtain the minimum value, i.e. $Min(ColMax)$.
$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$
Thus $Min(max)=Min(13, 12, 14, 14)=12$.
Step 5
$Max(min) =12$ and $Min(max)=12$. Since the $Max(min)= Min(max)=12$ for the game, the game has a saddle point.
Thus optimal strategy for Player $A$ is $A_{3}$ and the optimal strategy for Player $B$ is $B_{2}$.
The value of the game for player $A$ is $12$ and for player $B$ is $-12$.
Maximin-Minimax Principle Example 2
Solve the game with the following payoff for player $A$.
| Player $A$ \ Player $B$ | $B_1$ | $B_2$ | $B_3$ |
|---|---|---|---|
| $A_1$ | 15 | 2 | 3 |
| $A_2$ | 6 | 5 | 7 |
| $A_3$ | -7 | 4 | 0 |
Solution
We have two players $A$ and $B$. Player $A$ has three strategies and player $B$ has four strategies.
| B1 | B2 | B3 | |
|---|---|---|---|
| A1 | 15 | 2 | 3 |
| A2 | 6 | 5 | 7 |
| A3 | -7 | 4 | 0 |
Step 1
Select the minimum element of each row of the payoff matrix,
$$ \begin{equation*} \text{i.e., } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{equation*} $$
| B1 | B2 | B3 | RowMin | |
|---|---|---|---|---|
| A1 | 15 | 2 | 3 | 2 |
| A2 | 6 | 5 | 7 | 5 |
| A3 | -7 | 4 | 0 | -7 |
Step 2
For each column of the payoff matrix, select the maximum element and call it ColMax.
$$ \begin{equation*} \text{i.e., } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$
| B1 | B2 | B3 | RowMin | |
|---|---|---|---|---|
| A1 | 15 | 2 | 3 | 2 |
| A2 | 6 | 5 | 7 | 5 |
| A3 | -7 | 4 | 0 | -7 |
| ColMax | 15 | 5 | 7 |
Step 3
From each RowMin, obtain the maximum value, i.e., $Max(RowMin)$.
$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$
Thus $Max(min) = Max(2, 5, -7)=5$
Step 4
For each ColMax, obtain the minimum value, i.e. $Min(ColMax)$.
$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$
Thus $Min(max)=Min(15, 5, 7)=5$.
Step 5
$Max(min) =5$ and $Min(max)=5$. Since the $Max(min)= Min(max)=5$ for the game, the game has a saddle point.
Thus optimal strategy for Player $A$ is $A_{2}$ and the optimal strategy for Player $B$ is $B_{2}$.
The value of the game for player $A$ is $5$ and for player $B$ is $-5$.
Endnote
In this tutorial, you learned about the Maximin-minimax Principle to solve a two-person zero-sum game.
To learn more about different methods to solve a game please refer to the following tutorials:
Let me know in the comments if you have any questions on Maximin-minimax principle to solve game and your thought on this article.
