von Neumann Minimax Theorem

Section 5.2 von Neumann Minimax Theorem

In this section, show that the linear optimization scheme from Section 5.1 gives us exactly what we want by proving von Neumann’s Theorem.

🔗

Exploration 5.2.1.

Consider the tableau in Task 5.1.3.g and the associated primal-dual problems. Which of the following could possibly be true for these problems?

🔗

Both primal and dual problem achieve optimality.
🔗

🔗
The primal problem is unbounded and the dual problem is infeasible.
🔗

🔗
The primal problem is infeasible and the dual problem is unbounded.
🔗

🔗
Both problems are infeasible.
🔗

🔗

🔗

It would be very bad if either problem were infeasible or unbounded! It would be good to show that this is not the case.

🔗

Activity 5.2.2.

Let $A$ be a payoff matrix and $\p, \q$ represent the strategies of the row and column players respectively, with feasible regions $F_\p, F_\q\text{.}$

🔗

Let $A_{(i)}$ denote the $i$th row of a matrix $A$ and let $A^{(j)}$ denote the $j$th column of $A\text{.}$

🔗

(a)

Given a fixed column strategy $\q'$ which of these describes the role for the row player?

🔗

$\displaystyle \min_{\p \in F_{\p}} \p^\top A\q'\text{.}$
🔗

🔗
$\displaystyle \max_{\p \in F_{\p}} \p^\top A\q'\text{.}$
🔗

🔗
$\displaystyle \min_{\p \in F_{\p}} \sum_{i=1}^n \p_i A_{(i)}\q'\text{.}$
🔗

🔗
$\displaystyle \max_{\p \in F_{\p}} \sum_{i=1}^n \p_i A_{(i)}\q'\text{.}$
🔗

🔗

🔗

(b)

Given a fixed row strategy $\p'$ which of these describes the role for the column player?

🔗

$\displaystyle \min_{\q \in F_{\q}} \p'^\top A\q\text{.}$
🔗

🔗
$\displaystyle \max_{\q \in F_{\q}} \p'^\top A\q\text{.}$
🔗

🔗
$\displaystyle \min_{\p \in F_{\p}} \sum_{j=1}^m \p^\top A^{(j)}\q_j\text{.}$
🔗

🔗
$\displaystyle \max_{\p \in F_{\p}} \sum_{ij=1}^m \p^\top A^{(j)}\q_j\text{.}$
🔗

🔗

🔗

Activity 5.2.3.

We prove an interesting way to think of the optimal strategies.

🔗

Let $\q'$ denote a fixed column strategy, let $u_1=\displaystyle\max_{\p \in F_{\p} } \p^\top A\q'\text{,}$ and let $u_2=\displaystyle \max_{1\leq i\leq n}A_{(i)}\q'\text{.}$

🔗

(a)

Recall that $\p^\top A\q' = \displaystyle \sum_{i=1}^n \p_i A_{(i)}\q'\text{.}$ Prove that $\p^\top A\q' \leq u_2\text{.}$

🔗

(b)

Why must $u_1\leq u_2\text{?}$

🔗

(c)

Show that there is a (very simple) row strategy $\p''$ where $(\p'')^\top A \q'=u_2\text{.}$

🔗

(d)

Why must $u_2\leq u_1\text{?}$

🔗

(e)

What have we proven?

🔗

Activity 5.2.4.

We now prove a characterization theorem about the optimal solutions for both the row and column player.

🔗

Suppose we have a payoff matrix $A$ where every entry is positive. In other words, after each round Rowan is guaranteed to win money and Colleen is guaranteed to lose money. Rowan’s strategy here is to take Colleen for as much money as he can and Colleen’s strategy is to minimize her losses.

🔗

(We’ll ignore the obvious question of why Colleen would be willing to play this game.)

🔗

(a)

Write out the primal maximization problem for the Linear Optimization formulation of this game:

🔗

	$\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 the noncanonical primal problem including the objective function and constraint equalities and inequalities involving the $q_i$ and $\ec{v}$ where appropriate. (There should be no slack variables here.)

🔗

(b)

For each row and column strategy, we have expected row winnings $\ec{u}$ and $\ec{v}$ respectively. Why are these always positive?

🔗

(c)

Consider the inequality constraints in our formulation, divide each of these by $\ec{v}\text{.}$ Let $\tilde{q}_j:=\frac{q_j}{\ec{v}}\text{.}$ Can we rewrite our inequalities as linear combinations of $\tilde{q}_{j}$ is less than or equal to some constant?

🔗

(d)

Consider the equality constraint after dividing by $\ec{v}\text{,}$ rewrite this equality in terms of $\tilde{q}_j$ without negatives.

🔗

Remember, Colleen’s strategy is to minimize $\ec{v}$ which must be positive. Can we rephrase this as maximizing or minimizing a linear function involving then $\tilde{q}_j\text{?}$ What is this linear function and is it a maximization or minimization problem? (Note that the solution to this problem likely isn’t the solution to the original problem, but both are optimized under the same conditions.)

🔗

(e)

Rewrite the new canonical linear programming problem with variables $\tilde{q}_j$ that optimizes Colleen’s strategy.

🔗

(f)

Why is the feasible region for Colleen’s new problem nonempty but bounded? What does the Extreme Value Theorem then say about this?

🔗

(g)

Repeat tasks $\textbf{(b)-(c)}$ for Rowan’s strategy, where $\tilde{p}_i = \frac{p_i}{\ec{u}}\text{.}$

🔗

(h)

Compare Rowan and Colleen’s problems with the $\tilde{p}_i, \tilde{q}_j\text{.}$ Show that these problems are dual problems to each other. Which is the primal max and which is the dual min?

🔗

(i)

What does the Strong Duality Theorem Theorem 4.2.4 say about the optimal solutions to both problems? What, in turn, does that say about $\ec{u}$ and $\ec{v}\text{?}$

🔗

(j)

We’re still in this pretty ridiculous situation where Colleen is for some reason willing to throw money away at Rowan. To balance things out, Rowan has to pay Colleen $5 after each round. Would this fact change anything about Rowan and Colleen’s strategies?

🔗

Say it was $$r\text{,}$ would that make any difference?

🔗

(k)

Let $\p, \q$ denote any strategy for Rowan and Colleen. Let $E$ denote a $n\times m$ matrix with all 1’s. Show that $\p^\top(rE)\q=r\text{.}$

🔗

(l)

Show that for fixed strategies $\p', \q'$ and not fixed strategies $\p, \q$ that $\p^\top (A+rE)\q'$ is maximized when $\p^\top A \q'$ is maximized and $\p'^\top (A+rE)\q$ is minimized when $\p'^\top A \q$ is minimized.

🔗

Theorem 5.2.5. von Neumann’s Minimax Theorem.

Let $A$ be a payoff matrix and $\p, \q$ represent the strategies of the row and column players respectively, with feasible regions $F_\p$ and $F_\q\text{.}$ Also let $A_{(i)}$ denote the $i$th row of a matrix $A$ and let $A^{(j)}$ denote the $j$th column of $A\text{.}$

🔗

Then, there are optimal strategies $\p', \q'$ such that:

\begin{equation*} \displaystyle \min_{\q \in F_{\q}} \p'^\top A\q = \displaystyle \min_{1\leq i\leq n}A_{(i)}\q = \p'^\top A\q' = \max_{1\leq j\leq m}\p^\top A^{(j)} = \max_{\p \in F_{\p}} \p^\top A\q'. \end{equation*}

🔗

We call the described value the von Neumann Value of the game.

🔗

Activity 5.2.6.

Revisit Exploration 5.2.1. Has your answer adjusted at all?

🔗

Activity 5.2.7.

Consider the payoff matrix $A=\begin{bmatrix} 1 \amp 0 \\ 1\amp 2 \end{bmatrix}\text{.}$

🔗

(a)

Find the optimal strategy $\q'$ for Colleen in this game, and the game value $v\text{.}$

🔗

(b)

Find a strategy $\p$ for Rowan so that $\p^TA\q'=v\text{,}$ but $\p$ is not the optimal strategy.

🔗

(c)

What does this say about Theorem 5.2.5?

🔗

Activity 5.2.8.

In a simplified game of battleship played on a $2\times 3$ board, Colleen selects two consecutive squares on the board to place her ship. Rowan then picks one of six squares to fire at. If he hits, he gets a point, otherwise Colleen gets a point.

🔗

(a)

Write out a payoff matrix for this game. (Why is it $6\times 7\text{?}$)

🔗

(b)

Find the optimal solution for Colleen using Sage:

🔗

Does the game favor Rowan or Colleen?

🔗

(c)

Use Sage to find the optimal solution for Rowan:

🔗

Prev Top Next

	\(\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\)