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."
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.
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