纳什均衡

来自集智百科
跳到导航 跳到搜索

此词条暂由水流心不竞初译,未经审校,带来阅读不便,请见谅。

模板:简短说明

{{Infobox equilibrium

{{Infobox equilibrium

模板:Infobox equilibrium

}}

}}


In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.[1]

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

在博弈论中, 纳什均衡 Nash equilibrium是以数学家 约翰·福布斯·纳什 John Forbes Nash Jr.命名的博弈模型,是一种非合作博弈的解法,这个模型假定每个参与者都知道其他参与者的均衡策略,没有一个参与者仅仅通过改变自己的策略就能得到任何好处。[1]


If each player has chosen a strategy—an action plan choosing its own action based on what it has seen happen so far in the game—and no player can increase its own expected payoff by changing its strategy while the other players keep theirs unchanged, then the current set of strategy choices constitutes a Nash equilibrium.

If each player has chosen a strategy—an action plan choosing its own action based on what it has seen happen so far in the game—and no player can increase its own expected payoff by changing its strategy while the other players keep theirs unchanged, then the current set of strategy choices constitutes a Nash equilibrium.

如果每个玩家都选择了一个策略---- 一个根据游戏中所有已知信息选择行动的行动计划---- 并且没有玩家可以通过改变策略来提高自己的预期收益,而其他玩家则保持自己的策略不变,那么当前的一组策略选择就构成了一个 纳什均衡点


If two players Alice and Bob choose strategies A and B, (A, B) is a Nash equilibrium if Alice has no other strategy available that does better than A at maximizing her payoff in response to Bob choosing B, and Bob has no other strategy available that does better than B at maximizing his payoff in response to Alice choosing A. In a game in which Carol and Dan are also players, (A, B, C, D) is a Nash equilibrium if A is Alice's best response to (B, C, D), B is Bob's best response to (A, C, D), and so forth.

If two players Alice and Bob choose strategies A and B, (A, B) is a Nash equilibrium if Alice has no other strategy available that does better than A at maximizing her payoff in response to Bob choosing B, and Bob has no other strategy available that does better than B at maximizing his payoff in response to Alice choosing A. In a game in which Carol and Dan are also players, (A, B, C, D) is a Nash equilibrium if A is Alice's best response to (B, C, D), B is Bob's best response to (A, C, D), and so forth.

如果两个玩家 Alice 和 Bob 选择策略A 和 B,,如果 Bob 采取 B策略时Alice 没有比 A 更好的策略来增加回报,且Alice 采取 A策略时Bob 没有比 B 更好的策略来增加回报,那么(A, B) 是一个纳什均衡点 。在一个 Carol 和 Dan 也是玩家的游戏中,如果 A 是 Alice 对(B, C, D)的最佳对策,B 是 Bob 对(A, C, D)的最佳对策,那么(A, B, C, D)就是纳什均衡点,等等。


Nash showed that there is a Nash equilibrium for every finite game: see further the article on strategy.

Nash showed that there is a Nash equilibrium for every finite game: see further the article on strategy.

每一个有限的游戏都有一个纳什均衡点: 详见关于策略的文章。


Applications应用

Game theorists use Nash equilibrium to analyze the outcome of the strategic interaction of several decision makers. In a strategic interaction, the outcome for each decision-maker depends on the decisions of the others as well as their own. The simple insight underlying Nash's idea is that one cannot predict the choices of multiple decision makers if one analyzes those decisions in isolation. Instead, one must ask what each player would do taking into account what she/he expects the others to do. Nash equilibrium requires that their choices be consistent: no player wishes to undo their decision given what the others are deciding.

Game theorists use Nash equilibrium to analyze the outcome of the strategic interaction of several decision makers. In a strategic interaction, the outcome for each decision-maker depends on the decisions of the others as well as their own. The simple insight underlying Nash's idea is that one cannot predict the choices of multiple decision makers if one analyzes those decisions in isolation. Instead, one must ask what each player would do taking into account what she/he expects the others to do. Nash equilibrium requires that their choices be consistent: no player wishes to undo their decision given what the others are deciding.

博弈论专家使用纳什均衡点分析几个决策者战略互动的结果。在战略互动中,每个决策者的决策结果既取决于其他决策者的决策,也取决于他们自己的决策。纳什指出,如果一个人孤立地分析多个决策者的决策,那么他就无法预测多个决策者的选择。相反,玩家必须考虑到每个玩家期望博弈中的其他人做什么。 纳什均衡点需要他们的选择是一致的: 在已知其他人的决策时,没有玩家希望取消他们的决定。



The concept has been used to analyze hostile situations like wars and arms races[2] (see prisoner's dilemma), and also how conflict may be mitigated by repeated interaction (see tit-for-tat). It has also been used to study to what extent people with different preferences can cooperate (see battle of the sexes), and whether they will take risks to achieve a cooperative outcome (see stag hunt). It has been used to study the adoption of technical standards,[citation needed] and also the occurrence of bank runs and currency crises (see coordination game). Other applications include traffic flow (see Wardrop's principle), how to organize auctions (see auction theory), the outcome of efforts exerted by multiple parties in the education process,[3] regulatory legislation such as environmental regulations (see tragedy of the commons),[4] natural resource management,[5] analysing strategies in marketing,[6] even penalty kicks in football (see matching pennies),[7] energy systems, transportation systems, evacuation problems[8] and wireless communications.[9]

The concept has been used to analyze hostile situations like wars and arms races (see prisoner's dilemma), and also how conflict may be mitigated by repeated interaction (see tit-for-tat). It has also been used to study to what extent people with different preferences can cooperate (see battle of the sexes), and whether they will take risks to achieve a cooperative outcome (see stag hunt). It has been used to study the adoption of technical standards, and also the occurrence of bank runs and currency crises (see coordination game). Other applications include traffic flow (see Wardrop's principle), how to organize auctions (see auction theory), the outcome of efforts exerted by multiple parties in the education process, regulatory legislation such as environmental regulations (see tragedy of the commons), natural resource management, analysing strategies in marketing, even penalty kicks in football (see matching pennies), energy systems, transportation systems, evacuation problems and wireless communications.

这个概念已经被用来分析战争和军备竞赛等敌对情况[10](见囚徒困境) ,以及如何通过反复互动来缓和冲突(见以牙还牙)。它也被用来研究不同偏好的人可以在多大程度上合作,以及他们是否愿意冒一定的风险合作(见性别战)。它被用来研究怎样采用技术标准[citation needed],以及银行挤兑和[[Currency crisis|货币危机]如何发生(见协调博弈)。其他应用领域包括交通流量(见 Wardrop 原理) ,如何组织拍卖(见拍卖理论) ,教育过程中多方努力的结果[11],监管立法,如环境法规(见公地悲剧) ,自然资源管理[12],市场营销策略分析[13] ,甚至包括足球罚球(见匹配便士)[14] ,能源系统,交通系统,疏散问题[15] 和无线通信[16]


History历史

Nash equilibrium is named after American mathematician John Forbes Nash, Jr. The same idea was used in a particular application in 1838 by Antoine Augustin Cournot in his theory of oligopoly. In Cournot's theory, each of several firms choose how much output to produce to maximize its profit. The best output for one firm depends on the outputs of the others. A Cournot equilibrium occurs when each firm's output maximizes its profits given the output of the other firms, which is a pure-strategy Nash equilibrium. Cournot also introduced the concept of best response dynamics in his analysis of the stability of equilibrium. Cournot did not use the idea in any other applications, however, or define it generally.

纳什均衡点是以美国数学家John Forbes Nash Jr.命名的。1838年, 安托万·奥古斯丁·库尔诺特Antoine Augustin Cournot在他的寡头垄断理论[17]中使用了同样的思想。根据 Cournot 的理论,几家公司中的每一家都致力于实现利润最大化。一个公司的最佳决策取决于其他公司的产出情况。给定其他企业的产出情况,若企业实现利益最大化,则达到了Cournot均衡,这是一个pure-strategy的纳什均衡点。Cournot还在其均衡稳定性分析中引入了最佳响应动力学的概念。然而,Cournot并没有在其他任何应用程序中使用这个概念,或者给出一般性定义。

Nash equilibrium is named after American mathematician John Forbes Nash, Jr. The same idea was used in a particular application in 1838 by Antoine Augustin Cournot in his theory of oligopoly.[18] In Cournot's theory, each of several firms choose how much output to produce to maximize its profit. The best output for one firm depends on the outputs of the others. A Cournot equilibrium occurs when each firm's output maximizes its profits given the output of the other firms, which is a pure-strategy Nash equilibrium. Cournot also introduced the concept of best response dynamics in his analysis of the stability of equilibrium. Cournot did not use the idea in any other applications, however, or define it generally.


The modern game-theoretic concept of Nash equilibrium is instead defined in terms of mixed strategies, where players choose a probability distribution over possible actions (rather than choosing a deterministic action to be played with certainty). The concept of a mixed-strategy equilibrium was introduced by John von Neumann and Oskar Morgenstern in their 1944 book The Theory of Games and Economic Behavior. However, their analysis was restricted to the special case of zero-sum games. They showed that a mixed-strategy Nash equilibrium will exist for any zero-sum game with a finite set of actions. The contribution of Nash in his 1951 article "Non-Cooperative Games" was to define a mixed-strategy Nash equilibrium for any game with a finite set of actions and prove that at least one (mixed-strategy) Nash equilibrium must exist in such a game. The key to Nash's ability to prove existence far more generally than von Neumann lay in his definition of equilibrium. According to Nash, "an equilibrium point is an n-tuple such that each player's mixed strategy maximizes his payoff if the strategies of the others are held fixed. Thus each player's strategy is optimal against those of the others." Just putting the problem in this framework allowed Nash to employ the Kakutani fixed-point theorem in his 1950 paper, and a variant upon it in his 1951 paper used the Brouwer fixed-point theorem to prove that there had to exist at least one mixed strategy profile that mapped back into itself for finite-player (not necessarily zero-sum) games; namely, a strategy profile that did not call for a shift in strategies that could improve payoffs.

现代博弈理论中,纳什均衡点是用mixed strategies来定义的,玩家在选择的是行为的概率分布(而不是选择一个确定性的行动)。混合策略均衡的概念是由John von NeumannOskar Morgenstern在他们1944年出版的《博弈论与经济行为》一书中提出的。然而,他们的分析仅限于零和博弈的特殊情况。他们证明了一个混合策略的纳什均衡点对于任何零和博弈都是存在的。纳什在1951年的文章《非合作博弈》中定义了一个混合策略纳什均衡点,并证明了在这样的博弈中至少存在一个混合策略纳什均衡点。与冯 · 诺依曼相比,纳什能够更广泛地证明存在性的关键在于他对均衡的定义。按照 Nash 的说法,“一个平衡点是一个 n 元组,如果其他参与人的策略保持不变,那么每个参与人的混合策略使他的收益最大化。因此,每个玩家的策略都是相对于其他玩家的最优策略。”仅仅把这个问题放在这个框架中,Nash 就可以在他1950年的论文中使用角谷静夫不动点定理模型,在他1951年的论文中使用布劳威尔不动点定理模型来证明至少存在一个混合策略模型,这个模型可以映射回有限参与人(不一定是零和游戏)的博弈中,也就是说,一个策略模型不要求改变可以提高收益的策略。

The modern game-theoretic concept of Nash equilibrium is instead defined in terms of mixed strategies, where players choose a probability distribution over possible actions (rather than choosing a deterministic action to be played with certainty). The concept of a mixed-strategy equilibrium was introduced by John von Neumann and Oskar Morgenstern in their 1944 book The Theory of Games and Economic Behavior. However, their analysis was restricted to the special case of zero-sum games. They showed that a mixed-strategy Nash equilibrium will exist for any zero-sum game with a finite set of actions.[19] The contribution of Nash in his 1951 article "Non-Cooperative Games" was to define a mixed-strategy Nash equilibrium for any game with a finite set of actions and prove that at least one (mixed-strategy) Nash equilibrium must exist in such a game. The key to Nash's ability to prove existence far more generally than von Neumann lay in his definition of equilibrium. According to Nash, "an equilibrium point is an n-tuple such that each player's mixed strategy maximizes his payoff if the strategies of the others are held fixed. Thus each player's strategy is optimal against those of the others." Just putting the problem in this framework allowed Nash to employ the Kakutani fixed-point theorem in his 1950 paper, and a variant upon it in his 1951 paper used the Brouwer fixed-point theorem to prove that there had to exist at least one mixed strategy profile that mapped back into itself for finite-player (not necessarily zero-sum) games; namely, a strategy profile that did not call for a shift in strategies that could improve payoffs.[20]


Since the development of the Nash equilibrium concept, game theorists have discovered that it makes misleading predictions (or fails to make a unique prediction) in certain circumstances. They have proposed many related solution concepts (also called 'refinements' of Nash equilibria) designed to overcome perceived flaws in the Nash concept. One particularly important issue is that some Nash equilibria may be based on threats that are not 'credible'. In 1965 Reinhard Selten proposed subgame perfect equilibrium as a refinement that eliminates equilibria which depend on non-credible threats. Other extensions of the Nash equilibrium concept have addressed what happens if a game is repeated, or what happens if a game is played in the absence of complete information. However, subsequent refinements and extensions of Nash equilibrium share the main insight on which Nash's concept rests: the equilibrium is a set of strategies such that each player's strategy is optimal given the choices of the others.

随着纳什均衡点概念的发展,博弈论者发现它在某些情况下会做出误导性的预测(或者不能做出独特的预测)。他们提出了许多相关的解决方案概念(也称为纳什均衡的“精炼”) ,旨在克服纳什概念中的缺陷。一个特别重要的问题是,某些纳什均衡可能是基于不可信的威胁。1965年 Reinhard Selten 提出了一种改进的 子博弈精炼均衡Subgame perfect equilibrium,它消除了依赖于非可信威胁的均衡。纳什均衡点概念的其他扩展解决了如果一个游戏重复发生了什么,或者如果一个游戏在没有完整信息的情况下发生了什么。然而,随后对纳什均衡点的改进和扩展共享了纳什概念所依赖的主要洞察力: 均衡是一组策略,这样每个参与者的策略在其他人的选择下都是最优的。

Since the development of the Nash equilibrium concept, game theorists have discovered that it makes misleading predictions (or fails to make a unique prediction) in certain circumstances. They have proposed many related solution concepts (also called 'refinements' of Nash equilibria) designed to overcome perceived flaws in the Nash concept. One particularly important issue is that some Nash equilibria may be based on threats that are not 'credible'. In 1965 Reinhard Selten proposed subgame perfect equilibrium as a refinement that eliminates equilibria which depend on non-credible threats. Other extensions of the Nash equilibrium concept have addressed what happens if a game is repeated, or what happens if a game is played in the absence of complete information. However, subsequent refinements and extensions of Nash equilibrium share the main insight on which Nash's concept rests: the equilibrium is a set of strategies such that each player's strategy is optimal given the choices of the others.


Definitions定义

Nash Equilibrium纳什均衡

Informally, a strategy profile is a Nash equilibrium if no player can do better by unilaterally changing their strategy. To see what this means, imagine that each player is told the strategies of the others. Suppose then that each player asks themselves: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, can I benefit by changing my strategy?"

非正式地说,如果没有参与者能够单方面改变他们的策略,那么策略配置文件就是一个 纳什均衡点。要理解这意味着什么,想象一下,每个玩家都被告知其他玩家的策略。然后假设每个玩家都问自己: “知道其他玩家的策略,并且把其他玩家的策略当作一成不变的东西,我能通过改变策略而受益吗? ”

Informally, a strategy profile is a Nash equilibrium if no player can do better by unilaterally changing their strategy. To see what this means, imagine that each player is told the strategies of the others. Suppose then that each player asks themselves: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, can I benefit by changing my strategy?"


If any player could answer "Yes", then that set of strategies is not a Nash equilibrium. But if every player prefers not to switch (or is indifferent between switching and not) then the strategy profile is a Nash equilibrium. Thus, each strategy in a Nash equilibrium is a best response to all other strategies in that equilibrium.

如果任何一个玩家都能回答“是” ,那么这套策略就不是 纳什均衡点。但是如果每个玩家都不愿意切换(或者对切换和不切换无所谓) ,那么这个策略就是一个纳什均衡点。因此,纳什均衡点中的每个策略都是对均衡中所有其他策略的最佳回应。

If any player could answer "Yes", then that set of strategies is not a Nash equilibrium. But if every player prefers not to switch (or is indifferent between switching and not) then the strategy profile is a Nash equilibrium. Thus, each strategy in a Nash equilibrium is a best response to all other strategies in that equilibrium.[21]


The Nash equilibrium may sometimes appear non-rational in a third-person perspective. This is because a Nash equilibrium is not necessarily Pareto optimal.

从第三人称的角度来看,纳什均衡点有时可能显得非理性。这是因为 纳什均衡点不一定是 帕累托最优的。

The Nash equilibrium may sometimes appear non-rational in a third-person perspective. This is because a Nash equilibrium is not necessarily Pareto optimal.


The Nash equilibrium may also have non-rational consequences in sequential games because players may "threaten" each other with non-rational moves. For such games the subgame perfect Nash equilibrium may be more meaningful as a tool of analysis.

纳什均衡点在连续博弈中也可能产生非理性的后果,因为玩家可能会用非理性的举动“威胁”彼此。对于这样的游戏来说,子游戏的完美纳什均衡点作为分析工具可能更有意义。

The Nash equilibrium may also have non-rational consequences in sequential games because players may "threaten" each other with non-rational moves. For such games the subgame perfect Nash equilibrium may be more meaningful as a tool of analysis.


Strict/Weak Equilibrium 严格/弱平衡

Suppose that in the Nash equilibrium, each player asks themselves: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, would I suffer a loss by changing my strategy?"

假设在纳什均衡点游戏中,每个玩家都会问自己: “如果知道其他玩家的策略,并且把其他玩家的策略当作一成不变的东西,我会因为改变策略而遭受损失吗? ”

Suppose that in the Nash equilibrium, each player asks themselves: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, would I suffer a loss by changing my strategy?"


If every player's answer is "Yes", then the equilibrium is classified as a strict Nash equilibrium.

如果每个参与者的答案都是肯定的,那么这个均衡就被划分为一个严格的纳什均衡点。

If every player's answer is "Yes", then the equilibrium is classified as a strict Nash equilibrium.[22]


If instead, for some player, there is exact equality between the strategy in Nash equilibrium and some other strategy that gives exactly the same payout (i.e. this player is indifferent between switching and not), then the equilibrium is classified as a weak Nash equilibrium.

如果相反,对于某些玩家来说,纳什均衡点的策略和其他策略给出的回报完全相同(例如:。这个参与人在切换和不切换之间是无关紧要的) ,那么这个均衡被划分为弱纳什均衡点。

If instead, for some player, there is exact equality between the strategy in Nash equilibrium and some other strategy that gives exactly the same payout (i.e. this player is indifferent between switching and not), then the equilibrium is classified as a weak Nash equilibrium.


A game can have a pure-strategy or a mixed-strategy Nash equilibrium. (In the latter a pure strategy is chosen stochastically with a fixed probability).

一个游戏可以有纯策略或者混合策略的纳什均衡点。(在后一种情况下,为随机选择一个具有固定概率的纯策略)。

A game can have a pure-strategy or a mixed-strategy Nash equilibrium. (In the latter a pure strategy is chosen stochastically with a fixed probability).


Nash's Existence Theorem纳什存在定理

Nash proved that if we allow mixed strategies (where a player chooses probabilities of using various pure strategies), then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium (which might be a pure strategy for each player or might be a probability distribution over strategies for each player).

纳什证明,如果我们允许混合策略(参与者选择使用各种纯策略的概率) ,那么每个参与者数量有限且每个参与者可以从有限多个纯策略中选择的博弈都至少有一个纳什均衡点(这可能是每个参与者的纯策略,也可能是每个参与者的纯策略概率分布)。

Nash proved that if we allow mixed strategies (where a player chooses probabilities of using various pure strategies), then every game with a finite number of players in which each player can choose from finitely many pure strategies has at least one Nash equilibrium (which might be a pure strategy for each player or might be a probability distribution over strategies for each player).


Nash equilibria need not exist if the set of choices is infinite and noncompact. An example is a game where two players simultaneously name a number and the player naming the larger number wins. Another example is where each of two players chooses a real number strictly less than 5 and the winner is whoever has the biggest number; no biggest number strictly less than 5 exists (if the number could equal 5, the Nash equilibrium would have both players choosing 5 and tying the game). However, a Nash equilibrium exists if the set of choices is compact with each player's payoff continuous in the strategies of all the players. An example, in which the equilibrium is a mixture of continuously many pure strategies, is a game where two players simultaneously pick a real number between 0 and 1 (inclusive) and player one's winnings (paid by the second player) equal the square root of the distance between the two numbers.

如果选择集是无限的和非紧凑的,那么纳什均衡就不存在。一个例子是一个游戏,两个玩家同时说出一个数字,而说出较大数字的玩家获胜。另一个例子是,每个玩家选择一个实数严格小于5的数字,获胜者是拥有最大数字的人; 没有严格小于5的最大数字存在(如果数字可以等于5,纳什均衡点将有两个玩家选择5并平局)。然而,如果所有参与者的策略中,每个参与者的选择集与每个参与者的收益紧密相关,则存在一个纳什均衡点。一个例子,其中的均衡是连续的许多纯策略的混合物,是一个博弈,其中两个玩家同时选择一个介于0和1之间的实数(包括在内) ,并且玩家一的奖金(由第二个玩家支付)等于两个数字之间距离的平方根。

Nash equilibria need not exist if the set of choices is infinite and noncompact. An example is a game where two players simultaneously name a number and the player naming the larger number wins. Another example is where each of two players chooses a real number strictly less than 5 and the winner is whoever has the biggest number; no biggest number strictly less than 5 exists (if the number could equal 5, the Nash equilibrium would have both players choosing 5 and tying the game). However, a Nash equilibrium exists if the set of choices is compact with each player's payoff continuous in the strategies of all the players.[23] An example, in which the equilibrium is a mixture of continuously many pure strategies, is a game where two players simultaneously pick a real number between 0 and 1 (inclusive) and player one's winnings (paid by the second player) equal the square root of the distance between the two numbers.


Examples 样例

Coordination game 协调博弈


{ | align = right border = “1” cellpadding = “4” cellspacing = “0” style = “ margin: 1em 1em 1em 1em 1em; background: # f9f9f9; border: 1px # solid; border-collapse: collapse; font-size: 95% ; class = “ wikable”
A sample coordination game showing relative payoff for player 1 (row) / player 2 (column) with each combination
一个样本协调博弈,显示每个组合对参与人1(行)/参与人2(列)的相对收益
A sample coordination game showing relative payoff for player 1 (row) / player 2 (column) with each combination
模板:Diagonal split header Player 2 adopts strategy A Player 2采用策略 a Player 2 adopts strategy A Player 2 adopts strategy B Player 2采用策略 b Player 2 adopts strategy B
Player 1 adopts strategy A Player 1采用策略 a Player 1 adopts strategy A 模板:Diagonal split header 模板:Diagonal split header
Player 1 adopts strategy B 参与人1采用策略 b Player 1 adopts strategy B 模板:Diagonal split header 模板:Diagonal split header

|}


The coordination game is a classic (symmetric) two player, two strategy game, with an example payoff matrix shown to the right. The players should thus coordinate, both adopting strategy A, to receive the highest payoff; i.e., 4. If both players chose strategy B though, there is still a Nash equilibrium. Although each player is awarded less than optimal payoff, neither player has incentive to change strategy due to a reduction in the immediate payoff (from 2 to 1).

协调博弈是一个经典的(对称的)两个参与人、两个策略的博弈,右边显示了一个支付矩阵的例子。因此,参与者应该协调,都采用策略 A,以获得最高的回报,也就是说,4。如果两个玩家都选择了 B 策略,那么仍然有一个纳什均衡点。虽然每个参与人的回报都低于最优回报,但是由于直接回报减少(从2减少到1) ,两个参与人都没有改变策略的动机。

The coordination game is a classic (symmetric) two player, two strategy game, with an example payoff matrix shown to the right. The players should thus coordinate, both adopting strategy A, to receive the highest payoff; i.e., 4. If both players chose strategy B though, there is still a Nash equilibrium. Although each player is awarded less than optimal payoff, neither player has incentive to change strategy due to a reduction in the immediate payoff (from 2 to 1).


A famous example of this type of game was called the stag hunt; in the game two players may choose to hunt a stag or a rabbit, the former providing more meat (4 utility units) than the latter (1 utility unit). The caveat is that the stag must be cooperatively hunted, so if one player attempts to hunt the stag, while the other hunts the rabbit, she/he will fail in hunting (0 utility units), whereas if they both hunt it they will split the payoff (2, 2). The game hence exhibits two equilibria at (stag, stag) and (rabbit, rabbit) and hence the players' optimal strategy depend on their expectation on what the other player may do. If one hunter trusts that the other will hunt the stag, they should hunt the stag; however if they suspect that the other will hunt the rabbit, they should hunt the rabbit. This game was used as an analogy for social cooperation, since much of the benefit that people gain in society depends upon people cooperating and implicitly trusting one another to act in a manner corresponding with cooperation.

这类游戏的一个著名的例子是猎鹿,在游戏中,两个玩家可以选择猎鹿或猎兔,前者提供比后者更多的肉(4个实用单位)(1个实用单位)。需要注意的是,这只鹿必须被合作猎杀,所以如果一个参与者试图猎杀鹿,而另一个参与者猎杀兔子,她/他将在猎杀中失败(0个实用单位) ,而如果他们都猎杀鹿,他们将分享收益(2,2)。这个博弈因此展现了两个均衡(雄鹿,雄鹿)和(兔子,兔子) ,因此玩家的最佳策略取决于他们对另一个玩家可能做什么的期望。如果一个猎人相信另一个会猎鹿,他们就应该猎鹿; 但是如果他们怀疑另一个会猎兔,他们就应该猎兔。这种游戏被用来作为社会合作的类比,因为人们在社会中获得的大部分利益取决于人们之间的合作和相互间的隐性信任,以与合作相对应的方式行事。

A famous example of this type of game was called the stag hunt; in the game two players may choose to hunt a stag or a rabbit, the former providing more meat (4 utility units) than the latter (1 utility unit). The caveat is that the stag must be cooperatively hunted, so if one player attempts to hunt the stag, while the other hunts the rabbit, she/he will fail in hunting (0 utility units), whereas if they both hunt it they will split the payoff (2, 2). The game hence exhibits two equilibria at (stag, stag) and (rabbit, rabbit) and hence the players' optimal strategy depend on their expectation on what the other player may do. If one hunter trusts that the other will hunt the stag, they should hunt the stag; however if they suspect that the other will hunt the rabbit, they should hunt the rabbit. This game was used as an analogy for social cooperation, since much of the benefit that people gain in society depends upon people cooperating and implicitly trusting one another to act in a manner corresponding with cooperation.


Another example of a coordination game is the setting where two technologies are available to two firms with comparable products, and they have to elect a strategy to become the market standard. If both firms agree on the chosen technology, high sales are expected for both firms. If the firms do not agree on the standard technology, few sales result. Both strategies are Nash equilibria of the game.

协调博弈的另一个例子是这样一种情况,两个拥有类似产品的公司可以获得两种技术,他们必须选择一种策略来成为市场标准。如果两家公司都同意所选择的技术,那么两家公司的销售额都会很高。如果公司不同意标准技术,销售结果很少。这两个策略都是博弈的纳什均衡。

Another example of a coordination game is the setting where two technologies are available to two firms with comparable products, and they have to elect a strategy to become the market standard. If both firms agree on the chosen technology, high sales are expected for both firms. If the firms do not agree on the standard technology, few sales result. Both strategies are Nash equilibria of the game.


Driving on a road against an oncoming car, and having to choose either to swerve on the left or to swerve on the right of the road, is also a coordination game. For example, with payoffs 10 meaning no crash and 0 meaning a crash, the coordination game can be defined with the following payoff matrix:

在道路上面对迎面而来的车辆行驶,必须在左侧转弯或在右侧转弯之间做出选择,这也是一个协调博弈。例如,收益为10意味着没有崩溃,0意味着崩溃,协调博弈可以用下面的收益矩阵来定义:

Driving on a road against an oncoming car, and having to choose either to swerve on the left or to swerve on the right of the road, is also a coordination game. For example, with payoffs 10 meaning no crash and 0 meaning a crash, the coordination game can be defined with the following payoff matrix:


{ | align = left border = “1” cellpadding = “4” cellspacing = “0” style = “ margin: 1em 1em 1em 1em 1em; background: # f9f9f9; border: 1px # solid; border-collapse: collapse; font-size: 95% ” class = “ wikable”
The driving game
The driving game
The driving game
模板:Diagonal split header Drive on the Left 左边开车 Drive on the Left Drive on the Right 向右开车 Drive on the Right
Drive on the Left 左边开车 Drive on the Left 模板:Diagonal split header 模板:Diagonal split header
Drive on the Right 向右开车 Drive on the Right 模板:Diagonal split header 模板:Diagonal split header

|}


In this case there are two pure-strategy Nash equilibria, when both choose to either drive on the left or on the right. If we admit mixed strategies (where a pure strategy is chosen at random, subject to some fixed probability), then there are three Nash equilibria for the same case: two we have seen from the pure-strategy form, where the probabilities are (0%, 100%) for player one, (0%, 100%) for player two; and (100%, 0%) for player one, (100%, 0%) for player two respectively. We add another where the probabilities for each player are (50%, 50%).

在这种情况下,存在两个纯策略纳什均衡,当两者都选择左侧或右侧驱动时。如果我们承认混合策略(在某些固定的概率下,纯策略是随机选择的) ,那么对于同样的情况有三个纳什均衡: 我们从纯策略形式中看到的两个纳什均衡,其中参与人一的概率为(0% ,100%) ,参与人二的概率为(0% ,100%) ; 参与人一的概率为(100% ,0%) ,参与人二的概率分别为(100% ,0%)。我们在每个玩家的概率是(50% ,50%)的情况下再加一个。

In this case there are two pure-strategy Nash equilibria, when both choose to either drive on the left or on the right. If we admit mixed strategies (where a pure strategy is chosen at random, subject to some fixed probability), then there are three Nash equilibria for the same case: two we have seen from the pure-strategy form, where the probabilities are (0%, 100%) for player one, (0%, 100%) for player two; and (100%, 0%) for player one, (100%, 0%) for player two respectively. We add another where the probabilities for each player are (50%, 50%).


模板:Clear left


Prisoner's dilemma 囚徒困境

{ | align = right border = “1” cellpadding = “4” cellspacing = “0” style = “ margin: 1em 1em 1em 1em 1em; background: # f9f9f9; border: 1px # solid; border-collapse: collapse; font-size: 95% ; text-align: center = “ wikable”
Example PD payoff matrix
示例 PD 支付矩阵
Example PD payoff matrix
模板:Diagonal split header Cooperate (with other) (与其他人)合作 Cooperate (with other) Defect (betray other) Defect (背叛他人) Defect (betray other)
Cooperate (with other) 合作(与其他人) Cooperate (with other) −1, −1 −1, −1 −1, −1 −3, 0 −3, 0 −3, 0
Defect (betray other) Defect (背叛他人) Defect (betray other) 0, −3 0, −3 0, −3 −2, −2 −2, −2 −2, −2

|}

Imagine two prisoners held in separate cells, interrogated simultaneously, and offered deals (lighter jail sentences) for betraying their fellow criminal. They can "cooperate" (with the other prisoner) by not snitching, or "defect" by betraying the other. However, there is a catch; if both players defect, then they both serve a longer sentence than if neither said anything. Lower jail sentences are interpreted as higher payoffs (shown in the table).

想象一下,两个犯人被关在不同的牢房里,同时接受审讯,并且提出交易(减轻刑罚) ,因为他们背叛了自己的同伙。他们可以通过不告密来“合作”(与其他囚犯合作) ,或者通过背叛其他囚犯来“叛逃”。然而,这里有一个陷阱: 如果两个球员都叛变了,那么他们服刑的时间都会比双方都不说话的时间要长。较低的监禁刑罚被解释为较高的回报(如表所示)。

Imagine two prisoners held in separate cells, interrogated simultaneously, and offered deals (lighter jail sentences) for betraying their fellow criminal. They can "cooperate" (with the other prisoner) by not snitching, or "defect" by betraying the other. However, there is a catch; if both players defect, then they both serve a longer sentence than if neither said anything. Lower jail sentences are interpreted as higher payoffs (shown in the table).


The prisoner's dilemma has a similar matrix as depicted for the coordination game, but the maximum reward for each player (in this case, a minimum loss of 0) is obtained only when the players' decisions are different. Each player improves their own situation by switching from "cooperating" to "defecting", given knowledge that the other player's best decision is to "defect". The prisoner's dilemma thus has a single Nash equilibrium: both players choosing to defect.

囚徒困境Prisoner's dilemma具有与协调博弈相似的矩阵,但是只有当参与者的决策不同时,每个参与者的最大报酬(在这种情况下,最小损失为0)才能得到。每个玩家通过从“合作”到“叛逃”来改善自己的处境,因为他们知道另一个玩家的最佳决定是“叛逃”。因此,囚徒困境只有一个纳什均衡点: 双方都选择叛逃。

The prisoner's dilemma has a similar matrix as depicted for the coordination game, but the maximum reward for each player (in this case, a minimum loss of 0) is obtained only when the players' decisions are different. Each player improves their own situation by switching from "cooperating" to "defecting", given knowledge that the other player's best decision is to "defect". The prisoner's dilemma thus has a single Nash equilibrium: both players choosing to defect.


What has long made this an interesting case to study is the fact that this scenario is globally inferior to "both cooperating". That is, both players would be better off if they both chose to "cooperate" instead of both choosing to defect. However, each player could improve their own situation by breaking the mutual cooperation, no matter how the other player possibly (or certainly) changes their decision.

长期以来使这一情况成为值得研究的有趣案例的原因是,这种情况在全球范围内不如”双方合作”。也就是说,如果双方都选择“合作” ,而不是双方都选择背叛,那么双方都会过得更好。然而,每个玩家都可以通过打破相互合作来改善自己的处境,不管其他玩家可能(或肯定)如何改变他们的决定。

What has long made this an interesting case to study is the fact that this scenario is globally inferior to "both cooperating". That is, both players would be better off if they both chose to "cooperate" instead of both choosing to defect. However, each player could improve their own situation by breaking the mutual cooperation, no matter how the other player possibly (or certainly) changes their decision.


Network traffic 网络流量

Sample network graph. Values on edges are the travel time experienced by a 'car' traveling down that edge. is the number of cars traveling via that edge.

网络图示例。边缘上的值是一辆汽车沿着边缘行驶所经历的行驶时间。就是经过那个边缘的车辆数量。

文件:Nash graph equilibrium.png
Sample network graph. Values on edges are the travel time experienced by a 'car' traveling down that edge. x is the number of cars traveling via that edge.

thumb | 250px |网络图示例。边缘上的值是“汽车”沿该边缘行驶所经历的行驶时间。x 是通过该边缘行驶的汽车数量。

An application of Nash equilibria is in determining the expected flow of traffic in a network. Consider the graph on the right. If we assume that there are "cars" traveling from A to D, what is the expected distribution of traffic in the network?

纳什均衡的一个应用是确定网络中的预期流量。看看右边的图表。如果我们假设有从 a 到 d 的“汽车” ,网络中预期的流量分布是什么?

An application of Nash equilibria is in determining the expected flow of traffic in a network. Consider the graph on the right. If we assume that there are x "cars" traveling from A to D, what is the expected distribution of traffic in the network?


This situation can be modeled as a "game" where every traveler has a choice of 3 strategies, where each strategy is a route from A to D (either , , or ). The "payoff" of each strategy is the travel time of each route. In the graph on the right, a car travelling via experiences travel time of , where is the number of cars traveling on edge . Thus, payoffs for any given strategy depend on the choices of the other players, as is usual. However, the goal, in this case, is to minimize travel time, not maximize it. Equilibrium will occur when the time on all paths is exactly the same. When that happens, no single driver has any incentive to switch routes, since it can only add to their travel time. For the graph on the right, if, for example, 100 cars are travelling from A to D, then equilibrium will occur when 25 drivers travel via , 50 via , and 25 via . Every driver now has a total travel time of 3.75 (to see this, note that a total of 75 cars take the edge, and likewise, 75 cars take the edge).

这种情况可以被模拟为一个“游戏” ,每个旅行者都有3个策略可供选择,每个策略都是从 A 到 D 的路线(或者,或者)。每个策略的“回报”是每条路线的行程时间。在右边的图表中,一辆汽车经历的旅行时间是,哪里是在边上旅行的汽车的数量。因此,任何给定策略的收益都取决于其他参与者的选择,这是很正常的。然而,在这种情况下,目标是最小化旅行时间,而不是最大化。当所有路径上的时间完全相同时,平衡就会出现。当这种情况发生时,没有一个司机有任何动机改变路线,因为这只能增加他们的旅行时间。对于右边的图表,如果,例如,100辆汽车从 A 到 D,那么平衡将发生在25个司机经过,50个经过,和25个经过。现在,每个司机的总旅行时间为3.75(注意,总共有75辆车占据优势,同样,75辆车占据优势)。<!——25名司机使用 ABD,50名司机使用 ABCD,因此75辆汽车行驶在 AB 边缘。同样,75辆汽车行驶在边缘 CD 上。通过 ABD 旅行需要(1 + 75/100) + 2 = 3.75。其他路线的行程时间是相同的。-->

This situation can be modeled as a "game" where every traveler has a choice of 3 strategies, where each strategy is a route from A to D (either ABD, ABCD, or ACD). The "payoff" of each strategy is the travel time of each route. In the graph on the right, a car travelling via ABD experiences travel time of (1+x/100)+2, where x is the number of cars traveling on edge AB. Thus, payoffs for any given strategy depend on the choices of the other players, as is usual. However, the goal, in this case, is to minimize travel time, not maximize it. Equilibrium will occur when the time on all paths is exactly the same. When that happens, no single driver has any incentive to switch routes, since it can only add to their travel time. For the graph on the right, if, for example, 100 cars are travelling from A to D, then equilibrium will occur when 25 drivers travel via ABD, 50 via ABCD, and 25 via ACD. Every driver now has a total travel time of 3.75 (to see this, note that a total of 75 cars take the AB edge, and likewise, 75 cars take the CD edge).


Notice that this distribution is not, actually, socially optimal. If the 100 cars agreed that 50 travel via and the other 50 through , then travel time for any single car would actually be 3.5, which is less than 3.75. This is also the Nash equilibrium if the path between B and C is removed, which means that adding another possible route can decrease the efficiency of the system, a phenomenon known as Braess's paradox.

注意,这种分布实际上并不是社会最优的。如果100辆车同意50辆经过,其他50辆经过,那么任何一辆车的旅行时间实际上是3.5,小于3.75。如果 b 和 c 之间的路径被移除,这也是纳什均衡点,这意味着增加另一条可能的路径会降低系统的效率,这种现象被称为 Braess 悖论。

Notice that this distribution is not, actually, socially optimal. If the 100 cars agreed that 50 travel via ABD and the other 50 through ACD, then travel time for any single car would actually be 3.5, which is less than 3.75. This is also the Nash equilibrium if the path between B and C is removed, which means that adding another possible route can decrease the efficiency of the system, a phenomenon known as Braess's paradox.


Competition game 竞赛游戏

{ | align = right border = “1” cellpadding = “1” cellspacing = “0” style = “ margin: 1em 1em 1em 1em 1em; background: # f9f9f9; border: 1px # solid; border-collapse: collapse; font-size: 95% ; class = “ wikable”
A competition game
a competition game
A competition game
模板:Diagonal split header Choose '0' 选择「0」 Choose '0' Choose '1' 选择「1」 Choose '1' Choose '2' 选择「2」 Choose '2' Choose '3' 选择“3” Choose '3'
Choose '0' 选择「0」 Choose '0' 0, 0 0,0 0, 0 2, −2 2, −2 2, −2 2, −2 2, −2 2, −2 2, −2 2, −2 2, −2
Choose '1' 选择「1」 Choose '1' −2, 2 −2, 2 −2, 2 1, 1

1,1

1, 1 3, −1 3, −1 3, −1 3, −1 3, −1 3, −1
Choose '2' 选择「2」 Choose '2' −2, 2 −2, 2 −2, 2 −1, 3 −1, 3 −1, 3 2, 2 2,2 2, 2 4, 0

4,0

4, 0
Choose '3' 选择“3” Choose '3' −2, 2 −2, 2 −2, 2 −1, 3 −1, 3 −1, 3 0, 4

0,4

0, 4 3, 3

3,3

3, 3

|}


This can be illustrated by a two-player game in which both players simultaneously choose an integer from 0 to 3 and they both win the smaller of the two numbers in points. In addition, if one player chooses a larger number than the other, then they have to give up two points to the other.

这可以用一个两人游戏来说明,在这个游戏中,两个玩家同时选择一个从0到3的整数,并且他们都赢得两个数字中较小的一个点。另外,如果一个玩家选择了一个比另一个更大的数字,那么他们必须放弃两分给另一个。

This can be illustrated by a two-player game in which both players simultaneously choose an integer from 0 to 3 and they both win the smaller of the two numbers in points. In addition, if one player chooses a larger number than the other, then they have to give up two points to the other.


This game has a unique pure-strategy Nash equilibrium: both players choosing 0 (highlighted in light red). Any other strategy can be improved by a player switching their number to one less than that of the other player. In the adjacent table, if the game begins at the green square, it is in player 1's interest to move to the purple square and it is in player 2's interest to move to the blue square. Although it would not fit the definition of a competition game, if the game is modified so that the two players win the named amount if they both choose the same number, and otherwise win nothing, then there are 4 Nash equilibria: (0,0), (1,1), (2,2), and (3,3).

这个游戏有一个独特的纯策略纳什均衡点: 两个玩家都选择0(用淡红色突出显示)。任何其他的策略都可以通过一个玩家把他们的数字换成比另一个玩家更小的数字来改进。在相邻的桌子上,如果游戏从绿色的方块开始,那么参与人1的兴趣转移到紫色的方块上,参与人2的兴趣转移到蓝色的方块上。虽然它不符合竞争博弈的定义,但是如果对博弈进行修改,使得两个参与者在选择相同数字的情况下都赢得指定的金额,那么就有4个纳什均衡: (0,0) ,(1,1) ,(2,2)和(3,3)。

This game has a unique pure-strategy Nash equilibrium: both players choosing 0 (highlighted in light red). Any other strategy can be improved by a player switching their number to one less than that of the other player. In the adjacent table, if the game begins at the green square, it is in player 1's interest to move to the purple square and it is in player 2's interest to move to the blue square. Although it would not fit the definition of a competition game, if the game is modified so that the two players win the named amount if they both choose the same number, and otherwise win nothing, then there are 4 Nash equilibria: (0,0), (1,1), (2,2), and (3,3).


Nash equilibria in a payoff matrix 收益矩阵中的纳什均衡

There is an easy numerical way to identify Nash equilibria on a payoff matrix. It is especially helpful in two-person games where players have more than two strategies. In this case formal analysis may become too long. This rule does not apply to the case where mixed (stochastic) strategies are of interest. The rule goes as follows: if the first payoff number, in the payoff pair of the cell, is the maximum of the column of the cell and if the second number is the maximum of the row of the cell - then the cell represents a Nash equilibrium.

有一种简单的数值方法可以确定支付矩阵中的纳什均衡。在双人游戏中,如果玩家有两个以上的策略,这种方法尤其有用。在这种情况下,正式的分析可能会变得太长。这个规则不适用于混合(随机)策略有利益的情况。规则是这样的: 如果单元格的支付对中的第一个支付数是该单元格列的最大值,如果第二个支付数是该单元格行的最大值,那么该单元格表示一个纳什均衡点。

There is an easy numerical way to identify Nash equilibria on a payoff matrix. It is especially helpful in two-person games where players have more than two strategies. In this case formal analysis may become too long. This rule does not apply to the case where mixed (stochastic) strategies are of interest. The rule goes as follows: if the first payoff number, in the payoff pair of the cell, is the maximum of the column of the cell and if the second number is the maximum of the row of the cell - then the cell represents a Nash equilibrium.


{ | align = “ left” border = “1” cellpadding = “4” cellspacing = “0” style = “ margin: 1em; background: # f9f9f9; border: 1px # aaa solid; border-collapse: collapse; font-size: 95% ; class = “ wikable”
A payoff matrix – Nash equilibria in bold
一个回报矩阵-纳什均衡用粗体表示
A payoff matrix – Nash equilibria in bold
模板:Diagonal split header Option A 选项 a Option A Option B 选项 b Option B Option C 选项 c Option C
Option A 选项 a Option A 0, 0

0,0

0, 0 25, 40

25,40

25, 40 5, 10

5,10

5, 10
Option B 选项 b Option B 40, 25

40,25

40, 25 0, 0

0,0

0, 0 5, 15

5,15

5, 15
Option C 选项 c Option C 10, 5

10,5

10, 5 15, 5

15,5

15, 5 10, 10

10,10

10, 10

|}


We can apply this rule to a 3×3 matrix:

我们可以把这个规则应用到3 × 3矩阵上:

We can apply this rule to a 3×3 matrix:


Using the rule, we can very quickly (much faster than with formal analysis) see that the Nash equilibria cells are (B,A), (A,B), and (C,C). Indeed, for cell (B,A) 40 is the maximum of the first column and 25 is the maximum of the second row. For (A,B) 25 is the maximum of the second column and 40 is the maximum of the first row. Same for cell (C,C). For other cells, either one or both of the duplet members are not the maximum of the corresponding rows and columns.

使用这个规则,我们可以很快(比正式分析快得多)看到纳什均衡细胞是(B,A), (A,B), 和 (C,C)。实际上,对于单元格(B,A)40是第一列的最大值,25是第二行的最大值。对于(A,B)25是第二列的最大值,40是第一行的最大值。单元格(C,C)也是如此。对于其他单元格,一个或两个 duplet 成员都不是相应行和列的最大值。

Using the rule, we can very quickly (much faster than with formal analysis) see that the Nash equilibria cells are (B,A), (A,B), and (C,C). Indeed, for cell (B,A) 40 is the maximum of the first column and 25 is the maximum of the second row. For (A,B) 25 is the maximum of the second column and 40 is the maximum of the first row. Same for cell (C,C). For other cells, either one or both of the duplet members are not the maximum of the corresponding rows and columns.


This said, the actual mechanics of finding equilibrium cells is obvious: find the maximum of a column and check if the second member of the pair is the maximum of the row. If these conditions are met, the cell represents a Nash equilibrium. Check all columns this way to find all NE cells. An N×N matrix may have between 0 and N×N pure-strategy Nash equilibria.

也就是说,找到平衡单元的实际机制是显而易见的: 找到一列的最大值,然后检查一对单元的第二个成员是否是行的最大值。如果满足这些条件,则该细胞表示一个纳什均衡点。检查所有列这种方式,找到所有的 NE 细胞。一个 n × n 矩阵可能存在0到 n × n 纯策略纳什均衡。

This said, the actual mechanics of finding equilibrium cells is obvious: find the maximum of a column and check if the second member of the pair is the maximum of the row. If these conditions are met, the cell represents a Nash equilibrium. Check all columns this way to find all NE cells. An N×N matrix may have between 0 and N×N pure-strategy Nash equilibria.



< ! -- 宽屏布局修正 -- >


Stability 稳定性

The concept of stability, useful in the analysis of many kinds of equilibria, can also be applied to Nash equilibria.

稳定性的概念在分析多种平衡时很有用,也可以应用到纳什均衡中。

The concept of stability, useful in the analysis of many kinds of equilibria, can also be applied to Nash equilibria.


A Nash equilibrium for a mixed-strategy game is stable if a small change (specifically, an infinitesimal change) in probabilities for one player leads to a situation where two conditions hold:

一个混合策略博弈的纳什均衡点是稳定的,如果一个玩家的概率发生了微小的变化(具体地说,是极小的变化) ,导致出现两种情况:

A Nash equilibrium for a mixed-strategy game is stable if a small change (specifically, an infinitesimal change) in probabilities for one player leads to a situation where two conditions hold:


the player who did not change has no better strategy in the new circumstance

没有改变的玩家在新环境下没有更好的策略

  1. the player who did not change has no better strategy in the new circumstance
the player who did change is now playing with a strictly worse strategy.

那个改变了的玩家,现在采用了一个更糟糕的策略。

  1. the player who did change is now playing with a strictly worse strategy.


If these cases are both met, then a player with the small change in their mixed strategy will return immediately to the Nash equilibrium. The equilibrium is said to be stable. If condition one does not hold then the equilibrium is unstable. If only condition one holds then there are likely to be an infinite number of optimal strategies for the player who changed.

如果这两种情况都满足,那么在混合策略中稍有变化的玩家将立即返回纳什均衡点。这种平衡称为稳定的。如果条件一不成立,那么平衡就是不稳定的。如果只有一个条件成立,那么对于改变策略的玩家来说,可能存在无限多的最优策略。

If these cases are both met, then a player with the small change in their mixed strategy will return immediately to the Nash equilibrium. The equilibrium is said to be stable. If condition one does not hold then the equilibrium is unstable. If only condition one holds then there are likely to be an infinite number of optimal strategies for the player who changed.


In the "driving game" example above there are both stable and unstable equilibria. The equilibria involving mixed strategies with 100% probabilities are stable. If either player changes their probabilities slightly, they will be both at a disadvantage, and their opponent will have no reason to change their strategy in turn. The (50%,50%) equilibrium is unstable. If either player changes their probabilities (which would neither benefit or damage the expectation of the player who did the change, if the other player's mixed strategy is still (50%,50%)), then the other player immediately has a better strategy at either (0%, 100%) or (100%, 0%).

在上面的“驱动博弈”的例子中,既有稳定的均衡,也有不稳定的均衡。含有100% 概率的混合策略的均衡是稳定的。如果任何一个玩家稍微改变他们的概率,他们都将处于劣势,而他们的对手将没有理由依次改变他们的策略。(50% ,50%)平衡是不稳定的。如果任何一个玩家改变了他们的概率(这既不会有利于也不会损害改变策略的玩家的期望值,如果另一个玩家的混合策略仍然是(50% ,50%) ,那么另一个玩家立即有一个更好的策略在(0% ,100%)或(100% ,0%)。

In the "driving game" example above there are both stable and unstable equilibria. The equilibria involving mixed strategies with 100% probabilities are stable. If either player changes their probabilities slightly, they will be both at a disadvantage, and their opponent will have no reason to change their strategy in turn. The (50%,50%) equilibrium is unstable. If either player changes their probabilities (which would neither benefit or damage the expectation of the player who did the change, if the other player's mixed strategy is still (50%,50%)), then the other player immediately has a better strategy at either (0%, 100%) or (100%, 0%).


Stability is crucial in practical applications of Nash equilibria, since the mixed strategy of each player is not perfectly known, but has to be inferred from statistical distribution of their actions in the game. In this case unstable equilibria are very unlikely to arise in practice, since any minute change in the proportions of each strategy seen will lead to a change in strategy and the breakdown of the equilibrium.

稳定性在纳什均衡的实际应用中是至关重要的,因为每个参与者的混合策略并不是完全知道的,而是必须从他们在博弈中行为的统计分布中推断出来的。在这种情况下,实际上不太可能出现不稳定均衡,因为看到的每种策略的比例的任何微小变化都会导致策略的变化和均衡的崩溃。

Stability is crucial in practical applications of Nash equilibria, since the mixed strategy of each player is not perfectly known, but has to be inferred from statistical distribution of their actions in the game. In this case unstable equilibria are very unlikely to arise in practice, since any minute change in the proportions of each strategy seen will lead to a change in strategy and the breakdown of the equilibrium.


The Nash equilibrium defines stability only in terms of unilateral deviations. In cooperative games such a concept is not convincing enough. Strong Nash equilibrium allows for deviations by every conceivable coalition. Formally, a strong Nash equilibrium is a Nash equilibrium in which no coalition, taking the actions of its complements as given, can cooperatively deviate in a way that benefits all of its members. However, the strong Nash concept is sometimes perceived as too "strong" in that the environment allows for unlimited private communication. In fact, strong Nash equilibrium has to be Pareto efficient. As a result of these requirements, strong Nash is too rare to be useful in many branches of game theory. However, in games such as elections with many more players than possible outcomes, it can be more common than a stable equilibrium.

纳什均衡点货币基金组织仅仅用单边偏离来定义稳定性。在合作博弈中,这样的概念是不够令人信服的。强大的纳什均衡点可以允许任何可以想象的联盟出现偏差。从形式上讲,强大的纳什均衡点是一种纳什均衡点,在这种情况下,任何联盟都不能合作地偏离对其所有成员都有利的方向,按照给定的补充行事。然而,强大的纳什概念有时被认为过于“强大” ,因为环境允许无限的私人交流。事实上,强纳什均衡点必须是帕累托有效的。由于这些要求的结果,强纳什在博弈论的许多分支中实在是太稀有了。然而,在诸如选举这样的游戏中,参与者比可能的结果多得多,这种情况可能比稳定的均衡更常见。

The Nash equilibrium defines stability only in terms of unilateral deviations. In cooperative games such a concept is not convincing enough. Strong Nash equilibrium allows for deviations by every conceivable coalition.[24] Formally, a strong Nash equilibrium is a Nash equilibrium in which no coalition, taking the actions of its complements as given, can cooperatively deviate in a way that benefits all of its members.[25] However, the strong Nash concept is sometimes perceived as too "strong" in that the environment allows for unlimited private communication. In fact, strong Nash equilibrium has to be Pareto efficient. As a result of these requirements, strong Nash is too rare to be useful in many branches of game theory. However, in games such as elections with many more players than possible outcomes, it can be more common than a stable equilibrium.


A refined Nash equilibrium known as coalition-proof Nash equilibrium (CPNE) Further, it is possible for a game to have a Nash equilibrium that is resilient against coalitions less than a specified size, k. CPNE is related to the theory of the core.

另外,对于一个游戏来说,有可能有一个对小于一定规模的联盟具有弹性的纳什均衡点,这个纳什均衡点与核心理论有关。

A refined Nash equilibrium known as coalition-proof Nash equilibrium (CPNE)[24] occurs when players cannot do better even if they are allowed to communicate and make "self-enforcing" agreement to deviate. Every correlated strategy supported by iterated strict dominance and on the Pareto frontier is a CPNE.[26] Further, it is possible for a game to have a Nash equilibrium that is resilient against coalitions less than a specified size, k. CPNE is related to the theory of the core.


Finally in the eighties, building with great depth on such ideas Mertens-stable equilibria were introduced as a solution concept. Mertens stable equilibria satisfy both forward induction and backward induction. In a game theory context stable equilibria now usually refer to Mertens stable equilibria.

最后,在八十年代,作为解决方案的概念,引入了对这种思想进行深入研究的 mertens 稳定平衡。默顿斯稳定平衡同时满足正向归纳和逆向归纳法。在博弈论中,稳定均衡现在通常指的是 Mertens 稳定均衡。

Finally in the eighties, building with great depth on such ideas Mertens-stable equilibria were introduced as a solution concept. Mertens stable equilibria satisfy both forward induction and backward induction. In a game theory context stable equilibria now usually refer to Mertens stable equilibria.


Occurrence发生

If a game has a unique Nash equilibrium and is played among players under certain conditions, then the NE strategy set will be adopted. Sufficient conditions to guarantee that the Nash equilibrium is played are:

如果一个游戏有一个唯一的纳什均衡点,并且在一定条件下在玩家之间进行,那么将采用 NE 策略集。足够的条件,以保证纳什均衡点比赛是:

If a game has a unique Nash equilibrium and is played among players under certain conditions, then the NE strategy set will be adopted. Sufficient conditions to guarantee that the Nash equilibrium is played are:

The players all will do their utmost to maximize their expected payoff as described by the game.

所有的玩家都会按照游戏所描述的那样,尽最大努力最大化他们的预期收益。

  1. The players all will do their utmost to maximize their expected payoff as described by the game.
The players are flawless in execution.

玩家们的执行力完美无瑕。

  1. The players are flawless in execution.
The players have sufficient intelligence to deduce the solution.

玩家们有足够的智慧来推断出解决方案。

  1. The players have sufficient intelligence to deduce the solution.
The players know the planned equilibrium strategy of all of the other players.

玩家知道所有其他玩家的计划均衡策略。

  1. The players know the planned equilibrium strategy of all of the other players.
The players believe that a deviation in their own strategy will not cause deviations by any other players.

玩家相信他们自己策略的偏差不会引起其他玩家的偏差。

  1. The players believe that a deviation in their own strategy will not cause deviations by any other players.
There is common knowledge that all players meet these conditions, including this one. So, not only must each player know the other players meet the conditions, but also they must know that they all know that they meet them, and know that they know that they know that they meet them, and so on.

众所周知,所有的球员都满足这些条件,包括这个条件。因此,每个玩家不仅必须知道其他玩家满足条件,而且还必须知道他们都知道他们满足条件,知道他们知道他们满足条件,等等。

  1. There is common knowledge that all players meet these conditions, including this one. So, not only must each player know the other players meet the conditions, but also they must know that they all know that they meet them, and know that they know that they know that they meet them, and so on.


Where the conditions are not met 当条件无法满足

Examples of game theory problems in which these conditions are not met:

不符合这些条件的博弈论问题的例子:

Examples of game theory problems in which these conditions are not met:

The first condition is not met if the game does not correctly describe the quantities a player wishes to maximize. In this case there is no particular reason for that player to adopt an equilibrium strategy. For instance, the prisoner's dilemma is not a dilemma if either player is happy to be jailed indefinitely.

如果博弈没有正确地描述玩家希望最大化的数量,则不满足第一个条件。在这种情况下,该参与人没有特别的理由采取均衡策略。例如,囚徒困境不是一个进退两难的问题,如果任何一方都乐意无限期地被监禁。

  1. The first condition is not met if the game does not correctly describe the quantities a player wishes to maximize. In this case there is no particular reason for that player to adopt an equilibrium strategy. For instance, the prisoner's dilemma is not a dilemma if either player is happy to be jailed indefinitely.
Intentional or accidental imperfection in execution. For example, a computer capable of flawless logical play facing a second flawless computer will result in equilibrium. Introduction of imperfection will lead to its disruption either through loss to the player who makes the mistake, or through negation of the common knowledge criterion leading to possible victory for the player. (An example would be a player suddenly putting the car into reverse in the game of chicken, ensuring a no-loss no-win scenario).

执行中有意或偶然的缺陷。例如,一台能够完美逻辑运算的计算机面对第二台完美逻辑运算的计算机,将会达到平衡。缺陷的引入将导致其中断,或者造成犯错的玩家的损失,或者通过否定常识标准导致玩家可能的胜利。(举个例子,一个玩家突然把车倒进了鸡肉游戏,以确保不亏不赢的局面)。

  1. Intentional or accidental imperfection in execution. For example, a computer capable of flawless logical play facing a second flawless computer will result in equilibrium. Introduction of imperfection will lead to its disruption either through loss to the player who makes the mistake, or through negation of the common knowledge criterion leading to possible victory for the player. (An example would be a player suddenly putting the car into reverse in the game of chicken, ensuring a no-loss no-win scenario).
In many cases, the third condition is not met because, even though the equilibrium must exist, it is unknown due to the complexity of the game, for instance in Chinese chess. Or, if known, it may not be known to all players, as when playing tic-tac-toe with a small child who desperately wants to win (meeting the other criteria).

在许多情况下,第三个条件是不能满足的,因为即使均衡必须存在,但由于博弈的复杂性,它是未知的,例如在中国象棋中。或者,如果知道的话,也许不是所有的玩家都知道,比如和一个非常想赢的小孩玩井字游戏(符合其他标准)。

  1. In many cases, the third condition is not met because, even though the equilibrium must exist, it is unknown due to the complexity of the game, for instance in Chinese chess.[27] Or, if known, it may not be known to all players, as when playing tic-tac-toe with a small child who desperately wants to win (meeting the other criteria).
The criterion of common knowledge may not be met even if all players do, in fact, meet all the other criteria. Players wrongly distrusting each other's rationality may adopt counter-strategies to expected irrational play on their opponents’ behalf. This is a major consideration in "chicken" or an arms race, for example.

即使所有参与者事实上都符合所有其他标准,也可能不符合共同知识的标准。玩家错误地不信任对方的理性,可能会采取反策略,代表对方期待非理性的游戏。例如,在“鸡肉”或军备竞赛中,这是一个主要的考虑因素。

  1. The criterion of common knowledge may not be met even if all players do, in fact, meet all the other criteria. Players wrongly distrusting each other's rationality may adopt counter-strategies to expected irrational play on their opponents’ behalf. This is a major consideration in "chicken" or an arms race, for example.


Where the conditions are met 当条件满足

In his Ph.D. dissertation, John Nash proposed two interpretations of his equilibrium concept, with the objective of showing how equilibrium points

在他的博士论文中,约翰 · 纳什对他的平衡概念提出了两种解释,目的是展示平衡点是如何达到的

In his Ph.D. dissertation, John Nash proposed two interpretations of his equilibrium concept, with the objective of showing how equilibrium points


/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

A second interpretation, that Nash referred to by the mass action interpretation, is less demanding on players:

第二种解释,也就是纳什提到的群众动作解释,对玩家要求较低:

A second interpretation, that Nash referred to by the mass action interpretation, is less demanding on players:


/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

For a formal result along these lines, see Kuhn, H. and et al., 1996, "The Work of John Nash in Game Theory," Journal of Economic Theory, 69, 153–185.

关于这些方面的正式结果,参见 Kuhn,h. 和等人,1996,“约翰 · 纳什在博弈论中的工作” ,《经济理论杂志》 ,69,153-185。

For a formal result along these lines, see Kuhn, H. and et al., 1996, "The Work of John Nash in Game Theory," Journal of Economic Theory, 69, 153–185.


Due to the limited conditions in which NE can actually be observed, they are rarely treated as a guide to day-to-day behaviour, or observed in practice in human negotiations. However, as a theoretical concept in economics and evolutionary biology, the NE has explanatory power. The payoff in economics is utility (or sometimes money), and in evolutionary biology is gene transmission; both are the fundamental bottom line of survival. Researchers who apply games theory in these fields claim that strategies failing to maximize these for whatever reason will be competed out of the market or environment, which are ascribed the ability to test all strategies. This conclusion is drawn from the "stability" theory above. In these situations the assumption that the strategy observed is actually a NE has often been borne out by research.

由于能够实际观察到 NE 的条件有限,它们很少被当作日常行为的指南,或在人类谈判实践中被观察到。然而,作为经济学和进化生物学中的一个理论概念,NE 具有解释力。经济学的回报是效用(有时是金钱) ,而进化生物学的回报是基因传递; 两者都是生存的基本底线。将博弈论应用于这些领域的研究人员声称,无论出于什么原因,未能最大化这些策略都会在市场或环境之外竞争,因为市场或环境具有测试所有策略的能力。这个结论是从上面的“稳定性”理论得出的。在这些情况下,研究经常证实所观察到的策略实际上是一个 NE 的假设。

Due to the limited conditions in which NE can actually be observed, they are rarely treated as a guide to day-to-day behaviour, or observed in practice in human negotiations. However, as a theoretical concept in economics and evolutionary biology, the NE has explanatory power. The payoff in economics is utility (or sometimes money), and in evolutionary biology is gene transmission; both are the fundamental bottom line of survival. Researchers who apply games theory in these fields claim that strategies failing to maximize these for whatever reason will be competed out of the market or environment, which are ascribed the ability to test all strategies. This conclusion is drawn from the "stability" theory above. In these situations the assumption that the strategy observed is actually a NE has often been borne out by research.[28]


NE and non-credible threats NE(纳什均衡)与不可信的威胁

Extensive and Normal form illustrations that show the difference between SPNE and other NE. The blue equilibrium is not subgame perfect because player two makes a non-credible threat at 2(2) to be unkind (U).

广泛的和范式插图显示了 SPNE 和其他 NE 的区别。蓝色均衡不是子博弈完美的,因为玩家二在2(2)时做出不可信的威胁是不友善的(u)。

文件:SGPNEandPlainNE explainingexample.svg
Extensive and Normal form illustrations that show the difference between SPNE and other NE. The blue equilibrium is not subgame perfect because player two makes a non-credible threat at 2(2) to be unkind (U).

The Nash equilibrium is a superset of the subgame perfect Nash equilibrium. The subgame perfect equilibrium in addition to the Nash equilibrium requires that the strategy also is a Nash equilibrium in every subgame of that game. This eliminates all non-credible threats, that is, strategies that contain non-rational moves in order to make the counter-player change their strategy.

纳什均衡点是子游戏完美纳什均衡点的超集。美国子博弈精炼纳什均衡联盟和纳什均衡点联盟都要求这个战略在游戏的每个子游戏中都是一个纳什均衡点。这消除了所有不可信的威胁,也就是说,包含非理性举动的策略,以使对手改变他们的策略。

The Nash equilibrium is a superset of the subgame perfect Nash equilibrium. The subgame perfect equilibrium in addition to the Nash equilibrium requires that the strategy also is a Nash equilibrium in every subgame of that game. This eliminates all non-credible threats, that is, strategies that contain non-rational moves in order to make the counter-player change their strategy.


The image to the right shows a simple sequential game that illustrates the issue with subgame imperfect Nash equilibria. In this game player one chooses left(L) or right(R), which is followed by player two being called upon to be kind (K) or unkind (U) to player one, However, player two only stands to gain from being unkind if player one goes left. If player one goes right the rational player two would de facto be kind to her/him in that subgame. However, The non-credible threat of being unkind at 2(2) is still part of the blue (L, (U,U)) Nash equilibrium. Therefore, if rational behavior can be expected by both parties the subgame perfect Nash equilibrium may be a more meaningful solution concept when such dynamic inconsistencies arise.

右边的图片展示了一个简单的序贯博弈,说明了子博弈不完美纳什均衡的问题。在这个游戏中,一个玩家选择左(l)或右(r) ,然后二号玩家被要求对一号玩家友好(k)或不友好(u) ,然而,二号玩家只能从不友好中获益,如果一号玩家选择左。如果参与人一向右,理性参与人二在子博弈中实际上对她/他很友好。然而,2(2)这个不可信的不友好的威胁仍然是蓝色(l,(u,u))纳什均衡点的一部分。因此,如果双方都能预期到理性行为,那么当这种动态不一致性出现时,子博弈完美纳什均衡点可能是一个更有意义的解决方案概念。

The image to the right shows a simple sequential game that illustrates the issue with subgame imperfect Nash equilibria. In this game player one chooses left(L) or right(R), which is followed by player two being called upon to be kind (K) or unkind (U) to player one, However, player two only stands to gain from being unkind if player one goes left. If player one goes right the rational player two would de facto be kind to her/him in that subgame. However, The non-credible threat of being unkind at 2(2) is still part of the blue (L, (U,U)) Nash equilibrium. Therefore, if rational behavior can be expected by both parties the subgame perfect Nash equilibrium may be a more meaningful solution concept when such dynamic inconsistencies arise.


Proof of existence存在的证明

Proof using the Kakutani fixed-point theorem Kakutani不动点定理的证明

Nash's original proof (in his thesis) used Brouwer's fixed-point theorem (e.g., see below for a variant). We give a simpler proof via the Kakutani fixed-point theorem, following Nash's 1950 paper (he credits David Gale with the observation that such a simplification is possible).

Nash 的原始证明(在他的论文中)使用了 Brouwer 的不动点定理。在1950年 Nash 的论文之后,我们通过角谷静夫不动点定理给出了一个更简单的证明(他相信 David Gale 的观察,这样的简化是可能的)。

Nash's original proof (in his thesis) used Brouwer's fixed-point theorem (e.g., see below for a variant). We give a simpler proof via the Kakutani fixed-point theorem, following Nash's 1950 paper (he credits David Gale with the observation that such a simplification is possible).


To prove the existence of a Nash equilibrium, let [math]\displaystyle{ r_i(\sigma_{-i}) }[/math] be the best response of player i to the strategies of all other players.

为了证明纳什均衡点的存在性,让参与人 i 对所有其他参与人的策略做出最佳反应。

To prove the existence of a Nash equilibrium, let [math]\displaystyle{ r_i(\sigma_{-i}) }[/math] be the best response of player i to the strategies of all other players.

[math]\displaystyle{ r_i(\sigma_{-i}) = \mathop{\underset{\sigma_i}{\operatorname{arg\,max}}} u_i (\sigma_i,\sigma_{-i}) }[/math]

= mathop { underset { sigma _ i }{ operatorname { arg,max } u _ i (sigma _ i,sigma _ {-i }) </math >

[math]\displaystyle{ r_i(\sigma_{-i}) = \mathop{\underset{\sigma_i}{\operatorname{arg\,max}}} u_i (\sigma_i,\sigma_{-i}) }[/math]


Here, [math]\displaystyle{ \sigma \in \Sigma }[/math], where [math]\displaystyle{ \Sigma = \Sigma_i \times \Sigma_{-i} }[/math], is a mixed-strategy profile in the set of all mixed strategies and [math]\displaystyle{ u_i }[/math] is the payoff function for player i. Define a set-valued function [math]\displaystyle{ r\colon \Sigma \rightarrow 2^\Sigma }[/math] such that [math]\displaystyle{ r = r_i(\sigma_{-i})\times r_{-i}(\sigma_{i}) }[/math]. The existence of a Nash equilibrium is equivalent to [math]\displaystyle{ r }[/math] having a fixed point.

这里,Sigma </math > Sigma </math > ,其中 < math > Sigma = Sigma _ i 乘以 Sigma _ i } </math > ,是所有混合策略集合中的混合策略轮廓,< math > u _ i </math > 是参与人 i 的收益函数。定义一个集值函数 < math > r colon Sigma right tarrow 2 ^ Sigma </math > 使得 < math > r = r _ i (Sigma _ i })乘以 r _ {-i }(Sigma _ { i }) </math > 。纳什均衡点的存在相当于有一个不动点。

Here, [math]\displaystyle{ \sigma \in \Sigma }[/math], where [math]\displaystyle{ \Sigma = \Sigma_i \times \Sigma_{-i} }[/math], is a mixed-strategy profile in the set of all mixed strategies and [math]\displaystyle{ u_i }[/math] is the payoff function for player i. Define a set-valued function [math]\displaystyle{ r\colon \Sigma \rightarrow 2^\Sigma }[/math] such that [math]\displaystyle{ r = r_i(\sigma_{-i})\times r_{-i}(\sigma_{i}) }[/math]. The existence of a Nash equilibrium is equivalent to [math]\displaystyle{ r }[/math] having a fixed point.


Kakutani's fixed point theorem guarantees the existence of a fixed point if the following four conditions are satisfied.

如果满足以下四个条件,则 Kakutani 不动点定理保证了不动点的存在性。

Kakutani's fixed point theorem guarantees the existence of a fixed point if the following four conditions are satisfied.

[math]\displaystyle{  \Sigma }[/math] is compact, convex, and nonempty.

是紧凑的,凸的,非空的。

  1. [math]\displaystyle{ \Sigma }[/math] is compact, convex, and nonempty.
[math]\displaystyle{ r(\sigma) }[/math] is nonempty.

不是空的。

  1. [math]\displaystyle{ r(\sigma) }[/math] is nonempty.
[math]\displaystyle{ r(\sigma) }[/math] is upper hemicontinuous

是上半连续的

  1. [math]\displaystyle{ r(\sigma) }[/math] is upper hemicontinuous
[math]\displaystyle{ r(\sigma) }[/math] is convex.

数学是凸的。

  1. [math]\displaystyle{ r(\sigma) }[/math] is convex.


Condition 1. is satisfied from the fact that [math]\displaystyle{ \Sigma }[/math] is a simplex and thus compact. Convexity follows from players' ability to mix strategies. [math]\displaystyle{ \Sigma }[/math] is nonempty as long as players have strategies.

条件1. 满足 < math > Sigma </math > 是一个单形,因此是紧凑的。凸性取决于玩家混合策略的能力。只要玩家有策略,σ </math > 就不是空的。

Condition 1. is satisfied from the fact that [math]\displaystyle{ \Sigma }[/math] is a simplex and thus compact. Convexity follows from players' ability to mix strategies. [math]\displaystyle{ \Sigma }[/math] is nonempty as long as players have strategies.


Condition 2. and 3. are satisfied by way of Berge's maximum theorem. Because [math]\displaystyle{ u_i }[/math] is continuous and compact, [math]\displaystyle{ r(\sigma_i) }[/math] is non-empty and upper hemicontinuous.

条件2和3通过 Berge 最大值定理得到了满足。因为 < math > u _ i </math > 是连续的和紧凑的,< math > r (sigma _ i) </math > 是非空的和上半连续的。

Condition 2. and 3. are satisfied by way of Berge's maximum theorem. Because [math]\displaystyle{ u_i }[/math] is continuous and compact, [math]\displaystyle{ r(\sigma_i) }[/math] is non-empty and upper hemicontinuous.


Condition 4. is satisfied as a result of mixed strategies. Suppose [math]\displaystyle{ \sigma_i, \sigma'_i \in r(\sigma_{-i}) }[/math], then [math]\displaystyle{ \lambda \sigma_i + (1-\lambda) \sigma'_i \in r(\sigma_{-i}) }[/math]. i.e. if two strategies maximize payoffs, then a mix between the two strategies will yield the same payoff.

混合策略满足条件4。假设 r (sigma _ {-i }) </math > 中的∑ _ i,∑ _ i,那么 r (sigma _ {-i }) </math > λ _ sigma _ i + (1-lambda)∑ _ i </math > 。也就是。如果两个策略的收益最大化,那么两个策略的混合会产生相同的收益。

Condition 4. is satisfied as a result of mixed strategies. Suppose [math]\displaystyle{ \sigma_i, \sigma'_i \in r(\sigma_{-i}) }[/math], then [math]\displaystyle{ \lambda \sigma_i + (1-\lambda) \sigma'_i \in r(\sigma_{-i}) }[/math]. i.e. if two strategies maximize payoffs, then a mix between the two strategies will yield the same payoff.


Therefore, there exists a fixed point in [math]\displaystyle{ r }[/math] and a Nash equilibrium.

因此,在 < math > r </math > 中存在一个不动点和一个纳什均衡点。

Therefore, there exists a fixed point in [math]\displaystyle{ r }[/math] and a Nash equilibrium.[29]


When Nash made this point to John von Neumann in 1949, von Neumann famously dismissed it with the words, "That's trivial, you know. That's just a fixed-point theorem." (See Nasar, 1998, p. 94.)

1949年,当 Nash 向约翰·冯·诺伊曼提出这个观点时,von Neumann 用这样的话驳斥了这个观点: “你知道,这是微不足道的。这只是一个不动点定理。”(见 Nasar,1998,p. 94。)

When Nash made this point to John von Neumann in 1949, von Neumann famously dismissed it with the words, "That's trivial, you know. That's just a fixed-point theorem." (See Nasar, 1998, p. 94.)


Alternate proof using the Brouwer fixed-point theoremBrouwer不动点定理的交替证明

We have a game [math]\displaystyle{ G=(N,A,u) }[/math] where [math]\displaystyle{ N }[/math] is the number of players and [math]\displaystyle{ A = A_1 \times \cdots \times A_N }[/math] is the action set for the players. All of the action sets [math]\displaystyle{ A_i }[/math] are finite. Let [math]\displaystyle{ \Delta = \Delta_1 \times \cdots \times \Delta_N }[/math] denote the set of mixed strategies for the players. The finiteness of the [math]\displaystyle{ A_i }[/math]s ensures the compactness of [math]\displaystyle{ \Delta }[/math].

我们有一个游戏[math]\displaystyle{ G=(N,A,u) }[/math],其中[math]\displaystyle{ N }[/math] 是玩家的数目,[math]\displaystyle{ A = A_1 \times \cdots \times A_N }[/math]是玩家的动作集合。所有的动作集[math]\displaystyle{ A_i }[/math]都是有限的。设 [math]\displaystyle{ \Delta = \Delta_1 \times \cdots \times \Delta_N }[/math]表示玩家的混合策略集合。[math]\displaystyle{ A_i }[/math]s的有限性保证了[math]\displaystyle{ \Delta }[/math]的紧凑性。

We have a game [math]\displaystyle{ G=(N,A,u) }[/math] where [math]\displaystyle{ N }[/math] is the number of players and [math]\displaystyle{ A = A_1 \times \cdots \times A_N }[/math] is the action set for the players. All of the action sets [math]\displaystyle{ A_i }[/math] are finite. Let [math]\displaystyle{ \Delta = \Delta_1 \times \cdots \times \Delta_N }[/math] denote the set of mixed strategies for the players. The finiteness of the [math]\displaystyle{ A_i }[/math]s ensures the compactness of [math]\displaystyle{ \Delta }[/math].


We can now define the gain functions. For a mixed strategy [math]\displaystyle{ \sigma \in \Delta }[/math], we let the gain for player [math]\displaystyle{ i }[/math] on action [math]\displaystyle{ a \in A_i }[/math] be

我们现在可以定义增益函数了。对于 Delta 中的混合策略 [math]\displaystyle{ \sigma \in \Delta }[/math],我们让玩家[math]\displaystyle{ i }[/math][math]\displaystyle{ a \in A_i }[/math]行动得分为

We can now define the gain functions. For a mixed strategy [math]\displaystyle{ \sigma \in \Delta }[/math], we let the gain for player [math]\displaystyle{ i }[/math] on action [math]\displaystyle{ a \in A_i }[/math] be


[math]\displaystyle{ \text{Gain}_i(\sigma,a) = \max \{0, u_i(a, \sigma_{-i}) - u_i(\sigma_{i}, \sigma_{-i})\}. }[/math]

< math > 文本{ Gain } _ i (sigma,a) = max {0,u _ i (a,sigma _ i })-u _ i (sigma _ { i } ,sigma _ i })}。 </math >

[math]\displaystyle{ \text{Gain}_i(\sigma,a) = \max \{0, u_i(a, \sigma_{-i}) - u_i(\sigma_{i}, \sigma_{-i})\}. }[/math]


The gain function represents the benefit a player gets by unilaterally changing their strategy. We now define [math]\displaystyle{ g = (g_1,\dotsc,g_N) }[/math] where

增益函数代表玩家通过单方面改变策略而获得的收益。我们现在定义了 [math]\displaystyle{ g = (g_1,\dotsc,g_N) }[/math]

The gain function represents the benefit a player gets by unilaterally changing their strategy. We now define [math]\displaystyle{ g = (g_1,\dotsc,g_N) }[/math] where


[math]\displaystyle{ g_i(\sigma)(a) = \sigma_i(a) + \text{Gain}_i(\sigma,a) }[/math]

(a) = sigma _ i (a) + text { Gain } _ i (sigma,a) </math >

[math]\displaystyle{ g_i(\sigma)(a) = \sigma_i(a) + \text{Gain}_i(\sigma,a) }[/math]


for [math]\displaystyle{ \sigma \in \Delta, a \in A_i }[/math]. We see that

[math]\displaystyle{ \sigma \in \Delta, a \in A_i }[/math],我们看到

for [math]\displaystyle{ \sigma \in \Delta, a \in A_i }[/math]. We see that


[math]\displaystyle{ \sum_{a \in A_i} g_i(\sigma)(a) = \sum_{a \in A_i} \sigma_i(a) + \text{Gain}_i(\sigma,a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma,a) \gt 0. }[/math]

(a) = sum _ { a in a _ i } g _ i (sigma)(a) = sum _ a in a _ i } sigma _ i (a) + text { Gain } _ i (sigma,a) = 1 + sum _ { a in a _ i } text { Gain } _ i (sigma,a) > 0

[math]\displaystyle{ \sum_{a \in A_i} g_i(\sigma)(a) = \sum_{a \in A_i} \sigma_i(a) + \text{Gain}_i(\sigma,a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma,a) \gt 0. }[/math]


Next we define:

接下来我们定义:

Next we define:


[math]\displaystyle{ \begin{cases} f = (f_1, \cdots, f_N) : \Delta \to \Delta \\ f_i(\sigma)(a) = \frac{g_i(\sigma)(a)}{\sum_{b \in A_i} g_i(\sigma)(b)} & a \in A_i \end{cases} }[/math]

F = (f _ 1,cdots,f _ n) : Delta to Delta f _ i (sigma)(a) = frac { g _ i (sigma)(a)}{ sum _ b in a _ i (sigma)(b)} & a in a _ i end { cases } </math >

[math]\displaystyle{ \begin{cases} f = (f_1, \cdots, f_N) : \Delta \to \Delta \\ f_i(\sigma)(a) = \frac{g_i(\sigma)(a)}{\sum_{b \in A_i} g_i(\sigma)(b)} & a \in A_i \end{cases} }[/math]


It is easy to see that each [math]\displaystyle{ f_i }[/math] is a valid mixed strategy in [math]\displaystyle{ \Delta_i }[/math]. It is also easy to check that each [math]\displaystyle{ f_i }[/math] is a continuous function of [math]\displaystyle{ \sigma }[/math], and hence [math]\displaystyle{ f }[/math] is a continuous function. As the cross product of a finite number of compact convex sets, [math]\displaystyle{ \Delta }[/math] is also compact and convex. Applying the Brouwer fixed point theorem to [math]\displaystyle{ f }[/math] and [math]\displaystyle{ \Delta }[/math] we conclude that [math]\displaystyle{ f }[/math] has a fixed point in [math]\displaystyle{ \Delta }[/math], call it [math]\displaystyle{ \sigma^* }[/math]. We claim that [math]\displaystyle{ \sigma^* }[/math] is a Nash equilibrium in [math]\displaystyle{ G }[/math]. For this purpose, it suffices to show that

很容易看出,每一个 [math]\displaystyle{ f_i }[/math]都是 [math]\displaystyle{ \Delta_i }[/math]中有效的混合策略。检查每个 [math]\displaystyle{ f_i }[/math][math]\displaystyle{ \sigma }[/math]的连续函数也很容易,因此 [math]\displaystyle{ f }[/math]是一个连续函数。作为有限个紧凸集的叉积,[math]\displaystyle{ \Delta }[/math] 也是紧的和凸的。对[math]\displaystyle{ f }[/math][math]\displaystyle{ \Delta }[/math]应用布劳威尔不动点定理,我们得出结论: [math]\displaystyle{ f }[/math][math]\displaystyle{ \Delta }[/math]有一个不动点,叫[math]\displaystyle{ \sigma^* }[/math]。我们称 [math]\displaystyle{ \sigma^* }[/math][math]\displaystyle{ G }[/math]中的纳什均衡点。对于这个目的,只需要说明

It is easy to see that each [math]\displaystyle{ f_i }[/math] is a valid mixed strategy in [math]\displaystyle{ \Delta_i }[/math]. It is also easy to check that each [math]\displaystyle{ f_i }[/math] is a continuous function of [math]\displaystyle{ \sigma }[/math], and hence [math]\displaystyle{ f }[/math] is a continuous function. As the cross product of a finite number of compact convex sets, [math]\displaystyle{ \Delta }[/math] is also compact and convex. Applying the Brouwer fixed point theorem to [math]\displaystyle{ f }[/math] and [math]\displaystyle{ \Delta }[/math] we conclude that [math]\displaystyle{ f }[/math] has a fixed point in [math]\displaystyle{ \Delta }[/math], call it [math]\displaystyle{ \sigma^* }[/math]. We claim that [math]\displaystyle{ \sigma^* }[/math] is a Nash equilibrium in [math]\displaystyle{ G }[/math]. For this purpose, it suffices to show that


[math]\displaystyle{ \forall i \in \{1, \cdots, N\}, \forall a \in A_i: \quad \text{Gain}_i(\sigma^*,a) = 0. }[/math]

{1,cdots,n } ,for all a in a _ i: quad text { Gain } _ i (sigma ^ * ,a) = 0

[math]\displaystyle{ \forall i \in \{1, \cdots, N\}, \forall a \in A_i: \quad \text{Gain}_i(\sigma^*,a) = 0. }[/math]


This simply states that each player gains no benefit by unilaterally changing their strategy, which is exactly the necessary condition for a Nash equilibrium.

这只是说每个玩家单方面改变他们的策略不会获得任何好处,而这正是纳什均衡点的必要条件。

This simply states that each player gains no benefit by unilaterally changing their strategy, which is exactly the necessary condition for a Nash equilibrium.


Now assume that the gains are not all zero. Therefore, [math]\displaystyle{ \exists i \in \{1, \cdots, N\}, }[/math] and [math]\displaystyle{ a \in A_i }[/math] such that [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) \gt 0 }[/math]. Note then that

现在假设收益并非全部为零。因此,[ math ]存在于[1,cdots,n } ,</math > 和 < math > a </math > 中,以至于 < math > > > text { Gain } i (sigma ^ * ,a) > 0 </math > 。请注意

Now assume that the gains are not all zero. Therefore, [math]\displaystyle{ \exists i \in \{1, \cdots, N\}, }[/math] and [math]\displaystyle{ a \in A_i }[/math] such that [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) \gt 0 }[/math]. Note then that


[math]\displaystyle{ \sum_{a \in A_i} g_i(\sigma^*, a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma^*,a) \gt 1. }[/math]

< math > sum _ { a in a _ i } g _ i (sigma ^ * ,a) = 1 + sum _ { a in a _ i } text { Gain } _ i (sigma ^ * ,a) > 1. </math >

[math]\displaystyle{ \sum_{a \in A_i} g_i(\sigma^*, a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma^*,a) \gt 1. }[/math]


So let

所以,让我们

So let


[math]\displaystyle{ C = \sum_{a \in A_i} g_i(\sigma^*, a). }[/math]

C = sum _ { a in a _ i } g _ i (sigma ^ * ,a)

[math]\displaystyle{ C = \sum_{a \in A_i} g_i(\sigma^*, a). }[/math]


Also we shall denote [math]\displaystyle{ \text{Gain}(i,\cdot) }[/math] as the gain vector indexed by actions in [math]\displaystyle{ A_i }[/math]. Since [math]\displaystyle{ \sigma^* }[/math] is the fixed point we have:

此外,我们还将表示 < math > text { Gain }(i,cdot) </math > 作为 < math > a _ i </math > 中按操作索引的增益向量。自从 < math > sigma ^ * </math > 是我们有的固定点:

Also we shall denote [math]\displaystyle{ \text{Gain}(i,\cdot) }[/math] as the gain vector indexed by actions in [math]\displaystyle{ A_i }[/math]. Since [math]\displaystyle{ \sigma^* }[/math] is the fixed point we have:


[math]\displaystyle{ \begin{align} 1.1.1.2.2.2.2.2.2.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3 :\lt math\gt \begin{align} \sigma^* = f(\sigma^*) &\Rightarrow \sigma^*_i = f_i(\sigma^*) \\ Sigma ^ * = f (sigma ^ *) & right tarrow sigma ^ * i = f _ i (sigma ^ *) \sigma^* = f(\sigma^*) &\Rightarrow \sigma^*_i = f_i(\sigma^*) \\ &\Rightarrow \sigma^*_i = \frac{g_i(\sigma^*)}{\sum_{a \in A_i} g_i(\sigma^*)(a)} \\ [6pt] & right tarrow sigma ^ * i = frac { g _ i (sigma ^ *)}{ sum _ { a in a _ i } g _ i (sigma ^ *)(a)}[6 pt ] &\Rightarrow \sigma^*_i = \frac{g_i(\sigma^*)}{\sum_{a \in A_i} g_i(\sigma^*)(a)} \\ [6pt] &\Rightarrow \sigma^*_i = \frac{1}{C} \left (\sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \right ) \\ [6pt] & right tarrow sigma ^ * i = frac {1}{ c } left (sigma ^ * i + text { Gain } i (sigma ^ * ,cdot) right)[6 pt ] &\Rightarrow \sigma^*_i = \frac{1}{C} \left (\sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \right ) \\ [6pt] &\Rightarrow C\sigma^*_i = \sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \\ & right tarrow c sigma ^ * _ i = sigma ^ * _ i + text { Gain } _ i (sigma ^ * ,cdot) &\Rightarrow C\sigma^*_i = \sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \\ &\Rightarrow \left(C-1\right)\sigma^*_i = \text{Gain}_i(\sigma^*,\cdot) \\ & right tarrow left (C-1 right) sigma ^ * _ i = text { Gain } _ i (sigma ^ * ,cdot) &\Rightarrow \left(C-1\right)\sigma^*_i = \text{Gain}_i(\sigma^*,\cdot) \\ &\Rightarrow \sigma^*_i = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*,\cdot). & right tarrow sigma ^ * _ i = left (frac {1}{ C-1} right) text { Gain } _ i (sigma ^ * ,cdot). &\Rightarrow \sigma^*_i = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*,\cdot). \end{align} }[/math]

结束{ align } </math >

\end{align}</math>


Since [math]\displaystyle{ C \gt 1 }[/math] we have that [math]\displaystyle{ \sigma^*_i }[/math] is some positive scaling of the vector [math]\displaystyle{ \text{Gain}_i(\sigma^*,\cdot) }[/math]. Now we claim that

由于 < math > c > 1 </math > 我们知道 < math > sigma ^ * i </math > 是向量 < math > text { Gain } i (sigma ^ * ,cdot) </math > 的某种正比例缩放。现在我们声称

Since [math]\displaystyle{ C \gt 1 }[/math] we have that [math]\displaystyle{ \sigma^*_i }[/math] is some positive scaling of the vector [math]\displaystyle{ \text{Gain}_i(\sigma^*,\cdot) }[/math]. Now we claim that


[math]\displaystyle{ \forall a \in A_i: \quad \sigma^*_i(a)(u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) = \sigma^*_i(a)\text{Gain}_i(\sigma^*, a) }[/math]

对于 a _ i 中的所有 a: quad sigma ^ * _ i (a _ i,sigma ^ * _ {-i })-u _ i (sigma ^ * _ i,sigma ^ * _ {-i }) = sigma ^ * _ i (a) text { Gain } _ i (sigma ^ * * ,a) </math >

[math]\displaystyle{ \forall a \in A_i: \quad \sigma^*_i(a)(u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) = \sigma^*_i(a)\text{Gain}_i(\sigma^*, a) }[/math]


To see this, we first note that if [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) \gt 0 }[/math] then this is true by definition of the gain function. Now assume that [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) = 0 }[/math]. By our previous statements we have that

为了看到这一点,我们首先注意到,如果 < math > text { Gain } _ i (sigma ^ * ,a) > 0 </math > ,那么根据 Gain 函数的定义,这是正确的。现在假设 < math > text { Gain } _ i (sigma ^ * ,a) = 0 </math > 。根据我们之前的陈述,我们已经知道了

To see this, we first note that if [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) \gt 0 }[/math] then this is true by definition of the gain function. Now assume that [math]\displaystyle{ \text{Gain}_i(\sigma^*, a) = 0 }[/math]. By our previous statements we have that


[math]\displaystyle{ \sigma^*_i(a) = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*, a) = 0 }[/math]

< math > sigma ^ * i (a) = left (frac {1}{ C-1} right) text { Gain } _ i (sigma ^ * ,a) = 0 </math >

[math]\displaystyle{ \sigma^*_i(a) = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*, a) = 0 }[/math]


and so the left term is zero, giving us that the entire expression is [math]\displaystyle{ 0 }[/math] as needed.

所以左边的项是零,表示整个表达式是 < math > 0 </math > 。

and so the left term is zero, giving us that the entire expression is [math]\displaystyle{ 0 }[/math] as needed.


So we finally have that

所以我们最终得到了这个

So we finally have that


[math]\displaystyle{ \begin{align} 1.1.1.2.2.2.2.2.2.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3.3 :\lt math\gt \begin{align} 0 &= u_i(\sigma^*_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}) \\ 0 & = u _ i (sigma ^ * _ i,sigma ^ * _ {-i })-u _ i (sigma ^ * _ i,sigma ^ * _ {-i }) 0 &= u_i(\sigma^*_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}) \\ &= \left(\sum_{a \in A_i} \sigma^*_i(a)u_i(a_i, \sigma^*_{-i})\right) - u_i(\sigma^*_i, \sigma^*_{-i}) \\ & = left (sum _ { a in a _ i } sigma ^ * _ i (a _ i,sigma ^ * _ {-i }) right)-u _ i (sigma ^ * _ i,sigma ^ * _ {-i }) &= \left(\sum_{a \in A_i} \sigma^*_i(a)u_i(a_i, \sigma^*_{-i})\right) - u_i(\sigma^*_i, \sigma^*_{-i}) \\ & = \sum_{a \in A_i} \sigma^*_i(a) (u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) \\ & = sum _ { a in a _ i } sigma ^ * _ i (u _ i (a _ i,sigma ^ * _ {-i })-u _ i (sigma ^ * _ i,sigma ^ * _ {-i })) & = \sum_{a \in A_i} \sigma^*_i(a) (u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) \\ & = \sum_{a \in A_i} \sigma^*_i(a) \text{Gain}_i(\sigma^*, a) && \text{ by the previous statements } \\ 和 = sum _ { a in a _ i } sigma ^ * _ i (a) text { Gain } _ i (sigma ^ * ,a) & text { by the previous statements } & = \sum_{a \in A_i} \sigma^*_i(a) \text{Gain}_i(\sigma^*, a) && \text{ by the previous statements } \\ &= \sum_{a \in A_i} \left( C -1 \right) \sigma^*_i(a)^2 \gt 0 & = sum _ { a in a _ i } left (c-1 right) sigma ^ * _ i (a) ^ 2 \gt 0 &= \sum_{a \in A_i} \left( C -1 \right) \sigma^*_i(a)^2 \gt 0 \end{align} }[/math]

结束{ align } </math >

\end{align}</math>


where the last inequality follows since [math]\displaystyle{ \sigma^*_i }[/math] is a non-zero vector. But this is a clear contradiction, so all the gains must indeed be zero. Therefore, [math]\displaystyle{ \sigma^* }[/math] is a Nash equilibrium for [math]\displaystyle{ G }[/math] as needed.

最后一个不等式是一个非零向量。但这是一个明显的矛盾,因此所有的收益必然是零。因此,如果需要的话,sigma ^ * </math > 是 < math > g </math > 的纳什均衡点。

where the last inequality follows since [math]\displaystyle{ \sigma^*_i }[/math] is a non-zero vector. But this is a clear contradiction, so all the gains must indeed be zero. Therefore, [math]\displaystyle{ \sigma^* }[/math] is a Nash equilibrium for [math]\displaystyle{ G }[/math] as needed.


Computing Nash equilibria 计算纳什均衡

If a player A has a dominant strategy [math]\displaystyle{ s_A }[/math] then there exists a Nash equilibrium in which A plays [math]\displaystyle{ s_A }[/math]. In the case of two players A and B, there exists a Nash equilibrium in which A plays [math]\displaystyle{ s_A }[/math] and B plays a best response to [math]\displaystyle{ s_A }[/math]. If [math]\displaystyle{ s_A }[/math] is a strictly dominant strategy, A plays [math]\displaystyle{ s_A }[/math] in all Nash equilibria. If both A and B have strictly dominant strategies, there exists a unique Nash equilibrium in which each plays their strictly dominant strategy.

如果一个玩家A有一个支配策略[math]\displaystyle{ s_A }[/math] ,那么存在一个纳什均衡,在这个均衡中A选[math]\displaystyle{ s_A }[/math]。在两个博弈者A和B的情况下,存在一个纳什均衡,其中A选[math]\displaystyle{ s_A }[/math],B对[math]\displaystyle{ s_A }[/math]的反应最好。如果 [math]\displaystyle{ s_A }[/math]是严格占优策略,则A在所有的Nash均衡中扮演[math]\displaystyle{ s_A }[/math] 。如果A和B都有严格的占优策略,则存在一个唯一的纳什均衡,在这个均衡中,每个人都发挥各自的严格占优策略。

If a player A has a dominant strategy [math]\displaystyle{ s_A }[/math] then there exists a Nash equilibrium in which A plays [math]\displaystyle{ s_A }[/math]. In the case of two players A and B, there exists a Nash equilibrium in which A plays [math]\displaystyle{ s_A }[/math] and B plays a best response to [math]\displaystyle{ s_A }[/math]. If [math]\displaystyle{ s_A }[/math] is a strictly dominant strategy, A plays [math]\displaystyle{ s_A }[/math] in all Nash equilibria. If both A and B have strictly dominant strategies, there exists a unique Nash equilibrium in which each plays their strictly dominant strategy.


In games with mixed-strategy Nash equilibria, the probability of a player choosing any particular (so pure) strategy can be computed by assigning a variable to each strategy that represents a fixed probability for choosing that strategy. In order for a player to be willing to randomize, their expected payoff for each (pure) strategy should be the same. In addition, the sum of the probabilities for each strategy of a particular player should be 1. This creates a system of equations from which the probabilities of choosing each strategy can be derived.

在含有混合策略纳什均衡的博弈中,参与者选择任何特定策略(如此纯粹)的概率可以通过为每个策略分配一个变量来计算,该变量表示选择该策略的固定概率。为了使玩家愿意随机化,他们对每个(纯)策略的期望收益应该是相同的。此外,一个特定参与人的每个策略的概率之和应该是1。这就产生了一个方程组,从中可以推导出选择每种策略的概率。

In games with mixed-strategy Nash equilibria, the probability of a player choosing any particular (so pure) strategy can be computed by assigning a variable to each strategy that represents a fixed probability for choosing that strategy. In order for a player to be willing to randomize, their expected payoff for each (pure) strategy should be the same. In addition, the sum of the probabilities for each strategy of a particular player should be 1. This creates a system of equations from which the probabilities of choosing each strategy can be derived.[21]


Examples 样例

{ | border = “1” cellpadding = “4” cellspacing = “0” style = “ margin: 1em 1em 1em 1em; background: # f9f9f9; border: 1px # aaa solid; border-collapse: collapse; font-size: 95% ; class = “ wikitable floatright”
Matching pennies
Matching penny
Matching pennies
模板:Diagonal split header Player B plays H 玩家 b 扮演 h Player B plays H Player B plays T 玩家 b 玩 t Player B plays T
Player A plays H 参与人 a 扮演 h Player A plays H −1, +1 −1, +1 −1, +1 +1, −1 +1, −1 +1, −1
Player A plays T 参与人 a 扮演 t Player A plays T +1, −1 +1, −1 +1, −1 −1, +1 −1, +1 −1, +1

|}


In the matching pennies game, player A loses a point to B if A and B play the same strategy and wins a point from B if they play different strategies. To compute the mixed-strategy Nash equilibrium, assign A the probability p of playing H and (1−p) of playing T, and assign B the probability q of playing H and (1−q) of playing T.

在匹配的便士游戏中,如果 A 和 B 采用相同的策略并且如果他们采用不同的策略则赢得 B 的一分,那么 A 就会输给 B 一分。为了计算混合策略纳什均衡点,给 A 赋予 T 的策略 H 和(1-p)的概率 p,给 B 赋予 T 的策略 H 和(1-q)的概率 q。

In the matching pennies game, player A loses a point to B if A and B play the same strategy and wins a point from B if they play different strategies. To compute the mixed-strategy Nash equilibrium, assign A the probability p of playing H and (1−p) of playing T, and assign B the probability q of playing H and (1−q) of playing T.


E[payoff for A playing H] = (−1)q + (+1)(1−q) = 1−2q

E [ a 演奏 h 的收益] = (- 1) q + (+ 1)(1-q) = 1-2q

E[payoff for A playing H] = (−1)q + (+1)(1−q) = 1−2q

E[payoff for A playing T] = (+1)q + (−1)(1−q) = 2q−1

E [ a 演奏 t 的收益] = (+ 1) q + (- 1)(1-q) = 2q-1

E[payoff for A playing T] = (+1)q + (−1)(1−q) = 2q−1

E[payoff for A playing H] = E[payoff for A playing T] ⇒ 1−2q = 2q−1 ⇒ q = 1/2

E [ a 玩 h 的收益] = e [ a 玩 t 的收益] something 1-2q = 2q-1 something q = 1/2

E[payoff for A playing H] = E[payoff for A playing T] ⇒ 1−2q = 2q−1 ⇒ q = 1/2


E[payoff for B playing H] = (+1)p + (−1)(1−p) = 2p−1

E [ b 参与 h 的收益] = (+ 1) p + (- 1)(1-p) = 2p-1

E[payoff for B playing H] = (+1)p + (−1)(1−p) = 2p−1

E[payoff for B playing T] = (−1)p + (+1)(1−p) = 1−2p

E [ b 参与 t 的收益] = (- 1) p + (+ 1)(1-p) = 1-2p

E[payoff for B playing T] = (−1)p + (+1)(1−p) = 1−2p

E[payoff for B playing H] = E[payoff for B playing T] ⇒ 2p−1 = 1−2p ⇒ p = 1/2

E [ b 参与 h 的收益] = e [ b 参与 t 的收益]2p-1 = 1-2p something p = 1/2

E[payoff for B playing H] = E[payoff for B playing T] ⇒ 2p−1 = 1−2pp = 1/2


Thus a mixed-strategy Nash equilibrium, in this game, is for each player to randomly choose H or T with p = 1/2 and q = 1/2.

因此在这个博弈中,一个混合策略的纳什均衡点是让每个参与者随机选择 p = 1/2和 q = 1/2的 h 或 t。

Thus a mixed-strategy Nash equilibrium, in this game, is for each player to randomly choose H or T with p = 1/2 and q = 1/2.


See also 又及


Notes 备注

  1. 1.0 1.1 Osborne, Martin J.; Rubinstein, Ariel (12 Jul 1994). A Course in Game Theory. Cambridge, MA: MIT. p. 14. ISBN 9780262150415. 
  2. Schelling, Thomas, The Strategy of Conflict, copyright 1960, 1980, Harvard University Press, .
  3. De Fraja, G.; Oliveira, T.; Zanchi, L. (2010). "Must Try Harder: Evaluating the Role of Effort in Educational Attainment". Review of Economics and Statistics. 92 (3): 577. doi:10.1162/REST_a_00013.
  4. Ward, H. (1996). "Game Theory and the Politics of Global Warming: The State of Play and Beyond". Political Studies. 44 (5): 850–871. doi:10.1111/j.1467-9248.1996.tb00338.x.,
  5. Thorpe, Robert B.; Jennings, Simon; Dolder, Paul J. (2017). "Risks and benefits of catching pretty good yield in multispecies mixed fisheries". ICES Journal of Marine Science. 74 (8): 2097–2106. doi:10.1093/icesjms/fsx062.,
  6. "Marketing Lessons from Dr. Nash - Andrew Frank". 2015-05-25. Retrieved 2015-08-30.
  7. Chiappori, P. -A.; Levitt, S.; Groseclose, T. (2002). "Testing Mixed-Strategy Equilibria when Players Are Heterogeneous: The Case of Penalty Kicks in Soccer" (PDF). American Economic Review. 92 (4): 1138. CiteSeerX 10.1.1.178.1646. doi:10.1257/00028280260344678.
  8. Djehiche, B.; Tcheukam, A.; Tembine, H. (2017). "A Mean-Field Game of Evacuation in Multilevel Building". IEEE Transactions on Automatic Control. 62 (10): 5154–5169. doi:10.1109/TAC.2017.2679487. ISSN 0018-9286.
  9. Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (2017-09-27). "Mean-Field-Type Games in Engineering". AIMS Electronics and Electrical Engineering (in English). 1: 18–73. arXiv:1605.03281. doi:10.3934/ElectrEng.2017.1.18.
  10. Schelling, Thomas, The Strategy of Conflict, copyright 1960, 1980, Harvard University Press, .
  11. De Fraja, G.; Oliveira, T.; Zanchi, L. (2010). "Must Try Harder: Evaluating the Role of Effort in Educational Attainment". Review of Economics and Statistics. 92 (3): 577. doi:10.1162/REST_a_00013.
  12. Ward, H. (1996). "Game Theory and the Politics of Global Warming: The State of Play and Beyond". Political Studies. 44 (5): 850–871. doi:10.1111/j.1467-9248.1996.tb00338.x.,
  13. "Marketing Lessons from Dr. Nash - Andrew Frank". 2015-05-25. Retrieved 2015-08-30.
  14. Chiappori, P. -A.; Levitt, S.; Groseclose, T. (2002). "Testing Mixed-Strategy Equilibria when Players Are Heterogeneous: The Case of Penalty Kicks in Soccer" (PDF). American Economic Review. 92 (4): 1138. CiteSeerX 10.1.1.178.1646. doi:10.1257/00028280260344678.
  15. Djehiche, B.; Tcheukam, A.; Tembine, H. (2017). "A Mean-Field Game of Evacuation in Multilevel Building". IEEE Transactions on Automatic Control. 62 (10): 5154–5169. doi:10.1109/TAC.2017.2679487. ISSN 0018-9286.
  16. Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (2017-09-27). "Mean-Field-Type Games in Engineering". AIMS Electronics and Electrical Engineering (in English). 1: 18–73. arXiv:1605.03281. doi:10.3934/ElectrEng.2017.1.18.
  17. Cournot A. (1838) Researches on the Mathematical Principles of the Theory of Wealth
  18. Cournot A. (1838) Researches on the Mathematical Principles of the Theory of Wealth
  19. J. Von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, copyright 1944, 1953, Princeton University Press
  20. Carmona, Guilherme; Podczeck, Konrad (2009). "On the Existence of Pure Strategy Nash Equilibria in Large Games" (PDF). Journal of Economic Theory. 144 (3): 1300–1319. doi:10.1016/j.jet.2008.11.009. SSRN 882466.
  21. 21.0 21.1 von Ahn, Luis. "Preliminaries of Game Theory" (PDF). Archived from the original (PDF) on 2011-10-18. Retrieved 2008-11-07.
  22. "Nash Equilibria". hoylab.cornell.edu. Retrieved 2019-12-08.
  23. MIT OpenCourseWare. 6.254: Game Theory with Engineering Applications, Spring 2010. Lecture 6: Continuous and Discontinuous Games.
  24. 24.0 24.1 B. D. Bernheim; B. Peleg; M. D. Whinston (1987), "Coalition-Proof Equilibria I. Concepts", Journal of Economic Theory, 42 (1): 1–12, doi:10.1016/0022-0531(87)90099-8.
  25. Aumann, R. (1959). "Acceptable points in general cooperative n-person games". Contributions to the Theory of Games. IV. Princeton, N.J.: Princeton University Press. ISBN 978-1-4008-8216-8. 
  26. D. Moreno; J. Wooders (1996), "Coalition-Proof Equilibrium" (PDF), Games and Economic Behavior, 17 (1): 80–112, doi:10.1006/game.1996.0095, hdl:10016/4408.
  27. T. L. Turocy, B. Von Stengel, Game Theory, copyright 2001, Texas A&M University, London School of Economics, pages 141-144. 模板:Citation needed span – it can be represented as a strategy complying with his original conditions for a game with a NE. Such games may not have unique NE, but at least one of the many equilibrium strategies would be played by hypothetical players having perfect knowledge of all 模板:Citation needed span.
  28. J. C. Cox, M. Walker, Learning to Play Cournot Duoploy Strategies -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔,存档日期2013-12-11., copyright 1997, Texas A&M University, University of Arizona, pages 141-144
  29. Fudenburg, Drew; Tirole, Jean (1991). Game Theory. MIT Press. ISBN 978-0-262-06141-4. 


References 索引

Game theory textbooks博弈论教科书


Original Nash papers纳什原创论文


Other references其他文献


External links 外部链接


模板:Game theory



Category:Game theory equilibrium concepts

范畴: 博弈论均衡概念

Category:Fixed points (mathematics)

类别: 定点(数学)

Category:1951 in economics

分类: 1951年经济学


This page was moved from wikipedia:en:Nash equilibrium. Its edit history can be viewed at 纳什均衡/edithistory 此页摘自维基百科:英语:纳什均衡。它的编辑历史可以在纳什均衡/编辑历史记录查阅