Extended minimax theorems

V. Protassov, G.B.G. Frenk¹, and G. Kassay¹
Moscow State University, EUR

Let $A,B$ be nonempty sets and $f:A\times B\rightarrow \mathbb{R}$ some function. The so-called primal problem associated with the function $f$ is given by

$$v(P):=\inf_{b\in B}\sup_{a\in A}f(a,b) P$$

while the so-called dual problem has the form

$$v(D):=\sup_{a\in A}\inf_{b\in B}f(a,b). D$$

It is easy to verify that $v(D)\leq v(P)$ and in general this inequality is strict. One is now interested under which conditions on the function $f$ it follows that $v(D)=v(P)$ and such a result is called a minimax theorem.

Problems of this kind naturally appear in convex analysis, optimization theory (duality in optimization) and game theory. The study of the minimax problems starts with a famous work of von Neumann (1928), where the case of finite sets $A,B$ was considered. Later many authors generalized and sharpened that result. In particular, Kneser showed that $v(D)=v(P)$, whenever both $A,B$ are convex, $A$ is compact and $f$ is concave and upper-semicontinuous in $a$ and convex in $B$. Then Sion extended this theorem onto quasiconcave/quasiconvex functions.

We consider a generalized variant of the minimax problem. Let ${\mathcal{P}_A}, {\mathcal{P}_B}$ be the sets of all finitely-supported probability measures on $A$ and $B$ respectively. Let also $G_A$ and $G_B$ be some given subsets of $A$ and $B$. The problem is to determine sufficient and necessary conditions on the function $f$, under which

$$\sup\limits_{\lambda \in G_A}\inf\limits_{\mu \in G_B} \tilde f(\... ...inf\limits_{\mu \in G_B}\sup\limits_{\lambda \in G_A} \tilde f(\lambda, \mu ),$$

where $\tilde f(\lambda, \mu ) = \int\limits_{A\times B} f(a,b) d \lambda d\mu$. In a special case, when $G_A, G_B$ are the sets of all one-point measures, this problem becomes the classical minimax problem. For the case $G_A = {\mathcal{P}_A}, G_B = {\mathcal{P}_B}$ we present the following results:

Theorem 1   If the set $A$ is totally bounded (has a compact closure) and the family $\Bigl\{ f_{b}:A\rightarrow {\mathbb{R}},\ b \in B\Bigr\}$ is equicontinuous on $A$, then

$$\sup_{\lambda \in {\mathcal{P}_A}}\inf_{\mu \in {\mathcal{P}_B}} ... ...in {\mathcal{P}_B}}\sup_{\lambda \in {\mathcal{P}_A}} \tilde f (\lambda, \mu ).$$ (1)

Corollary 1   If both $A$ and $B$ are compact and the function $f$ is continuous on $A \times B$, then () holds.

A special case of Theorem 1 is well known:

Corollary 2   Equality () always holds whenever either $A$ or $B$ is finite.

Theorem 2   If both sets $A$ and $B$ are compact, the function $f_{b}:A\rightarrow {\mathbb{R}}$ is upper semicontinuous for every $b\in B$ and $f_{a}:B\rightarrow {\mathbb{R}}$ is lower semicontinuous for every $a\in A$, and the function $f:A\times B\rightarrow {\mathbb{R}}$ is either bounded from above or from below then () holds.

The proofs are based on the extended Riesz representation theorem and the separation theorems. The results are sharp in the sense that none of their assumptions can be weakened. Theorems 1 and 2 generalize several previously known results on minimax, in particular, van Noumann theorem and equilibrium theorems in game theory (mixed strategies in matrix games).