Paper Overview
Field: AI / Game Theory Authors: Kiran Vodrahalli, Rafael Frongillo, Jordan Cotler et al. Published: 2026-04-30 arXiv: 2604.28186
Abstract
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, the authors study an alternative solution concept: instead of requiring coalition deviation incentives to vanish, they minimize them, which guarantees existence of a solution.
Specifically, the paper focuses on minimizing the average payoff of deviating coalitions, and extends the framework to weighted averages and to the maximum intra-coalition payoff. In contrast, the minimum-payoff analog is proven to be computationally intractable. For the average-payoff and maximum-payoff objectives, the authors establish computational lower bounds for computing such equilibria and propose algorithms matching these bounds.
Finally, they use this framework to compute the exploitability welfare frontier (EWF) — the maximum social welfare achievable subject to a given constraint on exploitability (the largest payoff obtainable via any unilateral deviation).
--- *Auto-collected on 2026-05-02*