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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Best reply structure and equilibrium convergence in generic games》
---
作者：
Marco Pangallo, Torsten Heinrich, J Doyne Farmer
---
最新提交年份：
2018
---
英文摘要：
  Game theory is widely used as a behavioral model for strategic interactions in biology and social science. It is common practice to assume that players quickly converge to an equilibrium, e.g. a Nash equilibrium. This can be studied in terms of best reply dynamics, in which each player myopically uses the best response to her opponent\'s last move. Existing research shows that convergence can be problematic when there are best reply cycles. Here we calculate how typical this is by studying the space of all possible two-player normal form games and counting the frequency of best reply cycles. The two key parameters are the number of moves, which defines how complicated the game is, and the anti-correlation of the payoffs, which determines how competitive it is. We find that as games get more complicated and more competitive, best reply cycles become dominant. The existence of best reply cycles predicts non-convergence of six different learning algorithms that have support from human experiments. Our results imply that for complicated and competitive games equilibrium is typically an unrealistic assumption. Alternatively, if for some reason \"real\" games are special and do not possess cycles, we raise the interesting question of why this should be so.
---
中文摘要：
博弈论在生物学和社会科学中被广泛用作战略互动的行为模型。通常的做法是假设参与者迅速收敛到一个均衡，例如纳什均衡。这可以从最佳回应动力学的角度来研究，在最佳回应动力学中，每个玩家都会对对手的最后一步做出最佳反应。现有研究表明，当存在最佳回复周期时，收敛可能会出现问题。在这里，我们通过研究所有可能的两人正常形式博弈的空间并计算最佳回复周期的频率来计算这是多么典型。这两个关键参数是移动次数，它定义了游戏的复杂程度，以及收益的反相关性，它决定了游戏的竞争程度。我们发现，随着游戏变得越来越复杂，竞争也越来越激烈，最佳回复周期占据主导地位。最佳回复周期的存在预示着六种不同学习算法的不收敛性，这些算法得到了人类实验的支持。我们的结果表明，对于复杂的竞争性博弈，均衡通常是不现实的假设。或者，如果出于某种原因，“真实”游戏是特殊的，并且没有循环，我们会提出一个有趣的问题，即为什么会这样。
---
分类信息：

一级分类：Physics        物理学
二级分类：Physics and Society        物理学与社会
分类描述：Structure, dynamics and collective behavior of societies and groups (human or otherwise). Quantitative analysis of social networks and other complex networks. Physics and engineering of infrastructure and systems of broad societal impact (e.g., energy grids, transportation networks).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Physics        物理学
二级分类：Adaptation and Self-Organizing Systems        自适应和自组织系统
分类描述：Adaptation, self-organizing systems, statistical physics, fluctuating systems, stochastic processes, interacting particle systems, machine learning
自适应，自组织系统，统计物理，波动系统，随机过程，相互作用粒子系统，机器学习
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
-->

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Quantitative interactions equilibrium complicated competitive

泛型gamesMarco-Pangallo？中的最佳回复结构与均衡收敛性？，1,2，Torsten Heinrich1,2和J.Doyne Farmer1,2,3,4牛津大学牛津马丁学院新经济思想研究所，牛津牛津OX26ED，牛津大学英国数学研究所，牛津OX1 3LP，牛津大学英国计算机科学系，牛津OX1 3QD，英国圣达菲研究所，圣达菲，新墨西哥州87501，美国9月20日，2018年抽象博弈论被广泛用作生物学和社会科学中战略互动的行为模型。通常的做法是假设参与者很快收敛到非均衡，例如纳什均衡。这可以从最佳回应动力学的角度来研究，在最佳回应动力学中，每个玩家都会对对手的最后一步做出最佳反应。现有研究表明，当存在最佳回复周期时，收敛可能会出现问题。在这里，我们通过研究所有可能的两人正态博弈的空间并计算最佳回复周期的频率来计算这是多么典型。这两个关键参数是移动次数，它决定了游戏的复杂程度，以及支付的反相关性，它决定了游戏的竞争程度。我们发现，随着游戏变得越来越复杂，竞争也越来越激烈，最佳回复周期成为主导。最佳回复周期的存在预示着六种不同学习算法的不收敛性，这些算法得到了人类实验的支持。我们的结果表明，对于复杂且竞争激烈的情况，games均衡通常是一个不切实际的假设。

或者，如果出于某种原因，“真实”游戏是特殊的，并且没有循环，我们会提出一个有趣的问题，即为什么会这样。JEL代码：C62、C63、C73、D83。关键词：博弈论，学习，均衡，统计力学。*通讯作者：marco。pangallo@maths.ox.ac.ukCycles反馈回路是自然和社会系统不稳定的共同来源。在这里，我们研究了周期和不稳定性之间的关系，这些关系可以建模为两人游戏。其中包括个体参与者之间的战略互动【1】、进化过程【2】、社会现象，如合作的出现【3】和语言形成【4】、道路和互联网上的拥堵【5】以及许多其他应用。我们引入了一种称之为最佳回复结构的形式主义，以近似的游戏表示来描述不稳定性，其精神类似于考夫曼和马荣基因调控[6]和生态系统稳定性[7]的最终贡献。在博弈论中，不稳定性可以理解为策略未能收敛到某一固定点，如纳什均衡，因为agame是重复进行的[8]。众所周知，在匹配硬币或石头剪刀的游戏中，这种趋同很可能会失败【9、10、11】，在这种游戏中，游戏的最佳回复会形成一个循环（从某种意义上讲，这将在下文中阐明）。对于各种类型的非循环对策[12、13、14、15、16]，已经证明了非常普遍的收敛结果。但无环AMES有多典型？非循环游戏是否跨越了现实环境中可能遇到的游戏空间？还是它们很特别？在这里，我们系统地研究了所有可能的两人正态博弈的这个问题。我们用一个插入码来描述游戏的类别，在这个插入码中，我们随机构造支付矩阵，然后在游戏进行时将其固定。

我们的形式主义预测了集合参数变化时的典型收敛频率。我们表明，随着游戏变得（i）更加复杂，即每个玩家的移动次数更大，以及（ii）更具竞争性，即任何给定移动组合对两个玩家的回报是反相关的，最佳回复周期变得可能，收敛通常会失败。例如，有10个movesper玩家，关联度为0.7，非循环游戏只占总数的2.7%。因此，在一般的复杂竞争的games中，均衡收敛通常是一个不现实的假设。虽然研究系统集合的泛型性质是自然科学中的一种常见方法，但在博弈论中却不常见。因此，在更详细地描述我们的贡献以及与文献的关系之前，我们要澄清为什么我们认为这种方法对博弈论有用。罗伯特·梅（RobertMay）[17]在理论生态学中的工作是一个自然的比较点，他使用了一组随机生成的捕食者-猎物相互作用作为一般生态系统的空模型，并表明大型生态系统往往是不稳定的。真正的生态系统不是随机的，而是由进化选择和其他力量塑造的。许多真正的生态系统也存在了很长一段时间，这表明它们实际上是稳定的。这表明，真实的生态系统不是集合中的典型成员，并提出了一个重要问题，即它们到底是如何非典型的，以及为什么它们是稳定的。四十五年后，这仍然是一个活动研究的主题。在这里，我们将同样的方法应用于博弈论，将随机博弈集合作为可表示为博弈的真实世界场景的空模型。

寡头垄断市场中的定价、竞争企业中的创新策略、金融市场中的买卖、拍卖、竞争政党中的选举策略、道路交通和通过互联网发送包裹都是复杂竞争游戏的例子。与生态学相反，从经验的角度来看，它们是否是稳定的，先验上并不清楚：什么时候平衡是一个好的行为模式？这些游戏的规则是设计出来的，不是随机的，但只要它们可以被正常形式的游戏建模，它们都是我们在这里研究的集合的成员。如果复杂且竞争激烈的真实博弈是其集合的典型成员，我们的结果表明，均衡可能是一个很差的近似值。或者，如果人类设计的游戏是典型的，而周期是罕见的，为什么会这样？这可能因情况而异，但如果人性化设计的游戏往往是非典型的，我们的战略冲突必须具有特殊的属性。这是否属实，以及人类设计可能导致非典型行为的原因，尚不明显。如果人类设计的游戏是非典型的，那么这是一个值得进一步研究的有趣问题。为了更好地理解我们的形式主义，请考虑一种最简单的学习算法，即最佳回复动态。在这种算法下，每一位玩家都会对对手的最后一步做出短视的最佳回应。最佳回复动态收敛到吸引子，吸引子可以是固定点、对应的纯策略纳什均衡或周期。Weshow，一个非常简单的衡量最佳回复周期相对于固定点的相对“大小”的方法大致可以预测（R平方>0.75）几种知名且更现实的学习算法（强化学习、实战游戏、复制器动力学、经验加权吸引、k级学习）的非收敛频率。

其中一些学习算法得到了人类实验的支持，并结合了前瞻性的有限理性，这表明我们的结果至少在某种程度上描述了真实玩家的行为。关于学习算法的均衡收敛性质，已有大量的ingame理论文献；即使在入门课程中，最佳答案的作用也得到了广泛认可。这些文献通常在数学上是严格的，并且倾向于在特定类别的游戏中得到精确的结果【12、13、14、15、16】。我们的工作是对这篇文献的补充，因为我们提供了一般游戏的近似结果，并通过大量的数值模拟验证了我们的结果。这使我们有可能研究一些以前没有解决过的问题。例如，我们能够计算在同一个游戏中具有最佳回复周期和固定点的游戏中的收敛概率。一旦我们确定最佳回复结构具有预测价值，我们将确定其如何随移动次数和支付的相关性而变化。我们使用组合方法分析计算微正则系综下不同长度周期的频率。在博弈论中，使用受统计力学启发的方法的想法并不新鲜。然而，虽然现有研究具有纯策略纳什均衡【19、20、21】、混合策略均衡【22、23】和帕累托均衡【24】的量化特性，但我们是第一个量化最佳回复周期的频率和长度的研究。这就直观地解释了为什么在一般的复杂竞争博弈中收敛到均衡会失败【25】，并引入了一种可以在多个方向和不同领域扩展的形式主义。

例如，我们的结果还通过复制动力学（replicatordynamics）与食物网的稳定性相关[7，17]，我们的形式主义可以映射到布尔网络，这是考夫曼（Kau Offman）[6]作为基因调控模型首次引入的。当收敛到平衡点失败时，我们通常会观察到混沌学习动力学[26,25]。对于我们在此分析的六种学习算法，玩家不会收敛到任何类型的跨期“混沌平衡”[27、28、29]，因为他们的期望与游戏结果不匹配，即使在统计意义上也是如此。在许多情况下，结果吸引子是高维的，这使得“理性”玩家很难通过使用统计方法预测他们的移动来超越其他玩家。一旦至少有一个玩家系统性地偏离了均衡，学习和启发式就可以胜过均衡思维[30]，并且可以更好地描述玩家的行为。链复发集（31）和汇平衡（32）是可能适用于这种情况的解决方案概念。结果最佳回答结构假设一个两人正常形式的游戏，其中两人分别是行和列，每个播放动作i，j=1，N.最佳回应是指对对手的某一动作做出最佳回应的动作。

我们称最佳回复结构为最佳回复在支付矩阵中的排列。表1:TerminologyBest replyMove，它对某一支持方的给定动作给出了最佳回报。最佳回复结构Payoff矩阵中最佳回复的排列。最佳replydynamics简单学习算法，其中玩家以敏锐的眼光选择对其对手最后一步的最佳回复最佳回复周期长度k的最佳回复闭合循环（每个玩家移动k次）最佳回复固定点组合移动，这是两个玩家对其对手特定移动的最佳回复（纯Nash等式）。最佳回复向量vSet最佳回复动力学吸引子，从最长周期到固定点排序最佳回复配置两个玩家对其各自的自由移动/自由最佳回复移动的所有移动的唯一最佳回复集，既不是周期的一部分，也不是固定点。为了说明这一概念，我们使用了一个简单的学习算法，即最佳回复动态，其中每个玩家都会对对手的最后一步做出短视的最佳回复。我们考虑了一个特定版本的最佳回复动力学（best replydynamics），其中两名玩家交替移动，每个人都对heropponent的最后一步做出了最佳反应。要了解基本思想，请考虑图1A所示的N=4的游戏。假设我们选择（1，1）作为初始条件。假设列先移动，选择移动SC=2，这是对行移动SR=1的最佳响应。然后，行的最佳响应是SR=2，然后列移动SC=1，等等。这将在循环（1，1）中捕获层→ （1、2）→ （2，2）→（2，1）→ （1，1），对应红色箭头。我们称之为最佳回复2周期，因为每个玩家移动两次。

这个循环是一个吸引子，从（3，2）开始按行播放会导致循环这一事实可以看出。可以随机抽取第一个移动者；如果两个层在一个周期上，这没有区别，1 2 3 4sC1234sR7，-5 2,14-4,3-10，-6-9,16 10，-3 3,15-3，-7-8，-9 0，-6 8,1 6，-90,2 6，-7-1，-4-4，-6A1 2 3 4sC1234sR1,0,0,0,00,1,0,0,0,0,0 0,0图1：最佳回复结构的说明。SR={1，2，3，4}和SC={1，2，3，4}是玩家行和列的可能移动，矩阵中的每个单元格表示他们的支付（第一行）。最佳响应箭头指向对应于最佳响应的单元格。垂直箭头对应于playerRow，水平箭头对应于player列。如果箭头是周期的一部分，则为红色；如果箭头不是周期的一部分，则为橙色；如果箭头直接指向固定点，则为蓝色；如果箭头在多个步骤中指向固定点，则为青色。B中的Payoff矩阵是一种布尔约简，其构造与Payoff矩阵面板a具有相同的最佳回复结构，但其条目仅为1和0。但当有吸引者时，这可能很重要。事实上，对于这个例子，有两个吸引子：如果列改为先出现，我们将在（3，3）（以蓝色显示）的最佳回复固定点一步到位。最佳回复动态的固定点是纯策略纳什均衡。在图1B中，我们展示了Payoff矩阵的布尔化简，该矩阵通过将所有最佳回复替换为一个条目，将所有其他条目替换为零来获得。布尔约简的构造使其具有与其派生矩阵相同的最佳回复结构，但忽略了payoff s的任何其他方面。我们通过最佳回复向量v（π）=（nN，…）来刻画给定N×N payoff矩阵∏中最佳回复动态的吸引子集。

，n，n），其中nis是固定点的数量，n是2个循环的数量，等等。例如v=（0，0，1，1），例如inFig。1、我们将C=PNk=2nkk定义为循环中的移动次数。最佳回复动态的不收敛频率近似于周期与固定点的大小，即F（v）=C/（C+n）。英菲格。1，F（0，0，1，1）=2/3。这个数量是对payoff矩阵的布尔约简对应于一类特定的布尔网络的组合大小的粗略估计。我们计划在未来的工作中报告更多关于这封信函的细节。所有最佳回复周期的吸引盆地。它应被视为具有相同最佳回复向量但不同最佳回复配置的支付矩阵的多个实现的平均不收敛率，定义为两个玩家对其对手所有可能动作的唯一最佳回复集。虽然没有吸引人的最佳回复（免费最佳回复）可能会影响吸引力的基础，但这往往是平均值。预测值我们现在表明，最佳回复动态可以预测六种学习算法的收敛频率。我们的目标是在不限制其结构的情况下，刻画一般游戏的集合。我们通过使用扩展的数值模拟，随机生成支付矩阵，模拟重复博弈中参与者的学习过程，然后检查收敛到纯策略和混合策略纳什均衡。