The Chosen Coalitions Club: Inside von Neumann and Morgenstern Stability ✛
Context
Eight hundred participants, each with a strict preference list, enter a two-sided matching market. Some are firms. Others are workers. Everyone wants a single contract. Mathematically, this is a game theory with no repeat partnerships. The analysis of such markets began with John von Neumann and Oskar Morgenstern, who introduced the stable set concept. Yet linking the classical von Neumann–Morgenstern solution to modern matching theory tools proved tricky. The central question—can the vNM stable set be described in familiar terms?—long remained open. This work delivers a clear answer.
Methods
The path to the answer runs through two independent reductions of the preference profile. The first uses the optimization structure of the core. The core forms a lattice. Two extreme distributions—optimal for firms and for workers—set its boundaries. By sequentially removing pairs incompatible with moves inside the lattice (the Irving and Leather 1986 procedure), the authors keep only those relations that don’t break the dominance structure. The second reduction relies on the efficiency-adjusted deferred acceptance mechanism (EADA; Kesten, 2010). It filters out “blocking pairs”—those that stand in the way of Pareto improvements. Combining the two procedures yields the reduced profile P*. This is a collective behavior mirror of dominance ties.
Results
The main result: the von Neumann–Morgenstern stable set is unique. It exactly coincides with the core of the reduced profile P*. The chosen coalitions club is precisely all undominated outcomes in the specially trimmed game. Behind this compact statement lies a powerful technical apparatus. A key role is played by a generalization of the classic decomposition lemma. Differences between any two matchings from an internally stable set organize into cycles—IS-cycles. These cycles drive the reduction. They guarantee that the core of P* is both internally and externally stable in the original game. As a consequence, any outcome outside the core of P* is dominated by some club member. Moreover, the path to the core takes at most three dominance steps.
Implications
The result blurs the line between cooperative and structural views of stability. Instead of enumerating subsets, a simple procedure emerges: remove inessential pairs and take the core. This yields not only theoretical clarity. A practical algorithm appears. The notion of vNM stability ceases to be “exotic.” It slots into the general toolkit of matching theory. Dominance relations are now tied to topology.
Future development
The natural next step is to transfer the method to many-to-one and many-to-many markets. The lattice reduction generalizes partially. The EADA mechanism will need adaptation. Another direction is dynamics. Starting from an arbitrary state, how can agents drift toward the core? The three-step bound suggests: decentralized process converges fast. In the end, hundreds of participants can relax. Their chosen coalitions club is predictable.
Impact
Beyond pure game theory, the results matter for Dynamical Systems with decentralized decision making. Examples include organ donor allocation, school choice, and Graphs. Characterizing the stable set via a trimmed profile serves as a bridge between static normative analysis and realistic decentralized dynamics.
Next steps
Next steps: (1) generalize the characterization to multilateral markets; (2) build algorithms that find P* in polynomial time; (3) investigate whether decentralized dynamics always reach the core in exactly three steps.
Key open problems
The work contributes to the fundamental question of the existence of vNM stable sets in cooperative games. For matching markets, the answer is found: the set always exists and is unique. The reduction method shows that the key to the solution lies in removing inessential deviations.
The knowledge machine's view
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
The authors study vNM-stable sets in two-sided one-to-one markets with strict preferences. They introduce two preference profile reductions and show that the vNM-stable set is unique and coincides with the core of the reduced profile. The technical machinery relies on a generalization of the decomposition lemma and IS-cycles.
Where its strength is
The strength of the work lies in the explicit characterization of the vNM-stable set via the core after reduction, which connects cooperative stability with structural methods from matching theory.
Where it could go next
- Nearby in the archive there is a paper on how disorder gives rise to order; perhaps a similar view on stochastic perturbations of preferences could help understand the robustness of vNM-stability.based on: When Disorder Gives Birth to Order arXiv:2605.08967
- It might be interesting to explore the connection with work on communities by size in networks: there too, stable structures are sought, and transferring ideas about modularity to matching markets could yield new reduction algorithms.based on: Communities by Size: When Networks Assemble Like a Puzzle arXiv:2605.25248
Worth trying
- Check whether the uniqueness of the vNM-stable set persists under weak preferences or indifference.
- Assess the computational complexity of the proposed reduction on large random markets and compare it with brute-force enumeration.
- Apply the IS-cycle method to analyze the dynamics of bargaining processes where agents gradually change their preferences.
Why this may matter
Such a characterization could make vNM-stability practically computable and integrate it into the mechanism design toolkit for real two-sided markets.
Nearby works in our archive
- Neutrino Pairing Dance in a Dense Gassimilarity 0.56
- When Disorder Gives Birth to Ordersimilarity 0.56
- A Swarm of Insects Holds Together by Noisesimilarity 0.56
- The Atomic Nucleus: Not a Soloist, but a Choir of Voicessimilarity 0.56
- Communities by Size: When Networks Assemble Like a Puzzlesimilarity 0.55
- How the Brain Learns to Predict Without Cuessimilarity 0.55
The archive is sparse around this work: the closest review is only 0.56, against a usual 0.64. It looks like few have drilled nearby.
Original abstract
as written by the authors arXiv:2607.00869
This paper studies the structure and computation of von Neumann-Morgenstern (vNM) stable sets in one-to-one matching markets. While pairwise stability and corewise stability coincide under strict preferences and provide a well-understood benchmark, vNM stability is defined through dominance relations among sets of matchings and remains considerably more difficult to characterize. A key contribution of the paper is a generalization of the classical Decomposition Lemma. We show that the structural decomposition traditionally used to compare stable matchings extends to any pair of matchings belonging to the same internally stable set. This result reveals a previously unexplored connection between internal stability and the cycle structure underlying matching markets. Building on this characterization, we identify the relationships that are relevant for dominance-based stability and derive a reduced environment that concentrates all undominated outcomes. Our main result shows that the vNM stable set is unique and admits a simple characterization in terms of the core of this reduced environment. The characterization provides both structural insight and a constructive procedure for computing the vNM stable set using standard matching theoretic tools.
The decomposition lemma, usually proved only for the core, is generalized here for the first time to any internally stable sets. It is this generalization that allows “slicing” the market into independent IS-cycles and building the reduction. Thus the chosen coalitions club is born.
Key numbers
- maximum length of domination path to the core: 3
- number of reduction procedures to construct P*: 2