In mathematics, the max–min inequality is as follows: :For any function

\ f : Z \times W \to \mathbb\ ,

\sup_ \inf_ f(z, w) \leq \inf_ \sup_ f(z, w)\ .

When equality holds one says that , , and satisfies a strong max–min property (or a

saddle-point In mathematics, a saddle point or minimax point is a point on the surface of the graph of a function where the slopes (derivatives) in orthogonal directions are all zero (a critical point), but which is not a local extremum of the functi ...

property). The example function

\ f(z,w) = \sin( z + w )\

illustrates that the equality does not hold for every function. A theorem giving conditions on , , and which guarantee the saddle point property is called a

minimax theorem 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 from 1928, which was c ...

Proof

Define

g(z) \triangleq \inf_ f(z, w)\ .

For all

z \in Z

, we get

g(z) \leq f(z, w)

for all

w \in W

by definition of the infimum being a lower bound. Next, for all

w \in W

f(z, w) \leq \sup_ f(z, w)

for all

z \in Z

by definition of the supremum being an upper bound. Thus, for all

z \in Z

and

w \in W

g(z) \leq f(z, w) \leq \sup_ f(z, w)

making

h(w) \triangleq \sup_ f(z, w)

an upper bound on

g(z)

for any choice of

w \in W

. Because the supremum is the least upper bound,

\sup_ g(z) \leq h(w)

holds for all

w \in W

. From this inequality, we also see that

\sup_ g(z)

is a lower bound on

h(w)

. By the greatest lower bound property of infimum,

\sup_ g(z) \leq \inf_ h(w)

. Putting all the pieces together, we get

\sup_ \inf_ f(z, w) = \sup_ g(z) \leq \inf_ h(w) \leq \inf_ \sup_ f(z, w)

which proves the desired inequality.

\blacksquare

Proof

References

See also