Maximin ≤ Minimax: The Easy Direction

1. Building Intuition: An Analogy

Before diving into the formal proof, let's build an intuitive understanding of why maximin ≤ minimax must be true. The core idea is about the order of operations and the information it implies.

Imagine a grid of soldiers of varying heights arranged in ranks (rows) and files (columns). The height of each soldier is a function of their rank and file, height(rank, file).

Now, consider two different procedures:

1. Maximin Procedure: First, for each rank, we find the shortest soldier. Then, from this group of shortest soldiers, we pick the tallest one. This is the max of the mins.
2. Minimax Procedure: First, for each file, we find the tallest soldier. Then, from this group of tallest soldiers, we pick the shortest one. This is the min of the maxs.

Which of these two selected soldiers will be taller? The following video provides a clear and clever visual illustration.

As the video demonstrates, the soldier chosen via the maximin procedure can never be taller than the one chosen via the minimax procedure. The key is to consider any soldier at the intersection of the maximin soldier's rank and the minimax soldier's file. That soldier acts as a bridge, proving the inequality.

2. The Formal Proof

Now, let's translate this intuition into a rigorous mathematical proof. Your background in CS and mathematics means you'll appreciate the clean, step-by-step derivation that follows from first principles. The logic is surprisingly direct.

We want to prove:

Let's break down the argument.

• Step 1: The starting point.
  For any fixed strategy pair $({\sigma }_1,{\sigma }_2)$, the payoff $u({\sigma }_1,{\sigma }_2)$ is, by definition, less than or equal to the maximum possible payoff Player 1 could get against that specific strategy ${\sigma }_2$.

  $$u({\sigma }_1,{\sigma }_2)\le \underset{{\sigma }_1^{\prime }\in \Delta (S_1)}{\max }u({\sigma }_1^{\prime },{\sigma }_2)$$

  This is self-evident: a single value from a set cannot be greater than the maximum value in that set.

• Step 2: Accounting for the minimizer.
  The inequality above holds for any strategy ${\sigma }_2$ that Player 2 might choose. Therefore, it must also hold for the specific strategy ${\sigma }_2$ that minimizes the left-hand side. Since the inequality is universally true for all ${\sigma }_2$, we can take the minimum over all possible ${\sigma }_2$ on both sides without breaking the relation.

  $$\underset{{\sigma }_2\in \Delta (S_2)}{\min }u({\sigma }_1,{\sigma }_2)\le \underset{{\sigma }_2\in \Delta (S_2)}{\min }\left(\underset{{\sigma }_1^{\prime }\in \Delta (S_1)}{\max }u({\sigma }_1^{\prime },{\sigma }_2)\right)$$

• Step 3: Accounting for the maximizer.
  Look closely at the inequality from Step 2. The right-hand side is the definition of the minimax value. Critically, its value does not depend on ${\sigma }_1$. It is a single, fixed number. The inequality tells us that Player 1's guaranteed payoff for any given ${\sigma }_1$ (the left-hand side) is less than or equal to this fixed minimax value.
  Since this holds for any ${\sigma }_1$, it must also hold for the specific ${\sigma }_1$ that Player 1 chooses to maximize their guaranteed payoff. Thus, we can take the maximum over all ${\sigma }_1$ on the left-hand side.

  $$\underset{{\sigma }_1\in \Delta (S_1)}{\max }\left(\underset{{\sigma }_2\in \Delta (S_2)}{\min }u({\sigma }_1,{\sigma }_2)\right)\le \underset{{\sigma }_2\in \Delta (S_2)}{\min }\underset{{\sigma }_1^{\prime }\in \Delta (S_1)}{\max }u({\sigma }_1^{\prime },{\sigma }_2)$$

  This completes the proof.

To see this formal argument presented concisely, please review the following resource.

3. An Alternative Proof Structure

It's often useful in mathematics to see a concept from multiple angles. Another elegant way to prove the same result involves using the definitions of the optimal maximin and minimax strategies directly.

Let's use the notation from the previous lesson where $A$ is the payoff matrix, $x$ is Player 1's mixed strategy (a probability vector), and $y$ is Player 2's mixed strategy. The expected payoff is $x^{T}Ay$.

• Let $p$ be a maximin strategy for Player 1.
• Let $q$ be a minimax strategy for Player 2.

By their definitions:

• The maximin value is ${\nu }_r(A)={\min }_y{p}^{T}Ay$.
• The minimax value is ${\nu }_c(A)={\max }_x{x}^{T}Aq$.

We can construct a proof as a single chain of reasoning:

Let's analyze the two inequalities in this chain:

1. ${\min }_y{p}^{T}Ay\le p^{T}Aq$: The minimum payoff Player 1 can get with strategy $p$ (achieved by checking against all possible opponent strategies $y$) must be less than or equal to the payoff from that strategy $p$ against one specific opponent strategy, $q$.

2. $p^{T}Aq\le {\max }_x{x}^{T}Aq$: The payoff Player 1 gets with their specific strategy $p$ against $q$ must be less than or equal to the payoff they could get by choosing their absolute best response $x$ against that same strategy $q$.

Each step is straightforward, and chaining them together gives us ${\nu }_r(A)\le {\nu }_c(A)$, which is exactly what we wanted to prove.

This alternative proof is presented formally in the following resource.

Conclusion

Today we've rigorously established a key relationship between the maximin and minimax values of a game.

Key Takeaways:

• For any two-player game, the maximin value is always less than or equal to the minimax value: $\max \min u\le \min \max u$.
• This inequality formalizes the idea that having to commit to a strategy without knowing the opponent's move (maximin) cannot be better than being able to choose a best response to the opponent's committed strategy (minimax).
• We've seen two formal proofs of this result, both of which are direct consequences of the definitions of max and min.

Preview of the next lesson:
We've proven that maximin <= minimax. The truly profound result, established by John von Neumann, is that for any finite two-player zero-sum game, this inequality becomes an equality: maximin = minimax. This shared value is called the "value of the game." In our next lesson, we will state this famous Minimax Theorem and explore its deep connection to the concept of Nash Equilibrium.