PNAS 速递：博弈动力学中的一个不可能定理
2023-10-10
1,967
关键词：博弈论，博弈动力学，纳什均衡，计算复杂性
论文标题：An impossibility theorem in game dynamics
斑图链接：https://pattern.swarma.org/paper/97aefbf2-63e0-11ee-963a-0242ac17000d
原文链接：https://www.pnas.org/doi/10.1073/pnas.2305349120
纳什均衡是博弈论中的主要解决方案概念，不仅在经济学领域起着核心作用，还在其他领域中扮演着重要角色。它表示玩家在游戏中做出的选择组合，其中没有自私的玩家会改变他们的决策。尽管每个游戏都有一个纳什均衡，但目前尚不清楚在重复进行游戏的玩家中是否存在确定性行为，可以保证从任何起始点都收敛到游戏的纳什均衡。如果假设玩家的行为是一个离散时间或连续时间规则，其中当前的混合策略配置映射到下一个策略配置，那么这个问题就变成了动力系统理论的问题。
作者应用这个理论，特别是Conley指标理论（Conley index theory），来证明 一个普遍的不可能性结果：存在一些游戏，所有的游戏动态都无法从任何起始点收敛到纳什均衡，帮助证明这个不可能性结果的游戏是退化的，但同时猜想，在计算复杂性的假设下，非退化游戏也会得出相同的结果。
文章还对近似纳什均衡解概念证明了更强的不可能性结果：对于一组具有正测度的游戏，没有博弈动力学可以在考虑到足够小但相对重要的近似误差时收敛到近似纳什均衡解集。结果表明，尽管纳什均衡及其受计算方法启发的近似解概念在所有游戏中都是通用的，但它们从根本上不足以预测长期玩家行为。
集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「我的集智」推送论文信息。扫描下方二维码即可一键订阅：
推荐阅读
