A Discontinuous Payoff That Defeats Minimax Interchange

Why the Order of Optimization Can Matter

In a zero-sum game, let $x$ be the minimizing player's strategy, $y$ the maximizing player's strategy, and $g(x,y)$ the payoff to the maximizer. The minimizing player must account for the maximizer's best response, giving the value $\inf_x\sup_y g(x,y)$. Reversing the order gives $\sup_y\inf_x g(x,y)$: the maximizer chooses first, and the minimizer responds. The first quantity is always at least the second, but equality needs more than a bounded payoff and compact, convex strategy sets.

The example at the center of this tutorial has strategy sets that are both compact and convex, and its payoff is bounded. Its minimax gap comes from a precise failure of regularity: the payoff is not lower semicontinuous in the minimizing player's strategy, as required by Sion's minimax theorem.

Definition: For a payoff $g:X\times Y\to\mathbb{R}$, the minimax value is $\inf_{x\in X}\sup_{y\in Y}g(x,y)$, and the maximin value is $\sup_{y\in Y}\inf_{x\in X}g(x,y)$. Their difference, when both are finite, is the minimax gap. A strict gap means the minimax value is strictly larger than the maximin value.

The strategy sets here are nonempty and the payoffs are bounded, so both quantities are finite. The general weak minimax inequality gives the direction in which a gap can occur.

Theorem: If $X$ and $Y$ are nonempty and $g:X\times Y\to\mathbb{R}$ is bounded, then $$ \sup_{y\in Y}\inf_{x\in X}g(x,y) \ \leq\ \inf_{x\in X}\sup_{y\in Y}g(x,y). $$ Proof: Fix $x\in X$. For every $y\in Y$, $\inf_{x'\in X}g(x',y)\leq g(x,y)\leq\sup_{y'\in Y}g(x,y')$. The rightmost quantity does not depend on $y$, so taking the supremum over $y$ gives $\sup_y\inf_{x'}g(x',y)\leq\sup_{y'}g(x,y')$. This holds for every $x$; taking the infimum over $x$ proves the inequality. $\square$

The Diagonal-Indictor Game

Take $X=Y=[0,1]$, with their usual topology, and define

g(x,y)=\mathbf{1}_{\{x=y\}}= \begin{cases} 1,&x=y,\\ 0,&x\ne y. \end{cases}

This payoff is bounded between 0 and 1. The strategy sets are compact and convex. Nevertheless, the two optimization orders give different answers.

Worked Example: Computing Both Values

First fix $x$. The maximizer can choose $y=x$, which gives $g(x,x)=1$. Since no payoff exceeds 1, $\sup_{y\in[0,1]}g(x,y)=1$ for every $x$. Consequently,

\inf_{x\in[0,1]}\sup_{y\in[0,1]}g(x,y) =\inf_{x\in[0,1]}1=1.

Now fix $y$. The minimizer can choose any $x\ne y$, which is possible because $[0,1]$ contains more than one point. This gives payoff 0, the smallest possible value. Thus $\inf_{x\in[0,1]}g(x,y)=0$ for every $y$, and

\sup_{y\in[0,1]}\inf_{x\in[0,1]}g(x,y) =\sup_{y\in[0,1]}0=0.

The minimax value is 1, the maximin value is 0, and the gap is $1-0=1$. Both strategy sets are compact and convex, and both optimization calculations are exact. The gap is not caused by a missing extremum: it is caused by the payoff's failure to meet the regularity conditions needed for interchange.

Which Regularity Condition Fails?

Sion's minimax theorem gives one standard set of sufficient conditions for interchanging the two optimizations. In the orientation used here, its relevant hypotheses include a lower semicontinuous and quasiconvex payoff as a function of the minimizing strategy $x$, for each fixed $y$, and an upper semicontinuous and quasiconcave payoff as a function of the maximizing strategy $y$, for each fixed $x$. The strategy sets must also satisfy the theorem's convexity and compactness assumptions. Here both sets are compact and convex, so inspect the payoff sections.

For fixed $y$, the section in the minimizing strategy is $x\mapsto\mathbf{1}_{\{x=y\}}$. At $x=y$ it has value 1, but for any sequence $x_n\ne y$ with $x_n\to y$, its values are all 0. Lower semicontinuity would require $g(y,y)\leq\liminf_n g(x_n,y)$, or $1\leq0$, which is false. The section is not lower semicontinuous.

For an interior value of $y$, this section also fails quasiconvexity. For example, with $y=1/2$, the sublevel set $\{x:g(x,1/2)\leq1/2\}=[0,1]\setminus\{1/2\}$ is not convex: it contains 0 and 1 but not their midpoint. By contrast, for fixed $x$, the section in $y$ is upper semicontinuous and quasiconcave. Its upper-level sets are either empty, the singleton $\{x\}$, or all of $[0,1]$, each of which is convex. Thus the required condition in the minimizing coordinate already fails, even though the condition in the maximizing coordinate holds.

Key takeaway: Compactness, convexity, and boundedness alone do not imply minimax equality. For this game, the decisive failure is that the payoff section in the minimizing strategy is not lower semicontinuous; for interior fixed $y$, it is not quasiconvex either.

Worked Example: A Continuous Perturbation Leaves the Gap Intact

Consider the same strategy sets, but add the continuous term $x-y$:

h(x,y)=x-y+\mathbf{1}_{\{x=y\}}.

This payoff is bounded, since $-1\leq x-y\leq1$ and the indicator is either 0 or 1. Fix $x$. At $y=x$, $h(x,x)=1$. If $x>0$, choosing $y=0$ gives $h(x,0)=x\leq1$; every other off-diagonal choice gives $x-y\leq x\leq1$. When $x=0$, off-diagonal payoffs are $-y\leq0$, still below the diagonal payoff 1. Hence $\sup_y h(x,y)=1$ for every $x$, and the minimax value is 1.

For fixed $y>0$, choosing $x=0$ gives $h(0,y)=-y$. Every off-diagonal choice satisfies $h(x,y)=x-y\geq-y$, while the diagonal choice gives 1. Therefore $\inf_x h(x,y)=-y$. For $y=0$, the diagonal choice gives 1, while every $x>0$ gives $h(x,0)=x$. Since positive $x$'s can approach 0, $\inf_x h(x,0)=0$. It follows that

\sup_{y\in[0,1]}\inf_{x\in[0,1]}h(x,y) =\sup\bigl(\{0\}\cup\{-y:0<y\leq1\}\bigr)=0.

The gap is again $1-0=1$. In this example the infimum at $y=0$ is not attained, but its value is still 0; the calculation uses an infimum, not a minimum. Adding a continuous term has not removed the diagonal discontinuity responsible for the gap.

A More Pervasive Discontinuity

The diagonal example concentrates its discontinuity on a simple set. A related construction shows that the same optimization gap can occur when discontinuity is far more widespread. Let $X=Y=[0,1]$, and use the payoff that is 1 when the difference $x-y$ is rational and 0 otherwise. The payoff is bounded and measurable: the set of pairs with rational difference is a countable union of closed line segments intersected with the square.

Worked Example: Rational Differences

For every fixed $x$, the maximizing player can choose $y=x$. Then $x-y=0$, which is rational, and the payoff is 1. Since the payoff cannot exceed 1, $\sup_y g(x,y)=1$ for all $x$, so $\inf_x\sup_y g(x,y)=1$.

For every fixed $y$, there is an $x\in[0,1]$ such that $x-y$ is irrational: the interval $[-y,1-y]$ has positive length and contains irrational numbers. Choosing such an $x$ gives payoff 0. Since the payoff is nonnegative, $\inf_x g(x,y)=0$ for every $y$, and therefore $\sup_y\inf_x g(x,y)=0$. The gap is again 1.

Unlike the diagonal-indicator payoff, this one is discontinuous throughout the square: rational and irrational differences both occur arbitrarily close to any given difference, including at the boundary when neighborhoods are understood relative to $[0,1]^2$. The calculation does not require this stronger pathology; it illustrates that a strict gap can arise from several kinds of discontinuity.

Diagnosing the Gap

When a minimax interchange is in question, the inequality in the theorem above is a useful first check: it rules out a gap in the opposite direction. Then inspect the hypotheses of the particular interchange theorem being used. In the diagonal game, neither compactness nor convexity is the problem. The minimizing coordinate violates lower semicontinuity, and the interior sections also violate quasiconvexity. This pinpoints why a theorem such as Sion's cannot justify equality here; the direct calculations show that equality is in fact false.

A common mistake is to reason that both players have compact strategy sets, the payoff is bounded, and therefore the two optimization orders must agree. Those facts do not suffice. Another mistake is to replace an infimum by a minimum without checking attainment, as the $y=0$ calculation for the perturbed payoff demonstrates. Keep the order of optimization explicit, distinguish infima from attained minima, and check the regularity assumptions in the coordinate to which they apply.

Check Your Understanding

Answer these questions using the definitions and calculations above.

For the diagonal-indicator payoff, what strategy can the maximizer choose after $x$ is fixed, and what strategy can the minimizer choose after $y$ is fixed?
State the weak minimax inequality and explain why it rules out a negative minimax gap.
At a diagonal point, which lower semicontinuity inequality fails for the section in the minimizing strategy?
Why does the interior section $x\mapsto\mathbf{1}_{\{x=1/2\}}$ fail to be quasiconvex?
In the perturbed example at $y=0$, why is the infimum 0 even though no $x$ attains it?