(0) 阅读 (1155)

算法博弈论 编辑

词条创建者 匿名用户

算法博弈论

编辑

算法博弈论(AGT)是博弈论和计算机科学交叉的一个领域,其目的是理解和设计战略环境中的算法。通常,在算法博弈论问题中,给定算法的输入分布在许多对输出有个人利益的玩家之间。在这些情况下,代理人可能因为自己的个人利益而不如实报告输入。我们可以从两个角度来看待算法博弈论。分析:给定当前实现的算法,使用博弈论工具对其进行分析(例如,计算并证明其纳什均衡、无政府状态价格和最佳响应动态的属性)设计:设计同时具有良好博弈论和算法属性的游戏。在经典算法设计的常规要求(如多项式时间运行时间,良好的近似率)之上,设计者还必须关心激励约束。

算法博弈论的历史

编辑

Nisan-Ronen:研究算法的新框架1999年,Nisan和Ronen的开创性论文将理论计算机科学界的注意力吸引到了为自私(战略)用户设计算法上。正如他们在摘要中所说的那样。我们考虑分布式环境中的算法问题,在这种环境中,不能假设参与者遵循算法,而是他们自己的自我利益。由于这样的参与者,即代理人,能够操纵算法,算法设计者应该事先确保代理人的利益通过正确的行为得到xxx的满足。根据机制设计领域的概念,我们提出了一个研究这种算法的框架。在这个模型中,算法解决方案以对参与者的支付作为装饰,被称为机制。付款应该被精心选择,以激励所有参与者按照算法设计者的意愿行事。我们将机制设计的标准工具应用于算法问题,特别是最短路径问题。这篇论文创造了算法机制设计这一术语,并被2012年哥德尔奖委员会认定为奠定算法博弈理论发展基础的三篇论文之一。

无政府状态的代价

编辑

在2012年哥德尔奖中引用的另外两篇关于算法博弈理论基本贡献的论文,引入并发展了无政府状态的代价的概念。在1999年的论文《最坏情况下的均衡》中,Koutsoupias和Papadimitriou提出了一个新的衡量系统效率由于代理人的自私行为而下降的标准:最佳配置下的系统效率与最坏纳什均衡的效率之间的比率。(无政府状态的价格这一术语在几年后才出现)。

作为催化剂的互联网

编辑

互联网创造了一种新的经济--既是交换和商业的基础,也是它本身的权利。互联网的计算性质允许在这个新兴的经济中使用计算工具。另一方面,互联网本身也是许多人行动的结果。这对于在此之前的经典的、"自上而下"的计算方法来说是新的。因此,博弈论是看待互联网和其中的互动的一种自然方式,包括人类和机械的互动。博弈论研究均衡(如纳什均衡)。均衡通常被定义为一种状态,在这种状态下,没有任何一方有动力去改变他们的策略。在与互联网相关的几个领域中都能发现均衡,例如金融互动和通信负载平衡

算法博弈论

博弈论提供了分析均衡的工具,一种常见的方法是"寻找博弈"--即把具体的互联网互动形式化为一种博弈,并推导出相关的均衡状态。用博弈的方式重新表述问题,可以分析基于互联网的互动,并构建机制来满足特定的需求。如果能证明均衡的存在,就必须回答另一个问题:能否在合理的时间内找到一个均衡?这就导致了对寻找均衡的算法的分析。特别重要的是复杂性类PPAD,它包括算法博弈论中的许多问题。

研究领域

编辑

算法机制设计

机制设计是经济学的一个子领域,处理激励约束下的优化问题。算法机制设计考虑了经济系统在计算效率要求下的优化问题。研究的典型目标包括收入最大化和社会福利xxx化。

平衡的无效率

编辑

无政府状态的价格和稳定的价格的概念被引入,以捕捉由于参与者的自私行为导致的系统性能损失。无政府状态的价格反映了系统在均衡状态下的最坏情况下的性能。


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163376/

发表评论

登录后才能评论

词条目录
  1. 算法博弈论
  2. 算法博弈论的历史
  3. 无政府状态的代价
  4. 作为催化剂的互联网
  5. 研究领域
  6. 算法机制设计
  7. 平衡的无效率

轻触这里

关闭目录

目录