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

3，顶板。S2补充数值结果0.00.20.40.60.81.0R2w=0.94钢筋学习R2w=0.76虚拟铺层R2w=0.98复制动态0.0 0.2 0.4 0.6 0.8 1.00.20.40.60.81.0R2w=0.98EWA0.0.2 0.4 0.6 0.8 1.0R2w=0.92EWA，噪声0.0 0 0.2 0.4 0.6 0.6 0.8 1.0R2w=0.94Level-kR2w=1.0 W=0.41 R2w=1.0R2w=1.0 R2w=0.92 R2w=0.41最佳回复周期的份额F（v）非收敛动态图S6：与主要论文的图2，但N=5而不是N=20.0.00.20.40.60.81.0R2w=0.68钢筋学习R2w=0.63虚拟铺层R2w=0.72复制动态0.0 0 0.2 0.4 0.6 0.8 1.00.20.40.60.81.0R2w=0.76EWA0.0.2 0.4 0.6 0.8 1.0R2w=0.53EWA，噪声0.0 0 0.2 0.4 0.6 0.8 1.0R2w=0.74Level-KR22W W=0.98 R2w=0.69 R2w=0.93R2w=0.96 R2w=0.99 R2w=0.96最佳回复周期的份额F（v）非收敛动态图S7：相同如主文件的图2所示，但N=50而不是N=20。在本节中，我们首先对主要论文中的数值结果进行一些稳健性测试。然后，我们给出了一些关于学习算法的异质性以及布尔和非布尔payoff矩阵之间的相关性的其他结果。对于与稳健性测试相关的内容，一旦我们考虑不同的移动次数N，我们将检查是否得到与主要论文图2相同的结果。如图6和S7所示，总体模式相似，但存在一些差异。我们正在绘制最佳回复动态不收敛的分数，如最佳回复周期F（v）在水平轴上的相对份额所示。我们所考虑的六种学习算法的非收敛模拟运行部分位于纵轴上。当N=5时，相关性比N=20时更强，在非布尔Payoff矩阵中，加权相关系数的值甚至大于0.9。

我们推测，这是由于作为周期和固定点一部分的移动比例较高。实际上，对于N=5，最常见的具有周期的最佳回复向量是v=（0，0，0，1，0），因此作为周期一部分的移动是2/5。另一方面，在2周期且n=20的最佳回复向量中，属于该周期一部分的移动为2/20，因此非最佳回复的支付更为重要，而准最佳回复的问题更为严重。一个有趣的细节是，k级学习在大多数情况下都会收敛。对单个模拟运行的检查表明，通过预测对手的动作，玩家不太可能陷入周期性循环，而是收敛到混合策略均衡。对于N=50，我们观察到与N=5相反的模式：相关性变得更大（但在大多数情况下仍大于0.6）。这种影响最有可能是由作为周期或固定点的一部分的少量移动引起的（最常见的最佳回复向量isv=（0，…0，1，1），仅涉及3/50的移动）。准最佳回复可能发挥着更重要的作用。然而，我们不能排除测量误差。在图S8中，我们展示了我们所考虑的六种学习算法的共现收敛性的相关矩阵。对于N=20的1000个Payoff矩阵中的每一个，以及每个学习算法，我们计算不收敛的频率。因此，我们有六个1000个分量的向量，我们考虑了BMFPrDewaewanlevelKBMFPrDewaewanlevelK0.40.50.60.70.80.91.0图S8：在Bush-Mosteller（BM）学习、虚拟游戏（FP）、复制器动力学（RD）、经验加权吸引（EWA）的1000个支付矩阵中，任何一个矩阵中不收敛的共现相关矩阵，带噪声的EWA（EWAN）和k级学习（LEVELK）。他们

完美的相关性意味着对于每个Payoff矩阵，非收敛速度是不同的。我们发现，三种最相关的算法是复制子动力学、经验加权吸引（EWA）和k级学习。最不相关的两种算法是“实际播放”和“带噪声的EWA”。相关性范围在0.35和0.85之间，表明这六种算法之间存在较强的异质性。最后，在表S1中，我们展示了布尔型和非布尔型Payoff矩阵中收敛的共现性之间的相关性。与之前一样，我们考虑1000个分量的向量，其中每个分量是特定Payoff矩阵中不收敛的频率。相关关系是通过参考布尔和非布尔Payoff矩阵的向量之间的成对比较获得的。由于布尔支付矩阵被构造为与非布尔对应矩阵具有相同的最佳回复结构，因此缺乏完美的相关性是由于支付矩阵的细节。有趣的是，在游戏中，相关性非常低，而在复制动态和EWA中，相关性相对较高。BM FP RD EWA EWAN LEVELK平均值0.49 0.35 0.65 0.61 0.46 0.52 0.51表S1：对于我们考虑的六种学习算法，布尔和非布尔payoff矩阵中非收敛的共现之间的相关性。S3分析计算的详细信息首先，我们提供了最佳回复向量频率表达式的彻底推导，并在一些示例中使用它。其次，我们获得了量化任何给定长度的至少一个周期（包括固定点，即长度为1的周期）的Payoff矩阵的分形的其他表达式，并使用这些方程来确定没有执行点或至少一个周期的Payoff矩阵的份额。

第三，我们推导了有限维Payoff矩阵中循环频率和固定点的渐近估计。S3.1最佳回复向量的频率首先讨论形成最佳回复动态的k周期和固定点的方式的计数，然后我们计算放置免费最佳回复的方式（即不属于其他周期或固定点的方式）。最后，我们展示了如何将这些数字组合在一起，以获得对应于特定吸引子集的最佳回复配置数。1 2 3sC123sR1,0 0,0 0,10,0 0,1 1,00,1,0 0,0123sR公司123sC1 2 3sC123sR1,0 0,1 0,00,0 1,0,10,1 0,0 1,0123sR公司123sC1 2 3sC123sR0,0 1,0 0,11,0 0,1 0,00,1 0,0 1,0123sR公司123sC1 2 3sC123sR0,1 0,0 1,00,0 1,0 0,11,0 0,1 0,0123sR公司123sC1 2 3sC123sR0,1 1,0 0,00,0 0,1,01,0 0,0,1123sR公司123sC1 2 3sC123sR0,0 0,1 1,00,1 1,0 0,01,0 0,0,1123sR公司123sC1 2 3sC123sR1,0 0,0,10,1 1,0,00,0,1 1,0123sR公司123sC1 2 3sC123sR1,0 0,1 0,00,1 0,0 1,00,0 1,0 0,1123sR公司123sC1 2 3sC123sR0,0 1,0 0,10,1 0,0 1,01,0 0,1 0,0123sR公司123sC1 2 3sC123sR0,1 0,0 1,01,0 0,1 0,00,0 1,0 0,1123sR公司123sC1 2 3sC123sR0,1 1,0 0,01,0 0,0,10,0 0,1 1,0123sR公司123sC1 2 3sC123sR0,0 0,1 1,01,0 0,0,10,1 1,0 0,0123sR公司123sCFigure S9：所有可能的3！2！=12种方式组合每个玩家3个动作，形成3个循环。颜色代码与正文一致。（1,2,3）垂直数组包含移动标签，箭头表示最佳回复。一个周期是最佳回复的闭环。这12种组合也是最好的重复配置，其特点是在N=3的支付矩阵中具有3个周期。使用公式（S21），f（3，3）=12。我们通过示例开始k-循环的计数。在图S9中，我们详尽地报告了在N=3的Payoff矩阵中形成3个循环的所有可能途径。

垂直（1、2、3）数组和箭头连接着动作的标签，说明了主要的直觉：我们找到了所有可能的最佳回复序列，形成了一个闭环。我们任意地从sR=1开始（因为这是一个循环，起始点无关紧要），我们查看最佳的玩家回复列sC∈ {1，2，3}，我们将sR=1与sC连接起来。在左上方的面板中，我们将sR=1与sC=3连接起来。可通过k=3种方式进行选择。一旦我们按列确定了第一个最佳回复，我们将通过按行选择第二个最佳回复来继续构建循环。第二个选项只能在k中完成- 1=2路。在左上方的面板中，我们将sC=3连接到sR=2。然后，按列选择第二个最佳回复。同样，我们有k- 1=2种可能性。在左上角的面板中，我们将sR=2连接到sC=2。行和列的第三个也是最后一个最佳回复受到限制，只有一个（k-2=1）选择剩余BR的方式。在左上面板中，我们将sC=2连接到sR=3，并将sR=3连接到sC=1。我们有3·2·2·1·1=12种方式来形成3个周期，其中n=3个可用动作。回想一下，n表示每个玩家尚未成为周期或固定点一部分的移动次数。通常，n可能小于n，但在图S9中，所有移动都是循环的一部分，因此n=n=k=3。我们有可能将这个论点推广并得出结论，即存在k！（k）- 1） 哦！形成k循环的方法，一旦我们确定涉及玩家的行和列的移动。n中的任意移动都可以选择（由两个玩家选择），因此nk公司可能性。

我们定义（n，k）=nk公司k（k）- 1） ！，（S21）带2≤ k≤ n、 作为每个玩家有n个可用移动的k循环的方法计数。在上述示例中，f（3，3）=12.1 2 3sC123sR1,1 0,0,00,0 1,1 0,00,0 0,0 1,11 2 3sC123sR0,0 0,0 1,10,0 1,1 0,01,1 0,0,0,01 2 3sC123sR1,1 0,0,0,0 1,0 1,0,1 0,0,01 2 3sC123sR0,0 1,1 0,0,0 1,11,1 0,0,0,0,01 2 3sC123sR0,0,1,0,0 1 0,0 0,00,0 0,0 1,11 2 3sC123sR0,0 0,0 1,11,1 0,0 0,0 0,00,0 1,0,0图S10：所有可能的3！=6种方式组合每个玩家3个动作，形成3个固定点。颜色代码与正文保持一致。请注意，这些都是最佳回复配置，在N=3的支付矩阵中有3个百分点。使用公式（S21），f（3，1）f（2,1）f（1,1）=9=6。现在，我们来看一下形成固定点的方法，我们再次从示例开始。在图S10中，我们报告了在N=3的支付矩阵中形成3个固定点的所有可能方法。一旦我们确定哪些动作是固定点的一部分（在这种情况下是全部），我们就可以通过从两个层的可用动作列表中挑选成对的动作来形成所有可能的固定点组合。为了方便起见，我们再次从sR=1开始。我们通过选择anymove sC形成固定点∈ {1，2，3}，因此sR、sC是一个固定点。在左侧面板中，我们选择（1,1）作为第一个固定点。然后我们考虑sR=2。playerColumn只有两个动作可以构成第二个固定点。在左面板中，（2,2）是第二个固定点。最后，对于sR=3，只有一个move by Column可用。通过消除过程，左面板（3,3）中是第三个也是最后一个固定点。该示例说明，固定点数量的计算与循环的情况非常相似，实际上，固定点只是长度为1的循环。为了获得形成固定点的方法的数量，我们可以迭代地应用等式（S21），并考虑二元、三元等。

定点计数。我们得到nyj=1f（n+1- j、 1）j（S22）作为每个玩家有n个可用移动的n个固定点的方法计数。在上述示例中，f（3，1）f（3,2）f（3,3）=9=6.1 2 3sC123sR1,0,1 0,00,1 1,0 1,00,0 0,0,11 2 3sC123sR1,0,1 0,00,1,0 1,00,0 0,1 0,01 2 3sC123sR1,0,1 1,00,1 1,0,0,0,0,1 0,0,0,1 2 3sC123sR1,0,1,00,1 1,0,0,0,0,0,0,0,1 2 3sC123sR1,0,1 0,00,1,0,00,0,1,1,01 2 3sC123sR1,0,1 0,00,1 1,0,00,1 0,0 1,01 2 3sC123sR1,0,1 1,00,1,0,0,00,1 0,0,0,01 2 3sC123sR1,0,1 0,00,1,0,0,0图S11：所有可能的3- 1=选择其余两个最佳回复的8种方式，以便它们不会在（3，3）处形成固定点。色码与正文保持一致。使用公式（S23），g（1，0）=8。我们最终会计算放置免费最佳回复的方式，这些回复不属于其他周期或固定点的一部分。我们再次从示例开始。在图S11中，我们显示了每个玩家有一个免费最佳回复的支付矩阵。在左上角的面板中，行到列playingsC=3的最佳回复是sR=2；列对行播放sR=3的最佳回复是sC=3。免费的最佳回复可以自由选择，除非它们都是移动3，在这种情况下，它们将形成另一个固定点。本例中有3个- 1=选择免费最佳答案的8种方式，这样它们就不会形成其他周期或固定点。一般来说，gN（n，d）=N2n-nXk=1f（n，k）gN（n- k、 d+1）/（d+1）（S23）统计所有可能的方式，将n个免费的最佳回复组合在一个n×n支付矩阵中，以便它们不会形成其他周期或固定点。我们在本节末尾提供了公式（S23）的更完整示例。注意，N是一个参数，因此表示为一个下标，而len是一个递归变量：即使可用移动数N小于N，也可以从所有N个移动中选择N2nways中的任意最佳回复（见图S11）。

第二项统计“禁止”组合，即形成循环或固定点的组合。该术语具有递归结构。它计算形成每种类型吸引子的方法的数量，然后计算不具有其他吸引子的方法的数量。d表示递归深度。为了防止吸引子的二倍、三倍等计数，需要用d+1来划分。现在，我们结合所有获得周期、固定点和免费最佳回复的方法来计算与通用最佳回复向量v=（nN，nN）相对应的最佳回复配置数-1.nk。。。n、 n）。我们用n固定点的数量表示，用n表示，用2表示≤k≤ N、 k循环数。当然，v必须服从一个明显的约束，即固定点和k循环不会占用超过N个移动：PNk=1nkk≤ N、 最佳频率1 2 3 4 5 6 7 8 9 10 11sC1234567891011sR3，-10 3,14-20,2-2,11 0,3-9,11-24,3 3,8 0,1-2,0-5，-1-7,6 7,0-2，-1-7，-7-8，-1-3，-4，-2-5,3-10,1-2，-2-12，-92，-3 1，-17-3,2-10,0,0，-7 4,0-4,0-1，-4-10，-4-5，-5，-5 9 3，-11-2,4 0,2 8，-10 6,2-3，-9 0,2-13，-5-1,0-2,1 6,10-6，-3-5,0 1，-6 6 6,19-7，-6 2,7-17,4-1,7-18,0-4，-15 6，-7 2,1-3，-9-4,2 7，-11 8，-10-3，-4-3，-1-12，-7-14,01,11-6，-6-6,9-21,5-11,8 10，-4-8,13 0,4-2,6-22,4-7,01，-2，-8 2，-6-1，-11-3，-5-7，-9-1，-18 1,0，-5 1，-1-8,3 5，-4-7,1-7，-7，-4-4,2-3,4-25,0-1,7-13，-1-16,0,1 1，-7-2，-5 5，-12-5,1 0,0-1,0-2，-3 4，-7-5，-8 1，-2 0,1 1，-6,0 0，-1-4，-3 2,2-2,1图S12：N=11的支付矩阵。色码与正文保持一致。Payoff矩阵中最佳回复动态的吸引子集为v=（0，0，0，0，0，0，1，2，2），如果k>3，则n=1，n=2，n=2和nk=0。isPk=1nkk=9<11。回复向量v为ρ（v）=NYk=1nkYj=1fN-PNl=k+1nll- （j）-1） k，kjgNN公司-NXl=2NL- n、 0！，N2N.（S24）等式（S24）是等式。

（3） 在主要论文中。带f的第一项通过乘以k（第一乘积）的所有值和k（第二乘积）的特定值的所有k循环计数，计算所有k循环的方式。请注意，随着越来越多的移动成为k周期的一部分，我们逐渐减少了可形成k周期的移动次数（请参见下文中阐明这一点的示例）。如果有多个k-循环，nk>1，我们将计数除以j=1。。。nkso避免双重、三重等计数。k=1的情况占到了满分。第二项GN计算选择剩余N的所有方法-PNl=2nll-nfreebest回复。三项的乘积给出了对应于最佳回复向量v的最佳回复配置数。我们将该数除以可能的配置sn2n，得到频率ρ（v）。例如，我们使用图S12所示的同一组描述符计算最佳回复配置的数量。我们开始计算形成3个周期的方式。我们可以从11个动作中选择任何3个动作，让两名球员都成为3个周期的一部分，这意味着可能性。一旦我们为每个玩家选择了3个动作，我们可以通过选择3为每个选择获得12个循环！2！=12个动作序列。所以形成3-圈的方法是f（11，3）。同样的原因也适用于两个2周期，除了每个玩家只有8个和6个动作可用，并且2周期的方法数需要除以2，以避免重复计算。所以我们用f（11，3）乘以f（8，2）f（6，2）/2。剩余4个动作中有2个固定点的最佳回复配置的数量可以类似地计算：每个层可以从4个动作中选择第一个固定点，从3个动作中选择第二个固定点，但我们必须考虑重复计算。因此，f（4，1）f（3，1）/2给出了在剩下的4个动作中形成两个固定点的方法。

我们每个球员只有2个动作，不属于周期或分数的一部分。有11种方法可以选择免费的最佳回复，但我们必须排除那些会形成另一个2周期或一个或多个固定点的情况。有2种方式可以形成2个循环（f（2，2）），有4种方式可以形成1个固定点（f（2，1））。但对于后者，我们必须考虑所有兼容的配置，即计算g（1，1）：有多种方法可以选择免费的最佳回复，减去此选择将形成另一个固定点的方式（除以2，以说明有两个固定点的情况）。总之，最佳回复配置数由ρ（0，0，0，0，0，0，0，1，2，2）=f（11，3）f（8，2）f（6，2）f（4，1）f（3，1）g（2，0）/（11），（S25）和f（11，3）=3·2·2，f（8，2）=2，f（6，2）=2，f（4，1）=1，f（3，1）=g（2，0）=11- 2.- 4·g（1，1），g（1，1）=11- 1/2。频率的显式计算得出ρ（0，0，0，0，0，0，0，0，0，0，1，2，2）=1.44·10-6，因此图S12中的最佳回复向量非常罕见。