Paper Overview
Field: AI / Game Theory Authors: Kiran Vodrahalli, Rafael Frongillo, Jordan Cotler et al. Published: 2026-04-30 arXiv: 2604.28186
Summary
Most familiar equilibrium concepts, such as Nash equilibrium 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 equilibrium and coalition-proof equilibrium), these generally fail to exist.
This paper studies an alternative solution concept: instead of requiring coalitional deviations to vanish, it minimizes the incentive for such deviations, which ensures existence of a solution. Specifically, the authors focus on minimizing the average payoff of deviating coalitions, and extend the framework to weighted averages and to the maximum intra-coalition payoff. In contrast, the minimum-payoff analogue is shown to be computationally infeasible.
For the average-payoff and max-payoff objectives, the paper proves computational lower bounds for computing such equilibria and provides algorithms that match these bounds. Finally, the framework is applied to solving the exploitability welfare frontier (EWF) — the maximum social welfare achievable subject to a given constraint on exploitability (the best payoff achievable via any unilateral deviation).
Key Contributions
- Existence by minimization: Replacing the non-existence-prone "no profitable coalitional deviation" requirement with minimizing coalition deviation incentives.
- Multiple objectives: Average payoff of deviating coalitions, weighted averages, and maximum intra-coalition payoff; the minimum-payoff variant is computationally infeasible.
- Complexity results: Lower bounds for computing these equilibria, with matching algorithms.
- Application: Computing the exploitability welfare frontier (EWF).