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

我们检查是否在最后20%的时间步中，两个玩家最常用的移动概率都是单调递增的，而所有其他概率都是单调递减的。换句话说1。只考虑最后20%的时间步。2、对于每个玩家，找到概率最高的移动，并验证该概率在整个时间间隔内是否一直在增加。3、检查所有其他移动的概率是否在降低。4、如果两个参与者都满足条件2-3，则将模拟运行确定为收敛。这些标准只是反映了我们在图S3中观察到的情况。虽然我们不能得出这样的结论，但对100多个模拟值的直接检查表明，在绝大多数情况下，收敛到纯策略纳什均衡或未能收敛是正确的。最后，我们想对复制器动力学与其他学习算法相比似乎更强的不稳定性补充一句警告。由于内存有限，并且取决于初始条件，可能需要很长时间才能“找到”纯策略纳什均衡，这意味着复制器动态可能会在仍处于“瞬态”时首先达到机器精度极限。换句话说，它可能不在由周期决定的吸引盆地中，但也可能在信任时间间隔内未达到纯策略纳什均衡。这对于大型Payoff矩阵尤其如此，N≥ 从图S3底部面板中的直线可以看出。我们使用Python包decimal对任意精度的数字进行了实验。

这并不是很有帮助，因为随着模拟的进行，玩家切换到其他动作所需的时间会成倍增加。此外，它在计算上非常昂贵，因此一次具有任意精度数字的模拟运行的持续时间可能是具有浮点数的等效模拟运行的100倍以上。参数值我们通过选择δt=0.1的积分步长（足够小以防止概率单纯形边界的超调）和最大3000个时间步长的模拟时间来模拟复制器动力学。然而，如前所述，模拟时间通常较短，并由第一个到达机器精度边界的策略决定。S1.1.5经验加权吸引Camerer和Ho提出了经验加权吸引（EWA）[S16]，以推广强化和信念学习算法（如游戏或最佳回复动态）。关键的见解是，真正的玩家使用有关经验丰富的支付的信息，就像在强化学习中一样。但他们也会尝试预测对手的下一步行动，就像在信念学习（belieflearning）中一样。作者报告说，与简单的强化学习或游戏相比，实验样本外的拟合优度更好，这表明有证据支持他们的理论。强化和信念学习之间的联系在于更新未玩过的动作，即考虑已放弃的回报。如果只更新玩过的动作的概率，EWA将简化为强化学习的简单版本（而不是第S1.1.2节所述的Bush-Mosteller实现）。

如果所有概率都以相同的权重进行更新，则EWA将根据参数的不同，减少为实际播放或最佳回复动态。最后，请注意，EWA还通过限制某些参数（例如，通过限制有限内存）来降低复制因子的动态性。【S17】在EWA的正式定义中，混合策略是根据所谓的吸引力或倾向Qui（t）确定的。这些实数量化了玩家在t时对动作i的欣赏程度。吸引力没有标准化，因此玩家划船玩动作i的概率由logit给出，xi（t+1）=eβQRi（t+1）PjeβQRj（t+1），（S14），其中β是选项的支付敏感性或强度，类似的表达式适用于yj（t+1）。倾向更新如下：Qui（t+1）=（1- α） N（t）Qui（t）+（δ+（1- δ） I（I，su（t+1））∏u（I，s-u（t+1））N（t+1），（S15），其中N（t+1）=（1- α） （1）- κ） N（t）+1。（S16）这里，N（t）代表经验，因为它随所弹奏的圈数单调增加；它增长得越多，收到的回报对景点的影响就越小（随着分母的增加）。当使用移动i对抗移动s时，倾向会根据收到的支付而变化-其他参与者，即∏u（i，s-u（t+1））。如果I是uattime t+1播放的实际移动，则指示器函数I（I，su（t+1））等于1，即I=su（t+1），否则等于0。所有吸引力（与较大的β相对应的那些，玩家在决定策略时越考虑吸引力。在极限β中→ ∞球员们肯定会选择最吸引人的动作。

在极限β内→ 0他们随机选择，无视景点。对于已经玩过和没有玩过的策略）更新为权重δ，而额外的权重1- δ表示与实际显示的移动相对应的特定吸引力。最后，记忆丧失参数α决定了之前的吸引力和经验被打折的速度，而参数κ在累积和平均强化学习之间插值[39]。与其他学习算法一样，我们采用确定性限制。在批量学习假设下，等式（S15）readsQRi（t+1）=（1- α） N（t）QRi（t）+（δ+（1- δ） xi（t））Pj∏R（i，j）yj（t）N（t+1），（S17）和类似表达式适用于列。400 425 450 475 5000.00.20.40.60.81.0400 425 450 475 50010281023101810131081030 200 4000.00.20.40.60.81.00 200 40010361029210221015108101TXI（t）图S4：N=20的经验加权景点模拟运行实例。每一行都是行的混合策略向量的一个组件（并非所有组件都可见，因为它们重叠）。左侧面板：非收敛模拟运行。已选择水平轴的范围以便于动力学的可视化。右面板：聚合模拟运行。顶部面板：线性比例。底部面板：垂直轴上的对数刻度。收敛标准考虑图S4，右侧面板。与其他学习算法不同，EWA动力系统的所有组件都达到一个固定点，因此更容易识别收敛性。我们运行了500个时间步的EWA动力学，并考虑了最后20%的时间步来确定收敛性。对于我们为α、β、κ和δ选择的参数值，瞬态通常为100个时间步，因此500个步骤足以识别收敛。

然后，我们检查混合策略向量分量对数的平均方差是否超过某个（非常小）阈值。我们看对数是因为EWA动态之后的概率在指数尺度上变化，可以是，例如，10的数量级-100、在公式中，如果1/NPNi=15/TPTt=4/5T（对数xi（t））>10-2或1/NPNj=15/TPTt=4/5T（对数yj（t））>10-2，当T=500时，我们确定模拟运行为非收敛的。从计算角度来看，参数值EWA有两个主要优点。首先，如果记忆丢失参数为正（α>0），EWA系统的所有稳定吸引子都位于概率单纯形内。这意味着不会给任何移动赋予零概率或单位概率，并且可以在任意长的时间内可靠地模拟EWA映射，因为对于α的足够大的值，机器精度永远不会达到极限。这个属性的直觉很简单：非常成功或非常不成功的动作的表现会随着时间的推移呈指数级地被遗忘，因此即使是很小的α值也会提示玩家以正概率选择不成功的动作。第二个优点是，EWA系统在每一个时间步都被明确规范化，不太可能出现数值错误。EWA还有一个计算上的缺点：因为它使用指数函数将吸引力映射为概率，如果Payoff灵敏度β的值太大，混合策略向量的成分可能会变化太多数量级，因此会超出混合策略单纯形的边界。因此，在选择α和β值时应小心。这种情况也是因为EWA系统的另一个特点：记忆损失大或支付敏感性小，学习动态会收敛到策略单纯形的中心。

在β=0的极限范围内，玩家只需在可能的移动之间均匀地随机选择，而不考虑支付矩阵。参考文献[25]中观察到，对于α/β的足够大的值，唯一的固定点总是稳定的。这样一个固定点可以任意远离混合策略均衡，因此通过改变他们的策略，玩家可以提高他们的报酬。我们对这个“琐碎”的吸引子不感兴趣，因为我们想关注支付矩阵的最佳重复结构对学习动态的影响。因此，我们选择α和β的参数值，以防止收敛到此固定点。最后一个重要的技术备注是，我们通过√当支付矩阵变大时。原因是预期的sPj∏R（i，j）yjandPi∏C（j，i）xiscale为1/√N、 事实上，专注于玩家行的预期收益，Pj∏R（i，j）的规模为√N由于中心极限定理（回想一下，payoff是随机生成的，请参见下面的精确规则），而组件yj由于规格化约束而缩放为1/N。SoPj∏R（i，j）yjscales as 1/√N、 同样的参数也适用于ExpectedPayoff of player列。现在，请注意β乘以等式的预期收益。（S14）和（S17）。因此，增大payoff矩阵的大小与减小β具有相同的效果，直到策略单纯形中心的吸引子再次变得稳定。为了防止这种情况发生，我们通过√N、 因此，βPj∏R（i，j）yjandβPi∏C（j，i）xido不与N成比例。对于所有模拟，我们选择α=0.18，β=√N、 κ=1和δ=1，这确保了EWA动力学保持在概率单纯形内，不会超出单纯形边界，也不会到达单纯形中心的平凡吸引子。S1.1.6经验加权吸引与噪音到目前为止，我们假设批量学习。

在这里，我们考虑在线学习，即玩家在观察对手的单个动作后更新其混合策略。玩家根据混合策略向量给出的概率选择移动。我们关注EWA，因为它具有优越的数值特性（与其他算法相比）。考虑到引入噪声使得识别收敛性更具挑战性，我们选择了识别收敛性最简单的算法。含噪声的形式定义EWA仅由等式给出。（S14）、（S15）和（S16）。在时间t，玩家行选择移动i的概率为xi（t），玩家列选择移动j的概率为yj（t）。0 50 100 150 2000.00.20.40.60.81.00 50 100 150 2000.00.20.40.60.81.00 1000 2000 3000 4000 50000.00.20.40.60.81.00 1000 2000 3000 4000 50000.00.20.40.60.81.0txi（t）图S5：噪声为N=20的EWA和EWA模拟运行实例。每一行都是行的混合策略向量的一个组件（并非所有组件都可见，因为它们重叠）。左侧面板：非收敛模拟运行。右面板：聚合模拟运行。顶部面板：EWA的确定性近似。底部面板：有噪音的EWA。收敛标准如图S5所示，EWA的确定性近似值和噪声版本通常非常相似。在收敛示例中，会不时选择一个不是最常用的移动（即浅绿线），这可能会使玩家的行偏离平衡。取而代之的通常情况是，玩家在短时间后恢复平衡。我们使用以下收敛启发式：1。只考虑最后20%的时间步。2、只保留使用频率大于1/N.3的动作。找出最常见的概率值，即固定点。4.

计算概率与MOSTCOMON值相差大于0.02的事件。如果发生次数超过所考虑时间间隔的10%，则将模拟运行确定为非收敛。否则，将其标识为收敛。参数值不同于确定性EWA的情况，我们需要考虑一个较长的时间间隔，以便动力学稳定为吸引子。对于Bush Mosteller dynamics和Fictive play，我们最多需要5000次迭代。参数值相同，只是选择的强度不同：我们取β=√第2页。我们减少选择强度的原因是β=√N导致动力学过于接近策略单纯形的边界，噪声几乎消失。事实上，如果主导策略是以概率进行的，例如xi（t）=0.99995，则偏离均衡的可能性极低，并且是确定性的情况。S1.1.7 k级学习我们将k级学习称为预期学习的推广（Selten[S18]提出）。塞尔滕认为，player Row不相信该专栏会像过去那样行事。相反，他试图通过最好地回应他认为她将在下一个时间段采取的策略来智胜她。Row需要对她的策略进行预测，并通过假设Column是一名EWA学习者来获得该预测。这个想法可以通过假设玩家可以提前思考k步来推广【S19，S20】。在k级思维中【S21、S22】k级玩家假设其他玩家都是k级玩家- 1，该过程将迭代到级别1。一级玩家随机选择。二级玩家知道一级玩家随机选择，并根据这条信息选择产生最高回报的策略。三级玩家知道二级玩家的行为，并做出相应的反应，等等。在我们的案例中，1级玩家是EWA学习者。

二级玩家知道一级玩家使用电子战更新他们的策略，并试图通过先发制人来获得更好的回报。三级玩家将知道二级玩家如何选择策略，并选择可能的最佳策略作为回应。在这里，我们将假设两个参与者都是2级，因为我们没有发现k值越大的实质性差异（这很快就会变得行为不稳定）。形式定义为方便起见，我们结合了等式。（S14）和（S17）：xi（t+1）=xi（t）（1-α） N（t）/N（t+1）expβ（δ+（1- δ） xi（t））Pj∏R（i，j）yj（t）/N（t+1）Zx（t+1），（S18）带Zx（t+1）=Plxl（t）（1-α） N（t）/N（t+1）expβ（δ+（1- δ） xl（t））Pj∏R（l，j）yj（t）/N（t+1）.我们使用上标1表示玩家行是1级（即EWA）学习者。类似的表达式适用于列。我们用F（y（t））表示等式（S18）中的右侧，其中y（t）=（y（t）。yN（t））。所以，xi（t+1）=F（y（t））。玩家行基于列的过去混合策略向量进行学习。Wede fineyj（t+1）=F（x（t+1））。（S19）此处列为二级玩家，因为她认为Row是一级玩家，因此使用等式（S18）更新其策略。通常，ykj（t+1）=F（xk-1（t+1））。（S20）收敛准则动力学在性质上与EWA非常相似，因此我们使用相同的收敛准则。参数值我们也使用相同的参数值。行和列都是level-2players。S1.2 Payoff矩阵的初始化为了研究一般Payoff矩阵，我们通过随机生成Payoff元素对所有可能Payoff矩阵的空间进行采样。以下参考。

【25】在初始化时，我们随机生成Payoff s的NPAIR（即，如果行播放i，列播放j，则a、b对表示行播放a，列播放b），我们在其余模拟中保持Payoff矩阵固定（因此Payoff矩阵描述的系统可以视为已淬灭）。我们考虑Payoff矩阵的一个集合，该集合受对的均值、方差和相关性的约束。服从这些约束条件的最大熵分布是一个二元高斯分布[25]，我们用零均值、单位方差和相关性Γ对其进行参数化。因此，Γ<0意味着博弈是竞争性的（在Γ=-1） ，而Γ>0鼓励合作（见正文）。如果Γ=0，则所有最佳回复配置都是等概率的，因为支付是独立随机选择的，因此我们应将其视为基准情况，在这种情况下，我们以相同的概率抽样所有可能博弈的空间。主要论文的图2：我们从每个Payoff矩阵的100个随机初始条件开始，随机生成1000个Payoff矩阵，其中Γ=0，n=20。图3：我们从每个Payoff矩阵的10个随机初始条件开始，随机生成180个Payoff矩阵，其中Γ=0，移动次数如下：N={2，3，4，5，8，10，15，20，30，50，100，200，400}。我们明智地减少了每个N值的模拟运行次数，因为随机生成payoff矩阵、识别最佳回复结构和模拟动态都是N的耗时工作≥ 50.主要论文的图3，底部面板：与顶部面板相同，但我们考虑相关性Γ={-1.0，-0.9，-0.8，0.0，0.1，0.9、1.0}，且每个Γ值仅为50个Payoff矩阵。正文图4：同图。