揭示博弈均衡与效率代价的动态悖论,挑战传统理论稳定性假设。
Paradoxes of Game Theoretic Equilibria and Price of Anarchy

- 静态均衡缺乏可微向量场信息,导致策略激励无法区分。
- 最坏情况下的纳什均衡为拓扑不稳定的严格鞍点,导致效率代价无界。
- 即使最优后悔最小化,学习轨迹仍可能产生混沌行为,适合关注动态稳定性的研究者。
数十年来,静态解概念(纳什、相关和粗相关均衡)及价格代价(PoA)构成了算法博弈论的基础,且无遗憾学习被证明能快速收敛到这些均衡。本文指出,将多智能体学习简化为静态均衡与黑箱遗憾分析,会掩盖底层动态非均衡状态及博弈理论界限。首先,内部纳什均衡缺乏C¹向量场信息,使智能体无法区分一致激励与严格对立激励;继承此几何结构,最坏情况纯纳什均衡作为鲁棒PoA边界表现为拓扑不稳定的严格鞍点,在典型拥堵博弈中则表现为几乎处处严格劣势策略的全局排斥子。将效率保证锚定于此类不稳定状态,导致代数敏感性:我们证明,容纳所有正仿射成本时PoA无界。此外,将学习轨迹投影至相关策略的离散单纯形会系统性接受非理性行为;通过粗相关均衡或近端精化评估动态,仍无法排除严格劣势策略。更甚,最优的O(1/T)交换遗憾最小化也无法排除宏观湍流,甚至在最小博弈中表现为混沌极限集。最后,我们考察拥堵博弈的非原子极限:尽管被认为高度稳定且具有紧致亚线性Θ(p/ln p) PoA界(p为多项式次数),但我们在离散时间学习下证明,唯一均衡会失稳为李-约克混沌,且全局吸引子的时间平均低效随2^p指数退化。这些结果要求重新评估基于最坏情况均衡的动态度量框架。
原文摘要 · Abstract (English)
For decades, static solution concepts (Nash, Correlated, and Coarse Correlated Equilibria) and the Price of Anarchy (PoA) have formed the bedrock of algorithmic game theory, with no-regret learning proving fast convergence to such game-theoretic equilibria. We show that reducing multi-agent learning to static equilibrium and black-box regret analysis obscures underlying dynamic disequilibrium and game theoretic bounds. First, interior Nash equilibria lack $C^1$ vector field information, meaning agents cannot distinguish aligned from strictly opposing incentives. Inheriting this geometry, the worst-case pure Nash equilibria dictating robust PoA bounds manifest as topologically unstable strict saddles, and in canonical congestion games, as global repellers supported on almost everywhere strictly dominated strategies. Anchoring efficiency guarantees to these unstable states causes algebraic sensitivity; we prove that accommodating all strictly positive affine costs renders the PoA unbounded. Furthermore, projecting learning trajectories onto the discrete simplex of correlated play systematically accommodates non-rationalizable behavior. Evaluating dynamics via Coarse Correlated Equilibria or proximal refinements fails to preclude strictly dominated strategies. Moreover, optimal $O(1/T)$ swap-regret minimization does not preclude macroscopic turbulence, manifesting as chaotic limit sets even in minimal games. Finally, we examine the non-atomic limit of congestion games. Though considered highly stable with tight sub-linear $Θ(p/\ln p)$ PoA bounds (where $p$ is the polynomial degree), we prove that under discrete-time learning, the unique equilibrium destabilizes into Li-Yorke chaos and global attractors whose time-averaged inefficiency degrades exponentially as $2^p$. These results necessitate re-evaluating worst-case equilibrium frameworks for dynamically grounded metrics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。