View source for Minimax theorem

{{confuse|Min-max theorem}}
{{short description|Gives conditions that guarantee the max–min inequality holds with equality}}
In the mathematical area of [[game theory]] and of [[convex optimization]], a '''minimax theorem''' is a theorem that claims that
: <math>\max_{x\in X} \min_{y\in Y} f(x,y) = \min_{y\in Y} \max_{x\in X}f(x,y)</math>
under certain conditions on the sets <math>X</math> and <math>Y</math> and on the function <math>f</math>.<ref>{{Citation |last=Simons |first=Stephen |title=Minimax Theorems and Their Proofs |date=1995 |work=Minimax and Applications |series=Nonconvex Optimization and Its Applications |volume=4 |pages=1–23 |editor-last=Du |editor-first=Ding-Zhu |url=https://link.springer.com/chapter/10.1007/978-1-4613-3557-3_1 |access-date=2024-10-27 |place=Boston, MA |publisher=Springer US |language=en |doi=10.1007/978-1-4613-3557-3_1 |isbn=978-1-4613-3557-3 |editor2-last=Pardalos |editor2-first=Panos M.}}</ref> It is always true that the left-hand side is at most the right-hand side ([[max–min inequality]]) but equality only holds under certain conditions identified by minimax theorems. The first theorem in this sense is [[John von Neumann|von Neumann]]'s minimax theorem about two-player [[Zero-sum game|zero-sum games]] published in 1928,<ref name=":0">{{cite journal |last=Von Neumann |first=J. |year=1928 |title=Zur Theorie der Gesellschaftsspiele |journal=[[Mathematische Annalen|Math. Ann.]] |volume=100 |pages=295–320 |doi=10.1007/BF01448847|s2cid=122961988 }}</ref> which is considered the starting point of [[game theory]]. Von Neumann is quoted as saying "''As far as I can see, there could be no theory of games ... without that theorem ... I thought there was nothing worth publishing until the Minimax Theorem was proved''".<ref name="Casti">{{cite book |author=John L Casti |url=https://archive.org/details/fivegoldenrulesg00cast/page/19 |title=Five golden rules: great theories of 20th-century mathematics – and why they matter |publisher=Wiley-Interscience |year=1996 |isbn=978-0-471-00261-1 |location=New York |page=[https://archive.org/details/fivegoldenrulesg00cast/page/19 19] |url-access=registration}}</ref> Since then, several generalizations and alternative versions of von Neumann's original theorem have appeared in the literature.<ref>{{cite book |title=Minimax and Applications |date=1995 |publisher=Springer US |isbn=9781461335573 |editor1-last=Du |editor1-first=Ding-Zhu |location=Boston, MA |editor2-last=Pardalos |editor2-first=Panos M.}}</ref><ref>{{Cite journal |last1=Brandt |first1=Felix |last2=Brill |first2=Markus |last3=Suksompong |first3=Warut |year=2016 |title=An ordinal minimax theorem |journal=Games and Economic Behavior |volume=95 |pages=107–112 |arxiv=1412.4198 |doi=10.1016/j.geb.2015.12.010 |s2cid=360407}}</ref>

== Bilinear functions and zero-sum games ==
Von Neumann's original theorem<ref name=":0" /> was motivated by game theory and applies to the case where 

* <math>X</math> and <math>Y</math> are [[Simplex|standard simplexes]]: <math display="inline">X = \{ (x_1, \dots, x_n) \in [0,1]^n : \sum_{i = 1}^n x_i = 1 \}
</math> and <math display="inline">Y = \{ (y_1, \dots, y_m) \in [0,1]^m : \sum_{j = 1}^m y_j = 1 \}</math>, and
* <math>f(x,y)</math> is a linear function in both of its arguments (that is, <math>f</math> is [[Bilinear form|bilinear]]) and therefore can be written <math>f(x,y) = x^\mathsf{T} A y</math> for a finite matrix <math>A \in \mathbb{R}^{n \times m}</math>, or equivalently as <math display="inline">f(x,y) = \sum_{i=1}^n\sum_{j=1}^m A_{ij}x_iy_j</math>.

Under these assumptions, von Neumann proved that
: <math>\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. </math>
In the context of two-player [[Zero-sum game|zero-sum games]], the sets <math>X</math> and <math>Y</math> 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|payoff matrix]] <math>A</math>. The function <math>f(x,y)</math> encodes the [[expected value]] of the payoff to the first player when the first player plays the strategy <math>x</math> and the second player plays the strategy <math>y</math>.

== Concave-convex functions ==
[[File:Saddle point.svg|thumb|The function {{math|1=''f''(''x'', ''y'') = ''x''<sup>2</sup> − ''y''<sup>2</sup>}} is concave-convex.]]
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 <math>X \subseteq \mathbb{R}^n</math> and <math>Y \subseteq \mathbb{R}^m</math> be [[compact space|compact]] [[Convex set|convex]] sets. If <math>f: X \times Y \rightarrow \mathbb{R}</math> is a continuous function that is concave-convex, i.e.

: <math>f(\cdot,y): X \to \mathbb{R}</math> is [[concave function|concave]] for every fixed <math>y \in Y</math>, and
: <math>f(x,\cdot): Y \to \mathbb{R}</math> is [[convex function|convex]] for every fixed <math>x \in X</math>.

Then we have that

: <math>\max_{x\in X} \min_{y\in Y} f(x,y) = \min_{y\in Y} \max_{x\in X}f(x,y).</math>

== Sion's minimax theorem ==

Sion's minimax theorem is a generalization of von Neumann's minimax theorem due to [[Maurice Sion]],<ref name=":1">{{cite journal |last=Sion |first=Maurice |year=1958 |title=On general minimax theorems |journal=[[Pacific Journal of Mathematics]] |volume=8 |issue=1 |pages=171–176 |doi=10.2140/pjm.1958.8.171 |mr=0097026 |zbl=0081.11502 |doi-access=free}}</ref> relaxing the requirement that  It states:<ref name=":1" /><ref>{{cite journal |last=Komiya |first=Hidetoshi |year=1988 |title=Elementary proof for Sion's minimax theorem |url=http://projecteuclid.org/euclid.kmj/1138038812 |journal=[[Kodai Mathematical Journal]] |volume=11 |issue=1 |pages=5–7 |doi=10.2996/kmj/1138038812 |mr=0930413 |zbl=0646.49004}}</ref>

Let <math>X</math> be a [[Convex set|convex]] subset of a [[linear topological space]] and let <math>Y</math> be a [[compact space|compact]] [[Convex set|convex]] subset of a [[linear topological space]].  If <math>f</math> is a real-valued [[Function (mathematics)|function]] on <math>X\times Y</math> with

: <math>f(\cdot,y)</math> [[upper semicontinuous]]  and [[quasi-convex function|quasi-concave]] on <math>X</math>, for every fixed <math>y\in Y</math>, and
: <math>f(x,\cdot)</math> lower semicontinuous and quasi-convex on <math>Y</math>, for every fixed <math>x\in X</math>.

Then we have that

: <math>\sup_{x\in X}\min_{y\in Y} f(x,y) = \min_{y\in Y}\sup_{x\in X} f(x,y). </math>

== See also ==
* [[Parthasarathy's theorem]]{{snd}}a generalization of  Von Neumann's minimax theorem
* [[Dual linear program]] can be used to prove the minimax theorem for zero-sum games.
* [[Yao's principle]]{{snd}}an application of the minimax theorem to computational complexity

== References ==
{{Reflist}}

[[Category:Game theory]]
[[Category:Mathematical optimization]]
[[Category:Mathematical theorems]]


{{mathanalysis-stub}}
{{gametheory-stub}}