Minimax Theorem and Strong Duality

Introduction

In our previous lessons, we successfully translated the strategic problems of two players in a zero-sum game into the language of linear programming. Specifically:

• We formulated the row player's maximin problem as a primal linear program (LP).
• We then derived its dual and discovered that it is precisely the column player's minimax problem.

Today, we will complete this intellectual journey. The learning outcome for this lesson is to derive the minimax theorem as a direct consequence of the strong duality theorem of linear programming. We will formally connect the dots between these concepts to construct a complete and elegant proof of von Neumann's famous theorem. This is the central proof you need for your assignment.

1. From Game Theory to Linear Programming, Formally

Let's begin by formalizing the argument. The heart of the proof lies in showing that the players' problems can be expressed as LPs. We'll focus on the row player first.

The row player wants to choose a mixed strategy $\mathbf{x}$ that maximizes their guaranteed payoff. This guaranteed payoff is the minimum payoff they can get, considering all of the column player's possible responses. The row player's objective is therefore:

where $\mathbf{x}$ and $\mathbf{y}$ are probability vectors representing the players' mixed strategies.

A crucial insight is that for a fixed mixed strategy $\mathbf{x}$ from the row player, the column player's best response (i.e., the one that minimizes ${\mathbf{x}}^{T}A\mathbf{y}$) will always be a pure strategy. Why? Because ${\mathbf{x}}^{T}A\mathbf{y}$ is a weighted average of the values ${\mathbf{x}}^T{A}_j$ (where $A_j$ is the $j$-th column of $A$), and the minimum of any weighted average is achieved by putting all the weight on the smallest component.

Therefore, the row player's problem simplifies to:

where ${\mathbf{x}}^T{A}_j={\sum }_{i=1}^m{x}_i{A}_{ij}$ is the expected payoff for the row player if they play $\mathbf{x}$ and the column player plays the pure strategy $j$.

This is now a maximization problem that we can convert into a linear program. We use a standard technique: introduce a new variable, $u$, to represent the value of the inner minimization, ${\min }_j({\mathbf{x}}^T{A}_j)$.

The problem becomes:

This is exactly the primal LP for the row player's maximin problem that we formulated two lessons ago. Let's call its optimal value $u^{\ast }$. We have thus formally shown:

The following resource provides a concise walkthrough of this formulation and the rest of the proof.

2. The Power of Strong Duality

In the previous lesson, we did the hard work of showing that the dual of the row player's LP is the column player's minimax LP. Let's restate the two problems side-by-side.

Primal LP (Row Player)

Optimal Value: $u^{\ast }={\max }_{\mathbf{x}}{\min }_{\mathbf{y}}{\mathbf{x}}^{T}A\mathbf{y}$

Dual LP (Column Player)

Optimal Value: $w^{\ast }={\min }_{\mathbf{y}}{\max }_{\mathbf{x}}{\mathbf{x}}^{T}A\mathbf{y}$
(You can verify the equivalence between this LP and the minimax value using the same logic as we did for the row player).

Now, we bring in the main tool: the Strong Duality Theorem of Linear Programming.

Theorem (Strong Duality): If a primal linear program has a finite optimal solution, then so does its dual, and their optimal objective values are equal.

Does this theorem apply to our game?

1. Is the primal LP feasible? Yes. Any mixed strategy $\mathbf{x}$ provides a feasible solution.
2. Is the primal LP bounded? Yes. The payoff matrix $A$ contains finite numbers, so the expected payoff $u$ cannot be infinite.

Since the primal problem is both feasible and bounded, it must have a finite optimal solution $u^{\ast }$. Therefore, the Strong Duality Theorem applies directly, and we can conclude that the dual problem also has a finite optimal solution $w^{\ast }$, such that:

3. The Proof of the Minimax Theorem

We now have all the pieces for the final proof. It is a simple, beautiful chain of equalities.

1. The value of the row player's maximin problem is equal to the optimal value of the primal LP.

   $$\underset{\mathbf{x}}{\max }\underset{\mathbf{y}}{\min }{\mathbf{x}}^{T}A\mathbf{y}=u^{\ast }$$

2. By the Strong Duality Theorem, the optimal value of the primal LP is equal to the optimal value of the dual LP.

   $$u^{\ast }=w^{\ast }$$

3. The optimal value of the dual LP is equal to the value of the column player's minimax problem.

   $$w^{\ast }=\underset{\mathbf{y}}{\min }\underset{\mathbf{x}}{\max }{\mathbf{x}}^{T}A\mathbf{y}$$

Combining these three steps, we get:

This is the statement of the Minimax Theorem. The proof is complete.

The section of the document you read before also concludes the proof by invoking strong duality. It's a testament to the power of abstraction in mathematics: a deep theorem about games (Minimax) becomes an almost immediate consequence of a fundamental theorem about optimization (Strong Duality).

Conclusion

In this lesson, you have constructed the formal proof of the Minimax Theorem using the tools of linear programming. This is the central theoretical result of this course and a cornerstone of game theory.

Key Takeaways:

• The players' maximin and minimax problems in a zero-sum game can be exactly formulated as a primal-dual pair of linear programs.
• The argument relies on the insight that a player's best response to a fixed mixed strategy is always a pure strategy, which linearizes the inner part of the max-min or min-max expression.
• The Strong Duality Theorem provides the bridge, guaranteeing that the optimal values of these two LPs—and therefore the maximin and minimax values of the game—are equal.

Preview of the next lesson:

We have proved that the values are equal. But what about the strategies themselves? In our final lesson, we will interpret the optimal solutions to the primal and dual LPs, ${\mathbf{x}}^{\ast }$ and ${\mathbf{y}}^{\ast }$, and show how they form a Nash Equilibrium for the game.