基于启发式的分布式协调博弈中的自组织

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Self-organization in a distributed coordination game through heuristic
  rules》
---
作者：
S. Agarwal, D. Ghosh and A. S. Chakrabarti
---
最新提交年份：
2016
---
英文摘要：
  In this paper we consider a distributed coordination game played by a large number of agents with finite information sets, which characterizes emergence of a single dominant attribute out of a large number of competitors. Formally, $N$ agents play a coordination game repeatedly which has exactly $N$ Nash equilibria and all of the equilibria are equally preferred by the agents. The problem is to select one equilibrium out of $N$ possible equilibria in the least number of attempts. We propose a number of heuristic rules based on reinforcement learning to solve the coordination problem. We see that the agents self-organize into clusters with varying intensities depending on the heuristic rule applied although all clusters but one are transitory in most cases. Finally, we characterize a trade-off in terms of the time requirement to achieve a degree of stability in strategies and the efficiency of such a solution.
---
中文摘要：
在本文中，我们考虑了一个由大量具有有限信息集的代理参与的分布式协调博弈，其特征是大量竞争对手中出现了一个单一的主导属性。形式上，$N$代理重复地玩一个协调博弈，该博弈具有精确的$N$纳什均衡，并且所有均衡都是代理同样偏好的。问题是要以最少的尝试次数从$N$可能的均衡中选择一个均衡。我们提出了一些基于强化学习的启发式规则来解决协调问题。我们发现，尽管在大多数情况下，除一个簇外，所有簇都是暂时的，但代理会根据应用的启发式规则以不同的强度自组织成簇。最后，我们描述了在时间要求方面的权衡，以实现策略的一定程度的稳定性和这种解决方案的效率。
---
分类信息：

一级分类：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下载：
--> Self-organization_in_a_distributed_coordination_game_through_heuristic_rules.pdf (2.78 MB)

2022-5-25 12:02:06 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：分布式 自组织 启发式 Coordination Organization

基于启发式规则的分布式协调博弈中的自组织*Diptesh Ghosh+Anindya S.Chakrabarti2018年10月17日摘要在本文中，我们考虑了一个由大量代理使用有限信息集进行的分布式协调博弈，其特征是大量竞争对手中出现了一个单一的主导属性。形式上，N个代理重复地玩一个协调博弈，该博弈正好有N个纳什均衡，并且所有的均衡都是代理同样喜欢的。问题是在最少的尝试次数中选择N个可能平衡的一个平衡。我们提出了一些基于强化学习的启发式规则来解决协调问题。我们看到，尽管在大多数情况下，除了一个簇外，所有簇都是暂时的，但agent根据应用的启发式规则以不同的强度自组织成簇。最后，我们从时间要求的角度来描述一种权衡，以实现战略的一定程度的稳定性和这种解决方案的效率。关键词：多数游戏、适应、强化学习、分布式协调、自组织。JEL代码：C72、C63、D611简介了解大规模多智能体系统的集体行为是物理学和社会物理学文献中的一个重要问题[1,2]。通常在社会和经济世界中，我们会发现*电子邮件：shubham119413@gmail.com，印度理工学院，印度钦奈600036。+电子邮件：diptesh@iima.ac.in，生产和量化方法领域，印度管理学院，艾哈迈达巴德380015，印度（对应作者）电子邮件：anindyac@iima.ac.in，经济区，印度管理学院，Ahmedabad380015，印度。以及无法用基本性质来解释的全球特征的演变【3】。

我们找到了比竞争对手更受欢迎的特定社会规范或技术的例子，这些规范或技术在属性方面并不一定更差。同样，通过社会和经济主体之间的强化，规范和观点也呈现出非平衡状态【4】。领导者是通过数百万个人之间复杂的竞争和互动过程在政治环境中产生的。在本文中，我们提出了一个简单的多智能体游戏，以研究通过复杂和自适应的交互过程（参见参考文献[6]），在许多潜在竞争对手中出现一个主导属性。我们关注大尺度相互作用的两个性质。首先，代理可以从许多可能相同的选择中协调特定的选择，这些选择也可能被解释为合作的出现[7]，其次，这种协调可能需要时间才能达成，但一旦达成，就可以相当稳定。因此，我们讨论了协调发生的动态（和潜在非平衡）过程以及最终平衡的稳定性[5]。我们考虑一个原型模型来研究这种情况。特别地，我们考虑了一个具有N个代理和N个选择的简单协调博弈。个体代理的目标是收敛到一个普遍选择的结果；i、 这个游戏可以被认为是一个多数人游戏。在博弈论的语言中，这与均衡选择的思想有关。在我们的博弈中，存在N个可能的纯策略纳什均衡，每个均衡对代理都具有同等的吸引力。问题是，在没有交流的情况下，代理如何只收敛到一个平衡？当然，我们不允许中央计划者支配解决方案，因为这会使问题变得微不足道，也不切实际。在我们的模型中，代理反复玩游戏，他们总是想占大多数。

我们首先提出了几种基于naive学习的策略，允许代理以分布式方式解决此协调问题[8]。接下来，我们假设代理希望将其实验成本降到最低，即尽快提出一些固定的策略，即使其结果不是绝对多数。这导致了稳定性程度（达到近似经验法则的时间）和解决方案效率（即协调程度）之间的权衡。我们提出了多种启发式协调策略，在不同程度上解决了问题。我们根据著名的Polya的urnmodel提出了一个Polya方案，该方案允许我们在多种类型的强化学习过程之间进行插值[9]。本文与少数民族游戏的文献[10-12]和少数民族游戏的推广密切相关，少数民族游戏被称为加尔各答派餐厅（KPR）问题[13，14]。在少数派游戏中，有N个代理和2个选项可供选择。代理人的目标是在少数人中。KPR问题将其扩展到了一个具有N个代理和N个选项标记为餐馆的小游戏。本着参考文献[15]的精神，我们多次尝试提出使用有限理性的有限信息集的策略。有兴趣的读者可以参考参考文献[16]进行全面审查。我们提出的模型与多选少数民族博弈完全相反。这两个问题都是大规模分布式协调问题的例子，这些问题研究的是使用有限学习的自适应策略的计算代理。[17] 。在本文中，我们证明了由于强化学习，代理收敛到特定的选择。特别是，根据强化程度的不同，代理可能会被困在不同的选择中，产生不同大小的集群。

聚类行为已经在少数民族游戏的背景下进行了研究[18]。在这里，这种行为还意味着，由于强化，非均衡配置也可能存在，因此不一定是“赢家通吃”的情况。最后，我们表明，如果代理不仅重视协调，而且重视实现绝对协调所需的时间，那么最终解决方案的效率和稳定性将存在权衡效应。图1：有两名玩家的协调游戏的支付矩阵。A，A和B，B都是平衡。2 N-agent协调博弈我们考虑N个agent和M个选项。时间是离散的，在每个时间点，每个代理都会在M个选项中选择要使用的选项。为了验证这个想法，可以想象每个选项代表一家代理将在一段时间内访问的餐厅。因此，N个代理的策略是在每个时间段选择一家餐厅进行访问。在任何特定的时间段内，任何给定的餐厅最多可容纳N名代理。代理商的目标是保持大多数，即代理商希望搬到代理商数量较多的餐厅。原则上，N可能不等于toM。为了使问题具有对称性，我们假设n=M，即代理的数量等于餐厅的数量。我们在此还强调，博弈必然是非合作的，代理之间不允许通信。所有代理的信息集仅限于他们的历史和对餐馆客户过去演变的部分了解。自然，允许代理商获得所有餐厅的完整历史记录将立即解决问题，因为代理商可以采用一种策略，即在时间片1中，他们会选择并在下一个时间片中，他们会搬到第一时间片中吸引最多代理商的餐厅。

为了获得一个非平凡的解决方案，我们只允许代理使用部分历史集。我们详细阐述了以下每种策略的信息集的具体情况。图1显示了两个参与者的一般收敛博弈的支付矩阵。两位玩家都有策略A和B，即他们可以选择参观A餐厅或B餐厅。如果他们两人都决定参观同一家餐厅（A或B餐厅），那么两人的结果都会比参观不同餐厅的结果更好。可能会注意到几点。这个游戏是著名的性别之战游戏的简化版（参见教科书中的治疗）。两性之战游戏允许两个玩家参与，其中经纪人的目标是汇聚到一家餐厅，尽管他们对餐厅的偏好有所不同。在本文中，我们假设一个多agent多选择场景有2个≤ N<∞代理，但假设所有代理对餐厅都有相同的偏好。代理商根据餐厅的吸引力来决定他们的策略。我们将餐厅的吸引力（A）定义为选择该餐厅的代理数量。因此，吸引力取决于代理人所拥有的信息集。当然，在任何给定的时间段，都不可能知道有多少其他代理正在选择一个给定选项。为了完整性，我们定义了协调博弈的纳什均衡。纳什均衡被定义为一个策略集合，在给定其他每个代理的策略的情况下，每个代理通过不切换到不同的策略而表现出微弱的优势。出于我们的目的，本说明适用。有关教科书的描述，请参见[19]。从图1可以看出，存在两种纯策略纳什均衡，即：。要么去A餐厅，要么都去B餐厅。

在一般的N-代理博弈中，会有N个纯战略均衡。值得注意的是，纳什均衡是一种均衡描述和静态概念。它没有解释如何从现实中的许多候选均衡中选择一个均衡。因此，最重要的问题是，在没有任何关于其他主体在想什么的信息的情况下，主体如何协调，从N个可能的选择中收敛到一个平衡点？我们在下面指定了一组策略，使用有限的信息集解决这个问题，在某些情况下，不需要其他代理的信息。3启发式更新策略在本节中，我们提出了一组代理在协调博弈中可能采用的更新策略。这些可以被视为经验法则策略。特别是，它们并没有用尽所有可能的策略，而是提供了一套全面的策略，可用于解决游戏。在下文中，我们定义了代理的策略图2：“无学习”策略的模拟结果。收敛所需的时间片数，10次并行模拟的平均值。T（N）表示N个试剂的收敛时间。竖条显示模拟结果的标准偏差。在插图中，我们绘制了（N）/N作为系统大小N的函数，该系统大小稳定在8.5左右。因此，收敛所需的时间与N成线性比例。作为她分配给员工的概率向量，即向量的每个元素将代表她选择一家餐厅的概率。形式上，我们将时间片t上的i-thagent策略表示为j的{pijt}∈ N、 学习是根据过去的成功与失败更新概率向量。3.1无学习我们从无学习策略开始。

这需要进行概率更新，并表示基线情况。3.1.1零更新该策略分为两部分。考虑任何generictime片t。首先，第i个代理（i∈ N） 将以下概率分配给餐厅，pijt=N.（1）自然，这将导致代理在餐厅中的随机分布。特别是，[？]显示入住率，即餐厅数量占总数量N的比例，将为63.5%。因此，第一部分远远不能确保协调。图3：“无学习”策略的模拟结果。这种策略会导致随时间线性收敛。在y轴上，我们绘制了餐厅中代理人数最多（红色）、第二大（黑色）和第三大（蓝色）的人数。在x轴上，我们绘制时间。该策略的第二部分允许代理时间片t比较在时间片t做出的选择和餐厅在时间片t做出的选择。因为吸引力取决于餐厅中代理的数量，我们用Ajt表示第j家餐厅在时间片t的吸引力。因此，在kis餐厅的代理的策略是去j ifAjt餐厅≥ Akt，（2）否则，代理留在k。所需信息：在第t个时间段在餐厅k的第i个代理的信息集包括Akt和Ajtw，其中j是第i个代理随机选择方案（等式1）的结果。请注意，这需要收集第i-th代理在第t时间段没有访问过的第j家餐厅的信息，这意味着我们正在考虑本地信息。原则上，人们可以想象，代理人可能需要支付收集这些信息的费用。这是我们稍后将详细讨论的一点。结果：我们在图2和图3中给出了模拟结果。图2显示了绝对收敛T（N）所需的时间，即。

所有代理收敛到onerestaurant所需的最小时间片数，作为代理数N的函数。它显示出线性趋势，平均系数约为8。在插图中，我们显示了T（N）/Nas比率是N的函数，在初始陡升后约为8。在主图表中，我们还提供了对模拟次数的标准偏差Acroso（10）的估计。图3显示了在一次模拟中，在n=1000的情况下，一家餐厅在一段时间内相对于其他餐厅的优势（我们显示了第二和第三大餐厅）。第二个和第三个最拥挤的地产商最初开始吸引更多的代理，然后在代理数量上完全衰退，因为占主导地位的地产商变得绝对占主导地位，并吸引所有代理。这些结果表明，对称性破缺是由于随机选择引起的。所有餐厅都是从同样受欢迎开始的。但最终，只有一家餐厅成为最受欢迎的选择，而且其他餐厅也没有代理商。3.2学习策略在本节中，我们介绍了基于过去选择的成功与失败的更新规则。3.3事前知识这是之前策略的直接扩展。A每个时间段，i-th代理（i∈ N） 使用概率向量{pijt}选择餐厅 J∈N、 然后，她比较了芝加哥餐厅和她目前所在的餐厅的吸引力，并在下一个时间段选择了吸引力更高的餐厅。最后，基于吸引力的第i个agent更新概率向量。概率更新的最后一步将策略与无学习策略区分开来。我们将此策略称为事前策略，因为代理可以通过收集当前餐厅和新选择餐厅的吸引力信息来决定是否搬到选定的餐厅。拉特林秒。

3.5我们研究了一个事后更新的案例，该案例放松了这一假设。我们在多个方面扩展了正在考虑的战略。在第一种情况下，代理人奖励更高的吸引力，惩罚更低的吸引力。从形式上讲，更高的吸引力意味着代理将在概率向量中分配更高的权重，并将降低吸引力较低的餐厅的权重。这种策略在更新时被标记为不对称。在第二种情况下，代理只奖励高操作性。我们将此策略标记为不对称更新。此外，我们还考虑了允许代理选择多家餐厅以选择最佳选择的情况。形式上，每个代理的信息集增加到k个选项，其中k=1、2、3、。自然地，设置k=N使问题变得微不足道。因此，我们将重点放在suficientlysmall值为k的情况下。下面我们将详细描述这些策略。3.3.1对称更新考虑代理i，其中i∈ N，在任何通用的时间段t。假设她在餐厅r，并给定她的概率向量{pijt}，她概率选择餐厅l。如果Alt<Art，她留在餐厅r。否则，她同时搬到餐厅l，该代理更新了驻留对象l和r的概率，使得具有较高吸引力的一个在概率上增加分数（f），而另一个在概率上减少分数（f）。自然地，结果和被归一化为1。形式上，如果Alt<Art，pij（t+）=（pijt+f（1- pijt）对于j=r，pijt- f（pijt）表示j=l。如果Alt=Art，pij（t+）=pijt表示j∈ N，如果Alt>Art，则pij（t+）=（pijt+f（1- pijt）对于j=l，pijt- f（pijt）表示j=r。最后，对概率进行归一化：pij（t+1）=pij（t+）/Xipij（t+）。所需信息：对于k=1，信息集与无学习策略是一致的。