arXiv cs.MA· Boning Li, Longbo Huang·· 12 小时前AI 评分29
通用和博弈中如何认证解接近 Nash？基于遗憾累加器的在线证书
When Are We Near Nash? Certifying Solutions in General-Sum Games
AI 导读
针对通用和扩展式博弈的启发式求解器，研究提出一种在线证书：两人博弈中加权平均策略的 NashGap 等于最大化玩家的加权外部遗憾加一个有符号值修正项，可直接从求解器已维护的遗憾累加器读出，无需对平均值做最佳响应。
正文 · AI 翻译
摘要：针对一般和扩展式博弈的启发式求解器会产生一串迭代点，实践中会报告所返回策略组合的 NashGap。我们研究求解器仅凭其更新过程已经维护的遗憾累加器和终端分布累加器，能对自身的迭代点了解到什么。在两人博弈中，加权平均策略的 NashGap 在最大化玩家处等于加权外部遗憾加上一个有符号的值修正项。用运行中的反事实遗憾累加器对遗憾进行界定，可得到一个在线证书，其每个检查点的代价与终端历史数成线性关系。该证书在交替更新下以及三人及以上博弈中仍然成立。交替更新所评估的内容与平均值所记录的内容之间的不匹配，表现为一个带符号的比较项，对比较权重非零的每个玩家，通过一次反向遍历将其最大化。该界直接从遗憾状态读出，无需针对平均值计算最佳响应。运行一组无需训练的遗憾匹配求解器组合，输出证书最小的迭代点，并对该迭代点验证一次。在基准的有偏 Leduc 族上，由十六个无需训练的求解器（七个原始版本和九个近期变体）组成的池，以这种方式在阈值 $10^{-5}$ 下求解了 $64$ 个实例中的 $89\%$，与各求解器轨迹最小值的并集相当。同一协议求解了 $64$ 个预注册留出实例中的 $92\%$，并在此前任何阶段都未使用过的第三组 $64$ 个实例上再次达到 $89\%$。零最佳响应证书认证了全部 $57$ 个样本内求解结果和全部 $57$ 个新求解结果，以及 $59$ 个留出结果中的 $58$ 个。其精确比较器细化版本认证了三组中的每一个求解结果。该证书对两者都作出陈述并标明其界的来源。代码见 此 https URL。
| 评论： | 35 页，5 幅图 |
| 主题： | 计算机科学与博弈论（cs.GT）；人工智能（cs.AI）；多智能体系统（cs.MA） |
| 引用为： | arXiv:2610.29300 [cs.GT] |
| （或 arXiv:2610.29300v1 [cs.GT] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.29300 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Boning Li [查看邮箱]
[v1]
2026 年 10 月 21 日星期三 06:53:56 UTC（1,719 KB）
来源：arXiv cs.MA · arxiv.org