Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Minimax theorem
Gives conditions that guarantee the max–min inequality is also an equality

In the mathematical area of game theory and of convex optimization, a minimax theorem is a theorem that claims that

max x ∈ X min y ∈ Y f ( x , y ) = min y ∈ Y max x ∈ X f ( x , y ) {\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y)}

under certain conditions on the sets X {\displaystyle X} and Y {\displaystyle Y} and on the function f {\displaystyle f} . 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 von Neumann's minimax theorem about two-player zero-sum games published in 1928, 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". Since then, several generalizations and alternative versions of von Neumann's original theorem have appeared in the literature.

We don't have any images related to Minimax theorem yet.
We don't have any YouTube videos related to Minimax theorem yet.
We don't have any PDF documents related to Minimax theorem yet.
We don't have any Books related to Minimax theorem yet.
We don't have any archived web articles related to Minimax theorem yet.

Bilinear functions and zero-sum games

Von Neumann's original theorem6 was motivated by game theory and applies to the case where

  • X {\displaystyle X} and Y {\displaystyle Y} are standard simplexes: X = { ( x 1 , … , x n ) ∈ [ 0 , 1 ] n : ∑ i = 1 n x i = 1 } {\textstyle X=\{(x_{1},\dots ,x_{n})\in [0,1]^{n}:\sum _{i=1}^{n}x_{i}=1\}} and Y = { ( y 1 , … , y m ) ∈ [ 0 , 1 ] m : ∑ j = 1 m y j = 1 } {\textstyle Y=\{(y_{1},\dots ,y_{m})\in [0,1]^{m}:\sum _{j=1}^{m}y_{j}=1\}} , and
  • f ( x , y ) {\displaystyle f(x,y)} is a linear function in both of its arguments (that is, f {\displaystyle f} is bilinear) and therefore can be written f ( x , y ) = x T A y {\displaystyle f(x,y)=x^{\mathsf {T}}Ay} for a finite matrix A ∈ R n × m {\displaystyle A\in \mathbb {R} ^{n\times m}} , or equivalently as f ( x , y ) = ∑ i = 1 n ∑ j = 1 m A i j x i y j {\textstyle f(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{m}A_{ij}x_{i}y_{j}} .

Under these assumptions, von Neumann proved that

max x ∈ X min y ∈ Y x T A y = min y ∈ Y max x ∈ X x T A y . {\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}

In the context of two-player zero-sum games, the sets X {\displaystyle X} and Y {\displaystyle 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 {\displaystyle A} . The function f ( x , y ) {\displaystyle f(x,y)} encodes the expected value of the payoff to the first player when the first player plays the strategy x {\displaystyle x} and the second player plays the strategy y {\displaystyle 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 ⊆ R n {\displaystyle X\subseteq \mathbb {R} ^{n}} and Y ⊆ R m {\displaystyle Y\subseteq \mathbb {R} ^{m}} be compact convex sets. If f : X × Y → R {\displaystyle f:X\times Y\rightarrow \mathbb {R} } is a continuous function that is concave-convex, i.e.

f ( ⋅ , y ) : X → R {\displaystyle f(\cdot ,y):X\to \mathbb {R} } is concave for every fixed y ∈ Y {\displaystyle y\in Y} , and f ( x , ⋅ ) : Y → R {\displaystyle f(x,\cdot ):Y\to \mathbb {R} } is convex for every fixed x ∈ X {\displaystyle x\in X} .

Then we have that

max x ∈ X min y ∈ Y f ( x , y ) = min y ∈ Y max x ∈ X f ( x , y ) . {\displaystyle \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,7 relaxing the requirement that X and Y be standard simplexes and that f be bilinear. It states:89

Let X {\displaystyle X} be a convex subset of a linear topological space and let Y {\displaystyle Y} be a compact convex subset of a linear topological space. If f {\displaystyle f} is a real-valued function on X × Y {\displaystyle X\times Y} with

f ( ⋅ , y ) {\displaystyle f(\cdot ,y)} upper semicontinuous and quasi-concave on X {\displaystyle X} , for every fixed y ∈ Y {\displaystyle y\in Y} , and f ( x , ⋅ ) {\displaystyle f(x,\cdot )} lower semicontinuous and quasi-convex on Y {\displaystyle Y} , for every fixed x ∈ X {\displaystyle x\in X} .

Then we have that

sup x ∈ X min y ∈ Y f ( x , y ) = min y ∈ Y sup x ∈ X f ( x , y ) . {\displaystyle \sup _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\sup _{x\in X}f(x,y).}

See also

References

  1. Simons, Stephen (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Minimax Theorems and Their Proofs", Minimax and Applications, Nonconvex Optimization and Its Applications, vol. 4, Boston, MA: Springer US, pp. 1–23, doi:10.1007/978-1-4613-3557-3_1, ISBN 978-1-4613-3557-3, retrieved 2024-10-27 978-1-4613-3557-3 ↩

  2. Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Math. Ann. 100: 295–320. doi:10.1007/BF01448847. S2CID 122961988. /wiki/Mathematische_Annalen ↩

  3. John L Casti (1996). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. p. 19. ISBN 978-0-471-00261-1. 978-0-471-00261-1 ↩

  4. Du, Ding-Zhu; Pardalos, Panos M., eds. (1995). Minimax and Applications. Boston, MA: Springer US. ISBN 9781461335573. 9781461335573 ↩

  5. Brandt, Felix; Brill, Markus; Suksompong, Warut (2016). "An ordinal minimax theorem". Games and Economic Behavior. 95: 107–112. arXiv:1412.4198. doi:10.1016/j.geb.2015.12.010. S2CID 360407. /wiki/ArXiv_(identifier) ↩

  6. Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Math. Ann. 100: 295–320. doi:10.1007/BF01448847. S2CID 122961988. /wiki/Mathematische_Annalen ↩

  7. Sion, Maurice (1958). "On general minimax theorems". Pacific Journal of Mathematics. 8 (1): 171–176. doi:10.2140/pjm.1958.8.171. MR 0097026. Zbl 0081.11502. https://doi.org/10.2140%2Fpjm.1958.8.171 ↩

  8. Sion, Maurice (1958). "On general minimax theorems". Pacific Journal of Mathematics. 8 (1): 171–176. doi:10.2140/pjm.1958.8.171. MR 0097026. Zbl 0081.11502. https://doi.org/10.2140%2Fpjm.1958.8.171 ↩

  9. Komiya, Hidetoshi (1988). "Elementary proof for Sion's minimax theorem". Kodai Mathematical Journal. 11 (1): 5–7. doi:10.2996/kmj/1138038812. MR 0930413. Zbl 0646.49004. http://projecteuclid.org/euclid.kmj/1138038812 ↩