Existence and Computation of Core Stable Outcomes

This direction is split into other directions: core stability existence. Its last version stays readable and citable here.

Version 1 of 129 papers39 conceptsfrozen 2026-10-04

In collective decision-making, whether we are picking a committee, forming a social club, or partitioning a dataset, we face a fundamental question of fairness: can we reach an agreement that no group of people wants to walk away from?

This is the intuition behind the Core, a central concept in cooperative game theory. An outcome is in the core if no subgroup of agents (a "coalition") has both the incentive and the power to secede and form their own arrangement that they all prefer. While the core is the gold standard for stability, researchers across social choice, clustering, and game theory are discovering that guaranteeing its existence—and finding it efficiently—is one of the most difficult challenges in the field.

The Stability Gap

The primary tension in this research is the existence problem. In many systems, the core is simply empty. For example, in "max-loss" non-centroid clustering—where we group people based on the distance to their furthest group-mate—Leon Kellerhals and Jannik Peters recently proved that there are scenarios where no matter how you cluster the agents, a subset will always have an incentive to "revolt" and form their own group Kellerhals et al. (2025).

This same ghost haunts multi-winner voting. When voters use approval ballots to pick a committee, we want "core stability": no group of voters should be able to pick a smaller committee that they all prefer over the official one. As Haris Aziz has noted, it remains an open question whether such a committee is even mathematically guaranteed to exist for every possible set of voter preferences Aziz (2018).

Bridging the Gap with Approximation

If perfect stability is impossible to guarantee, how close can we get? This has led to a shift toward approximate stability. Instead of requiring that no group wants to deviate, we look for outcomes where the incentive to deviate is small—a "slack factor."

A major breakthrough in this direction came from Drew Gao and Jan Vondrák. They proved that while perfect stability is elusive, a 3.651-approximately stable committee always exists and can be found in polynomial time Gao & Vondrák (2025). Their approach works by treating the voting problem like an economic market, using Lindahl equilibria—a system where agents "pay" for public goods based on their marginal interest—and then using sophisticated randomized rounding to turn those economic fractions into a real committee.

The Complexity of Verification

Even if we find a potentially stable outcome, how do we know it’s actually stable? In many cases, simply verifying stability is as hard as finding it.

In hedonic games, where players' happiness depends entirely on who is in their coalition, Martin Gairing and Rahul Savani showed that finding stable partitions is generally PLS-complete, a complexity class associated with finding local optima in hard landscapes Gairing & Savani (2015).

Surprisingly, adding "niceness" doesn't always help. In altruistic hedonic games, where players care about their friends' happiness, Jörg Rothe and Ildikó Schlotter proved that verifying core stability is coNP-complete Rothe & Schlotter (2025). This means that even if a group is perfectly stable, proving it to be so might be computationally impossible for large networks.

New Frontiers: Time and Space

The search for stability is expanding into more complex domains:

  1. Temporal Voting: Bradley Phillips and colleagues are exploring how to maintain proportionality and stability when decisions are made sequentially over time, rather than in a single election Phillips et al. (2025).
  2. Spatial Voting: Arnold Filtser and Omrit Filtser investigate stability when voters and candidates are points in a metric space, seeking the minimum "relaxation" of majority rule needed to ensure a stable winner Filtser & Filtser (2020).
  3. Automated Reasoning: To tackle these existential questions, researchers like Vincent Conitzer and Marijn Heule are turning to computers, using SAT solvers and MILP (Mixed-Integer Linear Programming) to search for counterexamples or existence proofs that have eluded human mathematicians for decades Berker et al. (2025).

By moving from "perfect" stability to "approximate" stability, and from manual proofs to automated reasoning, this research direction is slowly mapping the boundaries of what it means for a collective decision to be truly unshakeable.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_existence_and_computation_of_core_stable_6c849499,
  title = {Existence and Computation of Core Stable Outcomes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-and-computation-of-core-stable-outcomes/rdr_6c849499ed254231bc58e2e16addeb49},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_existence_and_computation_of_core_stable_6c849499_v1,
  title = {Existence and Computation of Core Stable Outcomes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-and-computation-of-core-stable-outcomes/rdr_6c849499ed254231bc58e2e16addeb49/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}