Min-Max Games

Section 5.1 Min-Max Games

In this section, we introduce zero-sum games, some basic strategies for approaching them, and highlight a connection to linear optimization.

Exploration 5.1.1.

Suppose we have two players, then “Even” player and the “Odd” player. Each player picks an integer from 1-3.

If the sum is even:
- If the chosen numbers are distinct, then the Odd player pays the Even player the difference between the numbers.
- If the chosen numbers are the same, then the Odd player pays the Even player the sum of the numbers.
If the sum is odd: the Even player pays the Odd player $3.

(a)

Take turns playing this game, do you think either the even or odd player has any advantage in this game?

(b)

Record the net winnings to the Even player in the following table:

			Odd
		$1$	$2$	$3$
	$1$	$?$	$?$	$?$
Even	$2$	$?$	$?$	$?$
	$3$	$?$	$?$	$?$

(c)

Examinine this table, and comparing the rows, is there any advantage to the Even player in picking the first row over the third row?

(d)

Comparing the columns, is there any advantage to the Odd player in picking the third column over the first column?

(e)

Delete any row (column) corresponding to a choice that the Even (Odd) player would never make.

If the Even player always picks a 2, what is the optimal strategy for the Odd player? Similarly if the Odd player always picks a 1, what is the optimal strategy for the even player?

(f)

Do either player gain any advantage by picking a single choice and sticking to it?

(g)

Suppose the Even player flips a coin to make their choice, if the Odd player picks a 1, what is their average expected winnings? What if they choose a 2?

(h)

Suppose the Odd player flips a coin to make their choice, if the Even player picks a 2, what is their average expected winnings? What if they choose a 3?

(i)

Does this game favor either the Even or Odd player?

Definition 5.1.2.

In a two-player zero-sum game, where the row player has $n$ choices and the column player has $m$ choices, the payoff matrix is a matrix which records in each row and column the net payoff to the row player (this choice is purely by convention, but we will stick to it).

If a row $i$ has entries that are strictly greater than or equal to the entries of another row $j\text{,}$ then we say that row $i$ dominates row $j\text{.}$ We then may delete row $j$ since there is now reason the row player would choose $j\text{.}$ Similarly, if column $i$ is less than or equal to column $j\text{,}$ column $i$ dominates column $j$ and we may delete column $j\text{.}$

Activity 5.1.3.

Consider the payoff matrix for a game between Rowan and Colleen.

		Colleen
	$a_{11}$	$a_{12}$	$\cdots$	$\cdots$	$a_{1m}$
	$a_{21}$	$a_{22}$	$\cdots$	$\cdots$	$a_{2m}$
Rowan	$\vdots$	$\vdots$	$\ddots$	$\ddots$	$\vdots$
	$\vdots$	$\vdots$	$\ddots$	$\ddots$	$\vdots$
	$a_{n1}$	$a_{n2}$	$\cdots$	$\cdots$	$a_{nm}$

(a)

Suppose that Rowan pursues a mixed strategy a probability distribution of their choices $\p$ where

\begin{equation*} \p^\top = \begin{bmatrix} p_1 \\ p_2 \\ \vdots \\ p_n\end{bmatrix}, p_i\geq 0, \displaystyle \sum_{i=1}^n p_i=1. \end{equation*}

If Colleen chooses column $j$ as her strategy, what is $E_j(\p)$ the expected value of Rowan’s earnings?

$E_j(\p) = \displaystyle \sum_{i=1}^n a_{ij}\text{.}$
$E_j(\p) = \displaystyle \sum_{i=1}^n p_i\text{.}$
$E_j(\p) = \displaystyle \sum_{i=1}^n a_{ij}p_i\text{.}$
$E_j(\p) = \frac{1}{n}\displaystyle \sum_{i=1}^n a_{ij}\text{.}$
$E_j(\p) = \frac{1}{n}\displaystyle \sum_{i=1}^n p_i\text{.}$
$E_j(\p) = \frac{1}{n}\displaystyle \sum_{i=1}^n a_{ij}p_i\text{.}$

(b)

If Colleen somehow figures out Rowan’s strategy $\p\text{,}$ which column $j$ should she choose?

(c)

Rowan is aware that Colleen is a sharp player can likely figure out $\p\text{.}$ How then should he choose his strategy? $\p\text{?}$

Maximize $u=\displaystyle \max_{1\leq j\leq m}E_j(\p)\text{.}$
Maximize $u=\displaystyle \min_{1\leq j\leq m}E_j(\p)\text{.}$
Minimize $u=\displaystyle \max_{1\leq j\leq m}E_j(\p)\text{.}$
Minimize $u=\displaystyle \min_{1\leq j\leq m}E_j(\p)\text{.}$

(d)

At the exact same time, Colleen is pursuing her own mixed strategy $\q\text{:}$

\begin{equation*} \q = \begin{bmatrix} q_1 \amp q_2 \amp \cdots \amp q_m \end{bmatrix}, q_j\geq 0, \displaystyle \sum_{j=1}^m q_j=1. \end{equation*}

If Rowan chooses row $i$ as his strategy, what is $F_i(\q)$ the expected value of Colleen’s losses?

$F_i(\q) = \displaystyle \sum_{j=1}^m a_{ij}\text{.}$
$F_i(\q) = \displaystyle \sum_{j=1}^m q_j\text{.}$
$F_i(\q) = \displaystyle \sum_{j=1}^m a_{ij}q_j\text{.}$
$F_i(\q) = \frac{1}{n}\displaystyle \sum_{j=1}^m a_{ij}\text{.}$
$F_i(\q) = \frac{1}{n}\displaystyle \sum_{j=1}^m q_j\text{.}$
$F_i(\q) = \frac{1}{n}\displaystyle \sum_{j=1}^m a_{ij}q_j\text{.}$

(e)

If Rowan somehow figures out Colleen’s strategy $\q\text{,}$ which row $i$ should he choose?

(f)

Colleen is also aware that Rowan is a sharp player can likely figure out $\q\text{.}$ How then should she choose her strategy? $\q\text{?}$

Maximize $v=\displaystyle \max_{1\leq i\leq n}F_i(\q)\text{.}$
Maximize $v=\displaystyle \min_{1\leq i\leq n}F_i(\q)\text{.}$
Minimize $v=\displaystyle \max_{1\leq i\leq n}F_i(\q)\text{.}$
Minimize $v=\displaystyle \min_{1\leq i\leq n}F_i(\q)\text{.}$

(g)

Consider the primal-dual problems encoded by the tableau:

	$\ec{v}$	$q_1$	$q_2$	$\cdots$	$q_m$	$-1$
$\ec{u}$	$0$	$-1$	$-1$	$\cdots$	$-1$	$-1$	$=-0$
$p_1$	$-1$	$a_{11}$	$a_{12}$	$\cdots$	$a_{1m}$	$0$	$=-t_1$
$p_2$	$-1$	$a_{21}$	$a_{22}$	$\cdots$	$a_{2m}$	$0$	$=-t_2$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$p_n$	$-1$	$a_{n1}$	$a_{n2}$	$\cdots$	$a_{nm}$	$0$	$=-t_n$
$-1$	$-1$	$0$	$0$	$\cdots$	$0$	$0$	$=f$
	$=0$	$=s_1$	$=s_2$	$\cdots$	$=s_n$	$=g$

Write out both the primal and dual problems encoded by this tableau. (Including all equalities, inequalities, and the objective functions)

(h)

What primal constraint does the first row represent? How does it relate to Colleen’s strategy?

(i)

What primal constraint do the next $n$ rows represent? How does it relate to Colleen’s strategy?

(j)

What is the primal objective function? How does it relate to Colleen’s strategy?

(k)

Repeat (h)-(j) for the columns, and with regards to Rowan’s strategy.

(l)

Supposing that this system has an optimal primal and dual solution, what would those solutions represent?

Definition 5.1.4.

Suppose that the reduced payoff matrix had an entry $a_{ij}$ that is the largest value in it’s column and the smallest value in it’s row.

	$\ec{v}$	$q_k$	$\cdots$	$q_j$	$-1$
$\ec{u}$	$0$	$-1$	$\cdots$	$-1$	$-1$	$=-0$
$p_\ell$	$-1$	$a_{\ell k}$	$\cdots$	$a_{\ell j}$	$0$	$=-t_\ell$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$p_i$	$-1$	$a_{ik}$	$\cdots$	$a_{ij}$	$0$	$=-t_i$
$-1$	$-1$	$0$	$\cdots$	$0$	$0$	$=f$
	$=0$	$=s_k$	$\cdots$	$=s_j$	$=g$

Such an entry $a_{ij}$ is called a saddle point.

Activity 5.1.5.

Suppose a reduced payoff matrix had a saddle point $a_{ij}\text{.}$

	$\ec{v}$	$q_k$	$\cdots$	$q_j$	$-1$
$\ec{u}$	$0$	$-1$	$\cdots$	$-1$	$-1$	$=-0$
$p_\ell$	$-1$	$a_{\ell k}$	$\cdots$	$a_{\ell j}$	$0$	$=-t_\ell$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$p_i$	$-1$	$a_{ik}$	$\cdots$	$a_{ij}$	$0$	$=-t_i$
$-1$	$-1$	$0$	$\cdots$	$0$	$0$	$=f$
	$=0$	$=s_k$	$\cdots$	$=s_j$	$=g$

(a)

Pivot first on the entry with a $*$ then $**\text{.}$

	$\ec{v}$	$q_k$	$\cdots$	$q_j$	$-1$
$\ec{u}$	$0$	$-1$	$\cdots$	$-1^*$	$-1$	$=-0$
$p_\ell$	$-1$	$a_{\ell k}$	$\cdots$	$a_{\ell j}$	$0$	$=-t_\ell$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$p_i$	$-1^{**}$	$a_{ik}$	$\cdots$	$a_{ij}$	$0$	$=-t_i$
$-1$	$-1$	$0$	$\cdots$	$0$	$0$	$=f$
	$=0$	$=s_k$	$\cdots$	$=s_j$	$=g$

	$t_i$	$q_k$	$\cdots$	$0$	$-1$
$s_j$	$?$	$?$	$\cdots$	$?$	$C$	$=-q_j$
$p_\ell$	$?$	$?$	$\cdots$	$?$	$C'$	$=-t_\ell$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$0$	$?$	$?$	$\cdots$	$?$	$?$	$=-\ec{v}$
$-1$	$B$	$B'$	$\cdots$	$?$	$D$	$=f$
	$=p_i$	$=s_k$	$\cdots$	$=\ec{u} $	$=g$

(b)

For each entry $B, B', C, C'$ determine if:

The entry is zero.
The entry is positive.
The entry is negative.
The entries value cannot be determined.

(c)

What is $D\text{?}$ What are $\ec{u}, \ec{v}\text{?}$

(d)

After we delete the appropriate rows and columns, what could be said about the resulting primal-dual problems?

(e)

Would it make a difference if we pivoted by $**$ first then $*\text{?}$

Activity 5.1.6.

(a)

Follow the outline provided by Activity 5.1.3 to find the optimal strategies for the Even and Odd players in Exploration 5.1.1, and who if anyone the game favors.

(b)

To test out this solution edit this R code:

Where FIXMER1, FIXMER2, FIXMER3 represent the entries for the optimal mixed strategy for the row player Even, and FIXMEC1, FIXMEC2, FIXMEC3 are for the optimal mixed strategy for the column player Odd.

Then run the cell and see the distributions of winnings and the average winnings. How does this value compare to what you found.

(c)

Take turns, one student pick a new strategy for Even, and another student then modify the strategy for Odd in light of the new strategy. Can we do better than Odd’s current best strategy?

(d)

Conversely, take turns, one student pick a new strategy for Odd, and another student then modify the strategy for Even in light of the new strategy. Can we do better than Even’s current best strategy?

Activity 5.1.7.

Find the optimal strategies for two players Rowan and Colleen playing “Rock, Paper, Scissors”.

Prev Top Next

			Odd
		\(1\)	\(2\)	\(3\)
	\(1\)	\(?\)	\(?\)	\(?\)
Even	\(2\)	\(?\)	\(?\)	\(?\)
	\(3\)	\(?\)	\(?\)	\(?\)

		Colleen
	\(a_{11}\)	\(a_{12}\)	\(\cdots\)	\(\cdots\)	\(a_{1m}\)
	\(a_{21}\)	\(a_{22}\)	\(\cdots\)	\(\cdots\)	\(a_{2m}\)
Rowan	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\ddots\)	\(\vdots\)
	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\ddots\)	\(\vdots\)
	\(a_{n1}\)	\(a_{n2}\)	\(\cdots\)	\(\cdots\)	\(a_{nm}\)

	\(\ec{v}\)	\(q_1\)	\(q_2\)	\(\cdots\)	\(q_m\)	\(-1\)
\(\ec{u}\)	\(0\)	\(-1\)	\(-1\)	\(\cdots\)	\(-1\)	\(-1\)	\(=-0\)
\(p_1\)	\(-1\)	\(a_{11}\)	\(a_{12}\)	\(\cdots\)	\(a_{1m}\)	\(0\)	\(=-t_1\)
\(p_2\)	\(-1\)	\(a_{21}\)	\(a_{22}\)	\(\cdots\)	\(a_{2m}\)	\(0\)	\(=-t_2\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(p_n\)	\(-1\)	\(a_{n1}\)	\(a_{n2}\)	\(\cdots\)	\(a_{nm}\)	\(0\)	\(=-t_n\)
\(-1\)	\(-1\)	\(0\)	\(0\)	\(\cdots\)	\(0\)	\(0\)	\(=f\)
	\(=0\)	\(=s_1\)	\(=s_2\)	\(\cdots\)	\(=s_n\)	\(=g\)

	\(\ec{v}\)	\(q_k\)	\(\cdots\)	\(q_j\)	\(-1\)
\(\ec{u}\)	\(0\)	\(-1\)	\(\cdots\)	\(-1\)	\(-1\)	\(=-0\)
\(p_\ell\)	\(-1\)	\(a_{\ell k}\)	\(\cdots\)	\(a_{\ell j}\)	\(0\)	\(=-t_\ell\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(p_i\)	\(-1\)	\(a_{ik}\)	\(\cdots\)	\(a_{ij}\)	\(0\)	\(=-t_i\)
\(-1\)	\(-1\)	\(0\)	\(\cdots\)	\(0\)	\(0\)	\(=f\)
	\(=0\)	\(=s_k\)	\(\cdots\)	\(=s_j\)	\(=g\)

	\(\ec{v}\)	\(q_k\)	\(\cdots\)	\(q_j\)	\(-1\)
\(\ec{u}\)	\(0\)	\(-1\)	\(\cdots\)	\(-1\)	\(-1\)	\(=-0\)
\(p_\ell\)	\(-1\)	\(a_{\ell k}\)	\(\cdots\)	\(a_{\ell j}\)	\(0\)	\(=-t_\ell\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(p_i\)	\(-1\)	\(a_{ik}\)	\(\cdots\)	\(a_{ij}\)	\(0\)	\(=-t_i\)
\(-1\)	\(-1\)	\(0\)	\(\cdots\)	\(0\)	\(0\)	\(=f\)
	\(=0\)	\(=s_k\)	\(\cdots\)	\(=s_j\)	\(=g\)

	\(t_i\)	\(q_k\)	\(\cdots\)	\(0\)	\(-1\)
\(s_j\)	\(?\)	\(?\)	\(\cdots\)	\(?\)	\(C\)	\(=-q_j\)
\(p_\ell\)	\(?\)	\(?\)	\(\cdots\)	\(?\)	\(C'\)	\(=-t_\ell\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(0\)	\(?\)	\(?\)	\(\cdots\)	\(?\)	\(?\)	\(=-\ec{v}\)
\(-1\)	\(B\)	\(B'\)	\(\cdots\)	\(?\)	\(D\)	\(=f\)
	\(=p_i\)	\(=s_k\)	\(\cdots\)	\(=\ec{u} \)	\(=g\)