Minimax theorem explained

In the mathematical area of game theory, a minimax theorem is a theorem providing conditions that guarantee that the max–min inequality is also an equality. The first theorem in this sense is von Neumann's minimax theorem about zero-sum games published in 1928,^[1] which was 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".^[2] Since then, several generalizations and alternative versions of von Neumann's original theorem have appeared in the literature.^{[3] [4]} Formally, von Neumann's minimax theorem states:

Let

X \subset R ^{n} and Y \subset R ^{m} be compact convex sets. If f: X x Y → R is a continuous function that is concave-convex, i.e.f( ⋅ ,y): X \to R is concave for fixed y , andf(x, ⋅ ): Y \to R is convex for fixed x .

Then we have that

max _{x\in} min _{y\in} f(x,y) = min _{y\in} max _{x\in} f(x,y).

Special case: Bilinear function

The theorem holds in particular if

f(x,y) is a linear function in both of its arguments (and therefore is bilinear) since a linear function is both concave and convex. Thus, if f(x,y) = x ^{T} A y for a finite matrix A \in R ^{n} , we have:max _{x} min _{y} x ^{T} A y = min _{y} max _{x} x ^{T} A y. The bilinear special case is particularly important for zero-sum games, when the strategy set of each player consists of lotteries over actions (mixed strategies), and payoffs are induced by expected value. In the above formulation, A is the payoff matrix.

See also

• Sion's minimax theorem
• Parthasarathy's theorem - 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 minimax principle

Notes and References

1. Von Neumann . J. . 1928 . Zur Theorie der Gesellschaftsspiele . . 100 . 295–320 . 10.1007/BF01448847. 122961988 .
2. Book: John L Casti . Five golden rules: great theories of 20th-century mathematics – and why they matter . Wiley-Interscience . 1996 . 978-0-471-00261-1 . New York . 19 . registration.
3. Book: Du. Ding-Zhu. Pardalos. Panos M.. Minimax and Applications. 1995. Springer US. Boston, MA. 9781461335573.
4. Brandt. Felix. Brill. Markus. Suksompong. Warut. 2016. An ordinal minimax theorem. Games and Economic Behavior. 95. 107–112. 10.1016/j.geb.2015.12.010. 1412.4198. 360407 .