561
个编辑
更改
跳到导航
跳到搜索
第278行：
第278行： − + 第285行：
第285行： − + 第293行：
第293行： + 第306行：
第307行： − + − + − + 第322行：
第323行： − +
→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. 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 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 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.
第一个约束说明{{mvar|u}}向量的每个元素都必须是非负的，第二个约束要求{{mvar|M u}}向量的每个元素必须至少为1。对于得到的{{mvar|u}} 向量，其元素和的倒数就是博弈的值。将 {{mvar|u}}乘以这个值就得到了一个概率向量，给出了最大化的玩家选择每个可能的纯策略的概率。
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.
通过求解给定线性规划的对偶问题，可以找到最小化博弈者的均衡混合策略。或者，也可以通过使用上述过程来求解修正的支付矩阵，即 {{mvar|M}}的转置和否定（添加一个常数使其为正），然后求解结果博弈。
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}}
如果找到线性规划的所有解，它们将构成博弈的所有'''<font color="#ff8000"> 纳什均衡</font>'''。相反，任何线性程序都可以通过使用变量上述方程形式的变化，将其转换为两人零和博弈。所以，一般来说，这种游戏相当于线性程序。{{citation needed|date=October 2010}}
=== Universal solution ===
=== Universal solution ===