奇偶博弈与平均收益博弈中子博弈完美均衡的复杂度

《Journal of the ACM》：The Complexity of Subgame-perfect Equilibria in Parity and Mean-payoff Games

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须拥有高级访问权限。

了解更多登录

摘要

摘要

在本文中，我们证明了 SPE 约束存在性问题，即判定给定博弈中是否存在一个子博弈完美均衡使得其产生的收益组合位于两个给定阈值之间，对于奇偶博弈和平均收益博弈均为 $\mathsf{NP}$ 完全问题。为此，我们利用了协商函数的概念，以及一条轨迹与某个 SPE 兼容当且仅当该轨迹与该函数的一个不动点一致这一事实。我们的算法由以下三步猜测组成：（1）这样一个不动点，（2）一条与不动点一致且满足约束条件的轨迹存在的证书，以及（3）一个证明该不动点确为不动点的证书。

AI 摘要

AI 生成摘要（实验性功能）

本摘要由自动化工具生成，未经文章作者撰写或审核。它旨在支持文献检索，帮助读者评估相关性，并帮助来自相邻研究领域的读者理解该工作。它作为作者提供的摘要的补充，作者提供的摘要仍然是本文的主要摘要。完整文章仍然是权威记录版本。 点击此处了解更多。

点击 此处 对本摘要的准确性、清晰度和实用性进行评论。您的评论将有助于改进和生成未来版本。

要查看此 AI 生成的简明摘要，您必须拥有高级访问权限。