Minimax theorem
Minimax theorem
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>. 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.
Bilinear functions and zero-sum games Von Neumann's original theorem relaxing the requirement that X and Y be standard simplexes and that f be bilinear. It states:
Let <math>X</math> be a convex subset of a linear topological space and let <math>Y</math> be a compact convex subset of a linear topological space. If <math>f</math> is a real-valued function on <math>X\times Y</math> with
: <math>f(\cdot,y)</math> upper semicontinuous and 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>