pith. machine review for the scientific record. sign in

arxiv: 2604.28186 · v1 · submitted 2026-04-30 · 💻 cs.GT · cs.AI· cs.CC· cs.LG· econ.TH

Recognition: unknown

Computing Equilibrium beyond Unilateral Deviation

Mingyang Liu , Gabriele Farina , Asuman Ozdaglar
Authors on Pith no claims yet

Pith reviewed 2026-05-07 06:25 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.CCcs.LGecon.TH
keywords coalitional equilibriumaverage gainmaximum gainexploitability welfare frontiercomputational complexitystrong Nash equilibriumdeviation incentivessocial welfare
0
0 comments X

The pith

Equilibria that minimize average or maximum gains from coalitional deviations always exist and admit an algorithm whose complexity matches a proven lower bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Traditional solution concepts such as Nash equilibrium protect only against unilateral deviations, while concepts that protect against coordinated coalitional deviations, such as strong Nash equilibrium, frequently fail to exist. The paper instead selects strategy profiles that minimize the average gain (or, alternatively, the maximum gain) a coalition can obtain by deviating, a quantity that is always defined and therefore yields an equilibrium in every finite game. For these two objectives the authors establish a lower bound on computational complexity and supply a matching algorithm; they also show that the same minimization framework directly computes the maximum social welfare attainable under any prescribed bound on unilateral exploitability. The minimum-gain version of the same idea is shown to be computationally intractable.

Core claim

We introduce solution concepts that minimize the average gain, weighted-average gain, or maximum-within-coalition gain obtainable by any deviating coalition, rather than requiring these gains to be zero. 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. We use the framework to solve the Exploitability Welfare Frontier, the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).

What carries the argument

Minimization of the average (or maximum) gain from a deviating coalition, used as the objective for selecting a stable strategy profile.

If this is right

  • The proposed equilibria exist in every finite game.
  • They can be computed in time matching the proven lower bound for both average-gain and maximum-gain objectives.
  • The minimum-gain version of the same minimization problem is computationally intractable.
  • The same algorithmic framework directly yields the maximum social welfare attainable under any given bound on unilateral exploitability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach supplies a computationally tractable stability notion in games where exact strong Nash equilibria do not exist.
  • The explicit construction of the Exploitability Welfare Frontier makes the efficiency-stability tradeoff quantifiable for mechanism-design purposes.

Load-bearing premise

Minimizing the average or maximum gain from coalitional deviations produces a meaningful stability notion in finite games whose representation allows efficient evaluation of coalition payoffs.

What would settle it

A concrete finite game in which the proposed algorithm returns a profile whose average coalitional deviation gain is strictly larger than the minimum achievable gain, or an instance whose solution time exceeds the stated lower bound.

Figures

Figures reproduced from arXiv: 2604.28186 by Asuman Ozdaglar, Gabriele Farina, Mingyang Liu.

Figure 1
Figure 1. Figure 1: The relationship between different strong equilibrium notions. view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of a tree decomposition of the view at source ↗
Figure 3
Figure 3. Figure 3: LP denotes the linear programming solution from Section A, and Maximum denotes the maximum achievable social welfare. The baselines are comparatively fragile to multilateral deviations, while MASE is more robust and achieves higher social welfare. At the same time, MASE’s exploitability is close to that of the baselines. Given a tolerance ϵ ≥ 0, what is the optimal ϵ-approximate equilibrium that maximizes … view at source ↗
Figure 6
Figure 6. Figure 6: EWFCCE over four different games. Prior work has investigated related welfare–approximation trade-offs for NE (e.g., in congestion games (Christodoulou et al., 2011) and two-player normal-form games (Czumaj et al., 2015)). How￾ever, computational barriers limit what is achiev￾able. Czumaj et al. (2015)’s algorithm relies on an efficient oracle for computing approximate NE, yet computing NE is PPAD-hard (Ch… view at source ↗
Figure 8
Figure 8. Figure 8: LP refers to the linear program in Section A. Maximum marks the maximum social welfare. MASE outperforms the baselines in both games in terms of coalition exploitability and social welfare. 0.0 0.5 1.0 Weight on Individual Rationality (w) 0.0 0.1 Exploitability Chicken Game 0.0 0.5 1.0 Weight on Individual Rationality (w) 0.0 0.1 0.2 Exploitability Pigou’s Network 1.6 1.7 Social Welfare 1.4 1.5 Social Welf… view at source ↗
Figure 11
Figure 11. Figure 11: (a) The original graph G U corresponding to the polymatrix game (left) and the Utility Depen￾dency Graph. (b) The strategically equivalent game and its Utility Dependency Graph. • The utility function of an edge player ei,j is defined as the original interaction utility: U˜ ei,j = Ui,j . • The utility function of an original vertex player i (one of the original N players) is now a constant zero: U˜ i ≡ 0.… view at source ↗
read the original 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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript introduces a family of coalitional equilibrium concepts that always exist by minimizing the average (or weighted-average or maximum-within-coalition) gain obtainable by any joint deviation of a coalition. It proves that the analogous minimum-gain version is computationally intractable, establishes a lower bound on the complexity of computing average-gain and maximum-gain equilibria, and supplies a matching algorithm. The same framework is applied to compute the Exploitability Welfare Frontier (maximum social welfare subject to a bound on unilateral exploitability).

Significance. If the complexity results hold under the stated representation, the work supplies a tractable stability notion that accounts for coalitional deviations while guaranteeing existence, filling a gap left by strong Nash and coalition-proof equilibria. The tight lower/upper bounds for the average-gain and max-gain objectives, together with the EWF application, constitute a solid technical contribution. The paper correctly notes that the minimum-gain variant is intractable and separates the objectives cleanly.

major comments (2)
  1. [§4] §4 (Complexity of Average-Gain and Max-Gain Equilibria): The polynomial-time algorithm and matching lower bound presuppose that, for any coalition S and any joint deviation, the resulting payoff vector (or gain) for S can be evaluated in time polynomial in the input size. In an explicit normal-form representation this requires either enumerating 2^n coalitions or solving an |S|-player subgame whose size is exponential in |S|; neither is efficient for n>4. The reduction establishing the lower bound must be checked to confirm it is stated only in an oracle or succinct-game model; if so, the abstract and §1 must explicitly delimit the input model, as this assumption is load-bearing for the headline claim that the algorithm 'matches this bound'.
  2. [Definition 3.1 and Theorem 3.2] Definition 3.1 and Theorem 3.2: The existence proof for average-gain equilibria is by finiteness and minimization over a compact set, but the manuscript should state whether the minimization is over pure or mixed strategy profiles and whether the algorithm returns a pure or mixed equilibrium; this affects both the complexity claim and the EWF application in §6.
minor comments (3)
  1. [Abstract] Abstract: The sentence 'we prove a lower bound on the complexity … and present an algorithm that matches this bound' should name the bound (e.g., Ω(n) oracle queries) for immediate clarity.
  2. [§3] Notation: The symbol for 'average gain' is introduced without an explicit equation number in the first paragraph of §3; adding a displayed equation would aid readability.
  3. [§2] Related work: The discussion of strong Nash and coalition-proof equilibrium could usefully cite the known non-existence results (e.g., Bernheim et al. 1987) to sharpen the contrast with the new concept.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to improve clarity on the computational model and the strategy spaces involved.

read point-by-point responses

  1. Referee: [§4] §4 (Complexity of Average-Gain and Max-Gain Equilibria): The polynomial-time algorithm and matching lower bound presuppose that, for any coalition S and any joint deviation, the resulting payoff vector (or gain) for S can be evaluated in time polynomial in the input size. In an explicit normal-form representation this requires either enumerating 2^n coalitions or solving an |S|-player subgame whose size is exponential in |S|; neither is efficient for n>4. The reduction establishing the lower bound must be checked to confirm it is stated only in an oracle or succinct-game model; if so, the abstract and §1 must explicitly delimit the input model, as this assumption is load-bearing for the headline claim that the algorithm 'matches this bound'.

    Authors: We agree that the input model requires explicit statement. Our results are developed in the oracle model (standard in algorithmic game theory for coalitional settings), where an oracle returns the payoff vector or gain for any coalition S and any joint deviation of S in time polynomial in the input size. The lower-bound reduction is from a hard problem in this oracle/succinct representation model and does not apply to explicit normal-form games with n>4. We will revise the abstract and Section 1 to delimit the assumed input model and add a short discussion of the oracle assumption at the beginning of Section 4. revision: yes

  2. Referee: [Definition 3.1 and Theorem 3.2] Definition 3.1 and Theorem 3.2: The existence proof for average-gain equilibria is by finiteness and minimization over a compact set, but the manuscript should state whether the minimization is over pure or mixed strategy profiles and whether the algorithm returns a pure or mixed equilibrium; this affects both the complexity claim and the EWF application in §6.

    Authors: We thank the referee for this observation. The existence argument in Theorem 3.2 relies on minimization of a continuous objective over the compact set of mixed-strategy profiles (the product of simplices). Definition 3.1 likewise defines the equilibrium concept over mixed strategies. The algorithm of Section 4 returns a mixed equilibrium. We will make these statements explicit in the revised Definition 3.1 and Theorem 3.2 and will add a brief note on the implications for the EWF computation in Section 6. revision: yes

Circularity Check

0 steps flagged

No circularity in equilibrium definition or complexity bounds

full rationale

The paper defines the new equilibrium concept directly as any strategy profile minimizing the average (or max-within-coalition) gain over coalitional deviations; this is an explicit optimization objective, not a fitted parameter or self-referential quantity. The claimed lower bound on computational complexity and the matching algorithm are established as independent results for this objective via standard reductions and algorithmic constructions. No load-bearing self-citations, uniqueness theorems from prior author work, or ansatzes smuggled via citation appear in the derivation chain. The results remain self-contained once the input representation (allowing efficient coalition-payoff evaluation) is fixed, with no reduction of the central claims to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard domain assumptions of finite normal-form games with known payoffs; the novel equilibrium concept itself is the main added entity. No free parameters are introduced in the abstract.

axioms (1)
  • domain assumption The underlying game is a finite normal-form game whose payoff functions are known and can be evaluated for any coalition.
    Required to define coalitional deviation gains and to state computational complexity results.
invented entities (1)
  • Average-gain coalitional equilibrium (and its max-gain and weighted variants) no independent evidence
    purpose: Guarantees existence by minimizing rather than eliminating coalitional deviation incentives.
    Newly defined solution concept introduced to circumvent non-existence of strong Nash and coalition-proof equilibria.

pith-pipeline@v0.9.0 · 5500 in / 1439 out tokens · 120281 ms · 2026-05-07T06:25:35.984907+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 2 canonical work pages

  1. [1]

    Learning in non-convex games with an optimization oracle

    Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory (COLT), 2019

    2019

  2. [2]

    Optimistic mirror descent either converges to Nash or to strong coarse correlated equilibria in bimatrix games

    Ioannis Anagnostides, Gabriele Farina, Ioannis Panageas, and Tuomas Sandholm. Optimistic mirror descent either converges to Nash or to strong coarse correlated equilibria in bimatrix games. In Neural Information Processing Systems (NeurIPS), 2022

    2022

  3. [3]

    An O(nlogn )sortingnetwork

    Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, and Brian Hu Zhang. A polynomial-time algorithm for variational inequalities under the Minty condition. arXiv preprint arXiv:2504.03432, 2025

    work page arXiv 2025

  4. [4]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009

    2009

  5. [5]

    Acceptable points in General Cooperative n -person Games, pages 287--324

    Robert Aumann. Acceptable points in General Cooperative n -person Games, pages 287--324. Princeton University Press, 01 1959. doi:10.1090/fic/023/01

    work page doi:10.1090/fic/023/01 1959

  6. [6]

    Subjectivity and correlation in randomized strategies

    Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1 0 (1): 0 67--96, 1974

    1974

  7. [7]

    On the evolution of behavioral heterogeneity in individuals and populations

    Carl T Bergstrom and Peter Godfrey-Smith. On the evolution of behavioral heterogeneity in individuals and populations. Biology and Philosophy, 13 0 (2): 0 205--231, 1998

    1998

  8. [8]

    Coalition-proof Nash equilibria I

    B Douglas Bernheim, Bezalel Peleg, and Michael D Whinston. Coalition-proof Nash equilibria I . concepts. Journal of economic theory, 42 0 (1): 0 1--12, 1987

    1987

  9. [9]

    On the computational complexity of decision problems about multi-player Nash equilibria

    Marie Louisa T lb ll Berthelsen and Kristoffer Arnsfelt Hansen. On the computational complexity of decision problems about multi-player Nash equilibria. Theory of Computing Systems, 66 0 (3): 0 519--545, 2022

    2022

  10. [10]

    The myth of the folk theorem

    Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou. The myth of the folk theorem. Games and Economic Behavior, 70 0 (1): 0 34--43, 2010

    2010

  11. [11]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and G \'a bor Lugosi. Prediction, learning, and games. Cambridge university press, 2006

    2006

  12. [12]

    Settling the complexity of two-player Nash equilibrium

    Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In Symposium on Foundations of Computer Science (FOCS), 2006

    2006

  13. [13]

    On the performance of approximate equilibria in congestion games

    George Christodoulou, Elias Koutsoupias, and Paul G Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61 0 (1): 0 116--140, 2011

    2011

  14. [14]

    New complexity results about Nash equilibria

    Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63 0 (2): 0 621--641, 2008

    2008

  15. [15]

    Approximate Nash equilibria with near optimal social welfare

    Artur Czumaj, Michail Fasoulakis, and Marcin Jurdzinski. Approximate Nash equilibria with near optimal social welfare. In International Joint Conference on Artificial Intelligence (IJCAI), 2015

    2015

  16. [16]

    The complexity of computing a Nash equilibrium

    Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52 0 (2): 0 89--97, 2009

    2009

  17. [17]

    Inapproximability results for approximate Nash equilibria

    Argyrios Deligkas, John Fearnley, and Rahul Savani. Inapproximability results for approximate Nash equilibria. In International Conference on Web and Internet Economics (WINE), 2016

    2016

  18. [18]

    Graph theory, volume 173

    Reinhard Diestel. Graph theory, volume 173. Springer Nature, 2025

    2025

  19. [19]

    Polymatrix games with joint constraints

    B Curtis Eaves. Polymatrix games with joint constraints. SIAM Journal on Applied Mathematics, 24 0 (3): 0 418--423, 1973

    1973

  20. [20]

    Fundamental problems on bounded-treewidth graphs: The real source of hardness

    Bar s Can Esmer, Jacob Focke, D \'a niel Marx, and Pawe Rz a \.z ewski. Fundamental problems on bounded-treewidth graphs: The real source of hardness. In International Colloquium on Automata, Languages and Programming (ICALP), 2024

    2024

  21. [21]

    On the verification and computation of strong Nash equilibrium

    Nicola Gatti, Marco Rocco, and Tuomas Sandholm. On the verification and computation of strong Nash equilibrium. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2013

    2013

  22. [22]

    Existence of correlated equilibria

    Sergiu Hart and David Schmeidler. Existence of correlated equilibria. Mathematics of Operations Research, 14 0 (1): 0 18--25, 1989

    1989

  23. [23]

    Introduction to online convex optimization

    Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization , 2 0 (3-4): 0 157--325, 2016

    2016

  24. [24]

    Strategic cooperation in cost sharing games

    Martin Hoefer. Strategic cooperation in cost sharing games. International Journal of Game Theory, 42 0 (1): 0 29--53, 2013

    2013

  25. [25]

    Strong equilibrium in congestion games

    Ron Holzman and Nissan Law-Yone. Strong equilibrium in congestion games. Games and economic behavior, 21 0 (1-2): 0 85--101, 1997

    1997

  26. [26]

    Equilibria of polymatrix games

    Joseph T Howson Jr. Equilibria of polymatrix games. Management Science, 18 0 (5-part-1): 0 312--318, 1972

    1972

  27. [27]

    On the complexity of k-SAT

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT . Journal of Computer and System Sciences, 62 0 (2): 0 367--375, 2001

    2001

  28. [28]

    Correlated equilibria in graphical games

    Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz. Correlated equilibria in graphical games. In ACM Conference on Electronic Commerce, 2003

    2003

  29. [29]

    On the max-min fair stochastic allocation of indivisible goods

    Yasushi Kawase and Hanna Sumita. On the max-min fair stochastic allocation of indivisible goods. In AAAI Conference on Artificial Intelligence (AAAI), 2020

    2020

  30. [30]

    Kearns, Michael L

    Michael J. Kearns, Michael L. Littman, and Satinder Singh. Graphical models for game theory. In Conference on Uncertainty in Artificial Intelligence (UAI), 2001

    2001

  31. [31]

    Known algorithms on graphs of bounded treewidth are probably optimal

    Daniel Lokshtanov, D \'a niel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011

    2011

  32. [32]

    Luce and Howard Raiffa

    Duncan R.. Luce and Howard Raiffa. Games and Decisions. wiley, 1957

    1957

  33. [33]

    Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon

    Herv \'e Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7 0 (3-4): 0 201--221, 1978

    1978

  34. [34]

    Equilibrium points in n -person games

    John F Nash. Equilibrium points in n -person games. Proceedings of the national academy of sciences, 36 0 (1): 0 48--49, 1950

    1950

  35. [35]

    On the existence of strong Nash equilibria

    Rabia Nessah and Guoqiang Tian. On the existence of strong Nash equilibria. Journal of Mathematical Analysis and Applications, 414 0 (2): 0 871--885, 2014

    2014

  36. [36]

    Algorithmic game theory

    Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007

    2007

  37. [37]

    Computing correlated equilibria in multi-player games

    Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55 0 (3): 0 1--29, 2008

    2008

  38. [38]

    The economics of welfare

    Arthur Pigou. The economics of welfare. Routledge, 2017

    2017

  39. [39]

    Efficient equilibria in polymatrix coordination games

    Mona Rahn and Guido Sch \"a fer. Efficient equilibria in polymatrix coordination games. In International Symposium on Mathematical Foundations of Computer Science (MFCS), 2015

    2015

  40. [40]

    A class of games possessing pure-strategy Nash equilibria

    Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2 0 (1): 0 65--67, 1973

    1973

  41. [41]

    Strong and correlated strong equilibria in monotone congestion games

    Ola Rozenfeld and Moshe Tennenholtz. Strong and correlated strong equilibria in monotone congestion games. In International Workshop on Internet and Network Economics, pages 74--86. Springer, 2006

    2006

  42. [42]

    Online non-convex learning: Following the perturbed leader is optimal

    Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory (ALT), 2020

    2020

  43. [43]

    An optimization approach for approximate Nash equilibria

    Haralampos Tsaknakis and Paul G Spirakis. An optimization approach for approximate Nash equilibria. In International workshop on web and internet economics. Springer, 2007

    2007

  44. [44]

    van Megen , G

    F.J.C. van Megen , G. Facchini, P.E.M. Borm, and S.H. Tijs. Strong Nash equilibria and the potential maimizer. Center discussion paper, Operations Research, 1996

    1996

  45. [45]

    Market structure and equilibrium

    Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010

    2010