The Core in Max-Loss Non-Centroid Clustering Can Be Empty

Robert Bredereck, Eva Michelle Deltl, Leon Kellerhals, Jannik PetersarXiv 2025 · DOI · arXiv

Abstract

Non-centroid clustering models, where agent utility depends on group composition rather than distance to a central point, are increasingly relevant for collaborative tasks like team formation and federated learning. A central question in this domain is the existence of a "stable" clustering, defined by the Core in cooperative game theory. This paper settles an open question by demonstrating that under the max-loss objective—where an agent's cost is the distance to their furthest cluster-mate—the 1-core can be empty. Through a constructive proof involving a specific metric gadget and a 2D Euclidean point set, the authors show that stability is not guaranteed, even with small slack factors.

Introduction

In traditional clustering paradigms like k-means, agent loss is typically defined by the distance to an assigned cluster center. However, many real-world scenarios involve non-centroid clustering, where no central point exists and an agent's experience is determined entirely by the other members of their group. Examples include forming research teams or sports squads.

To evaluate the stability of such groupings, researchers apply the concept of the Core from cooperative game theory. A clustering is considered to be in the core if it is stable: no group of agents (of size at least $n/k$) can deviate from their current assignments to form a new cluster where every member of that new group is strictly better off. While previous research established that a stable 2-core (allowing for a slack factor of 2) always exists, the existence of a 1-core remained a significant open question. This work provides a definitive negative answer.

The Metric Gadget Construction

The authors utilize a constructive proof strategy centered on a specific "gadget"—a mathematical counterexample consisting of a set of agents and a distance matrix. This metric space is designed such that every possible partition into $k$ clusters results in at least one group with an incentive to "revolt."

The metric gadget construction featuring groups $G_1, G_2, G_3$ and special agents $a, b, c, w$.

As shown in Figure 1, the gadget includes three primary groups ($G_1, G_2, G_3$) and four special agents ($a, b, c, w$). The distances between these entities are carefully calibrated (e.g., $2^{1/5}, 2^{2/5}$) to create a "no-win" scenario. A critical component is the agent $w$, who acts as a "poison pill." Because $w$ is located at a distance $M \gg 1$ from all other agents, any group forced to include $w$ suffers a massive max-loss, creating constant pressure for agents to form tighter, alternative coalitions.

Case Analysis and Instability

The proof exhaustively analyzes potential clustering configurations, categorizing them into "pure" clusters (containing only one group) and "mixed" clusters. In every scenario, the authors identify a specific coalition that can improve its max-loss by deviating.

An illustration of a potential clustering partition and a deviating coalition (indicated by the dashed blue line).

Figure 3 illustrates how mixed clusters fail to maintain stability. The max-loss objective is particularly sensitive; because an agent's loss is determined by the single furthest person in their cluster, the inclusion of even one relatively distant agent can trigger a deviation. The authors prove that for their metric construction, a slack factor ($\alpha$) of at least $2^{1/5} \approx 1.148$ is required to guarantee stability.

Euclidean Reality and Computational Verification

To ensure these results are not merely artifacts of abstract metric spaces, the authors extended their search to 2D Euclidean space. Using an optimization algorithm, they identified a specific configuration of 9 points in $\mathbb{R}^2$ where the core remains empty for any $\alpha < 1.138$. This demonstrates that the instability persists even in common geometric settings. Furthermore, the authors provided a computational tool, CoreCheck, to verify the stability of any given set of points and clusters.

Conclusion

This paper establishes that the 1-core in max-loss non-centroid clustering can be empty, answering a fundamental question in computational social choice. While the results show that the 1.148-core can be empty, it is known that the 2-core is always non-empty. Future work remains to bridge this gap and find the exact "tipping point" for guaranteed stability. Additionally, the slightly lower bound found in Euclidean space (1.138) suggests that geometric constraints may inherently offer better stability guarantees than general metric spaces, a promising avenue for further investigation.

Summary updated

Abstract

We study core stability in non-centroid clustering under the max-loss objective, where each agent's loss is the maximum distance to other members of their cluster. We prove that for all $k\geq 3$ there exist metric instances with $n\ge 9$ agents, with $n$ divisible by $k$, for which no clustering lies in the $α$-core for any $α<2^{\frac{1}{5}}\sim 1.148$. The bound is tight for our construction. Using a computer-aided proof, we also identify a two-dimensional Euclidean point set whose associated lower bound is slightly smaller than that of our general construction. This is, to our knowledge, the first impossibility result showing that the core can be empty in non-centroid clustering under the max-loss objective.
BibTeX
@misc{bredereck2025core,
  author = {Robert Bredereck and Eva Michelle Deltl and Leon Kellerhals and Jannik Peters},
  title = {{The Core in Max-Loss Non-Centroid Clustering Can Be Empty}},
  year = {2025},
  eprint = {2511.19107},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.19107},
}
Figure