arXiv:2604.28186cs.GTcs.AI2026-04被引 1

提出新型均衡概念,让集体背叛收益最小化,确保存在性且可计算。

Computing Equilibrium beyond Unilateral Deviation

  • 以最小化联盟背叛平均收益为目标定义新均衡
  • 证明该问题复杂度下界并给出匹配算法
  • 可用于优化社会福利与可被利用性的权衡

主流均衡概念(如纳什均衡、相关均衡)仅保证单个参与者无法通过单边偏离获利,无法防范联盟协同背叛。尽管已有强纳什均衡、抗联盟均衡等概念试图解决多边偏离问题,但通常不存在。本文提出一种替代方案:不强制消除联盟背叛激励,而是将其最小化,从而保证均衡必然存在。具体聚焦于最小化联盟背叛的平均收益,并扩展至加权平均及联盟内最大收益情形。相比之下,最小收益版本被证明计算上不可行。针对平均收益与最大收益目标,本文证明了计算此类均衡的复杂度下界,并提出匹配该下界的算法。最后,将该框架应用于求解‘可利用性福利边界’(EWF),即在给定可利用性(所有单边偏离中的最大收益)约束下可达到的最大社会福利。

原文摘要 · Abstract (English)

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 (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish, and is therefore guaranteed to exist. Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains. In contrast, the minimum-gain analogue is shown to be computationally intractable. For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound. Finally, we use our framework to solve the \emph{Exploitability Welfare Frontier} (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).

博弈论均衡计算联盟博弈可利用性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。