Saddle Point Conditions for Minimax Equality

Why a Saddle Point Is a Certificate

In a two-player zero-sum game, the row player tries to make the payoff large and the column player tries to make it small. The minimax theorem for finite matrix games guarantees equality of the maximin and minimax values when players may use mixed strategies. A saddle point gives more than that equality: it identifies a pair of strategies that are optimal against one another and verifies this directly by checking deviations.

The direction of the inequalities depends on which player maximizes. Here the row player maximizes the payoff and the column player minimizes it. Thus, at a saddle point, changing the row strategy while holding the column strategy fixed cannot increase the payoff, and changing the column strategy while holding the row strategy fixed cannot decrease it. The common payoff is the game value.

Payoffs and the Saddle-Point Conditions

Let $A$ be an $m$-by-$n$ payoff matrix. Its entry $a_{ij}$ is the payoff to the row player when the row player chooses row $i$ and the column player chooses column $j$; the column player receives the negative of this payoff. A mixed strategy is a probability vector over the relevant pure strategies. Write $p$ for the row player’s mixed strategy and $q$ for the column player’s mixed strategy. The expected payoff to the row player is

L(p,q)=p^{\mathsf T}Aq.

A row player wants to choose $p$ to maximize this payoff, while a column player wants to choose $q$ to minimize it. A row strategy is a best response to $q$ if it maximizes $L(p,q)$ over row strategies $p$. A column strategy is a best response to $p$ if it minimizes $L(p,q)$ over column strategies $q$.

Definition: A pair $(p^*,q^*)$ is a saddle-point pair if, for every row strategy $p$ and every column strategy $q$, $$ L(p,q^*)\leq L(p^*,q^*)\leq L(p^*,q). $$ The number $v=L(p^*,q^*)$ is the payoff at the saddle point. The left inequality says $p^*$ is a best response to $q^*$; the right says $q^*$ is a best response to $p^*$.

The comparisons keep one player’s strategy fixed at the proposed pair. In the left comparison, the column player holds $q^*$ fixed while the row player considers alternatives. In the right comparison, the row player holds $p^*$ fixed while the column player considers alternatives. A pair is not certified merely because its payoff looks plausible or because each strategy is optimal against some other strategy.

Worked Example: A Pure-Strategy Saddle Point

Consider the payoff matrix

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}.

Take $p^*$ to be pure row 2 and $q^*$ to be pure column 2. The payoff at the proposed pair is $a_{22}=2$. Against column 2, the payoffs from rows 1 and 2 are 1 and 2, respectively. Thus, for every row mixture $p=(p_1,p_2)$,

L(p,q^*)=p_1(1)+p_2(2)\leq 2=L(p^*,q^*),

because $p_1+p_2=1$ and $p_1,p_2\geq0$. Against row 2, the payoffs in columns 1 and 2 are 4 and 2. Every column mixture $q=(q_1,q_2)$ therefore gives

L(p^*,q)=q_1(4)+q_2(2)\geq 2=L(p^*,q^*).

Both saddle inequalities hold. The row player cannot raise the payoff above 2 against column 2, and the column player cannot lower it below 2 against row 2. The pair certifies a game value of 2.

How the Pair Certifies Both Values

For mixed strategies in a finite matrix game, define the maximin value $\alpha$ and the minimax value $\beta$ by

\alpha=\max_p\min_q L(p,q), \qquad \beta=\min_q\max_p L(p,q).

The maximin asks how large a payoff the row player can guarantee, even if the column player responds to minimize it. The minimax asks how small a payoff the column player can guarantee, even if the row player responds to maximize it. The strategy spaces are finite-dimensional probability simplexes, and $L$ is continuous, so the extrema in these definitions are attained. The weak minimax inequality $\alpha\leq\beta$ follows because, for every fixed $q$, $\min_{q'}L(p,q')\leq L(p,q)$ for every $p$, and hence $\alpha\leq\max_p L(p,q)$; minimizing the right-hand side over $q$ gives $\alpha\leq\beta$.

Theorem: If $(p^*,q^*)$ is a saddle-point pair and $v=L(p^*,q^*)$, then $p^*$ attains the maximin value, $q^*$ attains the minimax value, and $\alpha=\beta=v$.

Proof. By the right saddle inequality, $L(p^*,q)\geq v$ for every $q$. Therefore $\min_q L(p^*,q)\geq v$, so $\alpha\geq v$. By the left saddle inequality, $L(p,q^*)\leq v$ for every $p$. Therefore $\max_p L(p,q^*)\leq v$, so $\beta\leq v$. The weak minimax inequality gives $\alpha\leq\beta$. Combining the three inequalities,

v\leq\alpha\leq\beta\leq v,

so $\alpha=\beta=v$. Moreover, the inequalities show that $p^*$ attains the maximin and $q^*$ attains the minimax. $\square$

The converse is also useful: if the maximin and minimax values are equal and the optimizing strategies are attained, any maximin strategy paired with any minimax strategy satisfies the saddle inequalities. This makes precise the relationship between minimax equality and a saddle-point certificate.

Result: Suppose $\alpha=\beta=v$, and let $p^*$ attain $\max_p\min_q L(p,q)$ while $q^*$ attains $\min_q\max_p L(p,q)$. Then $(p^*,q^*)$ is a saddle-point pair.

Proof. Since $p^*$ attains the maximin value, $\min_q L(p^*,q)=v$, so $L(p^*,q)\geq v$ for every $q$. Since $q^*$ attains the minimax value, $\max_p L(p,q^*)=v$, so $L(p,q^*)\leq v$ for every $p$. In particular, taking $q=q^*$ in the first inequality gives $L(p^*,q^*)\geq v$; taking $p=p^*$ in the second gives $L(p^*,q^*)\leq v$. Thus $L(p^*,q^*)=v$, and the two inequalities become

L(p,q^*)\leq L(p^*,q^*)\leq L(p^*,q)

for every $p,q$. This is exactly the saddle-point condition. $\square$

The attainment condition matters for this converse: equality of supremum and infimum values alone does not identify strategies that achieve them if optimizers do not exist. In a finite matrix game with mixed strategies, compactness of the probability simplexes and continuity of the expected payoff ensure attainment.

Worked Examples with Mixed Strategies

Worked Example: A Saddle Point with Both Players Mixing

Let

A=\begin{pmatrix}4&0\\1&3\end{pmatrix}.

Suppose the row player chooses row 1 with probability $p$, and the column player chooses column 1 with probability $q$. Against column strategy $q$, the payoffs from pure rows 1 and 2 are $4q$ and $q+3(1-q)=3-2q$. To make the row player willing to mix, set these equal:

4q=3-2q,\qquad 6q=3,\qquad q=\frac12.

At $q^*=\tfrac12$, each row gives payoff 2. Against row strategy $p$, the payoffs from pure columns 1 and 2 are $4p+1(1-p)=1+3p$ and $0p+3(1-p)=3-3p$. Set these equal to find a column mixture that makes the row player indifferent:

1+3p=3-3p,\qquad 6p=2,\qquad p=\frac13.

At $p^*=\tfrac13$, both columns give payoff 2. More explicitly, for every row mixture $p$,

$$ L(p,q^*)=2p+2(1-p)=2, $$

and for every column mixture $q$,

$$ L(p^*,q)=2q+2(1-q)=2. $$

Thus $L(p,q^*)\leq 2\leq L(p^*,q)$, with equality throughout. The pair $(p^*,q^*)=((\tfrac13,\tfrac23),(\tfrac12,\tfrac12))$ is a saddle point, and the game value is 2.

Worked Example: Matching Pennies Has No Pure Saddle Point

For the payoff matrix

A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix},

the row player wins 1 when the choices match and loses 1 otherwise. No pure-strategy pair is a saddle point. At either matching cell, changing the column can lower the payoff from 1 to $-1$, violating the right saddle inequality. At either nonmatching cell, changing the row can raise the payoff from $-1$ to 1, violating the left inequality.

Now let both players use $(\tfrac12,\tfrac12)$. Against either pure column, the row player’s expected payoff is $\tfrac12(1)+\tfrac12(-1)=0$; the same holds for either pure row against the column mixture. By linearity, every mixed strategy also gives payoff 0 against the other player’s half-and-half strategy. Therefore

$$ L(p,q^*)=0=L(p^*,q) $$

for all $p,q$. The mixed pair is a saddle point with value 0, even though no pure pair is one.

Common Mistake: Checking Only the Payoff at the Pair

A payoff at a proposed pair does not by itself show that either strategy is optimal. For example, in matching pennies, the pure pair (row 1, column 1) has payoff 1. But against column 1, switching to row 2 reduces the row player’s payoff to $-1$; the proposed row is not a best response. Also, against row 1, switching to column 2 lowers the payoff to $-1$; the proposed column is not a best response for the minimizing player. The required inequalities fail.

The correction is to compare against all unilateral deviations, not just to calculate $L(p^*,q^*)$. In a finite game, it suffices to check pure deviations: expected payoff is linear in each player’s mixed strategy, so if the relevant inequality holds for every pure strategy, it holds for every mixture of those strategies. This is why the mixed matching-pennies calculation checks each pure row and column before concluding that all mixtures satisfy the condition.

A saddle-point pair also certifies the value without requiring a separate comparison of every possible strategy pair. The row strategy guarantees at least $v$, the column strategy guarantees at most $v$, and the weak minimax inequality leaves no room for a different value. That direct certificate is useful in calculations and in checking proposed solutions to finite zero-sum games.

Check Your Understanding

Use the row-maximizer, column-minimizer convention throughout.

Write the two saddle-point inequalities and explain which player’s deviation each one checks.
Why does a saddle-point pair force the maximin and minimax values to equal its payoff?
In a finite matrix game, why is it enough to check the saddle inequalities against pure deviations?
What attainment condition is needed to conclude that optimal strategies form a saddle-point pair from minimax equality?
For matching pennies, explain why the equal-probability mixed strategies satisfy both saddle inequalities even though no pure pair does.