牛津大学计算机科学系、牛津大学OX1 3QD、牛津大学OX1 3UQ、牛津大学OX1 3UQ、牛津大学Heinrich经济学和工商管理系、开姆尼茨技术大学09107 Chemnitz、德国新经济思维研究所、牛津大学OX1 3UQ、牛津大学马丁学院、牛津大学OX1 3BD、英国抽象随机生成正规形式博弈的Payo矩阵，我们计算了n人m策略博弈集合中具有唯一纯策略纳什均衡的博弈的频率。这些都是完全可以预测的，因为它们必须收敛于纳什均衡。然后，我们考虑了一类在最佳反应动态下收敛的博弈，其中每个博弈者依次选择他们的最优纯策略。我们证明了收敛对策的出现频率随着玩家数量或策略数量的增加而趋于零。在两个玩家的情况下，我们表明对于至少有10个策略的大型游戏，具有多个纯策略均衡的收敛游戏比具有唯一纳什均衡的游戏更有可能。我们的新方法使用n部图来描述游戏。关键词：纯纳什均衡，最佳响应动力学，随机游戏2000 MSC:91A10，91A06电子邮件地址:Samuel.Wiese@wolfson.ox.ac.uk（塞缪尔·C·威斯），Torsten.Heinrich@wirtschaft.tu-chemnitz.de（托尔斯滕·海因里希）预印本20201年11月3日。正态分布博弈中的纳什均衡是这样一种策略，即给定其他博弈方的选择，没有一个博弈方有动机做出最优的选择。如果纳什均衡是纯策略的，我们称之为纯策略纳什均衡(PSNE)，否则称之为混合策略纳什均衡(MSNE)。约翰·纳什表明，任何游戏玩家数量和策略都至少有一个MSNE（纳什[1,2])。但事实并非如此。考虑一个n人，m策略的范式博弈，假设玩家按照一个发条顺序选择他们的最优策略（面对对手以前的最优策略）--玩家1选择，然后玩家2选择，等等。直到再次轮到它的玩家1。我们称一个游戏为收敛的，如果经过大量的转弯，在所描述的动态下，没有玩家改变他们的策略。我们用一个n部图来描述这类游戏，每个节点对应于除一个玩家之外的所有玩家的策略选择的纯策略规划，每个边对应于最优策略选择（最佳响应）。一个PSNE对应于长度为N的最短周期。一般来说，有三种类型的游戏:oa型：具有唯一PSNE的收敛游戏oB型：具有多个PSNE的收敛游戏oC型：非收敛游戏类型a游戏（例如，囚犯困境）非常容易理解和完全可预测。它们汇聚到PSNE。当我们重新安排玩家的策略时，B型游戏是协调的。C型游戏的一个例子是匹配便士。类型B和类型C的游戏至少有一个MSNE，我们将研究随机创建的游戏（类型A和类型B）在给定数量的玩家和每个玩家可用的给定数量的策略的游戏集合中收敛的可能性。频率可以提供对经济系统均衡的可预测性和稳定性的洞察力。对于低维（例如2人2策略）游戏方便建模的情况，这将是显而易见的。对于金融市场、创新系统或危机期间（例如新冠肺炎疫情）的交易行为，这是非常有效的。1.1。相关工作几篇论文考虑了与随机Payo s的PSNE ingames的数量有关的方面。我们考虑的是关于I.I.D.的随机支付的文件。

Goldman[3]考虑了零和2人博弈，并表明随着策略数量的增加，具有PSNE的概率将变为零。Goldberg等人。[4]考虑了一般的2人博弈，并证明了当策略数目增加时，至少有一个PSNE的概率收敛于1-exp(-1)。Dresher[5]将这一结果推广到任意玩家数目的情形。Powers[6]表明，当至少有两个玩家的策略数趋于完全时，PSNE数的分布收敛于Poisson(1)。Stanford[7]导出了随机对策中PSNE数目分布的精确公式。Stanford[8]表明，对于两人对称对策，对称和非对称PSNE的数目收敛于泊松分布。最近，Pangallo等人。[9]得到了2人情形下一个或多个PSNE出现频率的精确结果。阿隆等人。[10]研究了优势可解对策的频率，得到了2人情形下的精确公式。优势可解对策必然是收敛的，但反之亦然，所以我们研究了一个更大的对策类（例如，包含协调对策）。A型游戏中独特的PSNE被称为Cournotstable；Moulin[11].1.2研究了这类对策。我们的贡献我们引入了一个描述游戏最佳反应的n部图，并用它来获得在n人m策略游戏集合中随机创建的唯一游戏的频率。这些游戏是完全可以预测的。然后，我们研究了具有多个PSNE的博弈，这些博弈在最佳反应动力学下收敛，其中每个参与者都成功地选择了他们的最优纯策略。我们证明了PSNE数目较少的收敛对策比PSNE数目较多的收敛对策更普遍。对于具有任意数目PSNE的2人转化对策，我们得到了一个精确的频率。我们要强调的是，对于2个玩家和少于10个策略的游戏，有一个独特的PSNE的游戏比有多个PSNE的聚合游戏更常见，否则不太常见。方法2.1.具有n≥2个玩家和m≥2个策略的NotationA博弈是一个元组（n,m,{ui}i∈n)，其中n={1,...,n}是玩家的集合，m={1,...,m}是每个玩家的策略集合，ui:mn→R是一个Payo函数。一个策略profireles=(s，..，sn)∈Mnis一组针对玩家的策略。玩家i的环境是除i以外的每个玩家选择的策略的集合s-i∈Mn-1。博弈者i的最佳响应是从i的环境集合到i的策略的非空子集集合的映射，由bi(s-i):=arg maxsi∈Mui(si，S-i)定义。策略profureleS∈Mnis为纯策略纳什均衡(PSNE),如果所有i∈N和所有si∈M,ui(s)≥ui(si，S-i)。等价地，s∈Mnis为PSNE,如果所有i∈N和所有si∈M,si∈bi(S-i)。博弈是非退化的，如果对于每个博弈者i和环境s-i，最佳响应bi(S-i)是单态的；然后我们写Si=bi(S-I)。类似地，混合策略纳什均衡(MSNE)是混合策略中的一种策略选择。对策作为图，对策的最佳响应结构可以用一个最佳响应有向图来表示，该有向图的顶点集是策略属性集，其构造如下：对于每一个i∈N和每一对区分顶点s=(si,s-i)和s=(si,s-i)，只有当si=bi(s-i)时，才能从s到sifand放置一条有向边。只有在一个坐标下的策略方案之间才有边。我们现在引入一个n部图，作为给定的玩家组合序列的最佳反应的额外表示。在n个组中总共有NMN-1个节点，每个组对应于一个播放器，每个节点响应一个播放器的环境。

在每个节点，玩家选择最佳的响应；从形式上来说，边是这样构造的：对于玩家的eachpair(i，j)，其中j直接在i之后移动，并且每个环境-i=(sj，s-i，-j)（其中s-i，-j是s-i，没有j的策略选择），placea从s-ito到另一个环境s-j=(si，s-i，-j)，当且仅当si=bi(S-i)。（？）因为我们可以假定博弈是非退化的，所以表示博弈的图中的每个节点都有一个out度为1。PSNE对应于周期长度n。每个参与者在每个节点上选择m个策略，因此可能的安排总数为MnMn-1，每一个都相等。我们称如上构造的n部图为不满足条件（？）完整的n部图（参见图5（左））。任何对应于给定对策的n部图都是全n部图的子图。如果一个节点的out度是m，我们将调用它的free；如果它的out度是1，我们将调用fireced。图1显示了一个3人2策略的游戏，其中有一个PSNE。左边是对应的最佳响应有向图，右边是3部网络，播放序列为1-2-3.pl。3 V VII PL。2 III(0,0,0)(0,0,1)PL。1 IV（1,1,1)(0,1,0）II PL.2 III(1，0，1)(1，1，0)IV(0，1，0)(1，0，1)III-V对应于PSNE（I-IV-V）的最佳响应被标记出来。结果3.1.a型：具有唯一PSNEWe的收敛对策通过从具有零均值、零方差和零相关矩阵的多元正态分布中提取Payo s的mntuples随机生成n人、m策略对策。这确保了随机创建的游戏几乎可以肯定是不退化的。设pkn，m，表示n个博弈者，m-策略，完全k个博弈收敛对策的频率。定理1。在ensembles中，具有一个唯一PSNE的游戏的频率被给定bypn，m=rn-1+m-1m-r rm n-1-1，其中r:=m-1 mn+1。注意，频率pn，m→0随着策略的数目或玩家的数目而变小，并且pn，mis在n和m中都减少。例如:P2,M=M2-M p3,M=M3-M+M-M+M p4,B型：具有多个PSNE的收敛对策我们可以从上面定义具有多于一个PSNE的收敛对策的频率：定理2。对于k<k，我们有pkn，m>pkn，m，这意味着对于每k，pkn，m→0，因为策略的数目或玩家的数目是在firefnity。我们计算了3人2策略博弈的p3,2=≈48.43%,p3,2=≈20.21%,p3,2=≈1.37%,p3,2=≈0.049%,在两人博弈中，我们可以用Kpsnes精确地描述博弈的频率。定理3。当k≤m时，给出了2人m策略收敛对策的频率bypk2,m=2m-km2k+2(k-1)m！(m-k)！，否则为0。然后给出了2人收敛对策（a型或B型）的绘制频率bypk=1pk2,m,B型对策的频率ispmk=2pk2,m。数值证据表明，对于m=2,a型对策比B型对策更常见。...

,9、图3和图4显示了具有给定PSN数的随机抽取的收敛2人博弈的频率。1 2 3 4 5纯策略纳什均衡的数量0.00.10.20.30.40.50.60.70.8频率2-策略博弈5-策略博弈10-策略博弈20-策略博弈50-策略博弈100-策略博弈图3：随机抽取的具有psnes1 2 3 4 5 6 7 8 910 11121314151617181920纯策略纳什均衡数10-2810-2010-1210-4频率5-策略游戏10-策略游戏20-策略游戏50-策略游戏100-策略游戏图4：随机抽取的具有psnes1的随机抽取的收敛2人游戏的频率，其中频率是对数的。结论：我们研究了在最佳反应动态下，每个参与者依次选择其最优最优策略的博弈收敛频率。如果这些游戏有一个唯一的PSNE，或者有多个PSNE，那么它们可能是完全可预测的。我们用一种新的描述博弈的图论方法分析计算了博弈类型的频率，并证明了如果我们让博弈者的数目或策略的数目进入博弈，几乎所有的博弈都不收敛。在2人博弈中，我们给出了具有给定数目的PSNE的博弈频率的精确公式，并强调对于少于10个策略，具有唯一PSNE的博弈比具有多个PSNE的收敛博弈更常见，否则就更不常见。我们相信我们的图论方法通常可以非常有用地理解复杂的博弈。这一工作的扩展将包括对具有多个pureNash均衡或具有混合Nash均衡的多人博弈的分析频率进行修正。定理1的证明。考虑一个n人，m策略博弈的全n部图。我们按以下方式对节点进行排序:s-i<s-jfordi设置玩家i和j，当且仅当i<j，对于同一个玩家i，S-i<s-i，按词典排序。用GF=(Vf,Ef）表示这个全n部图，其中V是顶点集，E是边集。图G=(V，E)无多边和自环的拉普拉斯矩阵可以定义为边长为V且(L(G))iJ=δ+(i)的方阵，如果i=J-1,I6=j,(i，j)∈E0,I6=j,(i，j)6∈E0,其中δ+(i)是节点i的外度。对于上述GF，Laplacian矩阵采用以下形式:LGF^=Dn000nn-1s00d，其中D，S，N，..，nn-1是边长为mn-1的方阵，如下:oD=diag(m)是对角上有m的对角矩阵onk=diag(K，)。.....KMK-1)是块矩阵的对角线为Klonthe的块矩阵，其中每个KL的边长Mn-land由多个对角矩阵diag(-1)组成，边长为mn-l-1.·S的每一个都更加不规则，(S)ij=(-1，如果（i mod mn-2)=j-1m0。例如，在3人的情况下，2-策略游戏，图5（左）对应的Laplacianmatrix给定为BYL GF=2 0 0 0-1 0 0 0 0 00 2 0 0 0-1 0 0 0 00 0 0 2 0-1 0-1 0 0 0 00 0 0 0 2 0 0 0-1-1 0 00 0 0 0 0 0 2 0 0 0-1-1 0 00 0 0 0 0 0 0 2 0 0 0-1-10 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0-1-1-1-1-1-1-00 0 0 0 0 2 0 0 00 0-1-1 0 0 0 0 0 0 2 0 0-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0在不失去一般性的情况下，我们选择每个玩家选择他们的策略的节点。我们将这n个节点压缩为表示PSNE的单个节点，参见图5。

所述PSNE节点具有n度(m-1)；我们删除所有传出的边。得到的(N+1)-部图由NMN-1-(N-1)个节点组成，用GC=(Vc，Ec)表示，其中VC1是顶点集，EC1是边集。除了PSNE节点之外，所有节点都是自由的。Kirchho定理（应用于我们的问题）指出，生成树的个数是GC的Laplacian矩阵的行列式，它对应于PSNE节点。对于边长为n的二次矩阵a，我们将a定义为边长为(n-1)的二次矩阵。我们可以通过修改公式来计算det^L(Gc),namelydet^L(Gc)=m(Mn-1-1)(n-1)·deted-mn-1·es·n-1yi=1fni！.矩阵·qifni给定byeS·yifni！ij=m-[1,mn-δ(i)-1](j),其中δ(i):=arg minp∈[1,n-1]mink∈[1,mp]i-kmn-p-1.我们简化矩阵的-mn-1·es·qn-1i=1fni,得到一个矩阵a通过以下算法：算法SimplifyingeD-mn-1·es·qn-1i=1fni得到a1。对于p∈[1,...,n-1]:(a)对于i∈[1,...,mn-1-1]:i。如果i=MP-1或δ(i)6=n-p，则继续。从I.2中减去MP-1的行。对于k∈[1,..,nm-1-1]:(a)如果对于任何p∈[0,..,n-1],kmp,继续。(b)将列k加到列mn-δ(k)-1。矩阵a的行列式可以写为a=mm-1-n·detba对于边长为(n-1)的矩阵xba并且由ba ij=m+m-1 mn-1-m-1 mi-1i=jm-1 mn-i+j-1-m-1mj-1i>j-m-1mj-1i<j将第i列乘以-m加到第(i+1)列对于i=n-2，n-1 3、。.1,我们得到如下形式的矩阵dn0.0ed0.0nen-100d Whered=m-1 mn-1+1ei=m-1 mn-i-(m-1)D=mN=-m-1 mn-1。为了消除上对角线上的N项，我们将第i行乘以f:=-nd=m-1 mN+1m，添加到第(i-1)行，对于i=n-1,。...,2.则矩阵为低三角，且D项为fd=d+F·e+··+fn-2·en-1=d+n-3xi=0fi+1m-1m-1m-1m-1m-2n-3xi=0fi+1(m-1)=d+F m-1mn-2)n-3xi=0fi=d+F m-1mn-2f-1f=m(R-1)+m rn-1-rΩ-r(M-1)rΩ-m RM n-2-1+1，其中r:=M-1Mn+1，最后，给出只有一个PSNE的博弈的频率bypn,M=MnMnMn-1 det^L(Gc)=MMN-1 detA=MN-1 detBA=MFD，其中我们乘以PSNE的可能位置数，除以可能排列的总数。这就完成了定理2的证明。考虑一个完整的n部图，并分配k个PSNE，从而找出kn个节点的输出边。我们表明，当添加另一个PSNE时，游戏中可能实现的数量会减少。我们可以添加另一个PSNE（通常计算起来非常复杂）的方式的数量从上面被(mn-1-k)m=mn-km限定，这是因为每个玩家都有mn-1-k个自由节点，每个自由节点都有一个m的超度，并且在n循环中添加两个节点会添加其余的节点。然而，增加一个PSNE会使可能实现的博弈次数减少Mn-1倍，因为n个节点可能不会形成一个循环。对增加的PSNE的次数进行归纳就完成了证明。定理3的证明。