数学博弈论

有两个代理A、B和数据矩阵（9）U=（uA，uB）（uA，uB）（uA，uB）（uA，uB）=(7, 7) (1, 9)(9, 1) (3, 3).A和B按照以下规则进行游戏：（1）A选择U的第i行和第j列。（2）选择（i，j）意味着A被“惩罚”的值为uaij，B被“惩罚”的值为uBij。这个双人游戏有一个初始标准σ和4个其他状态（1，1），（1，2），（2，1），（2，2），对应于美国的四个参赛位置。代理商必须决定策略i，j∈ {1, 2}. 他们的j点决策（i，j）将把游戏从σ移动到最终状态σ=（i，j）。游戏在t=1时结束。那么，玩家A的效用就是价值uAij。B具有实用价值uBij。这种博弈通常被理解为一种成本博弈，即a和B的目标是最小化它们的效用。A和B应该最佳地做什么？即使玩家不是真正的“人”21。现实世界的数学模型备注1。9（囚犯的困境）。（9）yi eldsa版本中的效用矩阵U描述了所谓的囚徒困境，这是两名囚徒A和B的故事，他们可以单独“坦白”或“不坦白”他们共同被控的罪行。取决于他们的工作决定，他们可能会面临美国特有的监禁。他们的“困境”是：o无论他们做什么，至少有一个人最终会觉得做出了错误的决定。第22部分人物游戏2组合游戏从两个交替玩家的角度来看一般游戏。这方面揭示了游戏的递归特性。有限博弈是组合的。在正常的获胜规则下，组合博弈看起来就像广义数。例如，游戏代数允许人们明确计算nim游戏的获胜策略。1.

交替玩家让Γ成为在系统S上玩的游戏，并回忆说Γ代表了抽象意义上所有可能阶段的集合。假设Γ的具体实例开始于初始状态σ∈ 然后我们可以想象，游戏的进化是由两个“超级玩家”引起的，它们交替进行以下动作：（1）开始玩家选择一个阶段γ=σσ∈ Γ.（2） 然后第二个玩家选择一个s tageγ=σσ∈ Γ.（3） 现在又轮到第一个玩家实现下一个可行阶段γ=σ∑∈ Γ等等。（4） 如果下一个移动的玩家找不到可行的扩展γt+1，游戏停止∈ Γ的当前阶段γt。这种观点允许我们将游戏的演化解释为所谓的交替两人游戏的演化。对于这样的博弈a，weassume（a）有一个集合G和两个P层L和R，以及一个初始元素G∈ G.（A）每G∈ G、 有子集GL G和GR G.两组格兰·格林（A）是各自球员相对于G.24 2的选项集。组合游戏交替游戏A的规则是：（A）开始玩家选择与G相对应的选项。然后第二个玩家选择与G相对应的选项。现在第一个玩家可以选择与G相对应的选项，依此类推。（A） 如果轮到Gt的玩家没有相对Gt的选项（即，相应的选项集为空），游戏将以Gt停止。例2。1（国际象棋）。国际象棋是一个明显的两人交替游戏的例子。它的停止规则（A）说，当一名玩家的王位被带走（“将死”）时，游戏结束。备注2.1。虽然国际象棋比赛总是以白棋手的一个动作开始，但请注意，我们还没有明确说明L或R是否是交替2人棋局的一般定义中的第一个棋手。这个规定将在以后的递归分析中提供必要的灵活性。2.

递归上述两人交替游戏A有一个递归结构：（R）可行的移动G→ 玩家的G′将当前的游戏简化为一个新的交替2人游戏，初始元素为G′。为了让这一点在概念上更清晰，我们将p层L和R相对于G的选项表示为（10）G={GL，GL，|GR，GR，…}把G想象成一个G游戏的（递归）描述，它可能被L简化为一个游戏gli，或者被R简化为一个游戏GLj，这取决于谁在移动。3.组合游戏253。组合对策考虑了递归形式（10）的g 2人对策：g={GL，GL，…|GR，GR，…}。通过| G |表示G中可能的后续动作的最大值，我们说G是一个组合对策，如果|G |<∞,i、 例如，如果G保证在一定数量的移动后停止（无论玩家从哪个开始）。显然，所有的选项和GRjof G也必须成为组合游戏：|G |∞ ==> |GLi |，|GRj |≤ |G|- 1 < ∞.例2.2（国际象棋）。根据国际象棋的标准规则，国际象棋并不是一种组合游戏，因为棋手可以在一段时间内来回移动棋子，从而创造出一个永无止境的移动序列。在实践中，国际象棋有一个额外的规则，可以确保一致性，从而使其具有组合性（在上述意义上）。例如，计时时钟的使用限制了移动的次数。例2.3（Nim）。nim游戏G=G（N，…，Nk）有两个交替的布局，并从有限集合和成对不相交集合N，…，的初始配置开始，Nk。玩家的动作：o选择其中一组，sa y Nj，并从Nj中移除一个或多个元素。显然，在e上有| G（N，…，Nk）|≤ |N |+…+|Nk<∞. 所以尼姆是一个组合游戏。例2.4（青蛙）。有固定的数字n和k，两只青蛙L和R位于艺术的位置。

一只青蛙的动作包括向另一只青蛙跳跃至少1个但不超过k个位置：L→ o o o···o o o ←青蛙不能互相跳过。很明显，游戏在最多n步后结束。nim的一个流行版本是从四个集合N，N，N，Nof碎片（卵石或棋子等）开始的，带有|N |=1、|N |=3、|N |=5和|N |=7个元素2。组合游戏标记2.2。Ex.2.4中的青蛙游戏可以理解为一个有额外移动限制的游戏。最初，有一个包含元素的集合N（对应于分离青蛙的位置）。玩家必须移除至少1个但不超过k个元素。创造组合游戏。所有组合游戏的R类都可以系统地创建。我们首先观察到，确实存在一个|g |=0的组合游戏g，即gameO={······}，其中没有玩家可以移动。回忆一下，furt hermore，所有选项都必须满足|G |=t的游戏G≤ T- 1和| GR |≤ T- 1.所以我们可以想象R是在一个永无止境的过程中被“创造”出来的：第0天：游戏O={·|··}被创造出来并产生R={O}。第一天：游戏{O |·}，{·| O}，{O | O}被创建，一个人获得所有组合游戏G与|G |的类R={O，{| O}，{O |O}≤ 1.第2天：完成Ris选项组合游戏类的创建。这些游戏包括已经出现的游戏和新游戏{·|{O |·}、{·|{O |·}、{·|{···}。{O |{O |·}，{O |{O |··}，{O |···························。{O，{·| O}{O |·}，{O，{O |··}{O，{O |·································。{O，{·| O}{O |·}。。。。第t天：所有这些组合游戏G和Rt选项的课堂-它被创造出来了。所以有一个是R R . . .  Rt . . . 安德烈=R∪ R∪ . . . ∪ Rt∪ . . .例2.5。

组合博弈的数量迅速增长：（1）列出R中的所有组合博弈。（2）认为在第3天的第四天，有超过6000个组合博弈存在（见例2.6）。获胜策略27EX。2.6 . 显示rt=| rt |以超指数速度增长：rt>2rt-1（t=1，2，…）（提示：具有n=|S |元素的有限集S包含2个子集。）4.制胜策略组合游戏的开始是L或R第一步。这是第一个玩家。另一个玩家是第二个玩家。两人交替比赛的正常获胜规则是：（NR）如果一名球员∈ {L，R}无法移动，玩家i已失败，另一名玩家被宣布为赢家。例如，国际象棋比赛是按照正常规则进行的：国王的失败意味着比赛的失败（见例2.1）。备注2.3（错误）。米斯厄尔规则宣布没有移动的玩家是游戏的赢家。对于球员i来说，一个获胜的策略是一个移动（可选）选择规则，以确保我成为赢家。定理2.1。在任何组合游戏G中，第一个或第二个玩家都有一个整体获胜策略。证据我们用数学归纳法证明了这个定理。在t=0的情况下，我们有g=O={·|·}。因为第一个玩家在O中没有移动，第二个玩家在正常游戏中自动成为赢家，因此有一个简单的赢家策略。根据米斯规则，第一名玩家获胜。现在假设t≥ 1并且该定理适用于t天创建的所有游戏- 1或之前。考虑G中的rST播放器，并确保它是R.（L的参数将完全一样）！如果R没有选择权，在正常比赛中，L是宣布的赢家，而R是宣布的失利比赛中的赢家。

不管怎样，G都有一个肯定的赢家。如果选项存在，归纳假说认为，R的每个选项都会导致一种情况，即第一个或第二个玩家都会有赢家策略。28 2. 组合游戏如果（在l east）有一个选项GR，第二个玩家作为赢家，RCA可以选择这个选项并作为GR中的第二个玩家获胜。另一方面，如果所有的o f R选项都以第一个玩家作为赢家，则没有什么可以阻止l获胜。所以最初的第二名球员L有一个赢得比赛的总体策略。请注意，定理2.1的证明在以下意义上是有建设性的：（1）玩家i以v（Gi）=+1标记所有选项Giin G，将i作为赢家，并设置v（Gi）=-1否则。（2） 玩家i遵循策略移动到v值最高的选项。（3） 如果一个成功的策略对我来说是存在的，那么策略（2）对我来说就是一个胜利的策略。然而，读者必须注意。在现实生活中，制胜策略的具体组合可能是一项非常困难的任务，例如2.7（德布鲁因的游戏）。两个p层选择一个自然数n≥ 写下自己所有的数字1，2，3，N- 游戏者的一个动作是将其中一个数字s与它的所有（适当或不适当）除数连在一起，直到出现为止。请注意，在非正规比赛中，第一名球员的获胜策略是存在的。事实上，如果第二个玩家有“1”，第一个玩家可以在第一步删除“1”，然后（现在是第二个玩家）使用该策略并获胜。遗憾的是，目前还没有一种计算获胜策略的切实有效的方法。备注2.4。如果国际象棋是用统一规则下的，那么两个棋手中的一个就有一个获胜的策略。不幸的是，我们不知道它长什么样。

甚至不知道哪名球员是潜在的保证赢家。4.1. 练习打球。虽然获胜策略原则上可以计算（见定理2.1的证明），但许多游戏的组合结构非常复杂，即使是今天的计算机也无法有效地执行计算。5.博弈代数29在实践中，一个玩家我将按照以下v-贪婪策略进行：（vgi）分配一个质量估计v（Gi）∈ 选择所有选项，然后选择v值最高的选项。质量评估v不一定由游戏的绝对值来确定，但可能会反映以前的经验和其他考虑因素。一旦质量指标被认为是“合理的”，那么期望游戏按照与这些指标相关的贪婪策略发展或许是很自然的。例2.8。一种流行的经验法则评估p层W的国际象棋配置σ的质量，例如，通过将数字权重v分配给棋盘上的白色棋子。例如：v（兵）=1v（主教）=3v（骑士）=3v（城堡）=4.5v（女王）=9。式中，v（σ）是白色棋子的总重量，一个v-贪婪的玩家将选择一个最大值v（σ）的配置σ。（当然，球员B也可以对黑色棋子进行类似的评估。）5.博弈代数对于本章的其余部分，我们将（除非另有明确说明）假设：o所考虑的组合自然博弈是按照正常的获胜规则进行的。组合对策的集合R有一个代数结构，允许我们将对策视为广义数。本节将简要介绍这个想法。此外，国际象棋计算机程序也遵循这一理念（更多），在高度推荐的论文《J.H.康威，关于数字和游戏》中可以找到更多。A.K.彼得斯，2000年3月2日。组合博弈论。我们首先定义gameG={GL，GL。

.| GR，GR，…}∈ 比赛开始了(-G） 球员L和R交换角色：L扮演“右t”，R扮演“左”球员。所以我们递归地得到了否定对策-O=O-G={-GR，-GR.|-德国劳埃德船级社，-GL，…}如果G6=O，也-G是一个组合博弈，在e上有代数规则G=-(-G） 。附加游戏G和H的总和G+H是一个玩家i∈ {L，R}可以选择在G或H上玩。这意味着ati选择G中的一个选项或H中的一个选项，并相应地将游戏还原为G+H或G+Hi。请读者验证进一步的代数规则：G+H=H+G（G+H）+K=G+（H+K）G+O=G- H=G+(-H） 。例2.9。第二名选手赢得G- G在正常的游戏中，使用非凡的策略：o模仿第一个玩家的每一个动作。当第一名玩家选择Giin G选项时，第二名玩家将回答该选项(-Gi）在(-G） 等等5.1。合作游戏。受Ex.2.9的启发，我们说组合对策G和H是全等的（符号：“G≡ H”）如果（C）G-H由第二名选手（在正常比赛中）获胜。博弈代数，尤其是G≡ O表示G被第二个玩家赢了。定理2。2（同余定理）。为了所有的G，H，K∈ R有：（a）如果G≡ H、 然后H≡ G.（b）如果G≡ H、 然后G+K≡ H+K.（c）如果G≡ H和H≡ K、 THEN G≡ K.证据。com变异性规则（a）的验证留给读者。为了看到（b）是真的，我们考虑GAMM＝（G+K）。- （H+K）=G+K-H- K=（G）- H） +（K）-K） 。游戏K-K总是能被第二个玩家赢（例2.9）。因此，如果第二个玩家能够赢得G- H、 显然，M也是：o第二个玩家可以将各自的获胜策略应用于G-H和K- 传递性规则（c）的证明是相似的。

根据假设，gameT=（G- K） +(-H+H）=（G- H） +（H）- K） 可以由第二个p层赢得。我们必须证明第二名选手能赢- 假设与之相反的是：- k6≡ O是真的，游戏- K可能不是第一个选手赢的。然后，第一名球员可以从G中的胜利开始- 当第二个玩家在G中移动时，继续温斯顿策略- K.如果第二个玩家移动到K-K、 第一名球员在那里成为第二名，因此肯定会在K上获胜-K因此，第一个玩家将赢得T，但这与假设相矛盾。因此我们得出结论，G- K≡ 你必须坚持住。同余类。对于任何G∈ R、 全等对策的类是[G]={H∈ R | G≡ H} 。定理2.2表示，对于同余类es:[G]+[H]=[G+H]和[G]可以有意义地定义加法和反求-[H] =[G- H] .32.2。特别是，我们得到了熟悉的代数规则[G]- [G] =[G- G] =[O]，其中[O]是第二个玩家赢得的所有组合游戏的类别。因此，我们可以为玩家重新设定最佳策略（根据正常规则）：o获胜策略：采取行动G7→ G′到一个选项G′∈ [O] .5.2。战略对等。假设组合对策G和H在策略上是等价的~ H”）如果以下陈述之一为真：（SE）G和H可由第一名玩家（即G6）赢得≡ O 6≡ H） 。（SE）G和H可由第二名玩家赢得（即G≡ O≡ H） 。定理2.3（战略对等）。全等对策G，H∈ 罕见的战略等价物，例如≡ H==> G~ H.证据。我们声称战略上不等价的对策G和H不可能是一致的。例如，假设第一个玩家赢了s G（即G 6）≡ O） ，第二名玩家赢得H（即H≡ 因此(-H）≡ O） 。

我们将讨论第一个玩家对G的获胜策略-H、 也就是说G6≡ H.事实上，第一个玩家可以从G的制胜策略开始。一旦第二个玩家继续前进(-H） 第一名球员，现在是第二名球员(-H） ，在那里获胜。因此，第一名选手将获得全面胜利。6.不偏不倚的博弈组合博弈G被称为不偏不倚的（或中立的），如果双方都有相同的选择。形式定义是递归的：oO={·|··}是公正的。oG={A，B，…，T|A，B，…}如果所有选项A，B，他们不公正。注意公平博弈G和H的以下规则：（1）G=-因此G+G=G- G∈ [O] .6。游戏33（2）G+H是游戏的一部分。Nim是典型的公平博弈（我们将在下面的斯普拉格隆迪定理2.4中看到）。为了使这种说法正式化，我们使用了符号*n表示一个nim游戏相对于一组n=|n |元素的n。选择*n是thenim游戏*0, *1.*（n）- 1).此外，G=*n+*n+…+*NK是Ex.2.3中描述的n im游戏，有大小为n，n，…，的k堆，nk。例2.10。展示前2的青蛙游戏。4是不艺术的。我们现在确定了a、b、c……的mex（“最小排除值”），t是最小的自然数g，它不等于a，b，c，t：（11）mex{a，b，c，…，t}=min{g≥ 0 | g/∈ {a，b，c，…，t}，引理2.1中陈述了重要的观察结果。引理2.1。让a，b，c。不能是任意的自然数。然后一个hasG={*A.*B*C*t|*A.*B*C*t}≡ *mex{a，b，c，…}，即带有nim选项的公平博弈G*A.*B*C*t相当于简单的nim游戏*m=mex{a，b，c，…}。证据鉴于*m=- * m、 我们必须展示：G+*M≡ O、 也就是说，第二名玩家赢得G+*M