一般对策中的最优回复结构与均衡收敛

最佳回复动态的行为与其他学习算法的行为密切相关，这一事实表明，它为研究该问题提供了一种简单的方法，并且我们在后续章节中得出的关于最佳回复动态的非收敛性的结果可能表明了各种不同学习算法的行为。我们考虑了六种跨越不同信息条件和合理性水平的学习算法。首先，强化学习[33]是基于这样一个想法，即玩家更可能使用过去产生更好回报的招式。这是一种标准的学习算法，在信息有限和/或没有复杂推理的情况下使用，例如在动物学习中。我们研究了BushMosteller实现[34]。我们的第二种学习算法是虚拟游戏[35，36]，它需要更复杂的技巧，因为它假设玩家构建了对手的心理模型。每个玩家都将对手最后一步的经验分布作为她的混合策略，并对这一信念做出最佳反应。第三，复制子动力学[37]通常用于种群生态学，但与学习理论有着密切的联系[38]。第四，有人提出了经验加权吸引（Experience WeightedAttraction，EWA）来概括几种学习算法，并已证明能很好地拟合实验数据。到目前为止，我们只考虑了基于批量学习假设的学习算法的确定性近似：玩家在更新策略之前，会大量观察对手的动作，因此会根据对手的实际混合策略进行学习。确定性假设有助于从数值上确定固定点。作为第五种学习算法，我们放宽了这一假设，并考虑了EWA的随机版本。

在这个版本中，玩家在观察对手的一个动作后更新他们的策略，这是从她的混合策略中随机抽取的。这也称为在线学习。最后，在k级学习（40）或预期学习（41）中，玩家试图通过认为k步领先来智胜对手。例如，这里我们考虑2级EWA学习。两位玩家都认为对方是1级学习者，并使用EWA更新策略。因此，球员们试图根据她的预测动作抢先抢先，而不是根据她的历史动作频率行事。虽然otheralgorithms中的参与者是向后看的，但在这里他们是向前看的。学习算法和收敛标准的详细信息列于补充信息（SI）第1节。（我们在材料和方法部分提供了一个简短的总结。）我们在六种算法SABOVE下分别模拟学习伪造游戏。为了确定博弈，我们从二元高斯抽样，随机生成两个参与者的支付矩阵，这是这种情况下的最大熵分布（见SI，第1.2节）。在每次迭代游戏期间，支付矩阵保持不变。该过程在1000 rans中重复。例如，如果图1中的所有自由最佳回复都导致循环，则循环的吸引盆地将大于2/3。

但这是一种非典型配置，v=（0，0，1，1）。0.00.20.40.60.81.0R2w=0.83钢筋学习R2w=0.78虚拟铺层R2w=0.83复制器动态0.0 0.2 0.4 0.6 0.8 1.00.20.40.60.81.0R2w=0.87EWA0.0.2 0.4 0.6 0.8 1.0R2w=0.78EWA，噪声0.0 0 0.2 0.4 0.6 0.8 1.0R2w=0.84Level-kR2w=0.99 R2w=0.62 R2w=0.98R2w=0.99 R2w=0.99 R2w=0.99最佳回复周期的份额F（v）非收敛动态图2：测试最佳回复的效果结构预测了六种学习算法的不收敛性。我们生成1000个随机支付矩阵，描述N=20步的游戏，并模拟从100个随机初始条件中学习每一步。每个圆对应一个特定的最佳回复向量v，其大小是带有v的Payoff矩阵采样次数的对数。横轴是最佳回复动态F（v）下的非收敛频率。例如，F（v）=0.7附近的最大圆对应于经常采样的v=（0，…，0，1，1）。纵轴给出了模拟中不收敛的频率，对所有Payoff矩阵和具有相同v的初始条件进行了平均。在插图中，模拟基于Payoff矩阵的布尔约化。绘制标识线以供参考。domly生成支付矩阵，测试每个矩阵100个不同的初始条件。正文中报告了N=20的结果，SI第2节给出了N=5和N=50的结果。在图2中，我们比较了六种学习算法的最佳回复动态的收敛频率。每个面板中的圆圈对应于最佳回复向量v，将所有具有相同v的Payoff矩阵组合在一起。每个最佳回复向量的权重是对具有v的Payoff矩阵进行采样的（1000）倍的分数。

这决定了圆的大小，并用于加权相关系数Rw。我们将每个bestreply向量根据其在bestreply动态F（v）下的不收敛频率放置在水平轴上。在纵轴上，我们绘制了每个学习算法的不收敛频率。因此，如果最佳回复动态能够完美预测其他学习算法的收敛速度，那么所有圆圈都应该以身份线为中心。模拟值和预测值之间有很强的相关性，在每种情况下，加权相关系数Rw>0.75。在强化学习和游戏中，F（v）高估了非收敛的频率。这是因为这些算法经常会收敛到混合策略纳什均衡，而bestreply动态只能收敛到纯策略纳什均衡。然而，除了一个恒定的效应集，不收敛的速率是成比例的。相比之下，两个种群复制子动态无法收敛到混合策略纳什均衡[10]，因此收敛速度较低，并且没有来自身份线的影响集。在SI第2节中，我们展示了这六种学习算法收敛的相关矩阵。我们发现，平均60%的情况下会同时发生收敛，对于强化学习，原因更为技术性，并在SI中进行了讨论。在这里，我们考虑两个种群复制因子动态，而不是更标准的一个种群版本，因为专注于随机生成的博弈，支付矩阵是不对称的。这表明算法具有显著的异质性。虽然相关性很好，但在行为上并不总是有详细的对应关系。例如，即使没有最佳回复周期，也无法确定收敛性。F（v）=0上方的垂直圆列证明了这一点。

此列对应于并没有循环的最佳回复向量，即形式v=（0，…，0，0，x），其中x=1，2。是不同固定点的数量，从上到下递增。右侧列的圆圈对应的是具有周期且无固定点（F（v）=1）的最佳回复向量，从下到上的周期比例较高。在这种情况下，学习算法可能会收敛（例如，收敛到混合策略均衡），但随着最佳回复周期变得越来越可能，收敛速度明显下降。插图显示了使用Payoff矩阵的布尔约化进行模拟的结果。这种相关性现在非常强：在所有情况下，除了实际情况外，加权相关性都接近统一。布尔约化的相关性如此强的原因主要是因为原始Payoff矩阵具有连续值，因此学习算法可能遵循所谓的准最佳回复（见SI，第2节）。尽管布尔约简与原始矩阵具有完全相同的最佳回复动态，但如果学习规则涉及历史依赖性和有限理性，则其他支付的值可能很重要。例如，inFig。1A，第（2,3）列的付款为15，而第（2,1）列的付款为16。这两种支付方式非常接近，由于历史依赖性和有限理性，玩家栏可能会选择移动3而不是移动1，从而打破最佳回复周期并达到固定点。对于竞争性博弈，也存在着收敛到混合策略纳什均衡的问题，这就是布尔约简的相关性要低得多的原因。总之，平均收敛概率与最佳回复结构之间存在稳健的相关性。

即使最佳回复动力学的轨迹不一定能预测其他学习算法的轨迹，并且无法从最佳回复周期的份额中准确计算任何特定支付矩阵中的收敛概率，这也是事实。最佳回复结构的变化随着游戏属性的变化，我们现在调查最佳回复周期和固定点的流行情况。被深入研究的博弈类，如协调博弈、超模博弈、优势可解博弈和势博弈【12、13、14、15、16】都是最佳回复非循环的。什么时候是典型的，什么时候是罕见的？与Galla和Farmer[25]的观点一致，我们发现游戏的两个关键参数是可能的移动次数N和两个玩家的支付之间的相关性。随着N的增加，直觉上很明显，游戏变得更难学习，但这对最佳回复结构的影响并不明显。为了理解Γa如何影响收敛，我们生成了payoff矩阵，以便对于任何给定的移动组合，payoff对playersRow和Column的乘积的期望值等于Γ。负相关，Γ<0，意味着游戏是竞争性的，因为对一方有利的东西可能对另一方不利。极端情况为Γ=-1，意味着游戏是零和游戏。与此相反，0鼓励合作，因为这样做的好处往往要么对双方都有利，要么对双方都不利。这直观地增加了纯策略纳什均衡的机会，但不清楚这对于最佳回复周期意味着什么。在图3中，我们展示了最佳回复周期的份额如何随N和Γ而变化。对于给定的N和Γ值，我们随机生成payoff矩阵，并计算不收敛的平均频率F（v）。我们将其与EWA学习算法的平均不收敛频率进行比较。

（我们选择SEEWA是因为它是六种算法中最普遍的学习规则；它的行为是典型的）。标记与虚线之间的良好匹配证实了2 5 15 30 100 400N0.00.20.40.60.81.0-1.0-0.6-0.2 0.2 0.6 1.00.20.40.60.81.00.20.40.60.81.00.20.40.60.81.0=0.7=0.7N=50N=10N=3最佳回复周期（虚线）非收敛动态（标记）图3：最佳回复结构和收敛速度EWA随移动n和两个参与者的薪酬之间的平均相关性。虚线是最佳回复周期F（v）的份额（即最佳回复动态的不收敛率）。标记是不收敛的EWA模拟运行的分数。负相关Γ增加了最佳回复周期的份额；正相关具有相反的效果。随着N的增加（只要Γ不大且为正），最佳回复周期变得占主导地位。结果如图2所示，并进一步证明了最佳回复结构的预测值。唯一的例外是Γ=0和n≥ 30，其中最佳回复动态高估了WA不收敛的频率。我们发现，当Γ为非正且N足够大时，最佳回复周期变得普遍。在参数空间的这个区域，非循环博弈是极为罕见的。因此，优势可解、协调、势和超模对策只代表了可为这些N和Γ创建的所有可能支付矩阵的一小部分。分析方法对于Γ=0，可以通过分析得出最佳回复结构如何随N变化。可能的最佳回复配置总数为N2N。如果Γ=0，则所有Payoff矩阵∏的可能性相等。因此，我们可以通过计算导致v的最佳回复配置数来计算任何吸引子集Vb的频率ρ（v）。

用统计力学的术语来说，我们假设的是一个微观的游戏规范组合。在这里，我们只是简单介绍一下推导过程，让读者参考SI（第3.1节）进行详细解释。由于独立性，频率ρ（v）可以写成与获得每种类型吸引子的路径数相对应的项f的乘积，乘以自由移动的项g（不在吸引子上的最佳回复）。我们用每个玩家的移动次数来表示，移动次数是循环或固定点的重要组成部分。函数f（n，k）统计了获得k循环的方式（包括固定点，长度为k=1的循环）、f（n，k）=nk公司k（k）- 1） ！，（1） 其中，二项式系数意味着对于每个玩家，我们可以选择任意k个移动，形成循环或固定点，而因子量化了所有最佳回复的组合，这些组合产生了循环或固定点，与所选的kmoves。例如，在图1中，对于每个玩家，我们可以从4个动作中选择任意2个动作来形成a2循环，并且对于其中的每个动作，都有两个可能的循环（一个顺时针，另一个逆时针）。有2个循环的方法的数目是f（4，2）=72。同样，对于每个玩家，我们可以从剩余的两个动作中选择任何一个动作来形成一个固定点，f（2，1）=4种方式。在本例中，对于两个玩家，我们仍然可以自由选择一个最佳回复，前提是这不会形成另一个固定点（否则，最佳回复向量会有所不同）。英菲格。1，免费的最佳回复是（3，4）行和（4，1）列。一般来说，gN（n，d）统计将剩余的n个免费最佳回复组合在一个n×n支付矩阵中的方式数量，以便它们不会形成其他循环或固定点，gN（n，d）=N2n-nXk=1f（n，k）gN（n-k、 d+1）/（d+1）。（2） 第一个术语N2查询免费最佳回复的所有可能组合，总和计算“禁止”组合，即。

形成循环或固定点的。2 5 15 30 100 400N0.00.20.40.60.81.0频率1/3仅周期仅固定点周期+固定点图4：当Γ=0时，关于最佳回复周期的分析预测与数值模拟的比较。标记是数值结果，实线是分析结果。红色圆圈表示无固定点（F（v）=1）的随机生成支付矩阵的频率，蓝色三角形表示至少一个周期（F（v）>0）的频率。图中的文本指的是由实线分隔的区域，例如，“周期+执行点”表示同时包含周期和固定点的支付矩阵的分数是红色线和蓝色线之间的距离。最后，绿色方块表示最佳回复周期FN的平均份额；由于计算成本过高，在N=50时停止使用，请参见SI第3.2节）。该术语具有递归结构。它计算形成每种类型吸引子的方法的数量，然后计算不具有其他吸引子的剩余n的方法的数量-K移动。注意，N是一个参数，因此表示为一个下标，而N是一个递归变量。d表示递归深度。最后，需要用d+1除法来防止吸引子的二倍、三倍等计数。在图1的示例中，g（1，0）=15。对于任何给定的最佳回复向量v=（nN，…，n，n），其频率ρ的一般表达式为ρ（v）=NYk=1nkYj=1fN-PNl=k+1nll- （j）- 1） k，kj×gNN-NXl=1nll，0！，N2N.（3） 第一个括号中的乘积计算所有可能的吸引子集的方法。f，N的第一个参数-PNl=k+1nll-（j）-1） k，迭代量化尚未成为其他吸引子一部分的移动数。j的除法，就像式（2）中d+1的除法一样，需要防止吸引子的二倍、三倍等计数。

第二个术语GN统计所有可能的方式来定位freebest回复，以便它们不会形成其他吸引者。GNI的第一个参数是不属于吸引子的移动数，初始递归深度为0。最后，我们将频率除以所有可能的配置N2N。对于支付矩阵inFig。1，ρ（0，0，1，1）=f（4，2）f（2，1）g（1，0）/4=0.07。然后，可以使用公式（3）计算任意给定N的最佳回复动态F的不收敛的误差平均值，FN=Xvρ（v）F（v），（4）对所有可能的v s.t.PNk=1nkk求和≤N、 也可以计算其他数量，包括无固定点（F（v）=1）和无循环（F（v）=0）的支付矩阵分数。我们在SI（第3.2节）中提供表达式并解释其推导。在图4中，我们分析了N值增加的最佳回复结构。我们从下到上报告了无固定点的Payoff矩阵分数、最佳回复周期的平均份额FN以及至少有一个周期的Games分数。例如，对于N=30，36%的支付矩阵没有固定点，84%至少有一个周期（因此16%没有周期，48%有周期和固定点的混合），平均FN=0.70。分析结果（实线）和蒙特卡罗抽样（标记）之间有很好的一致性。具有圈的对策的分数是N的递增函数；对于大的N，计算这一点在计算上是困难的，但它似乎等于1。然而，至少有一个固定点的游戏分数似乎达到了N的固定值→ ∞. 在SI的第3.3节中，我们表明这近似为1/3，与数值模拟一致。讨论我们提出了一种新的形式主义，可以帮助我们理解在重复游戏中学习无法收敛到非平衡状态的情况。