Section 5.2 VonNeumann Minimax Theorem
In this section, show that the linear optimization scheme from
Section 5.1 gives us exactly what we want by proving VonNeuman’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'\)
(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 non-canonical 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)
Argue why, for an optimal solutions to the primal and dual problem, we have that \(\ec{u^*}, \ec{v^*} > 0\text{.}\)
(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 stretegy.
(f)
Why is the feasible region for Colleen’s new problem non-empty but bounded? What does the Extreme Value Theorem then say about this?
(g)
Repeat tasks (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.12 say about the optimal solutions to both problems? What in turn, does that say about
\(\ec{u^*}, \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 Collen’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. VonNeumann’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, 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*}
Activity 5.2.6.
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)
Activity 5.2.8.
In a simplified game of battleship played on a two \(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:
