We complete the characterization of the computational complexity of equilibrium in public goods games on graphs by proving that the problem is NP-complete for every finite non-monotone best-response pattern. This answers the open problem of [Gilboa and Nisan, 2022], and completes the answer to a question raised by [Papadimitriou and Peng, 2021], for all finite best-response patterns.
翻译：我们通过证明每个有限的非单体最佳反应模式都存在问题,从而完成了图表上公共产品游戏平衡计算复杂性的定性。 这解决了[Gilboa和Nisan,2022年]的未决问题,并完成了对所有有限最佳反应模式[Papadimitriou和Peng,2021年]的回答。
相关内容
CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点，具有清晰的数学轮廓和严格的数学格式。官网链接：https://link.springer.com/journal/37
Arxiv
0+阅读 · 2023年3月16日
Arxiv
12+阅读 · 2021年2月21日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员