通用博弈中的最优回复结构和均衡收敛

摘要

博弈论被广泛用于模拟相互作用的生物和社会系统。在某些情况下，博弈者可能会趋同于一个均衡，例如纳什均衡，但在另一些情况下，他们的战略动态会内生振荡。如果系统的设计不是为了鼓励趋同，那么我们可以先验地预期这两种行为中的哪一种呢？为了解决这个问题，我们采用了理论生态学中流行的一种方法来研究生态系统的稳定性： 我们根据可能代表现实世界博弈属性的约束条件随机生成回报矩阵。我们的研究表明，最优回复循环是博弈中的基本拓扑结构，它预示着六种著名的学习算法不会收敛，这些算法在生物学中得到了应用，或在人类玩家的实验中得到了支持。最优回复循环在复杂的竞争性博弈中占主导地位，这表明在这种情况下，均衡通常是一个不切实际的假设，我们必须明确地建立学习动态模型。

Introduction

博弈论是一套针对决策者之间战略互动的数学模型，可应用于各种问题，如合作的出现、语言的形成以及道路和互联网的拥堵。同样的数学工具也被用于生态学和种群生物学中的进化建模。一个长期存在的问题是，当玩家通过反复玩博弈进行学习时，他们是否会趋同于一个均衡点。人们对一般情况知之甚少，因为答案取决于博弈的属性和学习算法。在这里，我们引入了一种我们称之为最优回复结构的形式主义，它可以粗略度量各种学习算法在任何双人正态博弈中的收敛概率。生态学中的定性稳定性理论和使用雷诺数来理解流体动力学中的湍流都可以类比说明我们的方法在其他领域的实用性。

解决博弈论均衡收敛问题的标准方法是关注具有特殊数学性质的博弈类，选择它们作为现实世界情景的程式化模型。例如，在势博弈（potential games，也翻译成潜在博弈）中，单方面改变策略的所有收益差异都可以用一个全局势函数来表示; 拥塞博弈属于这一类，所以势博弈可以作为交通的程式化模型。势博弈中大多数学习算法收敛到一个纳什或相关的均衡在潜在的对策，在优势可解博弈（dominance-solvable game）、协调博弈（coordination game）、超模博弈（supermodular game）和弱非循环博弈（weakly acyclic game）中也是如此。研究具有特殊属性的博弈在机制设计等某一方玩家可以选择博弈形式的情况下是非常有用的。在这些情况下，也可以设计玩家将要使用的学习算法，并选择最有可能收敛到均衡的算法，例如在线拍卖和网络路由。

然而，在其他一些问题中，博弈和学习算法并不是设计出来的，而是由设置的内在性质决定的。例如，金融市场可以被看作是一场博弈，其中有许多可能的行动与交易者可以买卖的资产相对应。结果可能趋于均衡，也可能内生波动。如果系统的设计不是为了鼓励趋同，我们应该期待这两种行为中的哪一种？

为了解决这个问题，我们采用了一种在理论生态学和发育生物学中卓有成效、在物理学中也很普遍的方法。梅（May）的理论生态学开创性论文就是这种方法的一个例子。他研究了一组随机产生的捕食者-猎物相互作用，并将其作为一般生态系统的空模型。他的主要结果是，随机生态系统往往会随着规模的扩大而变得更加不稳定。当然，梅很清楚，真实的生态系统并不是随机的；相反，它们是由进化选择和其他力量塑造而成的。许多大型生态系统已经存在了很长时间，这表明它们实际上是稳定的。因此，这一矛盾表明，真实的生态系统并不是梅模型中使用的随机集合的典型成员，这就提出了一个重要的问题：这些生态系统究竟是如何变得不典型的，它们又是如何以及为什么进化成稳定的？45 年后的今天，对这一问题的正确回答仍然是一个活跃的研究课题。例如，约翰逊等人最近发现，真实的生态系统具有一种他们称之为营养相干性的特性，并证明将这种特性作为随机生成的生态系统集合的约束条件可以确保稳定性。

在这里，我们将类似的方法应用于博弈论，将随机生成的双人博弈集合作为一个空模型。出于可操作性的考虑，我们利用可以系统地枚举所有可能博弈的事实，研究正态博弈。在这里，我们详细研究了一个参数$G$，它可以调整两位博弈者收益的相关性。这可以调节博弈中的竞争强度，并将零和博弈作为 $G = -1$ 的一个特例。我们还简要介绍了如何构建其他约束条件，例如，研究潜在博弈的偏差。通过这种方法，我们可以看到偏离特定类别博弈会如何影响学习动态的稳定性。

随机生成的博弈和一般学习算法不具备允许精确求解的数学特性。为了克服这一局限性，我们开发了一种形式主义，以简单指标的函数形式获得收敛的近似概率。通过与流体力学的类比，我们可以清楚地了解这些近似解是如何发挥作用的。当流体被驱离平衡状态时，通常会从稳定流（或层流）过渡到不稳定流（或湍流）。描述流体动力学的纳维-斯托克斯方程没有解析解，但这种过渡可以用一个称为雷诺数 (7) 的非一维参数来粗略描述。雷诺数越大，发生湍流的可能性就越大。尽管这一预测并不精确—它只是一条经验法则—但却非常有用。我们对博弈的类似估计没有简单的封闭形式，但却具有类似的预测能力。与我们的方法类似的另一种方法是理论生态学中的定性稳定性理论 (6)。生态学中的许多模型都会考虑食物网中不同物种之间相互作用的程度。例如，这些模型会考虑兔子吃了多少草，狐狸吃了多少兔子。而定性稳定性方法只考虑捕食者与被捕食者之间关系的符号—兔子吃草，狐狸吃兔子。这样，仅从食物网的拓扑特性就可以对生态系统的稳定性进行近似评估。与定性稳定性理论一样，我们的方法只依赖于博弈的拓扑特性，而不依赖于收益的细节。

我们的形式主义基于最优回复动力学，在此动力学下，每个玩家都会对对手的最后一个行动做出近视的最优回复。最优回复动力学在博弈论中是众所周知的，并被广泛用于发展学习的直觉，但我们以一种新的方式使用它，以获得一般博弈中收敛的近似概率。在最优回复动力学条件下，系统要么会渐进地收敛到一个与纯策略纳什均衡相对应的固定点，要么会陷入一个循环。我们根据最优回复循环与博弈固定点的相对大小，考虑了一个非常简单的博弈不收敛指标。请注意，我们并没有假设玩家遵循最优回复动态。相反，我们假设回报矩阵的最优回复结构构成了一阶骨架，形成了玩家试图学习的博弈的主干，这对于理解许多学习算法的收敛性非常有用。

为了验证这一假设，我们选择了一组从真人博弈实验中得到的学习算法，包括强化学习、虚拟博弈、有噪声和无噪声的经验加权、k-level学习。我们也引入了（二种群）复制因子动力学在生态学和种群生物学中的重要性。基于最优回复动力学的方法预测了这些算法在$R^2≥0.78$时的不收敛频率。

在此，我们要强调的是，我们的目标是描述性的，而不是规范性的。在机制设计中，人们或机器使用的算法被设计为具有良好的收敛特性。例如，有些算法会收敛到相关均衡，这是纳什均衡的一种概括，允许博弈者在所有博弈中根据共同的信号进行协调。遗憾匹配就是这样一种算法，在这种算法中，玩家会考虑过去所有的博弈历史，并计算如果他们采取任何其他行动，他们的回报会是多少。虽然这些算法可以由机器或有足够记录能力的人来执行，但除非经过专门训练，否则不太可能被真人使用。据我们所知，这些算法只有间接的经验支持。我们将重点放在经过实验测试的算法上。当达到一个固定点时，这些算法会收敛到纳什均衡或接近纳什均衡的点，而不是更一般的相关均衡。

在证明最优回复结构形式主义可行之后，我们分析了最优回复周期或固定点是如何随着博弈的两个属性的变化而变化的。我们根据玩家可用的行动数$N$来定义一个博弈的复杂程度。简单的博弈只有几个行动，而复杂的博弈则有很多行动。博弈的竞争性由两名玩家的收益之间的相关性$G$来定义。相关性越负，博弈的竞争性越强。当我们改变博弈的这两个属性时，最优回复循环与固定点的相对比例会跟踪我们所考虑的六种算法的收敛频率，竞争性博弈中的虚拟博弈除外。

我们的研究表明，在一端，简单且无竞争性的博弈不太可能有循环，而在另一端，复杂且有竞争性的博弈很可能有循环。我们之前提到的几类博弈，即潜在博弈、优势可解博弈、协调博弈、超模态博弈和弱非循环博弈，在构造上都是非循环的。这些类别中的任何一类都可能是简单非竞争博弈集合的典型成员，在这些博弈中，非循环行为很常见，但对于复杂竞争博弈来说，它们肯定不是典型的非循环行为。这些结果与我们的直觉相吻合，即复杂博弈更难学习，当一个博弈者的收益就是另一个博弈者的损失时，博弈者就更难协调均衡。我们的形式主义可以量化这一点。例如，在每个玩家有两个行动、两个玩家的收益之间没有相关性（$G=0$）的情况下，非循环博弈约占总数的 85%。然而，在$N=10$和$G=-0.7$的情况下，非循环博弈只占总数的 2.7%。

我们还展示了如何利用最优回复形式主义来研究给定博弈类别（如势博弈）的稳定性，以了解它们在偏离给定类别情况下的稳定性。我们展示了这种行为可能是非线性的，例如，势博弈的微小扰动会导致不收敛性不成比例地大幅增加。

在收益不相关（$G=0$）的情况下，我们使用受统计力学启发的组合方法来分析计算不同长度的最优回复周期的频率。使用受统计力学启发的方法并不是博弈论中的新想法。以前的研究已经量化了纯策略纳什均衡、混合策略均衡和帕累托均衡的属性，但我们是第一个量化最优回复周期的频率和长度并展示其与学习相关性的研究。加拉和法默以前用不同的方法研究了随机博弈中经验加权吸引力在$N\rightarrow \infty$时的收敛频率；在这里，我们将其扩展到任意$N$，研究了一系列不同的学习算法，并对不稳定性的起源有了更深入的了解。我们引入的形式主义可以向多个方向扩展，并应用于不同领域。例如，我们的研究结果也与通过复制器动力学的食物网稳定性有关，并可映射到布尔网络中。

当收敛到均衡状态失败时，我们经常会观察到混乱的学习动态。当这种情况发生时，博弈者并没有收敛到任何形式的时际“混沌均衡”，即他们的预期与博弈结果不匹配，甚至在统计意义上也是如此。在许多情况下，由此产生的吸引子维度很高，这使得“理性”的玩家很难通过统计方法预测其他玩家的行动，从而获得优于其他玩家的结果。一旦至少有一名玩家系统性地偏离均衡状态，学习和启发式方法就能超越均衡思维，并能更好地描述玩家的行为。

我们首先开发了最优回复框架。接下来，我们将展示如何利用它来预测我们在此研究的六种学习算法的非收敛频率，首先提出一些论点，给出一些直观的解释，说明为什么这样做可行，然后提供更多量化证据。然后，我们研究了最优回复循环是否会随着博弈的某些属性的变化而变得普遍，并说明了两个不同的约束条件的影响，这两个约束条件代表了与众所周知的博弈类别的偏差。最后，我们开发了一种分析性组合方法，用于计算在收益不相关的情况下最优回复循环的频率。

Results

Best reply structure

首先，我们将介绍一个框架，该框架将证明，我们所分析的学习算法系列将收敛到一个固定点的可能性可以得到一个有用的估计。正如我们将演示的，这提供了一种框架，可以通过分析给出算法在玩家尝试学习博弈时将遇到的稳定性问题的一阶近似值。表 1 总结了我们将要介绍的术语。

假设在一个双人正则表达式博弈中，玩家分别是行玩家和列玩家，各自的行动（或移动，或纯策略）记作$i, j = 1, …, N$。最佳回应是指在回应对手给定行动时给出最佳回报的行动。最佳回应结构是最佳回应在收益双矩阵（即描述双方收益的两个矩阵）中的排列。(本文中，我们将使用 “收益矩阵 “一词来指双矩阵）在最佳回复动态下，每个玩家都会对对手的最后一个行动做出最佳回复。我们考虑的是最佳回应动态的一个特殊版本，即两位玩家交替下棋，各自选择对对手最后一个行动的最佳回应。

为了理解基本思想，我们考虑如下图所示的$N=4$的博弈。在图中，$S^R=\{1,2,3,4\}$和$S^C=\{1,2,3,4\}$分别是行玩家和列玩家的可能行动，矩阵中的每个格子反映了他们各自的收益，行玩家在左边。最优回复箭头指向了这个格子对应的最优回复格，垂直箭头对应行玩家，水平箭头对应列玩家。红色箭头表示该箭头是循环的一部分，橘黄色表示该箭头不在循环里，但会导向循环，蓝色表示直接指向固定点，天蓝色表示通过不止一步导向固定点。图B中的最优回复矩阵是布尔约简，其构造为具有与图A中的收益矩阵相同的最佳回复结构，但只有1和0作为其条目。假设我们选择了$(1,1)$作为初始条件，假设列玩家先行动，作为对$S^R=1$的最优回应，他选择了$S^C=2$。接下来行玩家行动，最优回应是$S^R=2$，由此列玩家又会再移动到$S^C=1$，等等。这样两个玩家将陷入循环$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,1)\rightarrow(1,1)$。我们将这样的循环称为最优回复双循环，因为每个玩家都移动两次。这个循环是一个吸引子，如果从$(3,2)$开始博弈，且行玩家先行，则博弈还是会进入到这个循环。先行玩家可以随机抽选，如果玩家的行动已经在循环了，那先行者的抽选对结果没有任何影响，因为至多有一个玩家有动机偏离当前的情况。然而如果当前不在循环，则玩家行动顺序就重要起来了。例如在这个例子中，存在两个吸引子，还是从$(3,2)$开始，列玩家先行，则博弈会一步到达最优回复固定点$(3,3)$，它是一个纯策略纳什均衡（NE）。

给定$N\times N$的收益矩阵$\Pi$，我们通过最优回复向量$v(\Pi)=(n_N,…,n_2,n_1)$来表征一组最优回复动力学的吸引子，其中$n_1$是固定点的数量，$n_2$是双循环的数量，以此类推。例如，图1中的向量是$v=(0,0,1,1)$，表示有1个固定点和1个双循环。

如上图B所示，将收益矩阵还原为最优回复矩阵是非常有用的。具体做法是将每位玩家的所有最佳回复替换为 1，所有其他条目替换为 0。最佳回复矩阵的最佳回复结构与其衍生的收益矩阵相同，但它忽略了收益的其他方面。最佳回复矩阵具有与原始博弈相同的循环和纯策略近似值，但一般来说，混合策略近似值有所不同。一旦知道了最佳回复动态的吸引子，就可以列出所有的混合策略近似值。每个最佳回复循环都有一个混合 NE，循环和固定点的所有可能组合都有一个混合 NE。与给定循环相关的混合策略近似值对应于随机走每一步，其频率与循环中出现的频率相同。例如，图 1B 中与最佳回复周期相关的混合策略均衡为$x,y=(0.5, 0.5, 0, 0), (0.5, 0.5, 0, 0)$。与每种可能的循环和固定点组合相关的混合策略 NE 对应于组合行动集的平均值。例如，在图 1B 中，与循环和固定点组合相关的混合 NE 为 $x, y = (0.33, 0.33, 0.33, 0),(0.33, 0.33, 0.33, 0)$。对于最佳回复矩阵，不存在其他混合策略近似点。

在从最佳回复矩阵到原始博弈的过程中，一些混合近似解可能会存活下来，而另一些则可能不会，并且可能会引入新的混合近似解。例如，在图 1A 中，它们都没有存活下来，而且在 $x, y = (0.32, 0, 0, 0.68), (0.36, 0.64, 0, 0)$ 和 $x, y = (0.26, 0.15, 0, 0.59), (0.32, 0.24, 0.44, 0)$处有两个混合均衡，它们与相关的最佳回复动态没有关系。我们在第 S2 节中对随机生成的 1000 个 $N = 10$ 的博弈进行了量化说明。

Learning dynamics

为了解决学习何时收敛的问题，我们研究了六种不同的学习算法。这些算法的选择跨越了不同的信息条件和理性水平。我们的重点是有经验支持的算法。这包括在生物学中用于动物学习或种群遗传学等目的的算法，以及用于在实验室环境中进行人类博弈行为实验的算法。我们在 “材料与方法 “中对六种算法逐一进行了简短总结，并在第 S1 节中介绍了详细内容。在此，我们仅讨论每种算法背后的基本思想，并说明将其纳入本研究的原因。

强化学习基于这样一种理念，即玩家更有可能采取过去收益更好的行动。它是标准的学习算法，用于信息有限和/或没有复杂推理的情况下，例如动物学习。我们研究的是布什-莫斯泰勒（Bush-Mosteller）算法，该算法已在实验中进行了广泛测试。

虚拟博弈需要更多的复杂性，因为它假定玩家构建了一个对手的心理模型。每个玩家都假定对手过去行动的经验分布就是她的混合策略，并根据这一信念下出最佳对策。一种常用的变体——加权虚拟博弈——假定过去的行动会打折扣。关于标准虚拟博弈和加权虚拟博弈的经验证据不一。从理论的角度来看，标准虚拟博弈在许多情况下会趋同于混合策略 NE，而加权虚拟博弈则不会。正如我们将看到的，如果学习算法经常达到混合均衡，我们的最佳回复形式主义就不能很好地发挥作用。我们选择标准版本的虚拟博弈来说明这一点，因为它提供了更有力的检验。

复制动力学常用于生态学和种群生物学。它表示种群中某些性状随世代的演变，每个性状的适合度取决于种群中所有其他性状的份额。复制动力学也可以看作是一种学习算法，其中每个性状都对应着一种行动。在这里，我们考虑的是双种群复制动力学，而不是更标准的单种群版本，因为在单种群版本中，两个参与者的收益矩阵顾名思义是对称的，而我们要研究的是收益的相关性。

经验加权吸引力（EWA）已被提出，用于归纳强化学习和虚拟博弈，并已被证明能很好地适应实验数据。其成功的关键在于一个权衡已实现报酬和已放弃报酬的参数。EWA 还包括其他参数，如记忆和报酬敏感性。与上述三种学习算法不同，其参数是决定收敛性的关键： 对于某些参数值，它总是收敛到固定点，而这些固定点可能离纳什均衡或相关均衡任意遥远。正如我们在 “补充材料 “中详细讨论的那样，由于缺乏对一般博弈中参数的实验指导，我们选择的参数值有可能使收敛接近近邻均衡。EWA 不会收敛到更一般的相关均衡，除非它们对应于NE。

上述算法都基于批量学习的概念，这很方便，因为这意味着它们都是确定性的。在批量学习中，棋手在更新自己的策略之前会大量观察对手的行动，因此会根据对手在每个时间点的实际混合策略进行学习。确定性假设有助于从数字上识别静止状态。在许多实验情况下，更现实的假设是，棋手在观察对手的单次行动后更新策略，而对手的行动是从其混合策略中随机取样的。这就是所谓的在线学习。作为在线学习的一个例子，我们研究了 EWA 的随机版本。

上述五种算法都是向后看的。为了与具有前瞻性行为的例子进行比较，我们使用了水平-k 学习或预期学习，其中棋手试图通过提前 k 步思考来战胜对手。level-k思维的观点得到了相当多的经验支持，一些研究还特别支持预期学习。在这里，我们通过使用第 2 层 EWA 学习来实现 k 级推理。两位棋手都假设对手是一级学习者，并使用 EWA 更新策略。因此，棋手会尝试根据对手的预测行动先发制人，而不是仅仅根据对手的历史行动频率采取行动。这为前瞻性行为提供了一个衡量标准。

总之，我们之所以选择这六种算法，是因为它们本身就很重要，而且能说明不同的特性。我们感兴趣的是生态学和生物学中使用的算法，或者在实验室人类实验中观察到的有界理性算法。我们特别不研究那些与计算机科学或机制设计相关，但与行为学观点无关的复杂算法。这些算法的收敛特性可能与本文研究的算法截然不同。遗憾匹配就是我们不研究的这类算法的一个例子，它被认为是一种 “自适应启发式”，是有界理性和近视的。然而，它仍然要求博弈者计算如果他们在之前的所有时间步骤中采取任何其他行动，他们会得到什么回报，而且没有经验证据表明人类实验中的博弈者会使用它。其他能达到相关均衡的算法，如校准学习法，则更为复杂。

How does the best reply structure shape learning dynamics?

我们的工作假设是，最佳回复结构会影响这些学习算法的收敛特性，即使学习轨迹可能并不详细遵循最佳回复周期。更具体地说，我们的假设是，最佳回复周期的存在与否与学习动态的稳定性相关。当没有最佳回复周期时，学习更有可能收敛，而当存在最佳回复周期时，学习则不太容易收敛。我们无法在一般博弈中分析证明这一点，但轶事实例支持了这一点。我们不可能详细介绍这些例子，但在这里，我们将举出几个有代表性的例子来说明对应关系。在下一节中，我们将提出更多量化证据。

为了直观地了解最佳回复结构是否以及为什么能够预测上述学习算法的收敛性，在图 2 中，我们分析了四个$N=3$的博弈，显示了四维策略空间三维投影中的一些学习轨迹（混合策略向量有六个分量，有两个归一化约束。轴标 $x_1$和$x_2$分别是行玩家采取$s^R=1$和$s^R=2$行动的概率，$y_1$是列玩家采取$s^C=1$行动的概率。策略空间$(x_1, y_1, x_2)=(1, 1, 0)$和$(0, 1, 1)$的角分别对应行动轮廓$(1, 1)$和$(2,1)$。

在图 2A 中，我们考虑了一个具有 2 循环和单一纯策略 NE 的最佳回复矩阵。我们的第一个示例使用了复制动力学。学习算法的吸引子与最佳回复动力学的吸引子非常相似；根据初始条件，所有轨迹都会到达固定点或极限循环。本例中的极限循环与最佳回复循环相对应，因为我们始终保持 $y_3=0$（由于六维系统的三维投影，坐标$y_3$ 未显示）。强化学习、EWA 和带噪声的 EWA 的表现类似。相反，虚拟博弈总是收敛到一个固定点，要么收敛到纯策略 NE，要么收敛到循环支持中的混合策略均衡，这取决于初始条件。我们从未观察到它收敛到另一个混合 NE，即对应于两个吸引子的组合。在第 S2 节中，我们证明了在 $N=10$ 的一般博弈中，就现有混合均衡的比例而言，虚拟博弈更有可能收敛到最佳回复循环支持下的混合均衡，而不是其他混合均衡。k 级 EWA 也会收敛（接近）到相同的混合均衡。我们将在下一节中定量地说明，在行动较少的博弈中，level-k EWA 的行为类似于虚拟博弈，而在行动较多的博弈中，它更类似于其他四种算法。对于最佳回复矩阵来说，学习动态模仿最佳回复结构并不奇怪，但由于学习算法具有自由参数和对过去的记忆，因此它们应该如此紧密地模仿最佳回复结构并不明显。

图 2B 中的收益矩阵与图 2A 中的最佳回复结构相同，但收益是通用的。为了展示更多的学习算法，我们这次用强化学习和带噪声的 EWA 来说明学习动态。在这两种情况下，学习轨迹要么收敛到纯策略 NE，要么不收敛。强化学习会收敛到一个与最佳回复周期相关的极限周期，即使该轨迹被扭曲并更深入地渗透到策略空间的中心。如图 2A 所示，复制动力学和 EWA 的表现类似，而虚拟博弈和水平-k EWA 收敛到或接近于混合均衡。

为了了解取消最佳回复循环后的情况，在图 2C 中，我们考虑了与图 2B 相同的报酬矩阵，只是位于$(3,1)$处的行的报酬是 2.0，而不是 0.1。在这种情况下，最佳回复动态的唯一吸引子是位于$(3,3)$处的纯策略 NE。在所有初始条件下，强化学习都会收敛到纯策略 NE，这说明了移除最佳回复循环是如何使固定点全局稳定的。然而，对于复制动力学，存在一些初始条件反而会导致极限循环，这表明即使没有最佳回复循环，不稳定学习动力学的小盆地仍可能存在。(虚拟博弈和水平-k EWA 的表现类似于强化学习，而 EWA 和带有噪声的 EWA 的表现类似于复制动力学）。

这个例子说明了学习动态如何从本质上偏离最佳答案动态。当复制器动态达到$(x_1, y_1, x_2)=(0.86, 0.87, 0.14)$ 点（图中黑色箭头所示）时，行玩家的预期报酬为 0.25。如果行玩家改用 $s^R=3$（他的最佳回答），他的报酬将增加到 1.60。如果换成$s^R=1$，行玩家的预期报酬仍会增加到 0.29，因此我们说行动 1 是更好的回复。随着时间的推移，在复制器的动态作用下，与更好的回复相对应的行动的概率也会增长，尽管增长率低于最佳回复。在这里，由于过去的博弈，$x_3$ 非常小（10-53 的数量级），所以 $x_1$ 在 $x_3$ 达到类似值之前就增加到了 1，动态过程陷入了图中所示的循环。

在图 2D 中，我们考虑了一个具有 2 循环且无纯策略 NE 的收益矩阵。在所有初始条件下，EWA 都会达到一个混沌吸引子。需要注意的是，这个吸引子与最佳回复循环的某些结构相同，会紧密访问策略空间的两个角，即 $(x_1, y_1, x_2) = (1, 0, 0)$ 和$(1, 1, 0)$，而另外两个角则较为松散。而水平-k EWA 则收敛到混沌吸引子中心的混合 NE 附近。由于有限记忆和有限报酬敏感性，EWA、带噪声的 EWA 和水平-k EWA 无法精确达到混合均衡。其他算法的表现类似： 有噪声的 EWA 和复制动力学都会达到一个混沌吸引子，而强化学习则会遵循一个极限循环。虚拟博弈在混合均衡附近波动，混合策略向量的每个分量与均衡点的最大距离为 0.03。

因此，我们看到，尽管这些算法的学习动态并未详细模仿最佳回复动态，但在大多数情况下，在学习动态中可以看到它的残余。即使对应关系不准确，最佳回复结构也会影响学习动力。

Quantitative evidence

现在，我们将对这一假设进行定量检验，即至少对于这些学习算法而言，最佳回复周期的存在与不收敛性呈正相关。为此，我们首先证明了一个非常有用的定理，它将循环和固定点的配置与不稳定最佳回复动态吸引盆地的相对大小联系起来。假设$n_k$是长度为$k$的最佳回复循环的数量，那么让 $C=\sum_{k=2}^N n_kk$ 是属于最佳回复循环中的行动数。数量$F(v)=C/(C+n_1)$测量的是吸引子上属于循环与固定点的相对数量。在图 1 的例子中，有一个固定点和一个周期，$F(0, 0, 1, 1)=2/3$。

这也衡量了最佳回复动态下循环与固定点吸引盆地的相对大小。例如，对于图 1 所示的博弈，8 个初始条件中有 5 个会导致循环，8 个初始条件中有 3 个会导致固定点。然而，如果我们对所有可能的 4 × 4 博弈进行平均，这些博弈都有一个长度为 2 的最佳回复循环和一个单一的纯策略 NE，而且没有其他最佳回复吸引子（对每个可能的博弈给予相同权重），那么导致最佳回复循环的初始条件的相对大小正好是 2/3。正如我们在补充材料中所展示的，这在一般情况下是正确的。

为了测试最佳回复动态与我们的学习算法系列的收敛特性之间的关系，我们随机生成博弈。正如第 S1.2 节所述，正态分布是最大熵分布，因此是自然选择。在此，我们让两位玩家的收益互不相关。然后，我们在收益矩阵固定不变的情况下，在重复博弈中模拟博弈者的学习过程。我们使用 “材料与方法 “和 “补充材料 “中解释的标准来检验纯策略和混合策略 NE 的收敛性。我们生成了 1000 个不同的博弈；对于每个博弈，我们从 100 个不同的初始条件开始模拟所有六种学习算法。作为比较，我们使用与随机生成的 1000 个博弈中的每个博弈相关的最佳回复矩阵重复整个过程。$N=20$的结果见图 3，$N=5$和$N=50$的结果见图 S8 和 S9。

图3比较了最佳回复周期$F(v)$ 与不收敛频率的比例。为了检验最佳回复向量$v$与学习动态之间的关系，我们将具有相同$v$的收益矩阵的结果分组，并画出一个半径与采样次数对数成正比的圆。我们根据每个最佳回复向量在最佳回复周期$F(v)$中所占的比例，将其放在横轴上。在纵轴上，我们绘制了使用该最佳回复向量的结果的平均不收敛频率。因此，如果最佳回复结构能完美预测其他学习算法的收敛速度，那么所有圆圈都应以同一直线为中心。我们使用与每个最佳回复向量采样次数相对应的权重来估算加权相关系数$R^2_w$。

我们使用最佳回复矩阵进行模拟的结果如图 3 顶部一行所示。除了虚拟博弈之外，所有算法的相关性都接近于 1。一方面，鉴于最佳回复矩阵没有更好的回复，这似乎并不太令人惊讶。但另一方面，这些学习算法都使用了对过去的记忆（除了最近的行动之外），而且它们中的大多数都有自由参数，而最佳回复动态则没有这些参数。有鉴于此，具有不同功能形式的学习算法的吸引力盆地的大小如此接近最佳回复动力学，这一点非常了不起。虚拟博弈之所以失败，是因为它有收敛到混合策略 NE 的强烈倾向，不过即使在这种情况下，它通常也无法在较长的周期内收敛。在大多数情况下，虚拟对局在 2 循环时收敛，但在 3 循环时则无法收敛，这与 Miyazawa（50）和 Shapley 的观点一致。图 3 顶部面板中的结果加强了我们的直觉，即对于最佳回复矩阵，学习算法的吸引子与除虚拟对弈之外的所有算法的最佳回复动态密切相关。

一般情况如图 3 底行所示。相关性仍然很强，虚构游戏的加权相关系数$R^2_w=0:78$，所有其他算法的相关系数$R^2_w≈0:84$。最佳回复动态并不能完美预测收敛性，但其预测结果仍然很好，非常有用。

这一分析还提供了关于导致不收敛的其他一些因素的线索。例如，即使$F(v)=0$表示不存在最佳答案循环，收敛也并不确定。这一点从每个图左边的垂直圆柱中可以明显看出。这一列对应的是没有循环的最佳回复矢量，即形式为$v=(0,…,0,0,x)$的矢量，其中$x=1,2,3,4$是不同固定点的数目。最高的圆对应一个固定点，其下的圆对应两个固定点，等等。在存在唯一的纯近地轨道且不存在循环的情况下，不收敛频率通常约为35%，如果存在两个纯均衡点，则不收敛频率降至约 20%。多个纯均衡的存在，使得像图 2C 中那样存在较好回复循环的可能性降低。相反，当存在没有任何固定点的循环时，也会出现收敛的情况。这与图 2C 右侧的垂直圆柱（$F(v)=1$）相对应，它适用于 k 级 EWA、虚拟博弈和强化学习。

在存在唯一的纯 NE 且没有循环的情况下，不收敛对于复制动力学尤其明显，当存在单个固定点时，约 60% 的时间会发生不收敛。正如我们在补充材料中所解释的，这部分是由于随着 N 的增长而变得更加严重的数值限制，因此如果$N\geq 50$，我们将放弃对复制动力学的观察。

在没有固定点的情况下，收敛完全是由于向混合策略 NE 的收敛。如图 S10 所示，这种影响几乎与 $F(v)$无关，因此会导致恒定偏移。如图 S10 所示，这种影响几乎与 $F(v)$无关，因此会导致恒定偏移。这就是当$F(v)>0$时，圆圈位于同一直线下方的原因。这种效应在强化学习和虚构游戏中尤为明显，强化学习有 21% 的时间收敛到混合均衡状态，而虚构游戏有 32% 的时间收敛到混合均衡状态。相比之下，（双种群）复制器动力学则不存在这种效应，因为它无法收敛到混合策略 NE (52)。其他算法收敛到混合策略 NE 的频率低于 15%。一旦考虑到这些影响，包括虚构游戏在内的所有学习算法的$F(v)$和非收敛率之间都存在很强的比例关系。

在图 S11 中，我们显示了六种学习算法收敛的相关矩阵。图 S11 显示了六种学习算法收敛的相关矩阵。我们发现，收敛平均有 60% 的时间是同时出现的，这表明算法之间存在很大程度的异质性，这与图 2 中的直觉是一致的。

总之，即使 $F(v)$ 忽略更好的回复并低估混合策略 NE 的收敛，收敛的平均概率与最佳回复周期的份额之间也存在稳健的相关性。这表明最佳回复结构与这些算法的稳定性密切相关。

Variation of the best reply structure

现在，我们将研究随着博弈属性的变化，最佳回复循环和固定点的普遍性，并检验随着参数的变化，非收敛性的预测。我们研究的参数是可能行动的数量$N$和两位棋手报酬之间的相关性$\Gamma$。(稍后，我们还会考虑一个参数$\xi$，用于在随机博弈和势博弈之间进行插值）。

和以前一样，我们随机生成博弈，但现在我们对从中抽取博弈的集合施加了限制。为了理解$\Gamma$如何影响收敛性，我们通过从二元正态分布中抽取来生成收益矩阵，这样在任何给定的行动组合中，行玩家和列玩家的收益乘积的期望值都等于$\Gamma$。负相关（$\Gamma<0$）意味着博弈是竞争性的，因为对一个玩家有利的事情很可能对另一个玩家不利。极端的情况是$G =-1$，这意味着博弈是零和的。相反，$G>0$则鼓励合作，因为收益往往对双方都有利，或者对双方都不利。

在图 4 中，我们展示了最佳回复周期的份额是如何随$N$和$\Gamma$的变化而变化的。对于给定的$N$和$\Gamma$值，我们随机生成收益矩阵，并计算最佳回复周期的平均份额$_{N,\Gamma}$。我们将$_{N,\Gamma}$与六种学习算法的平均不收敛频率进行比较。结果大致吻合。虚拟博弈是一个显著的例外，当$N$较大且$\Gamma$为负数时，它的收敛率较高。这与其他算法不同，其他算法很少在这一参数范围内收敛，而且与预测结果非常接近。因此，正如预期的那样，必须以不同于其他算法的方式来看待虚拟博弈。

我们想强调的是，这些预测都是先验的，不涉及任何参数拟合。除虚拟博弈外，预测结果符合数据的整体趋势，既能正确估计幅度，又能捕捉函数依赖性。对于其他五种算法，当$N$较大且$\Gamma$为强负值时，预测结果尤为出色，$N>10$时的拟合效果近乎完美。

当我们改变$N$和$\Gamma$时，有可能趋同的情况结论是什么？当$\Gamma$为正数时（意味着博弈不具有竞争性），几乎可以保证收敛，与$N$无关；但当$\Gamma$为强负数时，只有当$N$非常小时才有可能收敛。当$\Gamma=-0.7$ 时，对于$N=4$，不收敛率大约为$70\%$，到$N=8$时迅速上升到接近$100\%$。我们的分析表明，这是因为复杂的竞争博弈被循环所支配。在参数空间的这一区域，非循环博弈极为罕见。因此，优势可解博弈、协调博弈、势博弈和超模态博弈都是非典型的。

最后，我们将简要介绍如何引入其他约束条件来研究上述博弈类别的偏差。在这里，我们只做一个高层次的讨论，技术细节将在第 S4 节中报告。我们考虑的是势博弈，在势博弈中，单方面转换到另一个行动的所有报酬差异都可以用一个全局势函数来表示。势函数将每个行动轮廓映射为一个实数。我们随机生成收益矩阵，并为每个回报矩阵生成一个相关的势函数。然后，我们修改博弈，使收益差异符合势函数。这可以通过参数 $x\in [0,1]$ 来调整： 当$x=0$时，没有任何修正，因此博弈是完全随机的；当$x=1$时，收益矩阵描述了一个完美的势博弈。

改变$N$和$x$的效果如何？我们重复上述过程，对1000个报酬矩阵进行$N=3,10,50$ 和$x\in [0.0, 0.1, …, 0.5, …,0.9,1.0]$ 的取值。如图 S12 所示，当$x$接近 1 时，最佳回复循环的份额$_{N,\xi}$如期归零。当$N=3$和$x=0.8$时，它仅为$_{N,\xi}=0.05$，但当$N=50$和$x=0.8$时，它为$_{N,\xi}=0.35$。这表明，在某些情况下，与通常研究的博弈类别的微小偏差可能会导致最佳回复循环的份额显著增加，从而使它们在学习下变得不那么稳定。

Analytical approach

对于$\Gamma=0$，我们可以分析得出最佳回应结构是如何随$N$变化的。我们的推导遵循统计力学框架，这表明诸如最佳回应结构中是否存在相变等问题都可以在我们的形式主义中进行研究。我们将最佳回复配置定义为双方对对手所有可能行动的唯一一组最佳回复。由于最佳回复矩阵是布尔矩阵，因此对于任何给定的$N$，都有可数的可能性。可能的最佳回复配置总数为$N^{2N}$。对于不相关的回报($\Gamma=0$)，所有最佳回复配置的可能性相同。因此，我们可以通过计算导致$v$的最佳回复配置的数量来计算任意吸引子集$v$的频率$\rho(v)$。

在此，我们仅简要说明推导过程，详细解释请参阅第 S5.1 节。由于独立性，$\rho(v)$频率可以写成与获得每种吸引子的方法数量相对应的项$f$乘以自由行动（不在吸引子上的最佳回复）项$g$的乘积。我们用$n$表示每个玩家不属于循环或固定点的行动数。

函数$f(n, k)$会统计$k$循环的方式（包括固定点，即长度为$k=1$的循环）:

$$f(n,k)=\binom{n}{k}^2k!(k-1)!$$

其中，二项式系数意味着，对于每个玩家，我们可以从$n$个行动中任意选择$k$个行动来形成循环或定点，而阶乘则量化了所选$k$个行动产生循环或定点的所有最佳回复组合。例如，在图 1 中，对于每个玩家，我们可以从 4 个行动中任意选择 2 个行动来形成 2 循环，而对于每一个行动，都有两种可能的循环（一种是顺时针，另一种是逆时针）。形成 2 循环的方法数为$f(4, 2)=72$。同样，对于每个玩家，我们可以从剩下的两个动作中选择任意一个动作来形成一个固定点，方法数为$f(2, 1)=4$。

在这个例子中，对于两个玩家，我们仍然可以自由选择一个最佳回复，前提是这不会形成另一个固定点（否则，最佳回复向量就会不同）。在图 1 中，行玩家的自由最佳回复为$(3,4)$，列玩家的自由最佳回复为 (4，1)。一般来说，$g_N(n,d)$ 计算的是将$N\times N$ 报酬矩阵中剩余的$n$个自由最佳回复组合起来，使其不形成其他循环或固定点的方法数

$$g_N(n, d)=N^{2 n}-\sum_{k=1}^n f(n, k) g_N(n-k, d+1) /(d+1)$$

第一项$N^{2n}$ 量化了自由最佳回复的所有可能组合，求和计算“禁止”组合，即形成循环或固定点的组合。这个项具有递归结构。它先计算形成每种吸引子的方式数，然后计算在剩余的$n-k$个行动中没有其他吸引子的方式数。请注意，$N$是一个参数，因此用下标表示，而$n$是一个递归变量。最后，需要用$d+1$除法来防止吸引子的重复计算、三重计算等。在图 1 的例子中，$g_4(1,0)=15$。

对于任意给定最优回复向量，$v=(n_N,…,n_2,n_1)$，其频率$\rho$的通用表达式为：

$$\begin{gathered} \rho(\mathbf{v})=\left(\prod_{k=1 j=1}^N \prod_{n_k} \frac{f\left(N-\sum_{l=k+1}^N n_l l-(j-1) k, k\right)}{j}\right) \\ \times g_N\left(N-\sum_{l=1}^N n_l l, 0\right) /\left(N^{2 N}\right) \end{gathered}$$

第一个括号是计算包含吸引子$v$的所有可行方法数量。$f$的第一个参数$N-\sum_{l=k+1}^N n_l l-(j-1) k$迭代量化了不属于其他吸引子的行动的数量。除以$j$，就像公式3中除以$d+1$一样，是为了防止吸引子的重复计算、三重计算等。第二个项$g_N$计算了所有可能的方法来定位自由最佳回复，使其不形成其他吸引子。$g_N$的第一个参数是不属于吸引子的行动计数，初始递归深度为0。最后，我们通过除以所有可能的配置$N^{2N}$得到频率。对于图1中的收益矩阵，$\rho(0,0,1,1) =f(4,2)f(2,1)g_4(1,0)/4^8=0.07$。

然后，可以利用公式 4 计算然后，可以利用公式 4 计算出任何给定$N$的最佳回复周期$F$的集合平均值，并对所有可能的$v$求和，使得$\sum_{k=1}^N n_k k \leq N$。

$$\mathcal{F}_N=\sum_{\mathbf{v}} \rho(\mathbf{v}) \mathcal{F}(\mathbf{v})$$

我们还可以计算其他量，包括没有固定点$F(v)=1$和没有循环$F(v)=0$的收益矩阵的分数。我们将在第 S5.2 节中提供表达式并解释其推导过程。

在图 5 中，我们分析了$N$值增大时的最佳回复结构。我们从下往上报告了没有固定点的回报矩阵的比例、最佳回复循环$F_N$的平均比例以及至少有一个循环的博弈比例。例如，对于$N=30$，36% 的收益矩阵没有固定点，84% 的收益矩阵至少有一个循环（因此 16% 的收益矩阵没有循环，48% 的收益矩阵混合了循环和固定点），平均$F_N=0.70$。分析结果（实线）与蒙特卡罗取样（标记）之间的一致性非常好。有循环的博弈比例是$N$的递增函数；要计算大N的这一比例在计算上很难，但它似乎正趋向于1。然而，至少有一个固定点的博弈分数似乎在$N\rightarrow \infty$ 时达到一个固定值。在第 S5.3 节中，我们证明这个值近似为 1/3，与数值模拟结果一致，并接近精确结果$1/e$。

Discussion

我们描述了双人、正常形式、通用博弈中的不稳定性，表明最佳回复结构可以预测各种学习算法的收敛频率。这一结果非常了不起，因为这些算法与最佳回复动态没有明确的关系。最佳回复动态只取决于其他玩家的前一步棋，而这些算法都有较长的记忆，还因为最佳回复动态没有自由参数，而这些算法中的大多数都有。为什么这种对应关系有效？我们猜想，最佳回复循环的存在使得不稳定动态在统计上更有可能存在吸引盆地，而它们的不存在则使得纯策略 NE 有可能是全局稳定的固定点。这并不总是正确的—有些学习动力可能被困在最佳回复循环中，而另一些学习动力有时会收敛到混合策略近似点，但这是一个有效的近似，极大地简化了问题。它使我们有可能利用统计力学的概念框架，使用组合学来分析探索微观博弈集合下的一般博弈空间。

为什么最佳回复形式的预测结果如此之好？为了理解这一点，我们可以明确地将最佳回复的报酬矩阵视为一阶近似值，然后研究沿着与之相关的报酬矩阵族的连续路径移动时的行为。我们可以用这种方法来研究导致偏差的因素，例如混合均衡或最佳回复的出现和消失。这有可能导致一种扰动扩展，用于理解正态博弈中学习算法的收敛性。这超出了本文的研究范围，但可能是进一步研究的一个有趣课题。

我们还证明，在报酬没有任何限制的情况下，增加每个玩家的可用行动数量会使最佳回复循环占主导地位，从而使收敛到均衡的可能性降低。这类似于梅在大型生态系统上的结果（14）。我们考虑了一个竞争参数，该参数限制了双方玩家的报酬对。在负相关的情况下，博弈是竞争性的（在报酬完全反相关的极端情况下为零和），最佳回复周期变得更加普遍。相反，正相关会使最佳回复周期变得罕见。

我们还对博弈进行了限制，使报酬的差异符合全局势函数，就像在势博弈中一样。这种对应关系由一个参数来调整，该参数在完美随机博弈和完美势博弈之间进行插值。我们已经证明，当行动数量较多时，与完美势博弈的微小偏差会带来相当大比例的最佳回复循环。

还可以加入许多其他限制条件。超模态博弈在文献中也受到了极大的关注。在这些博弈中，行动是有序的，如果一个玩家增加她的行动，其他所有玩家的边际报酬都会增加（这就是策略互补性的概念）。我们可以随机生成具有这种约束条件的博弈，并观察最佳回复循环的份额在接近完美超模态博弈时是如何变化的。总的来说，我们的形式主义使我们有可能评估约束条件是否会使正态博弈集合变得更稳定或更不稳定。在大多数情况下，对于我们在此研究的学习算法，只需检查约束是否使最佳回复循环变得常见或罕见，而无需模拟学习动态。

我们在这里研究的是正态博弈，因为它们很容易理解，但我们的研究有可能扩展到其他类型的博弈。例如，在广义形式博弈中，不同行动的排序和私人信息的存在都是恰当的模型。虽然我们的理论并不直接适用，但广泛形式博弈有一个正常形式表示，这表明这种扩展应该是可能的。同样，我们已经开始研究有两个以上玩家的博弈。之前对无限行动数$N$的竞争博弈的研究表明，非收敛变得更有可能，而我们的初步结果表明，$N<\infty$时也是如此。

在生态学中，生态系统如此持久这一事实本身就表明，它们必须相当稳定。相比之下，有许多生物和社会系统会随着时间的推移而波动，而且它们的动态是外生的还是内生的，先验地并不明确。当使用博弈论对这些系统进行建模时，没有任何先验条件说它们应该是稳定的。因此，与预先知道答案的生态系统不同，在这些系统中，我们应该对它们是一般稳定还是不稳定持开放态度。在没有选择机制或有意设计的稳定性的情况下，我们的方法可以揭示这个问题。如果存在上述任何一种机制，我们的方法就能提供一个无效假设，据此来衡量这些机制的有效性。

这些结果很有用，因为它们对假设均衡是危险的情况提出了警告。在现实世界中，有许多情况下可能采取的行动数量很大，而且回报很可能是反相关的。在没有其他约束条件的情况下，我们的结果表明，在这些情况下，均衡不太可能是一个好的行为假设。虽然均衡是存在的，但只要正常形式博弈适用，只要我们在这里研究的学习算法类型相关，在这些情况下，收敛就不太可能。

Materials and methods

我们在此总结了用于模拟图 3 和图 4 中学习算法的协议。我们只报告了能够复制结果的最基本信息。我们将在 S1 部分提供更详细的说明，其中包括行为解释和其他规格。我们不得不对收敛标准和参数值进行任意选择，但在测试替代规格时，我们发现相关系数的变化不超过小数点后几个单位。这证实了最佳回复周期的份额与六种学习算法的非收敛频率之间存在稳健的相关性。

考虑一个双人、$N$种行动的正态博弈。我们用$\mu\in\{Row=R, Column=C\}$ 来表示玩家，用$i,j=1, … N$ 来表示他们的行动。让$x_i^\mu(t)$成为玩家$\mu$在$t$时刻采取$i$行动的概率，即她的混合策略向量的第$i$个分量。为方便记述，我们还用$x_i(t)$表示玩家R在$t$时刻采取$i$行动的概率，用$y_j(t)$ 表示玩家$C$在$t$时刻采取$j$行动的概率。我们进一步用$s_m(t)$表示玩家$m$在$t$时刻实际采取的行动，用$s_{- m}(t)$表示其对手采取的行动。玩家$m$的收益矩阵为$P_m$，$P_m(i, j)$ 表示如果玩家$m$采取行动$i$，而对方选择行动 $j$，那么玩家$m$得到的收益。

Reinforcement learning

我们只描述行玩家，因为列的学习算法是一样的。行玩家在时间$t$有一个抱负水平$AR(t)$，其更新为:

$$A^{\mathrm{R}}(t+1)=(1-\alpha) A^{\mathrm{R}}(t)+\alpha \sum_{i, j} x_i(t) \Pi^{\mathrm{R}}(i, j) y_j(t)$$

其中$\alpha$是参数。对于动作$i$和时间$t$，行玩家的满意度$\sigma_i^R(t)$为

$$\sigma_i^{\mathrm{R}}(t)=\frac{\sum_{i j} x_i(t) y_j(t)\left(\Pi^{\mathrm{R}}(i, j)-A^{\mathrm{R}}(t)\right)}{\max _{i, j}\left|\Pi^{\mathrm{R}}(i, j)-A^{\mathrm{R}}(t)\right|}$$

混合策略向量的所有元素都被更新。更新规则为

$$x_i(t+1)=x_i(t)+x_i(t) \Delta x_i(t)+\sum_{j \neq i} x_j(t) \Delta x_{i j}(t)$$

这里$\Delta x_i(t)$是行玩家选了动作$i$所带来的贡献（出现概率为$x_i(t)$），且$\Delta_{ij}(t)$是选了另一个动作$j$而对动作$i$的贡献（即标准化更新），发生的概率是$x_j(t)$。我们有：

$$\Delta x_i(t)=\left\{\begin{array}{cc} \beta \sigma_i^{\mathrm{R}}(t)\left(1-x_i(t)\right), & \sigma_i^{\mathrm{R}}(t)>0 \\ \beta \sigma_i^{\mathrm{R}}(t) x_i(t), & \sigma_i^{\mathrm{R}}(t)<0 \end{array}\right.$$

和

$$\Delta x_{i j}(t)=\left\{\begin{array}{cc} -\beta \sigma_j^{\mathrm{R}}(t) x_i(t), & \sigma_j^{\mathrm{R}}(t)>0 \\ -\beta \sigma_j^{\mathrm{R}}(t) \frac{x_j(t) x_i(t)}{1-x_j(t)}, & \sigma_j^{\mathrm{R}}(t)<0 \end{array}\right.$$

其中$\beta$是参数。

从随机混合策略向量——混合策略的初始化对于后面的所有学习算法都是相同的——以及愿望和满意度的空水平开始，我们在 5000 个时间步长内重复公式 6 至 10 中的动态过程（我们设置$a=0.2$和$b=0.5$）。为了确定模拟运行是否收敛，我们只考虑了最后 20% 的时间步数，以及在此时间间隔内平均概率大于 0.05 的混合策略向量成分。如果这些成分和时间步数的平均标准偏差大于 0.01，则该模拟运行被认定为非收敛。

Fictitious play

Replicator dynamics

Experience-weighted attraction

EWA with noise

Level-k learning

Payoff matrices