# Computing Equilibrium beyond Unilateral Deviation

arXiv: https://arxiv.org/abs/2604.28186 · HTML: https://mlsanity.com/paper/2604.28186/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 46 references that are in the map.
- First posted on arXiv 30 Apr 2026.

## Builds on (most cited first, 10 of 10)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Graphical Models for Game Theory](https://mlsanity.com/paper/1301.2281/) (2013)
- [Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games](https://mlsanity.com/paper/2203.12074/) (2022)
- [On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria](https://mlsanity.com/paper/2001.05196/) (2020)
- [A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition](https://mlsanity.com/paper/2504.03432/) (2025)
- [Efficient Equilibria in Polymatrix Coordination Games](https://mlsanity.com/paper/1504.07518/) (2015)
- [Inapproximability Results for Approximate Nash Equilibria](https://mlsanity.com/paper/1608.03574/) (2016)
- [Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness](https://mlsanity.com/paper/2402.07331/) (2024)

## Built on by (most cited first, 1 of 1)

- [Equilibrium with Internal Transfers](https://mlsanity.com/paper/2606.20960/) (2026)

## Abstract (arXiv)

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 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 Exploitability Welfare Frontier (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).