When Everyone Can Collude: A 76-Year-Old Gap in Game Theory Finally Closed
> *"In 1950, a 22-year-old doctoral student proved a theorem that changed economics: in any finite game, at least one Nash equilibrium exists—a state in which no player can do better by unilaterally changing strategy. But the young man overlooked a key question: what if two or more players collude and change their strategies together? This question troubled game theory for a full 76 years, until the spring of 2026, when three MIT researchers delivered an elegant answer."*
---
1. The Crack in the Prisoner's Dilemma
Imagine this scenario: you and your accomplice are arrested for theft and interrogated separately. If both stay silent (cooperate), each gets 1 year; if one informs (defects) while the other stays silent, the informant walks free and the silent one gets 10 years; if both defect, each gets 5 years.
This is the famous prisoner's dilemma—game theory's "hello world." In 1950, RAND mathematicians Melvin Dresher and Merrill Flood first ran this experiment, and Princeton professor Albert Tucker packaged the dry mathematical example into a vivid story.
According to Nash equilibrium analysis, no matter what the other does, defecting is your optimal strategy. So if both prisoners rationally maximize self-interest, the outcome is: both defect, 5 years each. This is clearly 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 does not say "no coalition deviation can improve your positions." If the two prisoners can collude—reaching a "both stay silent" agreement outside the interrogation room—they genuinely both do better.
Indeed, in the prisoner's dilemma, if coalitional deviations are allowed, Nash equilibrium collapses: the coalition {Prisoner A, Prisoner B} can jointly deviate to (cooperate, cooperate), reducing each sentence from 5 years to 1.
So the question is: why did the mainstream framework of game theory assume for 76 years that players only act alone?
---
2. Nash's Genius and Blind Spot
To understand the weight of this question, we must return to 1950.
That year, 22-year-old John Nash submitted his doctoral dissertation at Princeton. The thesis was only 28 pages long and contained what became known as the Nash equilibrium. Nash proved a stunning theorem: in any finite game, at least one Nash equilibrium exists—even when players use mixed strategies (randomizing over actions with certain probabilities).
Nash's proof used the Brouwer fixed-point theorem—an esoteric result from topology. The fixed-point theorem says that if you continuously map a disk to itself, at least one point stays fixed. Nash's insight: an equilibrium of a game can be seen as a fixed point—each player's strategy is a best response to the others', and the "best-response mapping" must have a fixed point.
This discovery earned Nash the 1994 Nobel Prize in Economics and laid the foundation for game theory's wide application in economics, political science, biology, and computer science.
But Nash's framework has a fundamental limitation: it only considers unilateral deviations. It is like boxing rules that allow only jabs, no combinations. In reality, players can collude, form alliances, build cartels.
Why did Nash (and decades of researchers after him) ignore coalitions? Simply because coalitions make the problem extremely hard. In an n-player game, there are 2^n - 1 possible coalitions; accounting for all possible coalitional deviations causes computational complexity to explode.
But this left a theoretical embarrassment: Nash equilibrium predicts "both defect" in the prisoner's dilemma, while in reality criminal gangs, monopoly cartels, and international treaties—all coalitions—constantly challenge that prediction.
---
3. Strong Equilibrium: Aumann's Ambition and Failure
In 1959, Israeli mathematician Robert Aumann (2005 Nobel laureate) proposed a bold solution: Strong Nash Equilibrium.
The requirements are extremely strict: not only can no single player improve by unilateral deviation, but no coalition can improve all its members through joint deviation.
In other words, a strong Nash equilibrium satisfies both conditions: 1. It is a Nash equilibrium (immune to unilateral deviation) 2. It is immune to all possible coalitional deviations
This sounds like the perfect solution. But it has a fatal flaw: it frequently does not exist.
Even in the simplest prisoner's dilemma, no strong Nash equilibrium exists. The coalition {A, B} can jointly deviate to (cooperate, cooperate), cutting each sentence from 5 years to 1—so "both defect" is not strong. But (cooperate, cooperate) is not strong either! If A unilaterally defects while B cooperates, A's sentence drops from 1 year to 0—so (cooperate, cooperate) is not even a Nash equilibrium.
In fact, in the coalition-permitted prisoner's dilemma, no strong Nash equilibrium exists at all.
This was a devastating blow. If a solution concept fails to exist even in the simplest two-player game, what use is it for the real world?
Aumann's contribution remains profound—he first formalized the logic of coalitions and pioneered cooperative game theory. But strong Nash equilibrium itself, due to its lack of guaranteed existence, was almost never used in applied economics.
---
4. Coalition-Proof Equilibrium: Self-Enforcing Agreements
In 1987, three economists—Douglas Bernheim, Bezalel Peleg, and Michael Whinston—proposed a more refined concept: Coalition-Proof Nash Equilibrium (CPNE).
Their core insight: not all coalitional deviations are credible. If a deviation can itself be further deviated from by a smaller sub-coalition, then it is not "self-enforcing."
CPNE's 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
- No self-enforcing coalitional deviation exists 4. A deviation is "self-enforcing" if:
- It is a CPNE of the coalition's "induced game" (with other players' strategies fixed)
- No sub-coalition can further deviate from it and improve all its members
But even CPNE cannot guarantee existence. Bernheim et al. themselves proved: even in simple three-player games, CPNE may not exist.
Why? The recursive constraints can break at any level. Picture a three-layer coalition: grand coalition A wants to deviate, but A's sub-coalition B can deviate further from A's deviation, and B's sub-coalition C can deviate from B's... the recursion can collapse at any depth.
CPNE has found some applications in economics—menu auctions, dynamic public goods provision, corporate takeovers. But its non-existence problem has always loomed.
---
5. MIT's Breakthrough: MASE—Minimize Rather Than Eliminate
In April 2026, MIT's Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar published a concise but profound paper that fundamentally reshapes the field.
Their core insight is extremely simple, yet revolutionary: rather than demanding that coalitional incentives vanish entirely (usually impossible), look for a strategy profile that makes coalitional deviation incentives as small as possible.
They call the new solution concept the Minimum Average-Strong Equilibrium (MASE).
Formally, MASE solves this optimization problem:
Minimize: max_{S} max_{deviation} (1/|S|) × Σ_{i∈S} [payoff of i after deviation − payoff of i before deviation]
In other words: among all possible coalitions S, find a joint strategy that minimizes the average payoff gain any coalition can obtain through joint deviation.
Why "average" rather than "sum"? Because coalition sizes vary enormously. A two-player coalition gaining total payoff 20 means something very different from a ten-player coalition gaining total 20. Average payoffs put coalitions of different sizes on the same scale.
MASE's first important property: it always exists. Because "the maximum average coalitional gain" is a well-defined real number, and on compact strategy spaces, continuous functions always attain a minimum.
This resolves the existence crisis of strong Nash equilibrium and CPNE in one stroke.
MASE's second important property: it is computable—at least in some settings. Liu et al. proved that for average-payoff and maximum-payoff objectives, MASE computation has tight complexity lower bounds, and they give algorithms matching those bounds.
Interestingly, for the minimum-payoff objective (guaranteeing the worst-off member of a coalition gains as little as possible), the problem is computationally infeasible. This reveals a deep tradeoff: you can minimize average harm or maximize protection for the most-injured party, but not both.
---
6. From PPAD to Computability: The Complexity Legacy of Nash Equilibrium
To understand MASE's computational significance, we need a detour through a landmark of computer science.
In 2007, Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou proved a result that shook academia: computing a Nash equilibrium is PPAD-complete even in two-player games.
What is PPAD? It is a complexity class defined by Papadimitriou in 1994: "Polynomial Parity Argument, Directed version." PPAD contains problems whose solution existence is guaranteed by parity arguments—for example: in a directed graph, if you start from a source and walk along edges, you must end at a sink or return to another source. Since the number of sources and sinks must have the same parity (equal mod 2), if one source has no sink paired with it, another source must exist.
The existence of Nash equilibrium is guaranteed by exactly such a parity argument (via the fixed-point theorem). Daskalakis et al. showed that computing a Nash equilibrium is as hard as finding a source/sink pair in such graphs—which in complexity theory means: unless PPAD = P (considered extremely unlikely), no polynomial-time algorithm computes a Nash equilibrium.
This finding was read by some as a "complexity-theoretic critique" of Nash equilibrium: if a solution concept is hard to compute even in theory, how could players reach it in practice?
Liu et al.'s work on MASE continues this tradition. They not only define a new solution concept but rigorously characterize its computational complexity—a crucial step toward moving a new concept from theory to application.
---
7. EWF: The Frontier of 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 possible unilateral deviations. Zero exploitability means the strategy is a Nash equilibrium.
But zero exploitability often comes at the cost of social welfare. Imagine an auction: strictly strategyproof mechanisms (like VCG) have zero exploitability—no one benefits from misreporting valuations—but are rarely used in practice due to complexity and inefficiency. Simpler mechanisms (like first-price sealed-bid auctions) have positive exploitability but run efficiently and feel intuitively fair.
The EWF problem is: given an exploitability budget (say, exploitability at most 0.1), maximize social welfare.
This is a precise tradeoff between safety and efficiency. The MASE framework provides the mathematical tools: by controlling the maximum average coalitional gain (directly related to exploitability), you can explore the "optimal compromise" in the direction of welfare maximization.
In the context of AI safety, EWF has deeper implications. When multiple AI agents interact, you want their strategies to be hard to exploit (low exploitability) while achieving high social welfare (high efficiency). MASE provides a systematic framework for finding that sweet spot.
---
8. Conclusion
From Nash's 1950 dissertation, to Aumann's 1959 strong equilibrium, to Bernheim et al.'s 1987 coalition-proof equilibrium, to MIT's 2026 MASE—this 76-year academic arc reveals a profound truth:
Scientific progress often comes not from finding perfect answers, but from redefining the question.
Nash asked: "Does a state exist in which no one can do better alone?" Yes—but it may be socially suboptimal.
Aumann asked: "Does a state exist in which no coalition can do better jointly?" Answer: in most interesting games, no.
Bernheim asked: "Does a state exist in which no credible coalitional deviation can succeed?" Answer: sometimes yes, sometimes no.
Liu, Farina, and Ozdaglar asked a different question: "If we cannot eliminate coalitional deviation, what is the best we can do?" Answer: minimize it. And this question always has a solution.
In the prisoner's dilemma, MASE tells us: if you cannot stop the two prisoners from colluding, at least choose a strategy profile that minimizes the average gain from their collusion. It is not perfect justice—but it is achievable justice.
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).