不完美回忆下的序贯均衡：定义与应用

ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月→→不完全回忆博弈的序贯均衡Joseph Y.康奈尔大学哈尔彭RAFAEL PASS，康奈尔大学（康奈尔理工学院）虽然序列均衡的定义可以不加改变地应用于不完美回忆的游戏，但这样做会导致不恰当的结果。我们重新定义了序贯均衡，使其定义与完美回忆博弈中的标准定义一致，同时在不完美回忆博弈中仍然给出合理的结果这个定义可以被看作是试图捕捉一个事前顺序均衡的概念这里的情况是，参与者在游戏开始前选择他们的策略，并致力于它，但他们选择的方式是，即使在均衡路径之外，它仍然是最优的一个临时顺序的概念平衡也被考虑。22CCS概念：·网络网络协议;·计算理论、博弈论和机制设计;附加关键词和短语：心不在焉，不完美的回忆，顺序平衡ACM参考格式：Joseph Y.Halpern和Rafael Pass2021年不完全回忆博弈中的序贯均衡 ACM Trans.Comput. 9、4、第二十二条（2021年10月），26页。https://doi.org/10.1145/34850021介绍序贯均衡[Kreps and Wilson1982]是外延形式博弈中最常见的解概念之一它试图捕捉这样一种直觉，即代理人不仅在均衡路径上，而且在均衡路径之外都是最优考虑到偏离均衡路径的情况的解决方案概念很重要，例如，消除由于不可信威胁而产生的纳什均衡不幸的是，序列均衡仅在这篇文章的一个较短的初步版本出现在第15届知识表示和推理原理国际会议（KR'16）的会议记录J. Y. Halpern部分得到了NSF资助IIS-0534064、IIS-0812045、IIS-0911036和CCF-1214844，以及AFOSR资助FA 9550 -08-1-0438、FA 9550 -09-1-0266和FA 9550 -12-1-0040和ARO资助W 911 NF-09-1-0281的支持R. 帕斯的部分支持者是阿尔弗雷德·P。Sloan Fellowship，a Microsoft New Faculty Fellowship，NSFAwards CNS-1217821 and CCF-1214844，NSF CAREER Award CCF-0746990，AFOSR Award FA9550-08-1-0197，AFOSR YIP授予FA 9550 -10-1-0093，BSF授予2006317，DARPA和AFRL根据合同FA 8750 -11-2-0211。本文件中包含的观点和结论是作者的观点和结论，不应被解释为国防高级研究计划局或美国的官方政策，无论是明示的还是暗示的。政府的作者Y. Halpern，计算机科学系，康奈尔大学，伊萨卡，纽约14853;电子邮件：cs.cornell.edu; R。Pass，ComputerScience Department，Cornell University（Cornell Tech），New York，NY 10044;email：rafael@cs.cornell.edu.允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2021版权归所有者/作者所有授权给ACM的出版权2167-8375/2021/10-ART22$15.00https://doi.org/10.1145/3485002ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月二十二：2J. Y. Halpern和R.通过图1.一、不完美回忆的微妙之处，由匹配性质游戏说明完美记忆游戏，玩家记住他们所做的所有动作和他们所观察到的。完美回忆在实践中似乎是一个不合理的假设即使是一个相对较短的纸牌游戏，如桥牌。在游戏进行到一半的时候，大多数人都不记得完整的叫牌顺序和完整的出牌过程（尽管这可能是高度相关的信息！）。事实上，更一般地说，我们不希望大多数人在比大多数博弈论论文中考虑的标准两步或三步博弈更长的博弈中表现出完美然而，作为这些解决方案概念基础的直觉，即参与者即使在偏离均衡路径的情况下也应该进行最优博弈，似乎在不完美回忆的博弈中也是有意义的一个回忆不完美的智能体仍然希望在所有情况下都能发挥最佳虽然一般来说，计算什么是最优博弈可能很复杂（事实上，序列均衡的定义本身就很复杂），但在许多博弈中，这并不难做到。然而，Piccione和Rubinstein [1997 b]的工作（从现在开始公关）提出了一些微妙之处。下面两个例子，都是由于公关，说明了问题。实施例1.1. 考虑图1中描述的单人游戏，我们称之为“匹配-自然”游戏，其中自然进行初始移动，向左或向右，然后代理移动。智能体可以在自然移动后立即停止游戏（通过玩S）如果代理人继续，它最好通过匹配自然的初始移动（因此得名）。然而，尽管智能体最初知道自然的移动（在x1和x2处），但如果他继续，他就会忘记它。因此，这是一个不完美回忆的游戏。不难看出，使期望效用最大化的策略在节点x1处选择行动S，在节点x2处选择行动B，在由x3和x4组成的信息集Xm处选择行动R。我们称之为策略B。设b是在x1处选择行动B，在x2处选择行动S，在Xm处选择L的策略。 正如PR所指出的，如果到达了节点x1，并且代理正在使用b，那么他不会觉得b是最优的，条件是在x1;他会想使用b。事实上，没有一个单一的策略，代理人可以使用，他会觉得在x1和x2都是最佳的。这里的问题是，如果智能体开始使用策略b（在x1处使用S，在x2处使用B，然后在信息集Xm处使用R），然后在到达x1时切换到b（在x1处使用B，在Xm处使用L）（但在到达x2时继续使用b），他最终使用的“策略”不尊重博弈的信息结构，因为他在两个节点处采取不同的不完全回忆博弈的序贯均衡二十二：3ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月−图二、心不在焉的司机游戏在信息集合Xm中。[1]正如Halpern [1997]所指出的，如果智能体知道他在任何时候都在使用什么策略，并且他被允许改变策略，那么信息集在描述智能体所知道的信息方面就做得不好，因为智能体可以在同一信息集中的两个节点上使用不同的策略。 代理将在x3和x4处知道不同的东西，尽管它们在相同的信息集中。实施例1.2.下 面 这个游戏，通常被称为心不在焉的司机悖论，说明了一个不同的问题。PR描述如下：一个人深夜坐在酒吧里计划他的午夜回家之旅 为了回家，他不得不走高速公路，在第二个出口下车。 在第一个出口处转弯会导致灾难性的区域（收益为0）。在第二个出口处转弯会产生最高的回报（收益4）。如果他继续走到第二个出口，他将到达高速公路的尽头，并找到一家旅馆过夜（收益1）。司机心不在焉，也意识到了这一点。当他到达一个十字路口时，他不知道这是第一个十字路口还是第二个十字路口，也不记得他经过了多少个十字路口。图2中的博弈树描述了这种情况。显然，司机必须做出的唯一决定是，当他到达出口时是否下车一个简单的计算表明，司机然而，假设司机开始使用最优策略，当他到达信息集时，他认为概率α在e1。然后，他考虑是否应该转换到一个新的策略，在这个策略中，他以概率p退出。另一个简单的计算表明，他的预期收益是α（（1 − p）2+ 4 p（1 − p））+（1 − α）（（1 − p）+4 p）= 1+（3 − α）p − 3αp2。（一）当p=min（ 1，（ 3α）/ 6α）时，等式（1）最大化，等式仅在α=1时成立。因此，除非驾驶员将概率1归因于在e1，否则当他到达信息集时，他应该想要改变 这意味着只要α <1，我们就不能指望在这个博弈中找到一个序列均衡。一旦到达信息集，驾驶员就会想要改变策略。虽然序列均衡的定义可以不加改变地应用于不完美回忆的游戏，但这样做会导致不恰当的结果。例如，不难看出，[1]通常，我们将纯策略b作为一个函数，它将博弈树中的每个节点关联为一步棋，使得如果x和x ∈ N是同一信息集中的两个节点，则b（x）= b（x ∈ N）。 我们偶尔会滥用符号，为一个不一定满足后一个条件的函数b_n写上“策略”even，也就是说，如果x和x_n在同一个信息集中，我们可能会有b_n（x）b_n（x_n）even。二十二：4J. Y. Halpern和R.通过ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月在比赛性质的博弈中没有序列均衡，但是，也许更严重的是，正如我们指出的，序列均衡所考虑的偏差与博弈的信息结构不相容在这篇文章中，我们提出了一个定义的顺序equilibrium，符合标准的定义，在游戏的完美回忆，同时仍然给出合理的结果，在游戏的不完美回忆。 我们的定义与Hillas和Kvasov [2020 a，2020 b]同时开发的定义有一些共同之处;本文第7节讨论了相似之处和差异。正如我们将清楚看到的那样，约翰·希拉斯根据他与克瓦索夫的工作所作的评论对我们目前的一些定义产生了重大影响众所周知，要定义完美回忆游戏中的序贯均衡，一个困难是确定参与者的信念，即她有多大可能出现在均衡路径上的信息中的这对于应对不可信的威胁是必要的 在不完美回忆的游戏中，即使在均衡路径上的信息集中，确定代理人的信念也是困难的。事实上，我们认为，得到一个很好的定义顺序均衡的不完美的回忆游戏需要一个明确的解释的意义，信息集和限制，他们施加的知识和策略的球员。考虑在信息集上定义信念的问题根据Selten [1975]使用的技术，也被PR采用，如果驾驶员使用最佳策略，则e1的概率应为3/ 5，e2的概率应为2/ 5。根据最优策略，达到e1的概率为1，达到e2的概率为2/ 3。因此，1和2/ 3应该给出在e1和e2的相对概率。 将这些数字归一化，我们得到3/5和2/5，结果是不存在序贯均衡。（Kline [2005]也提出了这一点正如PR和Aumann，Hart和Perry（AHP）[1997]所示，这种归因信念的方式保证了驾驶员不想使用任何偏离最佳策略的单一行动。也就是说，除了在一个节点上，没有与最优策略相同的“策略”b，并且具有比最优策略更高的收益。PR称之为修正的多自方法，而AHP称之为行动最优。层次分析法表明，这种方法解决了悖论。然而，Piccione和Rubinstein [1997 a]认为，很难证明代理人不能改变她未来行为的假设是合理的。（关于这个问题的进一步讨论，也可参见Gilboa[1997]和Lipman [1997]虽然代理人应如何归因于信仰的问题已被认为是在文学的长度，一个问题，已得到较少的关注是什么样的策略，代理人可以偏离在一个信息集。正如我们将要展示的，在序列均衡的概念背后有着不同的直觉 虽然在完美回忆的游戏中，它们都导致了相同的定义，但在不完美回忆的游戏中，情况不再如此。我们的定义可以被看作是试图捕捉一个事前序列均衡的概念。这里的情况是，参与者在游戏开始前选择了他们的策略，并致力于这些策略，而且他们选择策略的方式是，即使偏离均衡路径，他们也能保持最优 我们的事前序贯均衡概念不允许打破博弈信息结构的变化。例如，在匹配性质博弈中，我们不允许以策略b开始的代理在节点x2处切换到策略b。我们想要一个即使偏离均衡路径也是最优的策略，但我们只考虑尊重博弈信息结构的策略在完美回忆的游戏中，这种事前的顺序均衡概念与我们所认为的一致。这里称之为临时顺序均衡，其中代理人可以潜在地改变每个信息集的策略，从而可能打破信息结构（例如，在匹配性质博弈中，从b到b的转换可以在x3在不完全回忆博弈中，定义一个合理的临时序列均衡概念会引发一些概念性问题。 我们将在第6节讨论这些问题，并展示事前概念如何为定义一种明确允许在信息集上重新考虑的方法提供一些见解，从而可以被视为捕获临时序列均衡。不完全回忆博弈的序贯均衡二十二：5ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月在处理不完全回忆时，我们必须面对最后一个问题众所周知，在完全回忆博弈中，行为策略和混合策略是结果等价的[Kuhn 1953]（正式定义见第2.3节），但是一旦我们进入不完全回忆博弈，行为策略和混合策略都不足以达到纳什均衡;为了证明纳什均衡的存在，我们必须进入行为策略混合物-即行为策略上的分布[Isbell 1957]。因此，我们在本文中使用行为策略混合物，这导致了一些额外的技术复杂性。我们的事前序列均衡和临时序列均衡的概念都假定选择的基本目标是一种策略。 但正如匹配性质博弈已经表明的那样，如果智能体可以在任意信息集上从一种策略切换到另一种策略，就会出现概念上的问题。粗略地说，我们在事前概念中通过将选择限制在初始信息集来处理这个问题，我们在过渡概念中通过考虑与初始博弈相关的不同博弈来处理这个问题，在这种情况下，转换在某种意义上是不太成问题的。处理这个问题的另一种方法是将行动而不是战略视为选择的基本对象这基本上是做什么，例如，在公关的修改多自我的方法，并在所采取的方法层次分析法Lambert等人[2019]基于这种直觉，在不完美回忆游戏中定义了一些均衡概念通过采取行动作为选择的对象，他们可以限制到行为策略，而不需要考虑行为策略的混合。 虽然他们的概念和我们的一样，与完美回忆游戏中的标准定义一致，但他们是基于截然不同的直觉（一般来说，在不完美回忆游戏中与我们的不一致）。本文的其余部分组织如下。在第2节中，我们简要地扩展了一个数字前面提到的问题，如行为策略混合物;这些术语对于理解我们的（事前）序列均衡的正式定义是必要在第3节中，我们描述了我们的归因信念的方法，这在我们的定义中也起着关键作用。在第4节中，我们定义了不完美回忆博弈中的完美均衡;我们的定义与Selten [1975]的定义相同，除了我们处理的是行为策略混合物。 这构成了我们在第5节中给出的事前序列均衡定义的基础。然后我们在第6节讨论过渡序列均衡。 我们在第7节结束时讨论了相关的工作和一些相关的主题。2预赛在本节中，我们将讨论一些与序列均衡的定义相关的问题：不完美回忆和心不在焉，参与者知道什么，行为与行为。混合策略和信念归属。2.1不完全回忆与心不在焉我们假设读者熟悉扩展形式游戏的标准定义和此类游戏中的完美回忆（例如，参见Osborne和Rubinstein [1994]的正式处理）。 重新调用一个博弈，如果对于所有参与者i和参与者i的信息集X中的所有节点x1和x2，如果h j是导致x j的历史，j = 1，2，参与者i在h1和h2中采取了相同的行动，并经历了相同的信息集序列，则称该博弈表现出完美回忆。如果一个游戏没有表现出完美回忆，它被称为不完美回忆游戏。不完全回忆的一种特殊情况是心不在焉的记忆;心不在焉的记忆发生在相同的信息集中的两个历史h和h_n，并且h_n是h的一个prefix时。心不在焉和驾驶员的游戏会导致心不在焉，而比赛性质的游戏则不会。请注意，在Osborne和Rubinstein [1994]之后，我们更早地谈到了信息集中的历史，而不是节点。 我们可以互换使用这两个词，但值得回顾的是，从形式上讲，历史是一系列行动。每个历史都指向博弈树中的一个唯一节点如果历史二十二：6J. Y. Halpern和R.通过ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月−h是h的一个prefix（我们可以讨论prefixhe r e，因为历史是一个序列），而h所指向的节点是h所指向的节点的博弈树中的祖先。我们有时候会说一个节点在一个历史上;这只是意味着历史经过博弈树中的那个节点2.2战略知识大多数博弈论论文中的标准（通常是隐含的）假设是，参与者知道他们的策略。这个假设在博弈论的认知分析中往往是明确的;它也出现在许多关于不完美回忆的讨论为了简单起见，考虑一个玩家的游戏，即决策问题，具有完美回忆。 那么可以说，参与者并不真正需要知道他们的策略。毕竟，一个理性的参与者可以在每个信息集X上计算出事先的最优策略，然后在X上采取它推荐的行动。如果最优走法不是唯一的，那就没有问题任何最优走法的选择都可以。当我们进入不完美回忆的游戏时，情况就发生了变化考虑一下比赛性质的游戏。 如果智能体不能回忆起他的策略，那么在x2时重新考虑的任何讨论当然都变得毫无意义;智能体没有理由认为他会在x4时意识到他应该采取行动R. 但是，如果智能体甚至不能回忆起他最初的策略选择（因此不能承诺一个策略），那么策略b（在x1处玩B，在x2处玩S，在X处玩R）可能不是最优的。当代理人到达S时，他可能会忘记他应该采取R。可以说，只要智能体记住了博弈的结构，那么，就像在完美回忆的情况下一样，他可以在每个信息集X重新计算事前最优策略，并在X处采取它推荐的行动。然而，我们现在遇到了一个问题，如果最优策略不是唯一的。在不完全回忆的情况下，如果存在联系，那么代理人做出的选择可能很重要例如，假设我们将z4和z5的收益分别改为6和3，这样博弈树的左右两边就完全对称了。 那么，很难想象一个不记得自己采取了什么策略的行动者，会知道在X点采取L还是R。一个谨慎的代理人很可能决定在x1和x2两个位置上使用S！对于序列均衡的事前概念，假设代理人最初承诺采取一种策略（并且在博弈树的稍后节点上知道这种策略）似乎是合理的 但我们强调，如果我们允许在以后的信息集上重新考虑策略，这个假设是有问题的，正如我们在第6节中所做的那样。2.3混合策略与行为策略有两种类型的策略，涉及随机化，已被认为是在广泛的形式的游戏。广义博弈中的混合策略是纯策略的概率测度。因此，我们可以把混合策略看作是对应于这样一种情况：一个参与者抛硬币，并在游戏开始时根据抛硬币的结果选择一个纯策略，然后在整个游戏中使用该纯策略 通过对比，在行为策略中，玩家在每个信息集上随机化，随机选择在该信息集上玩的动作。形式上，行为策略是从信息集到动作分布的函数（我们可以将纯策略与行为策略的特殊情况区分开来，行为策略在每个信息集上的某个行动的概率都因此，我们可以将参与人i的行为策略看作是由参与人i的信息集索引的概率度量的集合;对于参与人i的每个信息集X，在信息集X上可以执行的动作都有一个概率度量。众所周知，在完全回忆游戏中，混合策略和行为策略是结果相当。也就是说，给定参与人i的混合策略b，存在行为策略使得无论剩余参与者使用什么策略配置文件（混合或行为）b-i不完全回忆博弈的序贯均衡二十二：7ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月––bBC（b，bi）和（b，bi）在两个水平上诱导相同的分化（i. 例如， 终端历史），相反，对于每个混合策略b，存在一个行为策略b，使得对于所有的策略p，对于主策略r，（b，bi）和（b，bi）的结果是等价的。（参见Osborne和Rubinstein [1994]的工作以获得更多细节。同样众所周知的是，当我们进入不完美回忆的游戏时，这种等价性就被打破了在没有心不在焉的不完美回忆博弈中，对于每一个行为策略，都存在一个结果等价的混合策略;然而，也存在一个没有心不在焉的不完美回忆博弈，在这个博弈中，混合策略不是结果等价的行为策略[Isbell1957]。正如PR所指出的那样，一旦我们允许心不在焉，可能会有一些与任何混合策略不等价的口头策略 在心不在焉的司机博弈中，两个纯策略分别达到z1和z3。因此，没有混合策略可以达到z2，而任何行为策略，把积极的概率在B和E都有一些积极的概率达到z2。后一个观察结果也表明，两种纯策略的非平凡混合并不等同于任何行为策略。纳什证明了每个有限博弈在混合策略下都有一个纳什均衡 根据前面提到的结果等价性，在完全回忆博弈中，行为策略也存在纳什均衡。在不完美回忆的游戏中，情况不再[Isbell1957]给出了一个不完美回忆的游戏的例子，在行为策略或混合策略中没有纳什均衡。因此，为了处理不完美回忆的游戏，一般来说，我们需要允许行为策略混合[Isbell1957]，这是行为策略的分布。[2]正如Kaneko和Kline（1995）所指出的，行为策略混合包括两种随机化：在游戏之前和游戏过程中。 行为策略是行为策略混合的特殊情况，其中随机化仅在游戏过程中发生;混合策略是随机化仅在开始时发生的特殊情况。在本文的其余部分，当我们说我们尝试一致地使用符号c来表示行为策略混合物并表示不是混合物的行为策略我们用Γ和Γ来表示博弈中博弈者的最优策略和最优策略混合物的集合。有无数种行为策略，所以一种行为策略混合物，行为策略上的概率，可能是一个相当复杂的对象。认为资源有限的玩家在使用它们似乎是不合理的如前所述，在没有心不在焉的不完美回忆游戏中，我们不需要它们;考虑混合策略就足够了然而，在心不在焉的游戏中，它们似乎是不可避免的。幸运的是，当使用行为策略混合时，参与者只需要混合200多种行为策略Alpern [1988]证明了以下结果。我在2.1上写 如果Γ是一个有限博弈，则存在一个常数DΓ，它只依赖于Γ，使得每个行为策略混合物的结果等价于一个行为策略混合物，该行为策略混合物混合了至多DΓ个策略。32Isbell [1957]实际上称它们为混合策略，Selten [1975]称它们为行为策略混合物，Hillas和Kvasov [2020a，2020b]（HK from now on）称之为一般策略。 我们遵循Selten，但写“行为”而不是“行为”，以便与我们在其他地方的术语保持一致。[3] Alpern [1988]陈述了一个较弱的结果：两人零和博弈中纳什均衡的组成部分是等价于有限数量的行为策略的混合然而，他的证明表明了我们所主张的更强有力的结果。我们感谢John Hillas为我们指出Alpern二十二：8J. Y. Halpern和R.通过ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月.∈×.∈.命题2.1的一个技术结论是，在有限博弈Γ中，参与者i有d i个信息集，并且在每个信息集上最多可以采取k i个动作，我们可以用（[0，1][0，1] kidi）DΓ的元素来识别参与者i的行为策略混合。，（aD'，bD'），其中a1，.，a Dr [0，1]，a i= 1，b j是参与人i的行为策略，因此在[0，1] kidi中，对于j = 1，... ，DΓ. 众所周知，有限维空间中紧致集的凸包是闭的[Rockafellar1970]，因此有限博弈Γ的行为策略混合集也是闭的，因而也是紧致的。解决方案的概念，如纳什均衡和序贯均衡是不敏感的替代战略的结果等效的战略。例如，如果策略配置文件b是一个Nash（respectively，sequential）均衡，并且bi是结果等价于bi的，则bi也是一个Nash（相应地，序列）均衡。我们定义的解决方案概念也是如此。因此，根据命题2.1，当考虑一个博弈Γ时，我们只考虑行为策略混合，其支持最多包含DΓ行为策略。序贯均衡通常用行为策略来定义，而不是混合策略。这是因为它通常是作为一个临时概念提出的也就是说，玩家通过比较他们正在做的事情和他们本来可以做的事情，来检查每个信息集是否是最佳的。由于参与者可以随机选择，因此将其视为使用行为策略而不是混合策略是有意义虽然我们认为我们的顺序均衡的概念作为一个事前的概念，我们允许代理使用行为策略的混合物。解释是代理人在开始时随机选择行为策略（与游戏的信息结构兼容的然后，智能体承诺采用这种口头策略，并在整个游戏中遵循它智能体可以在每个信息集上进行随机化，但他必须根据自己事先的行为策略选择进行随机化。2.4策略的期望效用每个行为策略混合轮廓c在叶子上诱导概率测度πc我们在一个博弈中确定一个节点x，事件由从x可以到达的叶子组成。在Grove和Halpern [1997]的语言中，我们用到达x的事件来识别x。给定这个标识，我们将πc（x）作为使用策略c时到达x之后的叶子的概率。为了讨论的目的，固定一个博弈Γ，让Z表示叶子（即，的终端历史）。通常，我们可以将EUi（c）取为zZπc（z）ui（z）。如果Y是叶子的子集，使得πc（Y）>0，那么计算参与者i在Y条件下的c的期望效用同样简单。该公司所做的只是欧盟i（c）|Y）=π c（z|Y）u i（z）.z∈Y也就是说，参与人i在Y条件下c的期望效用等于在Y中所有终端历史z上c在Y条件下的概率乘以z对i的效用之和。3不完全回忆博弈中的信念体系修复一个游戏Kreps和Wilson [1982]定义了一个关于Γ的信念系统μ，它是一个函数，该函数将Γ中的每个信息集X与X中历史的概率μ X相关联。 PR非常明确地将μ X（x）解释为到达节点x的概率，条件是到达X。就像Kreps和威尔逊，他们需要这样做。x∈XμX（x）=1.不完全回忆博弈的序贯均衡二十二：9ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月.∈∈∈..e{1}..x∈X。x∈X图三.在信息集上计算信念。由于我们的目标是定义一个序列理性的事前概念，我们将μX（x）解释为到达x的概率，条件是到达X。我们不再要求xXμX（x）=1. 虽然这一性质在完美回忆的游戏中成立，但在不完美回忆的游戏中，如果X包含两个节点，并且它们都在以正概率进行的历史上，则概率之和将大于1。例如，在心不在焉的驾驶员博弈中，事前最优策略以1的概率达到e 1，以2 / 3的概率达到e 2。第三章. 1（[Halpern1997]）。 给定一个信息集X，X的上一级由所有这些节点组成，使得在从根开始的某条路径上没有严格在x之前的节点x ∈ X。请注意，对于没有表现出心不在焉的游戏，我们有X=X。 这对于心不在焉来说是不正确的--例如，X=e。而不是要求μX（x）=1，我们要求，<$μX（x）=1-也就是说，在到达X的条件下，到达X的上边界的概率是1。由于在完美回忆博弈中X= X，这个要求推广了Kreps和Wilson的要求。此外，如果我们以显而易见的方式定义μ X，则该要求成立。ClAIM 3.2. 如果X是策略剖面c以正概率到达的信息集且dμX（x）=πc（x|X），x∈X<$μX（x）=1.PRo F. 根据定义，x∈X<$μX（x）= x∈X<$πc（x|X）=πc（X<$|X）=1。□有了信念系统，Kreps和Wilson就足以定义给定行为策略的终端历史的概率，条件是到达信息集X。不幸的是，如果我们被给予一个行为策略混合物c，这是不够的，因为到达X可能会导致一个智能体更新她关于其他智能体最初选择的行为策略的信念。以下示例说明了此问题。实施例3.3. 考虑一个博弈，其中参与人1在x0处向左或向右（L或R）移动，然后参与人2在节点x1和x2处向左或向右（lt或rt）移动，然后参与人1在节点x3-x6处向左或向右（4或r）移动，这形成了参与人1的信息集。忽略信息集，博弈如图3所示;假设参与者获得相同的收益。首先假设（这是众所周知的），参与人1使用的行为策略混合物c1的播放L;4与二十二：J. Y. Halpern和R.通过ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月--关于我们11∈.ix∈X3–+3=301是18倍以上的可能性达到通过11概率为1/2，以1/2的概率玩R; r，参与人2学习参与人1的第一步（因此x 1和x 2是独立的信息集）。显然在x1时，参与人2应该确定参与人1最初选择L;4，而在x2时，参与人2应该确定参与人1选择R;r。接下来假设参与人1仍然下c1，但是参与人2没有学会参与人1我们有一个信息集X=x1，x2在X点，参与人2应该将概率1/ 2分配给x1和x2。但是参与人2仍然知道如果实际节点是x1，那么参与人1一定选择了L;4如果实际节点是x2，那么参与人1一定选择了R; r因此，给定收益，参与人2应该选择rt。最后，假设参与人1的策略是c2 = 2 b 1+ 1b 2，其中b 1是.9（L ; 4）+。1（R;r），3 3B2是。1（L; 4）+。9（R;r）。同样，2号博弈者不知道1号博弈者一个直截了当计算表明，达到x1的概率为2×。9+ 1×。1=19，x2是概率2×11×。93 3 30十一岁注意：x b而不是b2，所以在x1，参与人2应该相信参与人1以18的概率选择b1，19概率1。类似地，在x点，参与人2应该相信参与人1在选b1921概率2和b2的概率是9.如例3.3所示，智能体i在信息集中的节点上，但是每个节点x X与行为策略简档上的概率的关联。在我们的背景下，定义信仰体系还有一个额外的复杂性 对于序列均衡的事前概念，我们首先考虑计算这些信念，但在每个代理i选择了她的行为策略混合物中她将采取的行为策略之后;此外，我们假设我会记住她选择的行为策略。这个选择显然会影响她对信息集的信念 这些意见构成以下定义的基础。定义3.4.博弈Γ的广义信念系统是一个对（μ，ν），其中μ与参与者i的每个信息集X和i的行为策略bi相关联，在X中的节点上的概率μ bi，X使得<$μ b，X（x）= 1，ν与每个节点x ∈ X和行为策略bi相关联，在B −i中具有有限支持度的行为策略剖面上的概率ν bi，x。4本着克雷普斯和威尔逊的精神，我们将对与行为策略混合物的轮廓c相一致的在这种情况下，概率μbi，X（x）是在i最初选择策略bi的情况下到达节点x∈X的概率(we只有当bi支持ci）并且对于b<$i支持c−i，vbi，x（b<$i）是x是r的每个e由（bi，bi）（相对于其他最好的策略，我supportoffc−i）。很明显，我不应该把责任分配给一个不会的战略文件，一开始就被选中了 如例3.3所示，如果X可由（b i，c i）到达，则计算这些信念是简单的。为了处理（bi，ci）不可达的信息集，我们以与Kreps和Wilson相同的精神定义3.5.一个参与人i的行为策略b i是完全混合的，如果对于i的每个信息集X和在X处可以采取的行动a，b i赋予采取a的正概率。一个博弈策略混合是完全混合的，如果它的支持下的每个行为策略都是完全混合的。[4]在这篇文章的早期草稿中，我们考虑了一种信念评估，就像Kreps和Wilson的评估一样，也就是说，它只有μ分量。我们感谢约翰·希拉斯的评论，他强调需要考虑代理人i对行为策略b i的初始选择，以及i需要更新她对其他参与者选择行为策略的概率的信念，正如ν所捕获的那样，这在精神上与他与Kvasov的1不完全回忆博弈的序贯均衡二十二：ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月–μ μnb∈Bb，Xb，XiiBb我∈ib−−i−∈·|nn我 我 μ（x），其中B如果bbi∈Bi−i−i−i−i对于每一个完全混合的策略集，我们可以通过下式定义一个广义最优系统（μc集，ν c集）：以明显的方式进行条件化（如例3.3中所示）：如果bi处于c的上点，则μbi，X（x）就是πbi，c <$ （x个|X），且若b∈i在c − i的上顶点，则v ∈i，x（b∈i）恰为相关概率-我-–）π∗（x个|十）、达到x的策略配置文件（b，b）;更确切地说，v（b）=i−i（b i，b−i）。我− ibi，x−iπ（bi，c <$）（x|十）、我其思想是，如果（μ，ν）是（μc）的极限，则取（μ，ν）与c，vcn ）对于一些完全混合的行为策略混合物的序列cn收敛到c。问题是，为了定义μ bi，X，我们需要考虑某个序列μ bn，X，其中b n在cn的支撑下。我我我我们应该采取哪种行为策略如果序列c1，c2，. 行为策略混合物如果在c的最高点上，每个c都是一个策略b，则我我我n n支持ci的行为策略，使得集合Bi收敛到bi（即，对于所有λ>0，存在n，使得对于所有n∈N>n，Bn∈N中的所有策略都在bj的1/2以内，其中，我我通过在所有i的信息集X上取动作的概率度量之间的距离的总和，来测量代理i的两个行为策略b和b之间的距离在X处由b和b确定，且cn（Bn）收敛于ci（bi）。我们称Bn为bi在cn中的类似物。我我我在计算，我们考虑所有策略n并对这些信念进行根据bn在Bn中的相对权重，确定bn的最优值。我们在计算ν时也进行类似的处理。我我定义3.6.一个广义信念系统（μ，ν）与一个行为策略混合剖面c是一致的，如果存在一个完全混合的策略剖面序列c1，c2，… 收敛到c，使得如果（μ n，ν n）是由c n确定的广义信念系统，则对于支持c i和i的信息集X的每个行为策略bi，μ bi，X（x）=.cn（bn）nnnnn策略配置文件在c的支持下，则v我（b））是lim.nnci（bi）νn（（B）n），其中（B）− ）n是b的类似物−i 在CN。−i我我我注意，如果（μ，ν）与c一致，并且X是i的信息集，则我们关心μbi，X和νbi，x仅当bi在ci的支撑下。在这种情况下，可以将νbi，x视为确定a行为策略混合配置文件C的支持是（不一定严格）的子集，c−i. 如果c是行为策略剖面−i，则ν是平凡的：bi，x （b−i））= 1对所有x ∈ X。因此，如果我们仅限于行为策略（就像Kreps和Wilson所做的那样），就不需要ν给定一个广义信念系统（μ，ν）和一个信息集X，就像Kreps和Wilson，我们想定义一个概率分布Pbi，μ，ν，X，它可以被认为是从X开始，对X的信念由μbi，X确定，对除i之外的参与者在x X处所采取的策略的信念由νb，x确定，然后从X继续，参与者i切换到biin（而其他参与者采取由νbi，x确定的最佳策略混合配置文件）。对于每个终端历史z，如果没有前缀z在X中，则P bi，μ，ν，X（z） =0;否则，如果xz我是X中以z为前缀的最短历史，则Pbi，μ，ν，X（z）是μ（x）和概率（b，c））通向终端bibi，X z我−i在xz中开始时的历史z，其中ci是由vbi，xz确定的行为策略混合。如果c是一个行为策略b，并且，ν）与c一致，那么我们对Pbi，μ，ν，X的定义是（μbi）1998年，张晓波（X）GivenbyKrepsandWilson[1982]forgames of perfect recall. 正如我们所观察到的，在这种情况下，对于所有x X，νb，x（bi）=1，所以我们可以用bi代替ν。唯一的区别是，在完全回忆的博弈中，终端历史在X中最多有一个前缀。在不完美回忆的游戏中不再是这种情况，所以我们必须指定哪个前缀Lim是b的类似物用c是行为n→∞cn（Bn）bn，X我我我我我bi，xn→∞bi∈Bicn（Bn）bn，x二十二：J. Y. Halpern和R.通过ACM Transactions on Economics and Computation，卷。号94、第二十二条。出版日期：2021年10月−b我|− ii（−∈a≥.∈α π（bi，b−i）（xz（bi，b−i）|πbi，ci（xz|十）、 π（bii，b 1i），xz（z）+· · ·+πbi，ci（xz|十）、 π（b，bk），xz（z）选择。请注意，如果终端历史z在X中有前缀，则z在X中的最短前