不同算法会选不同的纳什均衡,影响对局表现。
Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

- 算法类型决定选哪个均衡,与随机种子无关。
- 正则化方法选最大熵均衡,后悔平均方法趋向低熵面。
- 选的均衡影响对弱智对手的表现,尤其在隐藏信息游戏中。
许多双人零和博弈存在多个纳什均衡构成的凸集(即纳什多面体),它们共享最小最大值V*但行为不同。标准求解器各自收敛到某个均衡,常被视为可互换。本文通过六个解析已知纳什集的可表征游戏(含二维纳什多面体和Kuhn扑克)测试发现:(i) 选择由算法决定而非随机种子,仅在非对称纳什集中有差异;(ii) 正则化最后迭代方法(R-NaD、磁镜下降)选取最大熵成员(信息投影),在二维多面体上精确实现,且在Kuhn扑克中达99.7%最大熵;而后悔平均方法(CFR、CFR+、虚构博弈)趋向低熵面;在180个随机游戏集合中,R-NaD在100%收敛案例中取最大熵,而CFR+在94%案例中严格低于最大熵(配对Wilcoxon检验,p < 10^-27);(iii) 所选均衡对次优对手的表现有下游影响,随序贯/隐藏信息结构增强但有限制——在Kuhn中最大熵成员是严格更优的对冲策略,而在矩阵博弈中各均衡无支配关系。此外,我们纠正两个常见误解:移除CFR的正象限投影不会消除边界漂移;R-NaD的选择依赖锚点,非初始值无关。最大熵/信息投影特性被广泛验证为强数据支持的猜想。
原文摘要 · Abstract (English)
Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。