arXiv · AI· Boning Li, Longbo Huang·· 29 天前AI 评分33
近 N ash 解认证:在一般和博弈中通过累积遗憾值在线验证启发式解
When Are We Near Nash? Certifying Solutions in General-Sum Games
AI 导读
该研究提出一种在线证书方法,利用启发式求解器已维护的累积遗憾值终端分布,验证一般和博弈迭代解接近 N ash 均衡的质量,无需额外计算最佳反应。 证书成本随终端历史数线性增长,适用于双人对局及三人以上博弈,且兼容交替更新策略。在 64 实例的 Leduc 测试集上,使用 16 个无训练后悔匹配求解器组合,认证成功率达到 89% 至 92%,证实了方法的有效性。
来源:arXiv · AI · arxiv.org