更改

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. 740) by solving the following linear program to find a vector {{mvar|u}}:

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. 740) by solving the following linear program to find a vector {{mvar|u}}:

一个两人零和博弈的[[纳什均衡]]可以通过求解一个[[线性规划]]问题得到。假设一个零和博弈有一个支付矩阵{mvar | M}}，其中元素{math | M'{sub |“i”，“j''}}}}是当最小化的玩家选择纯策略{mvar | i}}而最大化的玩家选择纯策略{mvar | j}}时获得的收益（即，试图最小化收益的玩家选择行，而试图最大化收益的玩家选择列）。假设{mvar | M}的每个元素都是正的。博弈至少有一个纳什均衡。纳什均衡可以通过求解以下线性规划找到向量{mvar | u}来找到（Raghavan 1994，p.740）：

一个两人零和博弈的[[纳什均衡]]可以通过求解一个[[线性规划]]问题得到。假设一个零和博弈有一个支付矩阵{{mvar|M}}，其中元素{{math|''M''{{sub|''i'',''j''}}}}是当最小化的玩家选择纯策略 {{mvar|i}}而最大化的玩家选择纯策略 {{mvar|j}} 时获得的收益（即，试图最小化收益的玩家选择行，而试图最大化收益的玩家选择列）。假设 {{mvar|M}}的每个元素都是正的。博弈至少有一个纳什均衡。纳什均衡可以通过求解以下线性规划找到向量 {{mvar|u}}来找到（Raghavan 1994，p.740）：

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

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

: Minimize:

: Minimize:

 

::: <math>\sum_{i} u_i</math>

::: <math>\sum_{i} u_i</math>

: Subject to the constraints:

: Subject to the constraints:

:: {{math|''u'' ≥ 0}}

:: {{math|''u'' ≥ 0}}

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 of the possible pure strategies.

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 of the possible pure strategies.

 

If the game matrix does not have all positive elements, simply 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 have no effect on the equilibrium mixed strategies for the equilibrium.

If the game matrix does not have all positive elements, simply 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 have no effect on 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.  Or, 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's positive), then solving the resulting game.

The equilibrium mixed strategy for the minimizing player can be found by solving the dual of the given linear program.  Or, 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's positive), then solving the resulting game.

 

The most common or simple example from the subfield of social psychology is the concept of "social traps". In some cases pursuing individual personal interest can enhance the collective well-being of the group, but in other situations all parties pursuing personal interest results in mutually destructive behavior.

The most common or simple example from the subfield of social psychology is the concept of "social traps". In some cases pursuing individual personal interest can enhance the collective well-being of the group, but in other situations all parties pursuing personal interest results in mutually destructive behavior.

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.  So such games are equivalent to linear programs, in general. {{citation needed|date=October 2010}}

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.  So such games are equivalent to linear programs, in general. {{citation needed|date=October 2010}}

 

=== Universal solution ===

=== Universal solution ===