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

对于我们在此研究的六种学习算法，非收敛性与最佳回复周期的存在密切相关。当它们无法收敛时，通过策略空间的轨迹与最佳回复周期不匹配。相反，正如加拉（Galla）和法默（Farmer）为EWA所作的研究[25]所示，典型的情况是混沌动力学。那么，为什么最佳回复周期的存在与不收敛密切相关呢？我们的假设是，最佳回复周期的存在表明Payoff空间中存在更复杂的非线性结构，这使得收敛到平衡更加困难。制定最佳回复结构的优点是简单明了，没有可调整的参数，也不会进行学习。正如我们在这里所展示的那样，这使得我们可以使用组合学来分析探索微观正则系综下所有博弈的空间，使用统计力学的概念框架。这项工作可以扩展到几个方向。通过研究最佳回复动态的修改版本，应该可以解释准最佳回复、历史依赖性和有限理性。例如，我们可以允许嘈杂的最佳回复，在这种情况下，玩家以一定的概率选择一个不是最佳回复的动作。我们还可以在最佳回复动态中进行forlevel-k推理，以研究前瞻性策略与后向性策略的作用。另一方面，在有两个以上玩家的游戏中，描述最佳回复结构也很有趣。我们的初步结果表明，高阶结构可能是相关的。例如，在三人游戏中，两个玩家可能处于一个最佳回复周期，但其余玩家可能不在。

此外，我们还可以分析Payoff矩阵的其他集合，例如引入顺序约束。最后，本文介绍的方法可以与生态学相关。广义的洛特卡-沃尔特拉方程等价于复制子动力学[37]，因此可能将最佳回复结构与食物网的网络特性联系起来[7]。在参考文献[42]中，作者表明，稳定子图在经验食物网中的统计比例过高，从而减少了反馈回路。我们的初步调查表明，对于相应的支付矩阵中的最佳回复周期，网络中的循环是一个有效但不是必要的条件。我们论文的主要含义是：如果可以描述为两人游戏的真实世界情况在某种程度上由随机构造的游戏集合表示，如果真实玩家可以通过我们在这里研究的学习算法来近似描述，当移动次数较多且博弈具有竞争性时，均衡很可能是一种不切实际的行为假设。材料和方法我们在此总结了用于模拟图2和图3中的学习算法的协议。我们只报告允许复制结果的最少信息。补充信息第1节中给出了更详细的描述，其中我们提供了行为解释并提及了替代规范。我们必须对收敛标准和参数值做出任意选择，但在测试替代规范时，我们发现相关系数的变化不超过几个十进制单位。这证实了最佳回复动态的收敛速度与六种学习算法的收敛速度之间存在稳健的相关性。考虑一个双人N步的普通formgame。

我们按u对玩家进行索引∈ {行=R，列=C}和它们的移动由i，j=1。N设xui（t）为玩家u在时间t玩移动i的概率，即其混合策略向量的第i个分量。为了便于标记，我们还用xi（t）Bush-Mosteller学习表示，游戏和复制动力学都具有有限的记忆。我们观察到不稳定的轨道，其中一种策略取代了其他策略，并且这种情况会周期性地发生，周期随时间呈指数增长。示例见SI第1节。玩家R在t时执行移动i的概率，由yj（t）表示玩家c在t时执行移动j的概率。我们进一步用su（t）表示玩家u在t时实际执行的移动，用su（t）表示-（t）对手采取的行动。玩家u的支付矩阵为∏u，其中∏u（i，j）作为支付u收到的，如果她玩移动i，其他玩家选择移动j。因此，如果玩家行玩移动i，玩家列玩移动j，他们分别收到支付∏R（i，j）和∏C（j，i）。强化学习我们只描述玩家行，因为列的学习算法是等价的。时间t的玩家行有一个送气（t）级别，该级别更新为asAR（t+1）=（1- α） AR（t）+αXi，jxi（t）∏R（i，j）yj（t），（5），其中α是一个参数。对于每一步，t玩家行的每一次满足度σRi（t）由σRi（t）=Pijxi（t）yj（t）给出∏R（i，j）- AR（t）最大值，j∏R（i，j）- AR（t）|。（6） 更新混合策略向量的所有组件。更新规则是xi（t+1）=xi（t）+xi（t）xi（t）+Xj6=ixj（t）xij（t）。（7） 在这里，xi（t）是玩家行选择移动i的贡献（发生概率为xi（t），因此为乘法项），以及xij（t）是对移动i的贡献，因为选择了另一个移动j（即规范化更新），每个移动都以概率xj（t）发生。

我们有xi（t）=（βσRi（t）（1- xi（t）），σRi（t）>0，βσRi（t）xi（t），σRi（t）<0，（8）和xij（t）=(-βσRj（t）xi（t），σRj（t）>0，-βσRj（t）xj（t）xi（t）1-xj（t），σRj（t）<0，（9），β为参数。从随机混合策略向量开始，对于所有学习算法，混合策略的初始化将是相同的，这些学习算法遵循零期望和满意度水平，我们在等式中迭代动力学。（5） -（9）对于5000个时间步（我们设置α=0.2和β=0.5）。为了确定模拟运行是收敛的，我们只考虑最后20%的时间步，以及在此时间间隔内平均概率大于1/N的混合策略向量的组成部分。如果这些分量和时间步长的标准偏差平均值大于0.01，则认为模拟运行不收敛。虚拟玩家行计算时间T时列的预期混合策略的第j个分量，我们用▄yj（T）表示，作为过去j已经玩过的时间的分数：▄yj（T）=PTt=1I（j，sC（T））T.（10）在上述等式中，I（a，b）是指示函数，如果a=b，I（a，b）=1，如果a=b，I（a，b）=0，如果a=6=b。玩家行然后选择在时间T，I（T）=argmaxkXj∏R（k，j）~yj（T）最大化预期收益的移动。（11） 柱的行为是等效的。我们使用与强化学习相同的收敛准则和相同的模拟运行长度。实际播放中没有参数。复制器动态我们使用离散时间复制器动态xi（t+1）=xi（t）+xi（t）δtXj∏R（i，j）yj（t）-Xkjxk（t）∏R（k，j）yj（t）,yj（t+1）=yj（t）+yj（t）δtXi∏C（j，i）xi（t）-Xikyk（t）∏C（k，i）xi（t）！，（12） 其中δt=0.1是积分步长。其中，模拟运行的长度由到达机器精度边界的混合策略向量的第一个分量内生确定。

（由于复制器动力学具有乘法性质，因此组件向策略单纯形的面呈指数级移动，并迅速达到机器精度边界）。为了验证收敛性，我们检查每个层的混合策略向量的最大分量是否在最后20%的时间步长上单调增加，以及所有其他分量是否在相同的时间间隔内单调减少。经验加权吸引每个玩家在t时对移动i有吸引力Qui（t）。吸引力更新为Qui（t+1）=（1- α） N（t）Qui（t）+（δ+（1- δ） xui（t））Pj∏u（i，j）yj（t）N（t+1），（13），其中α和δ是参数，N（t）被解释为经验。经验更新asN（t+1）=（1- α） （1）- κ） N（t）+1，其中κisa参数。吸引力通过logit函数xui（t+1）=eβQui（t+1）PjeβQuj（t+1），（14）映射到概率，其中β是一个参数。我们模拟等式。（13） -（14）对于500个时间步，从n（0）=1开始。参数值为α=0.18，β=√N、 κ=1，δ=1。如果在最后100个时间步中，平均对数变量大于0.01，则模拟运行被确定为非收敛。在公式中，我们检查1/NPNi=15/TPTt=4/5T（对数xi（t））>10-2，并等效于列。经验加权吸引与噪声我们将等式（13）替换为qui（t+1）=（1- α） N（t）Qui（t）+（δ+（1- δ） I（I，su（t+1））∏u（I，s-u（t+1））N（t+1），（15），即我们考虑在线学习。参数值相同，但β除外=√第2页。收敛标准各不相同。事实上，我们运行了5000个时间步的动力学，在强化学习中，我们只考虑最后20%的时间步，并且只考虑在此时间间隔内平均概率大于1/N的混合策略向量的组成部分。

然后，我们确定固定点的位置，如果在超过10%的时间步内（即至少在100个时间步内），播放距离固定点超过0.02，我们将跑步分类为非收敛。k级学习让FR（·）和FC（·）分别是玩家行和列的EWA更新，即如果两个玩家都使用EWA，那么x（t+1）=FR（x（t），y（t））和y（t+1）=FC（x（t），y（t））。（没有下标的x和y表示全混合策略向量。）然后，如果列是alevel-2学习者，她会根据y（t+1）=FC（x（t+1），y（t））=FC更新策略FR（x（t），y（t）），y（t）. 行的行为等效。在模拟中，我们假设两个图层都是2级，并使用与EWA中相同的参数和收敛标准。Payoff矩阵对于每个Payoff矩阵，我们随机生成Payoff s对-如果行播放i和列播放j，则一对（a，b）意味着行接收payoff a，列获得Payoff b。然后，我们在剩下的模拟中保持Payoff矩阵固定。从平均值为0、方差为1、协方差为Γ的二元高斯分布中随机抽取每对样本。参考文献[1]R.B.Myerson，《博弈论》（Harvarduniversity出版社，2013）。[2] J.M.Smith，《进化论与游戏理论》（剑桥大学出版社，1982年）。[3] R.Axelrod，W.D.Hamilton，《合作的演变》。《科学》2111390–1396（1981）。[4] 《语言的进化》。《国家科学院学报》968028-8033（1999）。[5] 罗森塔尔，一类具有纯策略纳什均衡的博弈。《国际博弈论杂志》2,65–67（1973）。[6] S.A.Kau Offman，《随机构建的遗传网络中的代谢稳定性和基因形成》。《理论生物学杂志》22，437–467（1969）。[7] R.M.May，《模型生态系统的定性稳定性》。生态学54638–641（1973）。[8] D.Fudenberg，D.K.Levine，《游戏学习理论》，第卷。

2（麻省理工学院出版社，1998年）。[9] L.S.Shapley，《两个人的故事》中的一些主题。《博弈论进展》，数学研究年鉴52，1-29（1964年）。[10] H.Gintis，《博弈论演变：以问题为中心的战略行为建模导论》（普林斯顿大学出版社，2000年）。[11] Y.Sato，E.Akiyama，J.D.Farmer，Chaosin学习一个简单的双人游戏。《美国国家科学院院刊》99，4748–4751（2002）。[12] J.H.Nachbar，“进化”博弈中的选择动力学：收敛性和极限性质。《国际博弈论杂志》19，59–89（1990）。[13] D.P.Foster，H.P.Young，关于协调游戏中的非一致性游戏。《游戏与经济行为》25，79–96（1998）。[14] D.Monderer，L.S.Shapley，具有相同兴趣的游戏的虚拟播放财产。《经济理论杂志》68258–265（1996）。[15] P.Milgrom，J.Roberts，《战略互补博弈中的合理化、学习和均衡》。计量经济学：计量经济学学会杂志pp。1255–1277（1990年）。[16] I.Arieli，H.P.Young，《人口博弈中的随机学习动力学和收敛速度》。《计量经济学》84627–676（2016）。[17] 一个大型复杂系统会稳定吗？《自然》238413–414（1972）。[18] L.E.Blume，《战略互动的统计机制》。《游戏与经济行为》5387–424（1993）。[19] K.Goldberg，A.Goldman，M.Newman，《平衡点的概率》。《国家标准局研究杂志》72，93–101（1968）。[20] M.Dresher，n人博弈中纯平衡点的概率。《组合理论杂志》8134-145（1970）。[21]I.Y.幂，限制人博弈中纯策略纳什均衡数的分布。《国际博弈论杂志》19277–286（1990）。【22】J.Berg，A.Engel，《矩阵游戏，混合策略和统计力学》。

《物理审查信函》814999-5002（1998年）。[23]J.Berg，《随机两人博弈的统计力学》。《物理评论》E 612327-2339（2000）。[24]J.E.Cohen，《合作与自利：有限随机博弈中纳什均衡的帕累托效率》。国家科学院学报959724–9731（1998）。[25]T.Galla，J.D.Farmer，《学习复杂游戏的复杂动力学》。《美国国家科学院院刊》110，1232–1236（2013）。【26】B.Skyrms，游戏动力学中的混乱。逻辑、语言和信息杂志1111-130（1992）。[27]L.E.Blume，D.Easley，《学会理性》。《经济理论杂志》26340–351（1982）。【28】M.Boldrin，L.Montrucchio，关于资本积累路径的不确定性。《经济理论杂志》40，26–39（1986）。[29]C.Hommes，G.Sorger，《一致预期均衡》。宏观经济动态2287–321（1998）。【30】G.Gigerenzer，P.M.Todd，《让我们变得聪明的简单启发式》（牛津大学出版社，1999年）。[31]C.Papadimitriou，G.Piliouras，《2016年ACM理论计算机科学创新会议记录》（ACM，2016），第227-235页。[32]M.Goemans，V.Mirrokni，A.Vetta，《计算机科学基础》，2005年。FOCS 2005。第46届IEEE年会（IEEE，2005），第142-151页。【33】I.Erev，A.E.Roth，《预测人们如何玩游戏：强化学习非实验性游戏，具有独特的混合策略均衡》。《美国经济评论》88848–881（1998）。[34]R.R.Bush，F.Mosteller，《学习的随机模型》。（约翰·威利父子公司，1955年）。[35]J.Robinson，求解博弈的迭代方法。《数学年鉴》第296-301页（1951年）。[36]G.W.Brown，《生产和分配的活动分析》，T.Koopmans，ed.（Wiley，纽约，1951），第374-376页。[37]J.Hoffauer，K。

Sigmund，《进化游戏与人口动力学》（Evolutionarygames and population dynamics）（剑桥大学出版社，1998年）。[38]T.B¨orgers，R.Sarin，《通过信息和复制子动力学学习》。《经济理论杂志》77，1-14（1997）。[39]C.Camerer，T.Ho，在正常形式的游戏中体验加权吸引学习。《计量经济学》67827–874（1999）。【40】R.Nagel，《猜谜游戏中的解开：一项实验研究》。《美国经济评论》851313–1326（1995）。【41】R.Selten，《博弈均衡模型I》，R.Selten，ed.（Springer Verlag，BerlinHeidelberg，1991），第98-154页。【42】J.J.Borrelli，《选择对抗不稳定性：稳定子图在经验食物网中最常见》。Oikos 124、1583–1588（2015）。补充信息：一般游戏中的最佳回复结构和均衡收敛1模拟协议的详细信息我们在这里详细描述了如何生成图。主要论文的第二部分和第三部分。我们必须在高维随机博弈上模拟非常不同的学习算法，并确定收敛到均衡的模拟运行。这导致在学习算法的规格、参数值和决定收敛性的标准方面不可避免地出现任意选择。我们已经试验了许多设计选择的组合，总体情况对于特定的实现是稳健的。只有加权相关系数变化了几个十进制单位。我们在S1.1节中详细描述了所有这些问题。在S1.2节中，我们解释了如何生成支付矩阵。S1.1学习算法我们分析了六种学习算法：强化学习、实战游戏、复制器动力学、经验加权吸引（EWA）、带噪声的EWA和k级学习。对于其中的每一项，我们都提供了高层次的定性描述，我们对其进行了正式定义，并规定了收敛标准和参数值。

我们还解释了我们需要解决的数字问题。例如，在强化学习、模拟游戏和复制器动态的情况下，算法具有有限的内存，因此无法在有限的模拟时间内到达固定点。为了解决这个问题，我们需要引入我们在这里详述的近似值。一个具有挑战性的问题的另一个例子是由于数值近似和舍入误差而导致的归一化损失。对于EWA，带有噪音和k级学习的EWA记忆是有限的，因此更容易识别固定点。然而，如果内存太短，一些算法会收敛到单纯形中心的固定点，玩家在单纯形中随机化，与支付矩阵无关。这些固定点可以任意远离纳什均衡。因此，我们需要选择使游戏结构可能决定收敛性的参数值。一个重要的普遍观点是，在实际实验中，学习算法是随机的，即在游戏的每一轮中，玩家以其混合策略向量确定的概率抽样一个动作。然而，我们希望采用确定性近似，因为更容易确定学习动态是否收敛到固定策略。这种近似通常是通过假设玩家在更新混合策略之前观察对手的大量动作样本来实现的[S1]。在机器学习的行话中，确定性近似对应于批量学习，而随机版本对应于在线学习。