Computing Equilibrium beyond Unilateral Deviation
2026-04-30 • Computer Science and Game Theory
Computer Science and Game TheoryArtificial IntelligenceComputational ComplexityMachine Learning
AI summaryⓘ
The authors study ways to predict outcomes in games where groups of players might work together to change their strategy. Traditional ideas like Nash equilibrium only stop single players from gaining by changing their choice alone, but don’t stop groups from benefiting by coordinating. They propose a new approach that tries to minimize how much any group can gain by deviating, rather than requiring such gains to be zero, which ensures that a solution always exists. They also explore how hard it is to find these solutions and provide algorithms to do so efficiently. Finally, they apply their method to find the best social outcome that limits the incentive for individuals to deviate alone.
Nash equilibriumcorrelated equilibriumstrong Nash equilibriumcoalition-proof equilibriumcoalitional deviationssocial welfareexploitabilitycomputational complexitygame theoryalgorithm
Authors
Mingyang Liu, Gabriele Farina, Asuman Ozdaglar
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 (\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).