Nonconvex Strategy Sets and Strict Minimax Gaps

Why Strategy Restrictions Matter

Minimax equality is sensitive not only to the payoff function but also to the strategy sets over which the two optimizations are taken. A payoff may be continuous and bilinear, and the strategy sets may be finite, yet the two orders of optimization can give different answers when strategies are restricted to nonconvex sets. The gap is not a failure of algebra: the player who moves second in each optimization faces a different set of available responses.

Throughout, $x$ is the minimizing player’s strategy, $y$ is the maximizing player’s strategy, and $f(x,y)$ is the payoff to the maximizing player. The minimizing player wants this payoff small; the maximizing player wants it large.

Definition: The minimax value and maximin value are, respectively, $$ \inf_{x\in X}\sup_{y\in Y} f(x,y) \qquad\text{and}\qquad \sup_{y\in Y}\inf_{x\in X} f(x,y). $$ Their difference, $\inf_{x\in X}\sup_{y\in Y} f(x,y)-\sup_{y\in Y}\inf_{x\in X} f(x,y)$, is the minimax gap. The weak minimax inequality says that this difference is nonnegative.

The weak inequality does not require convexity. For any fixed $x$ and $y$, $\inf_{x'\in X}f(x',y)\leq f(x,y)\leq\sup_{y'\in Y}f(x,y')$. Taking the supremum over $y$ on the left and then the infimum over $x$ on the right gives

\sup_{y\in Y}\inf_{x\in X}f(x,y) \leq \inf_{x\in X}\sup_{y\in Y}f(x,y).

A strict inequality is possible if the strategy sets do not have the convexity needed for minimax interchange. The following small game isolates that issue while keeping the payoff especially simple.

A Strict Gap with Two Pure Strategies Each

Worked Example: The Product Payoff on Two Nonconvex Sets

Let $X=Y=\{-1,1\}$ and $f(x,y)=xy$. For each fixed $x$, the maximizing player can choose $y=x$, giving $xy=1$. The other choice gives $-1$. Thus $\sup_{y\in Y}xy=1$ for both choices of $x$, and $$ \inf_{x\in X}\sup_{y\in Y}xy=1. $$

For each fixed $y$, the minimizing player can choose $x=-y$, giving $xy=-1$. Hence $\inf_{x\in X}xy=-1$ for both choices of $y$, so $$ \sup_{y\in Y}\inf_{x\in X}xy=-1. $$

The minimax gap is $1-(-1)=2$. In matrix form, with rows indexed by $x$ and columns by $y$, the payoffs are

\begin{array}{c|rr} & y=-1 & y=1\\ \hline x=-1 & 1 & -1\\ x=1 & -1 & 1 \end{array}

Each player has a response that reverses the other player’s pure choice. Neither optimization order can select a compromise strategy, because zero is not in either pure strategy set.

What Convexification Changes

For a finite set of actions, a randomized strategy is a probability distribution over those actions. Under the usual expected-payoff extension, the payoff is averaged over the players’ randomizations. In this product game, if $X$ and $Y$ are independent random choices, then $E[XY]=E[X]E[Y]$. A distribution on $\{-1,1\}$ can have any mean in $[-1,1]$, so the expected payoff can be written as $uv$, where $u$ and $v$ are the two players’ means. This is the convexified game on the interval sets.

Result: For $f(u,v)=uv$ on $X=Y=[-1,1]$, both minimax values equal zero. The convexified game therefore has no minimax gap.

Here is the full calculation. For any fixed $u\in[-1,1]$, maximizing $uv$ over $v\in[-1,1]$ gives $|u|$: choose $v=1$ if $u\geq 0$, and $v=-1$ if $u<0$. Consequently,

\inf_{u\in[-1,1]}\sup_{v\in[-1,1]}uv = \inf_{u\in[-1,1]}|u| =0,

with the infimum attained at $u=0$. For fixed $v$, minimizing over $u$ gives $-|v|$, by choosing $u=-1$ when $v\geq 0$ and $u=1$ when $v<0$. Therefore,

\sup_{v\in[-1,1]}\inf_{u\in[-1,1]}uv = \sup_{v\in[-1,1]}(-|v|) =0,

attained at $v=0$. The two values agree, and the pair $(u,v)=(0,0)$ gives payoff zero. Convexification adds the ability to average the two original actions, rather than merely relabeling the original choices.

Proof of the convexification calculation: The maximum and minimum of the linear function $v\mapsto uv$ on $[-1,1]$ occur at an endpoint unless $u=0$, when the function is constant. Thus $\sup_v uv=|u|$. The minimum of $u\mapsto uv$ is likewise $-|v|$. Since absolute value is nonnegative and equals zero at the origin, the respective outer optimization gives zero in each case. $\square$

A Different Finite Game

The phenomenon is not restricted to a symmetric product payoff. In a finite matrix game, pure actions give the row and column choices, while randomized actions give probability vectors. The expected payoff is a bilinear function of those vectors.

Worked Example: An Asymmetric Two-by-Two Payoff Matrix

Let the minimizing player choose a row, the maximizing player choose a column, and use the payoff matrix

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

With pure strategies, the maximum in the first row is $2$, and the maximum in the second row is $1$. The minimizing player chooses the second row, so the pure-strategy minimax value is $\min(2,1)=1$. In the first column, the minimum payoff is $\min(0,1)=0$; in the second column it is $\min(2,0)=0$. The pure-strategy maximin value is therefore $\max(0,0)=0$. The pure-strategy gap is $1$.

Now let $p$ be the probability of choosing row 1 and $q$ the probability of choosing column 1. The expected payoff is $$ 0\cdot pq+2p(1-q)+1(1-p)q+0\cdot(1-p)(1-q) =2p+q-3pq. $$ For fixed $p$, this expression is linear in $q$, so its maximum over $q\in[0,1]$ is $2p+\max(0,1-3p)$. If $0\leq p\leq 1/3$, this is $1-p$, whose minimum on that interval is $2/3$, at $p=1/3$. If $1/3\leq p\leq1$, it is $2p$, whose minimum is also $2/3$, at $p=1/3$. Thus the randomized minimax value is $2/3$.

For the other order, fixing $q$ and minimizing over $p\in[0,1]$ gives $q+\min(0,2-3q)$. When $0\leq q\leq2/3$, this is $q$, whose maximum is $2/3$. When $2/3\leq q\leq1$, it is $2-2q$, whose maximum is again $2/3$. Hence the randomized maximin value is $2/3$, attained at $q=2/3$. Randomization closes the pure-strategy gap in this example as well.

These calculations show why it is important to say which strategies are allowed. Replacing pure actions by probability distributions changes the feasible sets and the values. It does not assert that the original pure-strategy values were equal; in both examples, they were not.

Convexifying Only One Side May Not Suffice

Worked Example: A Remaining Gap After One-Sided Convexification

Return to $f(x,y)=xy$ on the original sets $\{-1,1\}$. First convexify only the minimizing player’s set, so $X=[-1,1]$ but $Y=\{-1,1\}$. For any fixed $x$, the maximizing player can choose the sign of $y$ to obtain $|x|$. Hence $$ \inf_{x\in[-1,1]}\sup_{y\in\{-1,1\}}xy =\inf_{x\in[-1,1]}|x|=0. $$ For either fixed pure $y$, the minimizing player can choose $x=-y$, giving $-1$. Thus $$ \sup_{y\in\{-1,1\}}\inf_{x\in[-1,1]}xy=-1. $$ The gap is still $1$.

Instead convexify only the maximizing player’s set: $X=\{-1,1\}$ and $Y=[-1,1]$. For either fixed $x$, the maximizing player can choose $y=x$, so the minimax value is $1$. For fixed $y$, minimizing over the two choices of $x$ gives $-|y|$, and maximizing this over $y\in[-1,1]$ gives zero. The maximin value is $0$, so the gap is again $1$. In this particular game, convexifying both sets is what makes the two values coincide.

This one-sided calculation is a useful caution: convexifying a strategy set is not, by itself, a general guarantee of minimax equality. The conditions for an interchange concern the relevant strategy sets and the payoff’s behavior in both arguments. Here the missing convexity leaves the opposing player without the zero-mean response needed to match the other optimization order.

Common Pitfall

Wrong reasoning: “The payoff is bilinear and continuous, so the minimax values must be equal.”
Correction: The strategy-set hypotheses matter too. On $X=Y=\{-1,1\}$, $xy$ is bilinear and continuous on the ambient real line, but the pure-strategy values are $1$ and $-1$. Convexity cannot be inferred from bilinearity of the payoff.
Another error: Treating an available pure action as if it included every average of that action and another one. A mixed strategy is an additional permitted strategy, and its expected payoff must be calculated using the randomized-strategy rule.

Key takeaway: A strict minimax gap can arise from nonconvex strategy restrictions even in a finite, continuous, bilinear game. In the examples here, allowing randomization convexifies the strategy sets and removes the gap when both players can randomize; convexifying only one side need not do so.

Check Your Understanding

Use the definitions and calculations above to answer the following.

For $f(x,y)=xy$ on $X=Y=\{-1,1\}$, calculate each optimization order and the minimax gap.
In the same game, why does allowing each player to randomize permit a strategy with mean zero?
For the matrix $\begin{pmatrix}0&2\\1&0\end{pmatrix}$, verify the pure-strategy minimax and maximin values from the row and column extrema.
In the asymmetric matrix example, which probabilities attain the randomized minimax and maximin values?
What does the one-sided convexification example show about the claim that convexifying either one of the two strategy sets always guarantees equality?