Minimax theorem

From Glossary

Jump to: navigation, search

Proven by von Neumann in 1928, this is a cornerstone of duality (and of game theory). It states that there exists LaTeX: x \in S_m and LaTeX: y \in S_n such that LaTeX: x^T A y is a saddlepoint of the bilinear form:

LaTeX: \min \left\{ \max \{ u^T A v: v \in S_n\}: u \in S_m \right} = 
\max \left\{ \min \{ u^T A v: u \in S_m\}: v \in S_n \right\} = x^TAy.

This extends to the following.

Let LaTeX: F:X\timesY\rightarrow \mathbb{R} be such that LaTeX: X and LaTeX: Y are non-empty, convex, compact sets, LaTeX: F(.,y) is convex on LaTeX: X for each LaTeX: y \in Y, and LaTeX: F(x,.) is concave on LaTeX: Y for each LaTeX: x \in X. Then, there exists a saddlepoint, LaTeX: (x^*,y^*) \in X\times Y such that

LaTeX: \min \left\{ \max \{F(x,y): y \in Y\}: x \in X\right\} 
= \max \left\{ \min \{F(x,y): x \in X\}: y \in Y\right\} = F(x^*,y^*).

Personal tools