134 Learning Theory — Minimax

134.1 Overview

This module is the public entry point for the convex-compact minimax theorem: it gathers the finite minimax, coarse correlated equilibrium, core, separation, and no-regret components and exposes a single top-level statement asserting equality of the upper and lower values of a convex-concave payoff function on subsets of \(\mathbb {R}\).

134.2 Declarations

Theorem 134.1 Convex-compact minimax theorem on the line

✓

Let \(X, Y \subseteq \mathbb {R}\) be nonempty convex sets with \(X\) compact, and let \(f : \mathbb {R}\times \mathbb {R}\to \mathbb {R}\) be a payoff function that is bounded above and below on \(X \times Y\). Suppose that for every \(y \in Y\) the map \(x \mapsto f(x,y)\) is continuous and convex on \(X\), and that for every \(x \in X\) the map \(y \mapsto f(x,y)\) is concave on \(Y\). Then the minimax identity holds:

\[ \inf _{x \in X}\, \sup _{y \in Y}\, f(x,y) \; =\; \sup _{y \in Y}\, \inf _{x \in X}\, f(x,y). \]