Minimax theorem

Von Neumann's original theorem was motivated by game theory and applies to the case where • X and Y are standard simplexes: X = \{ (x_1, \dots, x_n) \in [0,1]^n : \sum_{i = 1}^n x_i = 1 \} and Y = \{ (y_1, \dots, y_m) \in [0,1]^m : \sum_{j = 1}^m y_j = 1 \}, and • f(x,y) is a linear function in both of its arguments (that is, f is bilinear) and therefore can be written f(x,y) = x^\mathsf{T} A y for a finite matrix A \in \mathbb{R}^{n \times m}, or equivalently as f(x,y) = \sum_{i=1}^n\sum_{j=1}^m A_{ij}x_iy_j. Under these assumptions, von Neumann proved that : \max_{x \in X} \min_{y \in Y} x^\mathsf{T} A y = \min_{y \in Y}\max_{x \in X} x^\mathsf{T} A y. In the context of two-player zero-sum games, the sets X and Y correspond to the strategy sets of the first and second player, respectively, which consist of lotteries over their actions (so-called mixed strategies), and their payoffs are defined by the payoff matrix A. The function f(x,y) encodes the expected value of the payoff to the first player when the first player plays the strategy x and the second player plays the strategy y. == Concave-convex functions ==

Von Neumann's minimax theorem can be generalized to domains that are compact and convex, and to functions that are concave in their first argument and convex in their second argument (known as concave-convex functions). Formally, let X \subseteq \mathbb{R}^n and Y \subseteq \mathbb{R}^m be compact convex sets. If f: X \times Y \rightarrow \mathbb{R} is a continuous function that is concave-convex, i.e. : f(\cdot,y): X \to \mathbb{R} is concave for every fixed y \in Y, and : f(x,\cdot): Y \to \mathbb{R} is convex for every fixed x \in X. Then we have that : \max_{x\in X} \min_{y\in Y} f(x,y) = \min_{y\in Y} \max_{x\in X}f(x,y). == Sion's minimax theorem ==

Sion's minimax theorem is a generalization of von Neumann's minimax theorem due to Maurice Sion, relaxing the requirement that X and Y be standard simplexes and that f be bilinear. It states: Let X be a convex subset of a linear topological space and let Y be a compact convex subset of a linear topological space. If f is a real-valued function on X\times Y with : f(\cdot,y) upper semicontinuous and quasi-concave on X, for every fixed y\in Y, and : f(x,\cdot) lower semicontinuous and quasi-convex on Y, for every fixed x\in X. Then we have that : \sup_{x\in X}\min_{y\in Y} f(x,y) = \min_{y\in Y}\sup_{x\in X} f(x,y). == See also ==