Clustering via Hedonic Games : New Concepts and Algorithms

Csáji, Gergely Kál and Gundert, Alexander and Rothe, Jörg and Schlotter, Ildikó Anna (2025) Clustering via Hedonic Games : New Concepts and Algorithms. In: Advances in Neural Information Processing Systems 38. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS), [s.l.], pp. 65292-65337. ISBN 9798331338275

Preview

Text 085713-1962open.pdf - Published Version Download (6MB) | Preview

Abstract

We study fundamental connections between coalition formation games and clustering, illustrating the cross-disciplinary relevance of these concepts. We focus on graphical hedonic games where agents’ preferences are compactly represented by a friendship graph and an enmity graph. In the context of clustering, friendship relations naturally align with data point similarities, whereas enmity corresponds to dissimilarities. We consider two stability notions based on single-agent deviations: local popularity and local stability. Exploring these concepts from an algorithmic viewpoint, we design efficient mechanisms for finding locally stable or locally popular partitions. Besides gaining theoretical insight into the computational complexity of these problems, we perform simulations that demonstrate how our algorithms can be successfully applied in clustering and community detection.

Actions (login required)

View Item