Clustering Via Hedonic Games
by Gergely Csáji
In Artificial Intelligence, clustering is a fundamental task, where the goal is to discover hidden structures within data by grouping similar elements together. Traditional methods, such as k-means or DBSCAN, typically optimize these groups based on geometric distances or density.
Cooperative game theory on the other hand, offers a fascinating alternative perspective through the study of coalition formation. This field models autonomous agents who have specific preferences about whom they want to be grouped with. A subset of this field, known as “hedonic games,” assumes that an agent’s satisfaction depends entirely on the other members of their own group (that is, they only care about themselves, hence the term hedonic). In this framework, the goal is not just to group agents, but to achieve “stability”—a state where the system is robust against strategic deviations by the agents.
We strengthen the bridge between these two distinct fields by treating data clustering as a graphical hedonic game. In our model, data points act as agents in a “friends, enemies, and neutrals” framework: friendship represents high similarity between data points, while enmity represents dissimilarity. Preferences depend on the number of friends and enemies. For example, an agent may want to maximize the number of friends he has and then have as few enemies as possible; or conversely, minimize the number of enemies, but have as many friends as possible.
We introduce the notion of local-popularity, which aims to avoid the situation where there is an agent whose deviation to a different coalition would result in more agents being better off (i.e., supporting it), than getting worse (i.e., being against it). Our theoretical analysis confirms that when relationships are symmetric—meaning friendship and enmity are mutual—our algorithms are guaranteed to find a locally-popular solution very efficiently, in almost linear time. We also find that “balanced” preferences, where agents place equal weight on being with friends and avoiding enemies, allow for the most efficient convergence.
Our experiments demonstrate that this game-theoretic approach is surprisingly competitive with standard machine learning techniques for general clustering tasks. When tested on benchmarks like the Karate Club network, the Iris flower dataset, or even the breast cancer Wisconsin dataset containing diagnostic images, our algorithms often outperformed or matched state-of-the-art methods like Leiden, k-means and DBSCAN. Hence, our algorithms provide a novel and efficient way for clustering that is particularly useful when the task is about grouping people or entities capable of own decisions and strategic actions, as their outcome is (i) high quality with respect to standard clustering metrics and (ii) also robust against potential deviations. All this, while compressing the amount of information extremely: instead of continuous distance, we transform to a game with just friendship, enmity, and neutral relations.
Clustering via Hedonic Games:
New Concepts and Algorithms
Gergely Csáji – Alexander Gundert – Jörg Rothe – Ildikó Schlotter
39th Conference on Neural Information Processing Systems (NeurIPS 2025) San Diego, CA, US
