全部版块 我的主页
论坛 经济学人 二区 外文文献专区
976 16
2022-06-02
英文标题:
《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下载:
-->
二维码

扫码加我 拉你入群

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

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

全部回复
2022-6-2 18:55:25
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),这是一个多主体、多选择的游戏。该问题的最初动机是引入大规模协调博弈的统计分析。
二维码

扫码加我 拉你入群

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

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

2022-6-2 18:55:28
引入了博弈论解决方案的概念,结果表明,即使没有任何全局协调器,代理(机器人)也可以使用一些简单的启发式方法达到令人惊讶的协调水平。这种方法与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)。
二维码

扫码加我 拉你入群

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

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

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

扫码加我 拉你入群

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

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

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

扫码加我 拉你入群

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

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

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

扫码加我 拉你入群

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

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

点击查看更多内容…
相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群