When Everyone Can Collude: A 76-Year-Old Gap in Game Theory Finally Closed
> *"In 1950, a 22-year-old PhD student proved a theorem that changed economics: in any finite game, at least one Nash equilibrium exists—a state where no player can do better by unilaterally changing strategy. But the young man overlooked a crucial question: what if two or more players collude and change strategy together? This question haunted game theory for 76 years, until the spring of 2026, when three MIT researchers delivered an elegant answer."*
---
1. The Crack in the Prisoner's Dilemma
Two accomplices are arrested and interrogated separately. If both stay silent (cooperate), each serves 1 year; if one betrays while the other stays silent, the betrayer goes free and the silent one serves 10 years; if both betray, each serves 5 years.
This is the famous Prisoner's Dilemma—game theory's "hello world." It was first experimentally run at RAND by mathematicians Melvin Dresher and Merrill Flood in 1950, and Princeton professor Albert Tucker packaged the dry math into a vivid story.
By Nash equilibrium analysis, betrayal is your best strategy no matter what the other does. So two rationally self-interested prisoners both betray and each serve 5 years—far worse than mutual cooperation (1 year each).
But here is an obvious loophole: Nash equilibrium only says "no unilateral deviation can improve your position." It says nothing about coalition deviations. If the two prisoners can collude—agree outside the interrogation room to both stay silent—they are both better off. In the Prisoner's Dilemma, the Nash equilibrium is helpless against the coalition {Prisoner A, Prisoner B}, which can jointly deviate to (cooperate, cooperate), reducing everyone's sentence from 5 years to 1.
Why did the mainstream framework of game theory assume for 76 years that players act only individually?
---
2. Nash's Genius and Blind Spot
In 1950, 22-year-old John Nash submitted his 28-page doctoral thesis at Princeton, introducing what became the Nash equilibrium. He proved a striking theorem: in any finite game, at least one Nash equilibrium exists—even with mixed strategies. The proof used the Brouwer fixed-point theorem from topology: an equilibrium is a fixed point of the best-response mapping. This earned Nash the 1994 Nobel Prize in Economics and underpinned game theory's applications across economics, political science, biology, and computer science.
But Nash's framework has a fundamental limitation: it considers only unilateral deviations—like boxing rules that allow only jabs, no combinations. In reality, players can collude, ally, and form cartels.
The reason Nash and decades of successors ignored coalitions is simple: coalitions make the problem extremely hard. In an n-player game there are 2^n − 1 possible coalitions; accounting for all coalition deviations explodes the complexity. Yet this left an embarrassing gap: crime syndicates, monopoly cartels, and international treaties—all coalitions—ceaselessly challenge the Nash prediction.
---
3. Strong Equilibrium: Aumann's Ambition and Failure
In 1959, Israeli mathematician Robert Aumann (2005 Nobel laureate) proposed Strong Nash Equilibrium: not only can no single player improve by deviating, no coalition can deviate such that all its members strictly improve.
This sounds like the perfect solution—but it has a fatal flaw: it frequently does not exist.
Even in the Prisoner's Dilemma, strong Nash equilibrium fails:
- (Betray, Betray) is a Nash equilibrium, but the coalition can deviate to (Cooperate, Cooperate), so it is not strong.
- (Cooperate, Cooperate) is not even Nash: a unilateral betrayal drops the betrayer's sentence from 1 year to 0.
- MASE always exists. The maximum average coalition gain is a well-defined real number, and a continuous function on a compact strategy space attains its minimum. This resolves the existence crisis of strong Nash equilibrium and CPNE in one stroke.
- MASE is computable—at least in some settings. Liu et al. proved tight complexity lower bounds for the average-payoff and maximum-payoff objectives and gave algorithms matching them.
- However, for the minimum-payoff objective (protecting the worst-off coalition member), the problem is computationally infeasible—revealing a deep trade-off: you can minimize average harm or maximize protection of the most-hurt player, but not both.
- Nash asked: "Does a state exist where no one can do better alone?" Yes—but it may be socially suboptimal.
- Aumann asked: "Does a state exist where no coalition can jointly do better?" In most interesting games, no.
- Bernheim asked: "Does a state exist where no credible coalition deviation succeeds?" Sometimes yes, sometimes no.
- Liu, Farina, and Ozdaglar asked differently: "If we cannot eliminate coalition deviations, what is the best we can do?" Answer: minimize them—and that question always has a solution.
So in the Prisoner's Dilemma with coalitions allowed, no strong Nash equilibrium exists at all. If a solution concept fails to exist in the simplest two-player game, what use is it for the real world?
Aumann's contribution remains profound—he formalized coalition logic and founded cooperative game theory—but strong Nash equilibrium itself saw almost no use in applied economics due to its non-existence.
---
4. Coalition-Proof Equilibrium: Self-Enforcing Agreements
In 1987, economists Douglas Bernheim, Bezalel Peleg, and Michael Whinston proposed a subtler concept: Coalition-Proof Nash Equilibrium (CPNE).
Their core insight: not all coalition deviations are credible. A deviation that itself can be further deviated from by a smaller sub-coalition is not "self-enforcing."
The recursive definition is elegant: 1. For single-player games, CPNE is just Nash equilibrium. 2. Suppose CPNE is defined for games with fewer than n players. 3. In an n-player game, a strategy profile is CPNE if it is a Nash equilibrium and no self-enforcing coalition deviation exists. 4. A deviation is self-enforcing if it is a CPNE of the induced game (others' strategies fixed) and no sub-coalition can further deviate from it and improve all its members.
This recursive structure makes CPNE much weaker than strong Nash equilibrium—it only guards against "credible" deviations. But even CPNE cannot guarantee existence: Bernheim et al. proved that even in simple three-player games, CPNE may not exist, because the recursive constraints can break at any depth. CPNE has found applications (menu auctions, dynamic public goods, corporate takeovers), but its non-existence problem remains a shadow.
---
5. The MIT Breakthrough: MASE—Minimize Rather Than Eliminate
In April 2026, MIT's Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar published a concise but deep paper that fundamentally changed the field.
Their core insight is simple yet revolutionary: rather than requiring the incentive for coalition deviations to vanish (usually impossible), find a strategy profile that makes that incentive as small as possible.
They call the new solution concept Minimum Average-Strong Equilibrium (MASE). Formally, MASE solves the optimization problem:
Minimize: max over coalitions S and deviations of (1/|S|) × Σ_{i∈S} [deviation payoff of i − original payoff of i]
i.e., choose a joint strategy minimizing the average payoff gain the best-deviating coalition can obtain. Why "average" rather than "total"? Because coalitions differ wildly in size: a total gain of 20 means something very different for a 2-player coalition versus a 10-player one. Averages put coalitions of all sizes on the same scale.
Key properties:
---
6. From PPAD to Computability: The Complexity Legacy of Nash Equilibrium
To appreciate MASE's computational significance, recall a milestone: in 2007, Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou proved that computing a Nash equilibrium is PPAD-complete even for two-player games.
PPAD ("Polynomial Parity Argument, Directed version"), defined by Papadimitriou in 1994, contains problems whose solutions are guaranteed by parity arguments—e.g., in a directed graph, if you start at a source and walk along edges, you must reach a sink or another source; since sources and sinks have equal parity, an unpaired source implies another source exists. Nash equilibrium existence is guaranteed by exactly such an argument (via fixed-point theorems). Their result means: unless PPAD = P (considered extremely unlikely), no polynomial-time algorithm computes Nash equilibria—a "complexity-theoretic critique" of the concept itself.
Liu et al.'s study of MASE continues this tradition: defining a new solution concept and rigorously characterizing its computational complexity—the key step from theory toward application.
---
7. EWF: The Frontier Between Safety and Efficiency
An important application of the MASE framework is the Exploitability Welfare Frontier (EWF) problem.
In game theory and AI, exploitability measures how far a strategy is from Nash equilibrium: the maximum payoff gain over all unilateral deviations. Zero exploitability means the strategy is a Nash equilibrium. But zero exploitability often comes at the cost of social welfare: the strictest strategyproof mechanisms (like VCG) have zero exploitability yet are rarely used in practice because they are complex and inefficient; simpler mechanisms (first-price sealed-bid auctions) have positive exploitability but run efficiently.
The EWF problem: maximize social welfare subject to an exploitability budget (e.g., exploitability ≤ 0.1)—a precise trade-off between safety and efficiency. The MASE framework supplies the mathematical tools: by controlling the maximum average coalition gain (directly linked to exploitability), you can explore the optimal compromise in the direction of welfare maximization.
In the AI safety context, EWF runs deeper: when multiple AI agents interact, you want strategies that are neither easily exploited (low exploitability) nor socially wasteful (high welfare). MASE provides a systematic framework for finding that sweet spot.
---
8. Conclusion
From Nash's 1950 thesis, to Aumann's strong equilibrium (1959), to Bernheim et al.'s coalition-proof equilibrium (1987), to MIT's MASE (2026)—this 76-year arc reveals a deep truth:
Scientific progress often comes not from finding perfect answers, but from redefining the question.
Perhaps truly wise play is not seeking an impossible perfect equilibrium, but finding the most stable one in an imperfect world.
---
References
1. Liu, M., Farina, G. & Ozdaglar, A. *Computing Equilibrium beyond Unilateral Deviation.* arXiv:2604.28186 [cs.GT] (2026). 2. Nash, J.F. *Equilibrium Points in N-Person Games.* *PNAS* 36, 48-49 (1950). 3. Aumann, R.J. *Acceptable Points in General Cooperative n-Person Games.* In *Contributions to the Theory of Games IV* (1959). 4. Bernheim, B.D., Peleg, B. & Whinston, M.D. *Coalition-Proof Nash Equilibria I. Concepts.* *J. Econ. Theory* 42, 1-12 (1987). 5. Daskalakis, C., Goldberg, P.W. & Papadimitriou, C.H. *The Complexity of Computing a Nash Equilibrium.* *SIAM J. Comput.* 39, 195-259 (2009). 6. Papadimitriou, C.H. *On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.* *J. Comput. Syst. Sci.* 48, 498-532 (1994). 7. Tucker, A.W. *A Two-Person Dilemma.* Stanford University Memo (1950). 8. von Neumann, J. & Morgenstern, O. *Theory of Games and Economic Behavior.* Princeton University Press (1944). 9. Fearnley, J. et al. *The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.* *J. ACM* 70, 1-74 (2023). 10. Luce, R.D. & Raiffa, H. *Games and Decisions: Introduction and Critical Survey.* Wiley (1957).