KPR传奇：理论和实验发展

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《The Saga of KPR: Theoretical and Experimental developments》
---
作者：
Kiran Sharma, Anamika, Anindya S. Chakrabarti, Anirban Chakraborti,
  Sujoy Chakravarty
---
最新提交年份：
2017
---
英文摘要：
  In this article, we present a brief narration of the origin and the overview of the recent developments done on the Kolkata Paise Restaurant (KPR) problem, which can serve as a prototype for a broader class of resource allocation problems in the presence of a large number of competing agents, typically studied using coordination and anti-coordination games. We discuss the KPR and its several extensions, as well as its applications in many economic and social phenomena. We end the article with some discussions on our ongoing experimental analysis of the same problem. We demonstrate that this provides an interesting picture of how people analyze complex situations, and design their strategies or react to them.
---
中文摘要：
在这篇文章中，我们简要叙述了加尔各答佩斯餐厅（KPR）问题的起源和最新发展概况，该问题可以作为在大量竞争主体存在的情况下更广泛类别的资源分配问题的原型，通常使用协调和反协调博弈进行研究。我们讨论了KPR及其几个扩展，以及它在许多经济和社会现象中的应用。在文章的最后，我们对我们正在进行的对同一问题的实验分析进行了一些讨论。我们证明，这提供了一幅有趣的图片，展示了人们如何分析复杂的情况，设计策略或做出反应。
---
分类信息：

一级分类：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系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：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).
社会和团体（人类或其他）的结构、动态和集体行为。社会网络和其他复杂网络的定量分析。具有广泛社会影响的基础设施和系统（如能源网、运输网络）的物理和工程。
--
一级分类：Quantitative Finance        数量金融学
二级分类：General Finance        一般财务
分类描述：Development of general quantitative methodologies with applications in finance
通用定量方法的发展及其在金融中的应用
--

---
PDF下载：
--> The_Saga_of_KPR:_Theoretical_and_Experimental_developments.pdf (135.83 KB)

2022-6-2 18:55:21 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Coordination Applications Quantitative Developments Experimental

KPR传奇：理论与实验发展Skiran Sharma*, Anamika+，Anindya S.Chakrabarti，Anirba n Chakrab orti§，Sujoy C h akravartyP2017年12月19日摘要本文简要叙述了加尔各答Paise餐厅（KPR）问题的起源和最新发展概况，该问题可以作为在众多竞争代理存在的情况下解决更广泛资源分配问题的原型，通常使用协调和反协调游戏进行研究。我们讨论了KPR及其几个扩展，以及它在许多经济和社会现象中的应用。在文章的最后，我们对我们正在进行的对同一问题的实验分析进行了一些讨论。我们证明，这为人们分析复杂情况、设计策略或做出反应提供了一幅有趣的画面。*电子邮件地址：kiran34sit@jnu.ac.in，印度新德里贾瓦哈拉尔·尼赫鲁大学计算与综合科学学院，邮编：110067+电子邮件地址：anamika@jnu.ac.in，印度新德里贾瓦哈拉尔·尼赫鲁大学计算与综合科学学院，邮编：110067电子邮箱：anindyac@iima.ac.in，印度古吉拉特邦艾哈迈达巴德印度管理学院经济区§电子邮件地址：anirban@jnu.ac.in，印度新德里贾瓦哈拉尔·尼赫鲁大学计算与综合科学学院，邮编：110067P电子邮件地址：sujoyc@gmail.com，新德里贾瓦哈拉尔·尼赫鲁大学社会科学学院，邮编：110067，India1 IntroductionChakrabarti等人[1，2]介绍了加尔各答餐馆问题（KPR），这是一个多主体、多选择的游戏。该问题的最初动机是引入大规模协调博弈的统计分析。

引入了博弈论解决方案的概念，结果表明，即使没有任何全局协调器，代理（机器人）也可以使用一些简单的启发式方法达到令人惊讶的协调水平。这种方法与Brian Arthurin的著名论文《El Farol bar问题》（EFB）[3]所遵循的方法是平行的，之后产生了物理学家制定的少数群体游戏（MG）[4]。Arthur的基本思想是表明基于归纳法的启发式方法对于解决博弈论场景非常有用。PRK问题可以简单地看作是EFB问题的一个直接的一般化，但在数学上是可以处理的。然而，正如我们在本文中所提到的，尽管对MG问题进行了大量的研究[5]，KPR还是提供了一个更大的实验室来研究许多“复杂”的突发现象。近年来，它还被用于具有巨大实际应用的运筹学问题。例如，出租车服务（如优步和奥拉）解决了双边匹配问题，而KPR为分析此类游戏提供了一个起点[6]。为了保证完整性，我们在这里只陈述了KPR问题的两个版本，尽管有很好的参考资料，可以进行更完整的描述和讨论。感兴趣的读者可参考参考文献[7、8]和[9]。我们可以定义KPR的两个版本，一个没有排名，另一个有排名。第一个游戏更简单，更接近于标准（反）协调游戏，因此我们从一个没有游戏的游戏开始。游戏1考虑一组n个玩家和一组m个相同的餐厅（n=m是最有趣的情况）。每个玩家都有权访问自己的一组信息，这些信息可以为空（原则上），并且必须安全访问一家餐厅（win）。

每个玩家都必须决定去哪家餐厅，如果在任何一家餐厅有一个以上的玩家，那么只有一个玩家以相同的概率随机选择。游戏2与上述内容相同，只是餐厅现在已排名，这是所有玩家普遍同意和了解的。对于第一个博弈（在对称情况下，n=m），可以通过将每个代理仅分配给onerestaurant来实现纳什均衡，这样就可以分配所有m个餐厅，并且有nwinner。在第二种情况下，情况当然更复杂——想象一下，所有n个代理被一对一地分配到m家餐厅，并解决KPR问题。由于餐厅现在已排名靠前，因此被分配到较低级别餐厅的人员有可能会偏离并选择排名靠前的餐厅。这类案例已经得到了详细的考虑【9】，Chakrabarti等人【1】提供了存在纯策略纳什均衡的条件。下面，我们简要讨论KPR的不同方面。2学科交叉点的KPR在多个学科中存在大量的协调问题研究。计算机科学家致力于作业的并行处理，并试图通过生成高效算法来解决分配问题。统计物理学文献处理了t r a ffic模型，该模型涉及导致拥挤和效率低下的个人选择。显然，从博弈论的角度来看，显然不同的场景本质上可以理解为一个拥挤博弈。这个游戏还有许多其他可能的应用和解释。因此，我们认为KPR问题代表了一种范式，而不是一个单一的特定问题。

在下文中，我们描述了已经研究的K PR问题的一些方向，以及与跨学科现有文献的联系。2.1解决复杂协调问题的启发式算法KPR研究的主要部分是将其建模为复杂协调问题，并展示了两件事：第一，简单和局部启发式算法对于解决全局优化问题非常有用。其次，它可以提供关于不同启发式如何有效解决问题的见解。想象一下，这是一场资源竞争游戏，每一场成功的比赛都会带来繁殖的成功。然后，战略库将开始支持更成功的战略。Chakrabarti和Ghosh（参见参考文献[10]和[11]）考虑了一系列启发式方法，还引入了有限的学习形式，并分析了相关的成功案例。结果表明，简单的强化学习规则几乎不使用代理的任何全局或局部信息，实际上可以高效地解决分配问题。2.2实现分布式协调设计高效解算器的一个重要问题是找到一种方法，将负载分布在不同的处理器上，以实现并行处理。考虑到这一点，新方法是考虑一个跨处理器分配任务的中央协调器。然而，在一个具有大量代理的多代理系统中，为所有可能的意外事件预先规划这样的任务（或资源）分配可能会花费高昂的成本。

因此，我们可能希望拥有智能代理，这些代理可以对任务进行分类并发现自己划分任务的方法。Cigler和Faltings[12]考虑了这种方法，并提出相关均衡（Aumann在博弈论文献中提出）可以解决这一公共关系问题；但他们也认识到，这种装置（会产生反协调）基本上起着中央协调器的作用，因此这个想法并没有被证明是非常有用的。因此，他们进一步提出了一些学习规则，这些规则对于解决此类问题非常有用。Hansenand Giauque[13]提出了动态规划算法作为任务分配问题的替代算法。还有许多其他论文也提出了类似的问题（例如，参见参考文献[14]、[15]、[16]）。2.3与博弈论的联系KPR本质上是一个博弈论问题，因此经济学家对类似的范式感兴趣也就不足为奇了。KPR问题的原始公式假设，不仅代理商对餐厅有控制权，而且所有代理商都一致同意并知道排名。更明确地说，每个代理都同意在任何给定的两个餐厅中哪一个更好。同一问题的一个更复杂的版本已经被称为稳定婚姻问题，其中一个假设是有两组成员（数量相同），例如男性和女性，他们将彼此结婚。在目前的情况下，不考虑同性婚姻。每个妈妈都有一个女人的名字，反之亦然。问题是要找到两组成员之间的匹配，这样就不会有两个成员愿意分手结婚。1962年，盖尔和沙普利提出了一种算法来解决这个问题。

这个问题有一些相关的变体，如分配问题，其中必须使用相同数量的任务来分配多个代理，这样匹配是一对一的。问题是每个匹配都有一个实现成本，所以问题是最小化所有匹配的总成本。从实践的角度来看，这些问题非常重要。Roth和Pernson【18】提供了一个详细的算法以及解决此类分配问题的应用程序。很明显，尽管KPR涉及分配问题，但上述方法存在显著差异。其中一个关键区别是，在上述pr问题中，假设存在分配任务的中心协调员，而inKPR则不存在。因此，我们现在从讨论中央计划转向分散的结果。从博弈论的角度来看，一类重要的博弈称为拥塞博弈，它与K-PR问题密切相关。这类游戏还认为玩家可以在多个选项（道路）中选择任何一个选项，如果更多玩家选择相同的选项（导致拥堵），那么这对所有玩家都不利。这可以在简化后映射到KPR问题（无排名）。最近的问题是由Gr enag-er等人（19）以及阿尔珀南德·雷尼尔（20）提出的，他们称之为分散游戏。然而，具有Ranking的KPR具有更一般的结构。下面，我们将讨论KPR与基于代理的建模文献，尤其是与minoritygame文献的联系。2.4 Challet和Zhang提出并分析了基于代理的模型和与EFB问题MGA变体的联系，后来作为少数群体游戏（MG）获得了相当大的普及【4，21–25】。

从结构上看，MG是一个N代理人、2选择重复博弈。在考虑的两家餐厅中确定了选择，不太拥挤一侧的代理商被视为赢家，而其余的则被宣布为输家。引入MG的首要目的是为金融市场提供一个简单的模型。交易执行的“买入”或“卖出”期权有两种选择。在任何一天，买家多于卖家都意味着卖家获得收益（正回报），而当卖家多于买家时，则相反。所有代理人的总报酬可被视为等同于市场的超额需求，并被视为市场的价格回报（与超额需求直接成比例）[21]。游戏玩家可以从他们自己的游戏历史中学习，并根据需要改变他们的优化策略。玩家在稳态中使用不同策略的情况反映了游戏固有的动态性和适应性。基于代理的建模和蒙特卡罗模拟，以及从统计物理学中借用的工具，都被用来表明，在内存大小和玩家数量方面，可以最小化函数的可变性。物理学家和经济学家开始对相关的问题感兴趣，比如在意见形成的背景下，代理人的拥挤与反拥挤运动。MG已成为进化和自适应系统的原型模型。Sysi Aho et a l.【26–29】在一系列研究中，研究了MG的一个改进版本，参与者能够根据其相对表现，使用遗传交叉机制选择新的策略。

这种修改有助于使基于代理的模型适用于许多实际系统，尤其是具有异构代理和非线性交互的系统。3实验室实验能否提供新的见解？大量的实验室实验已经验证了人类因素是否在各种不同的情况下发挥纳什均衡策略，包括一次性和连续性。一些在实验室测试过的具有唯一纯策略纳什均衡的一次性博弈包括囚犯困境（30,31）、自愿捐款机制（VCM）博弈（32）、拍卖（35）、伯特兰定价博弈（36）和塔维勒困境（37）。实验室研究了一些顺序博弈，包括最后通牒讨价还价博弈[38,39]和信任博弈[40]。这些研究的结果大致证明，人类玩家并不像预期的那样超理性。参见参考文献。[33]和[34]分别用于囚犯困境和线性公共物品的元分析。从理论上讲，实验室的结果往往不是纳什均衡。在大多数研究中，有限理性以及对平等的关注都会影响人类决策。Stahl和Wilson【42】引入了k级理性模型，试图对单人游戏中的不同理性水平进行建模。实验室实验结果提供的其他相关偏好模型包括thoseby Rabin【43】、Fehr和Schmidt【44】以及Bolton和Ockenfels【45】。与我们的研究特别相关的一类游戏是协调游戏。这些都以其正常形式建模为一次博弈，具有多个纳什均衡，可以是帕累托均衡[46]，也可以是非帕累托均衡[47，48]。

在这种博弈中，博弈理论家和实验经济学家感兴趣的一个实证问题是，代理人是否能够成功地发挥协调结果，为他们实现最高水平的共同利益，即福利最大化或效率最高的结果。鉴于有必要从这组多重均衡中找出更可能的均衡，博弈论者和实验者制定了可能的均衡选择标准，并测试了其经验有效性。广义地说，所建议的选择标准要么依赖于游戏的结构特性，要么依赖于以自然心理标签形式出现的显著性。哈桑·伊恩（Harsanyian）和塞尔滕（Selten）[49]提出了一个重要的标准，该标准依赖于游戏的结构特性，涉及支付和风险优势的概念。谢林（Schelling）[47]首先提出了依赖于焦点存在的分层决策理论，梅塔（Mehta）等人（48）对此进行了检验。因此，常识的自然发生的标签可以允许进行更大的协调，特别是在存在许多非帕累托可分级纳什均衡的情况下。对具有多个帕累托均衡的协调博弈的重要实验研究包括Van Huyck等人[50]的工作，他研究了14至16名受试者的七个帕累托rankable纳什均衡的最小效用协调博弈。他们发现静态重复，主观上试图协调支付主导的纳什均衡，但在几个时期内，仅能收敛到风险主导均衡。Cooper等人[51]使用了一种更简单的两人三人策略设计，并以类似的方式发现了与Harsanyi和Selten[49]的观点相反的情况。