加尔各答Paise餐厅分布式协调的出现

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Emergence of Distributed Coordination in the Kolkata Paise Restaurant
  Problem with Finite Information》
---
作者：
Diptesh Ghosh, Anindya S. Chakrabarti
---
最新提交年份：
2017
---
英文摘要：
  In this paper, we study a large-scale distributed coordination problem and propose efficient adaptive strategies to solve the problem. The basic problem is to allocate finite number of resources to individual agents such that there is as little congestion as possible and the fraction of unutilized resources is reduced as far as possible. In the absence of a central planner and global information, agents can employ adaptive strategies that uses only finite knowledge about the competitors. In this paper, we show that a combination of finite information sets and reinforcement learning can increase the utilization rate of resources substantially.
---
中文摘要：
本文研究了一个大规模的分布式协调问题，并提出了有效的自适应策略来解决该问题。基本问题是将有限数量的资源分配给各个代理，以尽可能减少拥塞，并尽可能减少未使用资源的比例。在没有中央计划者和全球信息的情况下，代理可以采用自适应策略，仅使用有关竞争对手的有限知识。在本文中，我们证明了有限信息集和强化学习的结合可以显著提高资源的利用率。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：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下载：
--> Emergence_of_Distributed_Coordination_in_the_Kolkata_Paise_Restaurant_Problem_wi.pdf (394.51 KB)

2022-6-13 22:27:13 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：加尔各答 分布式 AIS Coordination Applications

有限信息Kolkata PaiseRestaurant问题中分布式协调的出现Diptesh Ghosh*Anindya S.Chakrabarti+2018年11月9日摘要本文研究了一个大规模的分布式协调问题，并提出了有效的自适应策略来解决该问题。基本问题是将有限数量的资源分配给各个代理，以尽可能减少拥塞，并尽可能减少未利用资源的比例。在缺乏中央规划师和全球信息的情况下，代理商可以采用仅使用有关竞争对手的有限知识的适应性投资策略。在本文中，我们证明了有限信息集和强化学习的结合可以显著提高资源的利用率。关键词：少数民族博弈、适应性策略、信息集、资源配置。在现代经济和社会中，大规模的协调问题比比皆是。在金融市场和供应链中，交易流、多流程或计算、匹配订单流是需要代理之间进行协调以使相应系统顺利运行的一些情况。在像集中市场这样的集中化系统中，人们可以想到一个中心规划器或一个算法来解决协调问题，并确保资源分配以最大限度地减少浪费。然而，许多经济和社会系统的特点是有大量独立参与的代理人和代理人竞争的有限资源[12]。在这种情况下，收集有关所有代理的信息以用于集中规划过程的成本过高。

因此，一个重要的问题是为使用最小计算能力的单个代理找到有效的策略，并解决所有代理在本地使用时的全局协调问题[4]。这种自治的多智能体系统具有许多独特的特征。参考文献[10]总结了此类属性，如下所示。参与代理的数量很大，而且它们之间没有明确的通信。系统的聚合行为对单个代理故障具有鲁棒性，即单个代理的错误不会导致系统中断。这表明系统的适应能力和it自组织能力是其基本特征。经济和社会系统往往表现出巨大的相似性[15]，这两个系统在没有任何全球协调者的情况下，有时会受到外部和内部干扰的干扰，接近最优状态。加尔各答Paise餐厅（以下简称KPR）问题被认为是一个一般化的多主体、多选择问题[3、7]，本质上是这种情况的特征。有N个代理（人员）在竞争N个资源（再驻留人员）。一个资源在每个时间点只能为一个代理提供服务。代理的决策问题是选择一个资源，该资源由少数代理选择，或者没有其他代理选择。在选择资源时，代理不知道其他代理重新计划选择哪些资源。Thusit也是一个通用的少数民族游戏。在KPR背景下，客户在任何时期选择餐厅的策略都由a1×N概率向量表示，在此期间，客户将访问每个餐厅。这个*印度古吉拉特邦艾哈迈达巴德IIM生产和定量方法区，邮编380015。电子邮件：diptesh@iima.ac.in+印度古吉拉特邦艾哈迈达巴德IIM经济区，邮编380015。

电子邮件：anindyac@iima.ac.in; 概率值的对应来源等于1。候选人的概率修正协议涉及在向量的组件之间重新分配概率和。如果候选人的概率向量在除一个位置外的所有位置上都有0，而在其余位置上只有1，则称其为稳定的。这种概率向量称为稳定化。一个稳定的顾客会在所有时期都去同一家餐厅，除非她修改了自己的概率向量。最近的研究集中于寻找客户可以在本地使用的策略（即不使用全球信息的策略），并动态地达到餐厅利用率最大化的状态。已经报告了几种此类战略。目前的文献表明，达到0.8的自动化率是可以实现的（即从长远来看，每个时期80%的餐厅都会为80%的顾客提供服务）。在本文中，我们提出了一套将局部信息与强化学习相结合的修订协议，并表明与文献中提出的策略相比，该协议的利用率有了显著的提高。我们提出的更新协议有两个重要组成部分。文献[8]表明，强化学习在解决协调博弈中非常有用。从本质上讲，这取决于巴甫洛夫式的“赢-留-输-移”战略。然而，仅仅依赖于这样一种策略，在实现高水平的利用率之前，将需要多指标和误差。如果反复出错代价高昂（例如，在通过计算机处理器解决任务分配问题或分配跨负载的情况下），那么这种策略就不是很有效。

增强快速收敛到高利用率状态的一种可能方法是允许代理拥有更大的信息集。好处是代理可以使用信息集来减少错误尝试的次数。然而，这也是有代价的。跨多个代理拥有相似的信息集将迫使他们选择相同的资源集，因此，将无法实现留在“少数群体”或避开人群的最终目标【14】。我们在这篇论文中的贡献表明，这两种策略的结合可以提高资源的利用率。一个更重要的结果是，这种组合非常有效，因为在几次迭代中，利用率变得非常高。参考文献[9]在当地信息的帮助下研究了少数群体游戏中合作的出现。在此之前，研究了少数群体游戏，其中代理人可以访问一组随机代理人的历史。在一个关键的方面，我们的工作与那些人不同。此类模型中考虑的代理是布尔型的，这表明代理的选择集相当有限。另一方面，这里的资源数量也随着代理数量的增加而增加。因此，multi-choiceenvironment的引入使得解决方案的计算更加密集。然而，我们发现有非常简单的rev-ision协议使用本地信息，并且能够在全局水平上解决协调问题。在本文中，我们首先介绍了第二节中带强化学习的KPR问题。2、秒。3我们为客户提供了六个修订协议，以提高资源利用率。每个协议有两个变体。以秒为单位。4我们按照第节中介绍的修订协议模拟代理的行为。3、仿真结果表明，其中几个协议的利用率接近100%。

我们在第二节总结了本文中的结果。5.2强化学习的KPR问题设I为客户集（| I |=N），R为R资产集（| R |=N），t=1，2。是代理和餐厅互动的时间段。在KPR表格m中，在每个时段开始时，每位客户选择一家她将在该时段访问的餐厅。因此，每家餐厅都会有z ero，一个或多个客户在任何时期选择餐厅。如果餐厅没有顾客，则在这段时间内餐厅将保持闲置状态。如果只有一位顾客，那么餐厅会为她提供服务。如果有多个顾客选择餐厅，餐厅会随机选择其中一个并为她提供服务，而其他顾客在此期间没有餐厅提供服务。我们的目标是确定每个客户在选择餐厅时将单独采用的概率修订协议，以便在一段时间内（我们称之为利用率）为客户提供服务的频率在多个时间段后尽可能高。在强化学习中，最初，每个客户分配一个访问每个餐厅的概率1/N inR。然后，她根据自己（可能有限）对前一时间段内客户在餐厅的分配情况的了解，修改了访问各种美国餐厅的可能性。在修订协议文献[3]中看到的一个假设是，如果客户与一家res taurant成功匹配，那么她将永远选择那家餐厅。这种修订协议有一个明显的缺点。Suppos e arestaurant在不同时期为不同的客户提供服务。然后，这些客户将在随后的所有时段都访问该餐厅，除其中一位外，其他所有客户都不会在任何时段提供服务。

从长远来看，遵循这些修订协议将导致低利用率。在本文中，我们提出了修订协议并进行了实验，在该协议中，如果某个客户在某个特定时期内没有得到服务，那么无论她过去是否得到过任何服务，他都会在下一个时期内更改其概率向量。这意味着，在这些修订协议中，顾客只有在餐厅也回报顾客忠诚的情况下，才会对餐厅忠诚。3修订协议如上所述，在文献中，在每个时期将客户分配到餐厅后，对客户的概率向量进行了修订，如下所示。步骤1.1：对于当前期间餐厅服务的每位客户，将其概率向量修改为除为其提供服务的餐厅外的所有条目均为0，且与其提供服务的目标相对应的条目为1。（即，客户的概率向量稳定。）步骤1.2：对于当前期间未接受任何房地产服务且其概率向量不稳定的每个客户，我们修改其概率向量。步骤1.3：对于当前期间未接受任何房地产服务且其概率向量为s表的每个客户，我们不会修改其概率向量。不同的修订协议在步骤1.2中修订概率向量的方式上有所不同。对于任何修正方法，如果以这种方式修正概率向量，我们将修正机制称为该修正方法的变体1。据指出，变体1有以下缺点。假设有两个客户和两个餐厅jand j。假设他们都在第一阶段参观了jin餐厅和restaurantserves i。然后，我在所有后续阶段参观restaurant j。

现在，假设在第二阶段，客户ivisits resta urant jagain。餐厅可以在餐厅里随机挑选顾客。在第二阶段，假设餐厅j为客户i提供服务。然后，在第二阶段之后的所有阶段，我和我都会访问j。每个阶段只提供其中一个。然而，餐厅在所有时段都处于闲置状态，利用率永远不会超过0.5。克服这一缺点的一种方法是允许所有在一段时间内没有得到服务的客户在下一个时间段内调整其可能性向量。本修订协议的实施如下。步骤2.1：对于本期餐厅服务的每位客户，以及前一期餐厅服务的每位客户，我们不修改概率向量。步骤2.2：对于在当前期间由餐厅提供服务且在前一期间未提供服务的每位客户，我们为该客户保留一份可能性向量的副本。然后，我们将她的概率向量修改为一个，其中除了为她服务的餐厅外，所有条目都是0，而为她服务的餐厅对应的条目是1。步骤2.3：对于当前期间没有任何餐厅提供服务但在前一期间提供服务的每位客户，我们将其概率向量替换为保存的副本（请参阅步骤2.2）。然后我们修正她的概率向量。步骤2.4：对于当前期间或前一期间没有餐厅服务的每位客户，我们修改其概率向量。同样，不同的修订协议在第2步中修订概率向量的方式上也有所不同。

对于任何修正方法，如果以这种方式修正概率向量，我们将修正机制称为该修正方法的变体2。现在，我们描述了不同的修订协议，用于在信息有限的情况下修订概率向量。回想一下，这些修正是对概率向量进行的，而概率向量在周期开始时并不稳定。3.1修订协议RP1：关于竞争对手的本地信息我们假设第i个客户知道第i个客户（i+1）到第n个客户（i+k）在t期间发生了什么。因此，每个客户都知道给定订单中的特定客户子集。显然，两个客户的信息集是完全相同的，尽管它们可能会相交。假设客户i在时段t访问餐厅r，但没有得到服务。然后她修改了她的概率向量。她在下一个期间将访问r餐厅和客户（i+1）通过（i+k）在t期间访问的所有其他餐厅的概率重置为0，并根据她在t期间分配给这些餐厅的概率，将她分配给这些餐厅的概率值重新分配给保留餐厅。让Vit成为客户i至（i+k）|按iod t访问，并让Pit=Pj∈Vitpijt；i、 例如，Pit是指我分配给她或她所知道的其中一位客户在t期间访问过的餐厅的概率。如果Pit=1，则她将访问餐厅的概率平均分布在Vita以外的餐厅中，并将其概率向量修改为Ij（t+1）=如果j，则为0∈ 维生素，1/（N）- |Vit |）否则。（1） 如果Pit<1，则她将概率质量Pit按比例分配给不在Vit的餐厅。

本修订协议中的Thusher修正概率向量ispij（t+1）=（如果j∈ Vit、pijt1+Pitpijt/（1）- 坑）否则（2） 3.2修订协议RP2：信息集的划分在现实中，人们通常会形成亲密伙伴和朋友的集群，而不是重叠的连接串。为了模拟这种情况，我们假设客户被划分为多个组。每个组都知道在t期间组中的其他成员发生了什么。假设C是客户集合的一个分区，客户i属于集合Ci∈ 此分区中的C。我们假设分区的每个集合中的客户彼此共享他们之前访问的结果。RP2中c客户的修订协议与RP1中的修订协议非常相似。两个修订协议之间的区别在于，在RP2中，集合Ci中每个成员的处置信息∈ C是相同的，而在RP1中，每个客户都知道不同且独特的客户群的访问结果。3.3修订协议RP3：划分有关资源的信息集，前提是客户不了解其他客户，但可以访问有关餐厅如何利用的信息。更具体地说，餐厅被分成若干组。在t时段内，在餐馆就餐的顾客知道r所住群体中的其他餐馆发生了什么。假设R是一组restaurants的一个划分。在t期间参观过餐厅的客户i了解r中餐厅的状态∈ Rr其中Rr∈ R、 假设顾客在P时段访问餐厅R，但没有得到服务，并修改其概率向量。她将分配给RRT中在t期间为客户提供服务的餐厅的概率重新分配给RRT中在t期间不为客户提供服务的餐厅。