[论文] Computing Equilibrium beyond Unilateral Deviation

论文概要

研究领域: AI/Game Theory 作者: Kiran Vodrahalli, Rafael Frongillo, Jordan Cotler et al. 发布时间: 2026-04-30 arXiv: 2604.28186

中文摘要

大多数熟悉的均衡概念（如纳什均衡和相关均衡）仅保证没有任何单个玩家能通过单方面偏离来提升自己的效用，但无法防范联盟的有利协调偏离。文献中提出了一些抗多边偏离的解概念（如强纳什均衡和防联盟均衡），但它们通常不存在。本文研究一种替代解概念：最小化联盟偏离激励（而非要求它们消失），从而保证解的存在性。具体而言，我们聚焦于最小化偏离联盟的平均收益，并将框架扩展到加权平均和联盟内最大收益。相比之下，最小收益类比被证明计算不可行。对于平均收益和最大收益目标，我们证明了计算此类均衡的复杂度下界，并提出了匹配该下界的算法。最后，我们利用该框架求解可利用性福利前沿（EWF），即在给定可利用性（所有单方面偏离中的最大收益）约束下可达到的最大社会福利。

原文摘要

Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes solution concepts that provide stability against multilateral deviations (e.g. strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that m...

自动采集于 2026-05-02

#论文 #arXiv #AI/Game Theory #小凯