Minimax theorems

The minimax inequality

The minimax inequality is

\[\textstyle \max_y\min_x\Phi(x,y) \le \min_x\max_y\Phi(x,y)\]

It holds for any $\Phi$, and its proof is elementary. Let $g(y)\triangleq\min_x\Phi(x,y)$. By $g$’s definition, we have

\[\textstyle g(y) \le\Phi(x,y)\text{ for any }(x,y).\]

Maximizing both side with respect to $y$, we obtain

\[\textstyle \max_y\Phi(x,y) \le \max_y g(y)\text{ for any }x.\]

This inequality holds for any $x$, so we can minimize with respect to $x$ to obtain the minimax inequality.

The minimax inequality has a game-theoretic interpretation. Consider the left side of the minimax inequality $\max_y\min_x\Phi(x,y)$ as the outcome of a two-player game in which one player chooses $x$ to minimize the outcome and the other player chooses $y$ to maximize the outcome. The $x$-player goes second because their minimization problem $\min_x\Phi(x,y)$ depends on $y$; ie the $y$-player’s choice. Similarly, the right side of the minimax inequality $\min_x\max_y\Phi(x,y)$ is the outcome when the $y$-player goes second. The minimax inequality states that going second is advantageous for both players:

When the $x$-player goes second, the outcome is at most as large as the outcome when $x$-player goes first. Since the $x$-player seeks to minimize the outcome, going second is advantageous for the $x$-player.
Similarly, when the $y$-player goes second, the outcome is at least as large as the outcome when the $y$-player goes first. Since the $y$-player seeks to maximize the outcome, going second is advantageous for the $y$-player.

Intuitively, going second is advantageous the player that goes second see’s the other player’s action and can adapt their action accordingly. The surprising thing is there are (many) problems in which going second has no advantage (at equilibrium).

Minimax equality and saddle points

When there is no advantage to going second, the minimax inequality holds with equality. Results that guarantee minimax equality are called minimax theorems, and there are many of them. Two prominent examples are Nash’s and von Neumann’s minimax theorem.

Nash’s minimax theorem: For any $A\in\reals^{m\times n}$, we have

\[\textstyle \max_{q\in\Delta^{n-1}}\min_{p\in\Delta^{m-1}}p^\top Aq = \min_{p\in\Delta^{m-1}}\max_{q\in\Delta^{n-1}}p^\top Aq,\]

where $\Delta^{m-1}$ (resp $\Delta^{n-1}$) is the probability simplex in $\reals^m$ (resp $\reals^n$).

von Neumann’s minimax theorem: Let $\cX\subset\reals^m,\cY\subset\reals^n$ be compact convex sets and $\Phi:\cX\times\cY\to\reals$ is convex is its first argument and concave in its second argument. We have

\[\textstyle \max_y\min_x\Phi(x,y) = \min_x\max_y\Phi(x,y).\]

Minimax theorems are often stated in terms of saddle points. Recall a point $(x_\star,y^\star)$ is a saddle point of $\Phi$ iff

\[\Phi(x_\star,y)\le\Phi(x_\star,y^\star)\le\Phi(x,y^\star)\text{ for all }x,y\in\cX\times\cY. \tag{SP}\]

The existence of a saddle point is (almost) equivalent to minimax equality. If $(x_\star,y^\star)$ is a saddle point, then

\[\begin{aligned}\textstyle \min_x\max_y\Phi(x,y) &\le\max\nolimits_y\Phi(x_\star,y),\\ &\le\Phi(x_\star,y^\star) &\text{(1st ineq in (SP))},\\ &\le \min\nolimits_x\Phi(x,y^\star) &\text{(2nd ineq in (SP))},\\ &\le\textstyle \max_y\min_x\Phi(x,y^\star).\\ \end{aligned}\]

This is exactly the reverse of the minimax inequality! We conclude that the minimax inequality holds with equality. On the other hand, if minimax equality holds and the min and max are attained, then $(x_\star,y^\star)$, where

\[\textstyle x_\star\triangleq\argmin_x\max_y\Phi(x,y)\text{ and }y^\star\triangleq\argmax_y\min_x\Phi(x,y),\]

is a saddle point. First, we check that the saddle point attains the minimax equality value:

\[\begin{aligned}\textstyle \max_y\min_x\Phi(x,y) &=\textstyle\min_x\Phi(x,y^\star) &\text{($y^\star$ def)},\\ &\le\Phi(x_\star,y^\star),\\ &\le\textstyle\max_y\Phi(x_\star,y),\\ &=\textstyle\min_x\max_y\Phi(x,y) &\text{($x^\star$ def)}. \end{aligned}\]

Since minimax equality holds, we deduce that the two inequalities in the proceeding display are actually equalities. After replacing them with equalities, we see that the first and fourth steps in the preceding display are equivalent to the first and second inequalities in (SP). We conclude that $(x_\star,y^\star)$ is a saddle point.

Bickel’s proof of Nash’s minimax theorem

For any $p\in\Delta^{m-1}$, let $\cF(p)\triangleq\{p^\top Aq:q\in\Delta^{n-1}\}$ be the set of achievable payoffs for the row player when they play the (mixed) strategy $p$. It is not hard to see that $\cF(p)$ is an interval whose endpoints depend on $p$. Similarly, let $\cG(q)\triangleq\{p^\top Aq:p\in\Delta^{m-1}\}$ be the set of achievable payoffs for the column player when they play the (mixed) strategy $q$. For any pair of strategies $p$ and $q$, we have $\cF(p)\cap\cG(q)\neq\emptyset$ because $p^\top Aq$ is in both sets.

Posted on February 10, 2025 from Ann Arbor, MI.