策略

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

本词条由舒寒初步翻译。

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others.[1] A player's strategy will determine the action which the player will take at any stage of the game.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

在博弈论中,一个玩家的策略是他或她在一个不仅取决于他们自己的行动,而且也取决于其他人的行动的环境中所选择的任何一个选项。玩家的策略将决定玩家在游戏的任何阶段将采取的行动。


The strategy concept is sometimes (wrongly) confused with that of a move. A move is an action taken by a player at some point during the play of a game (e.g., in chess, moving white's Bishop a2 to b3). A strategy on the other hand is a complete algorithm for playing the game, telling a player what to do for every possible situation throughout the game.

The strategy concept is sometimes (wrongly) confused with that of a move. A move is an action taken by a player at some point during the play of a game (e.g., in chess, moving white's Bishop a2 to b3). A strategy on the other hand is a complete algorithm for playing the game, telling a player what to do for every possible situation throughout the game.

战略的概念有时(错误地)与行动的概念相混淆。行动是一个玩家在博弈过程中的某个时刻所采取的行动(例如,在国际象棋中,将 white 的 Bishop 移动到 b3)。另一方面,策略是博弈的完整算法,告诉玩家在整个游戏中的每个可能情况下应该做什么。


A strategy profile (sometimes called a strategy combination) is a set of strategies for all players which fully specifies all actions in a game. A strategy profile must include one and only one strategy for every player.

A strategy profile (sometimes called a strategy combination) is a set of strategies for all players which fully specifies all actions in a game. A strategy profile must include one and only one strategy for every player.

战略配置文件(有时称为战略组合)是一套战略的所有球员,其中充分规定了这个博弈中的所有行动。一个战略档案必须包括一个和只有一个战略的每个球员。


Strategy set

A player's strategy set defines what strategies are available for them to play.

A player's strategy set defines what strategies are available for them to play.

玩家的策略集定义了他们可以使用的策略。


A player has a finite strategy set if they have a number of discrete strategies available to them. For instance, a game of rock paper scissors comprises a single move by each player—and each player's move is made without knowledge of the other's, not as a response—so each player has the finite strategy set {rock paper scissors}.

A player has a finite strategy set if they have a number of discrete strategies available to them. For instance, a game of rock paper scissors comprises a single move by each player—and each player's move is made without knowledge of the other's, not as a response—so each player has the finite strategy set {rock paper scissors}.

如果一个玩家有许多可用的离散策略,那么他的策略集是有限的。例如,石头剪刀布游戏包括每个玩家的一个动作---- 每个玩家的动作都是在不知道对方的动作的情况下进行的,而不是作为一种反应---- 所以每个玩家都有一个有限的策略集合{石头剪刀布}。


A strategy set is infinite otherwise. For instance the cake cutting game has a bounded continuum of strategies in the strategy set {Cut anywhere between zero percent and 100 percent of the cake}.

A strategy set is infinite otherwise. For instance the cake cutting game has a bounded continuum of strategies in the strategy set {Cut anywhere between zero percent and 100 percent of the cake}.

否则策略集是无限的。例如,切蛋糕游戏在策略集{切蛋糕的0% 到100% 之间的任何地方}中有一个有限的连续统一体。


In a dynamic game, the strategy set consists of the possible rules a player could give to a robot or agent on how to play the game. For instance, in the ultimatum game, the strategy set for the second player would consist of every possible rule for which offers to accept and which to reject.

In a dynamic game, the strategy set consists of the possible rules a player could give to a robot or agent on how to play the game. For instance, in the ultimatum game, the strategy set for the second player would consist of every possible rule for which offers to accept and which to reject.

在一个动态博弈中,策略集由玩家可能给机器人或代理人的游戏规则组成。例如,在最后通牒博弈中,为第二个参与者设置的策略将包括所有可能的规则,哪些提议可以接受,哪些可以拒绝。


In a Bayesian game, the strategy set is similar to that in a dynamic game. It consists of rules for what action to take for any possible private information.

In a Bayesian game, the strategy set is similar to that in a dynamic game. It consists of rules for what action to take for any possible private information.

在贝叶斯博弈中,策略集类似于动态博弈中的策略集。它包括对任何可能的私人信息采取何种行动的规则。


Choosing a strategy set

In applied game theory, the definition of the strategy sets is an important part of the art of making a game simultaneously solvable and meaningful. The game theorist can use knowledge of the overall problem to limit the strategy spaces, and ease the solution.

In applied game theory, the definition of the strategy sets is an important part of the art of making a game simultaneously solvable and meaningful. The game theorist can use knowledge of the overall problem to limit the strategy spaces, and ease the solution.

在应用博弈论中,策略集的定义是使博弈既可解又有意义的艺术的重要组成部分。博弈论者可以利用整体问题的知识来限制策略空间,并简化解决方案。


For instance, strictly speaking in the Ultimatum game a player can have strategies such as: Reject offers of ($1, $3, $5, ..., $19), accept offers of ($0, $2, $4, ..., $20). Including all such strategies makes for a very large strategy space and a somewhat difficult problem. A game theorist might instead believe they can limit the strategy set to: {Reject any offer ≤ x, accept any offer > x; for x in ($0, $1, $2, ..., $20)}.

For instance, strictly speaking in the Ultimatum game a player can have strategies such as: Reject offers of ($1, $3, $5, ..., $19), accept offers of ($0, $2, $4, ..., $20). Including all such strategies makes for a very large strategy space and a somewhat difficult problem. A game theorist might instead believe they can limit the strategy set to: {Reject any offer ≤ x, accept any offer > x; for x in ($0, $1, $2, ..., $20)}.

例如,严格地说,在最后通牒游戏中,玩家可以有以下策略: 拒绝($1,$3,$5,... ,$19) ,接受($0,$2,$4,... ,$20)。把所有这些战略都包括在内,会产生一个非常大的战略空间和一个有点难度的问题。博弈论者可能相信他们可以将策略集限制为: { Reject any offer ≤ x,accept any offer x; for x in ($0,$1,$2,... ,$20)}。


Pure and mixed strategies

A pure strategy provides a complete definition of how a player will play a game. In particular, it determines the move a player will make for any situation they could face. A player's strategy set is the set of pure strategies available to that player.

A pure strategy provides a complete definition of how a player will play a game. In particular, it determines the move a player will make for any situation they could face. A player's strategy set is the set of pure strategies available to that player.

纯策略为玩家如何玩游戏提供了一个完整的定义。特别是,它决定了球员在任何情况下都会采取的行动。一个玩家的策略集是该玩家可用的纯策略集。


A mixed strategy is an assignment of a probability to each pure strategy. This allows for a player to randomly select a pure strategy. (See the following section for an illustration.) Since probabilities are continuous, there are infinitely many mixed strategies available to a player.

A mixed strategy is an assignment of a probability to each pure strategy. This allows for a player to randomly select a pure strategy. (See the following section for an illustration.) Since probabilities are continuous, there are infinitely many mixed strategies available to a player.

混合策略是给每个纯策略赋予一个概率。这允许玩家随机选择一个纯策略。(见以下部分的说明。)因为概率是连续的,所以一个参与人可以使用无限多的混合策略。


Of course, one can regard a pure strategy as a degenerate case of a mixed strategy, in which that particular pure strategy is selected with probability 1 and every other strategy with probability 0.

Of course, one can regard a pure strategy as a degenerate case of a mixed strategy, in which that particular pure strategy is selected with probability 1 and every other strategy with probability 0.

当然,我们可以把纯策略看作是混合策略的退化情形,在这种情形下,某个特定的纯策略的选择概率为1,而其他的策略的选择概率为0。


A totally mixed strategy is a mixed strategy in which the player assigns a strictly positive probability to every pure strategy. (Totally mixed strategies are important for equilibrium refinement such as trembling hand perfect equilibrium.)

A totally mixed strategy is a mixed strategy in which the player assigns a strictly positive probability to every pure strategy. (Totally mixed strategies are important for equilibrium refinement such as trembling hand perfect equilibrium.)

一个完全混合策略是一个混合策略,其中玩家为每个纯策略赋予一个严格正的概率。(完全混合策略对于均衡精化非常重要,比如颤抖手完美均衡。)


Mixed strategy

Illustration

{ | 右对齐
模板:Payoff matrix

浮动 | 宽度}

|}


Consider the payoff matrix pictured to the right (known as a coordination game). Here one player chooses the row and the other chooses a column. The row player receives the first payoff, the column player the second. If row opts to play A with probability 1 (i.e. play A for sure), then he is said to be playing a pure strategy. If column opts to flip a coin and play A if the coin lands heads and B if the coin lands tails, then he is said to be playing a mixed strategy, and not a pure strategy.

Consider the payoff matrix pictured to the right (known as a coordination game). Here one player chooses the row and the other chooses a column. The row player receives the first payoff, the column player the second. If row opts to play A with probability 1 (i.e. play A for sure), then he is said to be playing a pure strategy. If column opts to flip a coin and play A if the coin lands heads and B if the coin lands tails, then he is said to be playing a mixed strategy, and not a pure strategy.

考虑右边的收益矩阵(称为协调博弈)。在这里,一个玩家选择行,另一个玩家选择列。第一行玩家获得第一个回报,第二列玩家获得第二个回报。如果行选择以概率1(即。当然是 a) ,那么他就是在玩纯策略。如果一列选择抛出一枚硬币,如果硬币正面朝上,则选择 a,如果硬币正面朝上,则选择 b,那么他就是在玩一种混合策略,而不是单纯的策略。


Significance

In his famous paper, John Forbes Nash proved that there is an equilibrium for every finite game. One can divide Nash equilibria into two types. Pure strategy Nash equilibria are Nash equilibria where all players are playing pure strategies. Mixed strategy Nash equilibria are equilibria where at least one player is playing a mixed strategy. While Nash proved that every finite game has a Nash equilibrium, not all have pure strategy Nash equilibria. For an example of a game that does not have a Nash equilibrium in pure strategies, see Matching pennies. However, many games do have pure strategy Nash equilibria (e.g. the Coordination game, the Prisoner's dilemma, the Stag hunt). Further, games can have both pure strategy and mixed strategy equilibria. An easy example is the pure coordination game, where in addition to the pure strategies (A,A) and (B,B) a mixed equilibrium exists in which both players play either strategy with probability 1/2.

In his famous paper, John Forbes Nash proved that there is an equilibrium for every finite game. One can divide Nash equilibria into two types. Pure strategy Nash equilibria are Nash equilibria where all players are playing pure strategies. Mixed strategy Nash equilibria are equilibria where at least one player is playing a mixed strategy. While Nash proved that every finite game has a Nash equilibrium, not all have pure strategy Nash equilibria. For an example of a game that does not have a Nash equilibrium in pure strategies, see Matching pennies. However, many games do have pure strategy Nash equilibria (e.g. the Coordination game, the Prisoner's dilemma, the Stag hunt). Further, games can have both pure strategy and mixed strategy equilibria. An easy example is the pure coordination game, where in addition to the pure strategies (A,A) and (B,B) a mixed equilibrium exists in which both players play either strategy with probability 1/2.

在他著名的论文中,约翰·福布斯·纳什证明了每个有限博弈都存在均衡。我们可以把纳什均衡分为两种类型。纯策略纳什均衡是所有参与者都采用纯策略的纳什均衡。混合策略纳什均衡是至少有一个参与人采用混合策略的均衡。虽然 Nash 证明了每个有限博弈都有纳什均衡点,但并不是所有的博弈都有纯策略纳什均衡。有关纯策略中没有纳什均衡点的游戏的例子,请参阅匹配便士。然而,许多博弈确实存在纯策略纳什均衡(例如:。协调博弈,囚徒困境,猎鹿)。此外,博弈可以同时具有纯策略和混合策略均衡。一个简单的例子是纯协调博弈,其中除了纯策略(a,a)和(b,b)之外,还存在一个混合均衡,其中两个参与者都采用概率为1 / 2的策略。


A disputed meaning

During the 1980s, the concept of mixed strategies came under heavy fire for being "intuitively problematic".[2] Randomization, central in mixed strategies, lacks behavioral support. Seldom do people make their choices following a lottery. This behavioral problem is compounded by the cognitive difficulty that people are unable to generate random outcomes without the aid of a random or pseudo-random generator.[2]

During the 1980s, the concept of mixed strategies came under heavy fire for being "intuitively problematic". Randomization, central in mixed strategies, lacks behavioral support. Seldom do people make their choices following a lottery. This behavioral problem is compounded by the cognitive difficulty that people are unable to generate random outcomes without the aid of a random or pseudo-random generator.

在20世纪80年代,混合策略的概念因“直觉上有问题”而受到猛烈抨击。以混合策略为核心的随机化缺乏行为支持。很少有人在买彩票后做出选择。这个行为问题是由认知困难,人们不能产生随机的结果没有随机或伪随机生成器的帮助。


In 1991,[3] game theorist Ariel Rubinstein described alternative ways of understanding the concept. The first, due to Harsanyi (1973),[4] is called purification, and supposes that the mixed strategies interpretation merely reflects our lack of knowledge of the players' information and decision-making process. Apparently random choices are then seen as consequences of non-specified, payoff-irrelevant exogenous factors. However, it is unsatisfying to have results that hang on unspecified factors.[3]

In 1991, game theorist Ariel Rubinstein described alternative ways of understanding the concept. The first, due to Harsanyi (1973), is called purification, and supposes that the mixed strategies interpretation merely reflects our lack of knowledge of the players' information and decision-making process. Apparently random choices are then seen as consequences of non-specified, payoff-irrelevant exogenous factors. However, it is unsatisfying to have results that hang on unspecified factors.

1991年,博弈理论家阿里埃勒·鲁宾斯坦 · 马丁描述了理解这个概念的不同方式。首先,由于哈萨尼(1973) ,被称为净化,并假定混合策略解释仅仅反映了我们对参与者的信息和决策过程的知识的缺乏。显然,随机的选择被看作是未指定的、与回报无关的外生因素的结果。然而,结果依赖于未指明的因素是不令人满意的。


A second interpretation imagines the game players standing for a large population of agents. Each of the agents chooses a pure strategy, and the payoff depends on the fraction of agents choosing each strategy. The mixed strategy hence represents the distribution of pure strategies chosen by each population. However, this does not provide any justification for the case when players are individual agents.

A second interpretation imagines the game players standing for a large population of agents. Each of the agents chooses a pure strategy, and the payoff depends on the fraction of agents choosing each strategy. The mixed strategy hence represents the distribution of pure strategies chosen by each population. However, this does not provide any justification for the case when players are individual agents.

第二种解释假设游戏玩家代表一大群代理人。每个代理选择一个纯策略,回报取决于选择每个策略的代理所占的比例。因此,混合策略代表了每个种群所选择的纯策略的分布。然而,当球员是单个经纪人时,这并不能为这种情况提供任何理由。


Later, Aumann and Brandenburger (1995),[5] re-interpreted Nash equilibrium as an equilibrium in beliefs, rather than actions. For instance, in rock paper scissors an equilibrium in beliefs would have each player believing the other was equally likely to play each strategy. This interpretation weakens the predictive power of Nash equilibrium, however, since it is possible in such an equilibrium for each player to actually play a pure strategy of Rock.

Later, Aumann and Brandenburger (1995), re-interpreted Nash equilibrium as an equilibrium in beliefs, rather than actions. For instance, in rock paper scissors an equilibrium in beliefs would have each player believing the other was equally likely to play each strategy. This interpretation weakens the predictive power of Nash equilibrium, however, since it is possible in such an equilibrium for each player to actually play a pure strategy of Rock.

后来,Aumann 和 Brandenburger (1995)重新解释了纳什均衡点,认为它是信仰的平衡,而不是行动的平衡。例如,在石头剪刀布游戏中,信念的均衡会让每个玩家相信另一个玩家同样可能使用每种策略。然而,这种解释削弱了纳什均衡点的预测能力,因为在这样的均衡中,每个玩家都有可能实际使用一种纯粹的摇滚战略。


Ever since, game theorists' attitude towards mixed strategies-based results have been ambivalent. Mixed strategies are still widely used for their capacity to provide Nash equilibria in games where no equilibrium in pure strategies exists, but the model does not specify why and how players randomize their decisions.

Ever since, game theorists' attitude towards mixed strategies-based results have been ambivalent. Mixed strategies are still widely used for their capacity to provide Nash equilibria in games where no equilibrium in pure strategies exists, but the model does not specify why and how players randomize their decisions.

从那时起,博弈论者对基于混合策略的结果的态度一直是矛盾的。在纯策略不存在均衡的博弈中,混合策略仍然被广泛用于提供纳什均衡,但是这个模型并没有说明为什么以及参与者如何随机化他们的决策。


Behavior strategy

While a mixed strategy assigns a probability distribution over pure strategies, a behavior strategy assigns at each information set a probability distribution over the set of possible actions. While the two concepts are very closely related in the context of normal form games, they have very different implications for extensive form games. Roughly, a mixed strategy randomly chooses a deterministic path through the game tree, while a behavior strategy can be seen as a stochastic path.

While a mixed strategy assigns a probability distribution over pure strategies, a behavior strategy assigns at each information set a probability distribution over the set of possible actions. While the two concepts are very closely related in the context of normal form games, they have very different implications for extensive form games. Roughly, a mixed strategy randomly chooses a deterministic path through the game tree, while a behavior strategy can be seen as a stochastic path.

当混合策略在纯策略之上分配一个概率分布 / 值时,行为策略在每个信息集上分配一个概率分布 / 值,在可能的行动集上分配一个值。尽管这两个概念在范式游戏的背景下是密切相关的,但是它们对于范式游戏有着非常不同的含义。粗略地说,混合策略通过博弈树随机选择一条确定性路径,而行为策略可以看作是一条随机路径。


The relationship between mixed and behavior strategies is the subject of Kuhn's theorem. The result establishes that in any finite extensive-form game with perfect recall, for any player and any mixed strategy, there exists a behavior strategy that, against all profiles of strategies (of other players), induces the same distribution over terminal nodes as the mixed strategy does. The converse is also true.

The relationship between mixed and behavior strategies is the subject of Kuhn's theorem. The result establishes that in any finite extensive-form game with perfect recall, for any player and any mixed strategy, there exists a behavior strategy that, against all profiles of strategies (of other players), induces the same distribution over terminal nodes as the mixed strategy does. The converse is also true.

混合策略和行为策略之间的关系是库恩定理的主题。结果表明,在任何具有完全回忆的有限扩展形式的博弈中,对于任何玩家和任何混合策略,都存在一种行为策略,这种策略针对所有策略(其他玩家的) ,在终端节点上诱导出与混合策略相同的分布。反之亦然。


A famous example of why perfect recall is required for the equivalence is given by Piccione and Rubinstein (1997)模板:Full citation needed with their Absent-Minded Driver game.

A famous example of why perfect recall is required for the equivalence is given by Piccione and Rubinstein (1997) with their Absent-Minded Driver game.

Piccione 和 Rubinstein (1997)在他们的心不在焉的 Driver 游戏中给出了一个著名的例子来说明为什么等价物需要完全回忆。


See also


References

  1. Ben Polak Game Theory: Lecture 1 Transcript ECON 159, 5 September 2007, Open Yale Courses.
  2. 2.0 2.1 Aumann, R. (1985). "What is Game Theory Trying to accomplish?". In Arrow, K.; Honkapohja, S.. Frontiers of Economics. Oxford: Basil Blackwell. pp. 909–924. http://www.ma.huji.ac.il/raumann/pdf/what%20is%20game%20theory.pdf. 
  3. 3.0 3.1 Rubinstein, A. (1991). "Comments on the interpretation of Game Theory". Econometrica. 59 (4): 909–924. doi:10.2307/2938166. JSTOR 2938166.
  4. Harsanyi, John (1973). "Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points". Int. J. Game Theory. 2: 1–23. doi:10.1007/BF01737554.
  5. Aumann, Robert; Brandenburger, Adam (1995). "Epistemic Conditions for Nash Equilibrium". Econometrica. 63 (5): 1161–1180. CiteSeerX 10.1.1.122.5816. doi:10.2307/2171725. JSTOR 2171725.


模板:Game theory

Category:Game theory

范畴: 博弈论


This page was moved from wikipedia:en:Strategy (game theory). Its edit history can be viewed at 策略/edithistory