Proof of the Stable Solution Theorem
For a two player, zero sum game, a stable solution is one such that each player always plays the same, unchanging strategy. The Stable Solution Theorem states that there will only be a stable solution when the row maximum of the matrix representing the playoffs for one player equals the column minimum.
If the matrix represents the payoffs forof each combinations of strategies of each player, withandplayer A's and B's play safe winnings respectively, then
For any zero sum game,
A zero sum game has a stable solution if and only if
Prove 1 first. If both players play safe thenwins at leastandwins at leastso the total winnings are at leastbut in a zero sum game the total winnings are always zero so
Sinceis the row maximin there is a row in which the smallest element isIf the row is the kth row then playerwill be playing safe by playing strategySimilarlyis the column minimax, there is a column minimax, there is a column, say the lth, in which the largest entry isPlayerwill be playing safe by choosing strategy
The value of the game tois given by the elementin the matrix.sinceis the smallest number in rowandsinceis the biggest number in columnHence
buthencehenceandis then the smallest in rowand the biggest in column
Playerassumes that playerwill play strategyThere is no benefit toin changing strategy sincegives the biggest payoff toalso assumes thatwill play strategyThere is no benefit toin changing strategy sincegives the biggest payoff tosowill always play strategy l. The game is table andis the saddle point.
To prove the 'only if' part, note that if the game is stable there is a saddle point or possibly points that give the game's value. Since this is a zero sum game this must be equal and opposite for each player so