Maximin-Minimax Principle to solve game

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.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.

Leave a Comment