minimax inequality

The minimax inequality was first proved by John von Neumann. It is the starting point to discuss two-players zero-sum static games theoryMathworldPlanetmath.


For any mΓ—n matrix Ai,j, we have


(2)max1≀i≀m⁑min1≀j≀n⁑Ai,j=min1≀j≀n⁑max1≀i≀m⁑Ai,j if and only if Ai,j~≀Ai~,j~≀Ai~,jβ€ƒβ€…βˆ€i,j is valid for some (i~,j~)

For a 2 players zero-sum gameMathworldPlanetmath, the entries of Ai,j is interpreted as the payoff when player 1 has chosen the it⁒h strategy while player 2 has chosen the jt⁒h strategy. The value Ai~,j~ is known as the value of the game.

𝐏𝐫𝐨𝐨𝐟 Since min1≀j≀n⁑Ai,j≀max1≀i≀m⁑Ai,jβ€ƒβ€…βˆ€i,j. The LHS is independent of j while the RHS is independent of i, therefore we obtain max1≀i≀m⁑min1≀j≀n⁑Ai,j≀min1≀j≀n⁑max1≀i≀m⁑Ai,j


Let Sm={xβˆˆβ„m|xiβ‰₯0β’βˆ€i,βˆ‘i=1mxi=1}βŠ†β„m. For any mΓ—n matrix Ai,j, we have


Here 0≀xi≀1 is interpreted as the probability that Player 1 will choose strategy i while 0≀yj≀1 is the probability that Player 2 will choose strategy j.

𝐏𝐫𝐨𝐨𝐟 For any x∈Sm and any y∈Sn we have maxx∈Sm⁑miny∈Snβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yjβ‰€βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj

Taking maximum for x∈Sm on both sides, we have maxx∈Sm⁑minx∈Snβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj≀maxs∈Smβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj

Taking minimum for y∈Sn on both sides, we have v1=maxx∈Sm⁑miny∈Snβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj≀v2=miny∈Sn⁑maxx∈Smβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj

The prove of other half of the inequality takes two steps:

Step 1Suppose there is a y∈Sn such that βˆ‘j=1nAi,j⁒yj≀0 β‡’There is some x~∈Sm such that βˆ‘i=1m(βˆ‘j=1nAi,j⁒yj)⁒x~i≀0

β‡’maxx∈Snβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yj≀0 β‡’v2=miny∈Snmaxx∈Smβˆ‘i=1mβˆ‘j=1nAi,jxiyj≀0  (*1)

Step 2Suppose there is a x∈Sm such that βˆ‘i=1mAi,j⁒xi⁒yj>0 β‡’There is some y~∈Sn such that βˆ‘j=1n(βˆ‘i=1mAi,j⁒xi)⁒y~jβ‰₯0

β‡’miny∈Snβ’βˆ‘i=1mβˆ‘j=1nAi,j⁒xi⁒yjβ‰₯0 β‡’v1=maxx∈Smminy∈Snβˆ‘i=1mβˆ‘j=1nAi,jxiyjβ‰₯0  (*2)

Combining (*1) and (*2) we see that either 0≀v1 or v2≀0 is the case and v1<0<v2 cannot be valid. Repeat the same procedure to the matrix A~i,j=Ai,j-Ξ» and we see that v1-Ξ»<0<v2-Ξ» is invalid, i.e. v1<Ξ»<v2 is not valid for any Ξ». Since Ξ» is arbitrary, we conclude that v2≀v1.

An entire theory on minimax has already been developed and is one of the major research area in optimization theory. The following contains some good sources for further reference:


  • 1 V.F.DemyanovΒ andΒ V.N.Malozemov, Introduction to Minimax, Keter Publishing House Jerusalem Ltd, 1974.
Title minimax inequality
Canonical name MinimaxInequality
Date of creation 2013-03-22 16:57:16
Last modified on 2013-03-22 16:57:16
Owner bchui (10427)
Last modified by bchui (10427)
Numerical id 32
Author bchui (10427)
Entry type Theorem
Classification msc 91A99
Classification msc 91A05