推翻了学习动态吸引子与吸收平衡一一对应的经典猜想,揭示了局部排斥点的阻碍作用。
Sink equilibria and the attractors of learning in games
- 通过构造反例,证明吸收平衡与学习动态吸引子并非一一对应
- 发现局部排斥点是破坏一一对应的关键障碍,且其存在为必要条件
- 提出伪凸性新概念,可准确刻画双人博弈中吸引子的结构
刻画学习动态的极限行为——即吸引子——是博弈论中最基本的开放问题之一。近期研究提出猜想:复制动态的吸引子与博弈的吸收平衡(即偏好图中的吸收强连通分量)之间存在一一对应关系,并已证明至少存在一对多关系。本文通过三个定理证明该一一对应猜想不成立:首个定理否定更强形式,后两个分别在两人和N人(N>2)情形下否定较弱形式。反例均源于一种称为局部源的结构——位于吸收平衡内部但局部向外排斥的点。我们证明:无局部源是实现一一对应的必要条件,但非充分条件。为此,我们引入双人博弈中吸收平衡的局部性质‘伪凸性’,并证明当吸收平衡满足伪凸性时,其恰好定义了吸引子。伪凸性推广了此前已知成立的情形(如零和博弈、势博弈),并以简洁的图论性质重新表述这些情况。
原文摘要 · Abstract (English)
Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game -- the sink strongly connected components of a game's preference graph -- and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and $N$-player ($N>2$) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source -- a point lying within the sink equilibrium, and yet which is `locally repelling'; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases -- such as zero-sum games and potential games -- where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。