Editing Zero-sum game (section)

=== Solving ===

The [[Nash equilibrium]] for a two-player, zero-sum game can be found by solving a [[linear programming]] problem.  Suppose a zero-sum game has a payoff matrix {{mvar|M}} where element {{math|''M''{{sub|''i'',''j''}}}} is the payoff obtained when the minimizing player chooses pure strategy {{mvar|i}} and the maximizing player chooses pure strategy {{mvar|j}} (i.e. the player trying to minimize the payoff chooses the row and the player trying to maximize the payoff chooses the column).  Assume every element of {{mvar|M}} is positive.  The game will have at least one Nash equilibrium.  The Nash equilibrium can be found (Raghavan 1994, p.&nbsp;740) by solving the following linear program to find a vector {{mvar|u}}:

{{block indent|em=1.2|text= Minimize:
<math display="block">\sum_{i} u_i</math>
Subject to the constraints:
{{block indent|em=1.2|text={{math|''u'' ≥ 0}}}}
{{block indent|em=1.2|text={{math|''M&thinsp;u'' ≥ 1}}.}}}}

The first constraint says each element of the {{mvar|u}} vector must be nonnegative, and the second constraint says each element of the {{mvar|M&thinsp;u}} vector must be at least 1.  For the resulting {{mvar|u}} vector, the inverse of the sum of its elements is the value of the game.  Multiplying {{mvar|u}} by that value gives a probability vector, giving the probability that the maximizing player will choose each possible pure strategy.

If the game matrix does not have all positive elements, add a constant to every element that is large enough to make them all positive.  That will increase the value of the game by that constant, and will not affect the equilibrium mixed strategies for the equilibrium.

The equilibrium mixed strategy for the minimizing player can be found by solving the dual of the given linear program. Alternatively, it can be found by using the above procedure to solve a modified payoff matrix which is the transpose and negation of {{mvar|M}} (adding a constant so it is positive), then solving the resulting game.

If all the solutions to the linear program are found, they will constitute all the Nash equilibria for the game.  Conversely, any linear program can be converted into a two-player, zero-sum game by using a change of variables that puts it in the form of the above equations and thus such games are equivalent to linear programs, in general.<ref>Ilan Adler (2012) The equivalence of linear programs and zero-sum games. Springer</ref>