Clustering via Hedonic Games: New Concepts and Algorithms. G. Csáji, A. Gundert, J. Rothe, and I. Schlotter. Proceedings of the 39th Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2025), San Diego, CA, USA, and Mexico City, Mexico. Advances in Neural Information Processing Systems 38, pages 65292-65337, November/December 2025. (Also presented at the 8th International Workshop on Matching Under Preferences (MATCH-UP 2026), nonarchival proceedings, New York University in Paris, France, July 2026.)
we are looking for a talented undergraduate student that has fundemental knowledge of theoretical computer science (especially algorithmics and computational complexity), technical skills in programming (e.g., C++/C, Java, JavaScript, Python, Karate, ...) and software development, and, if possible, expertise in Deep Generative Models for Image Classification and other clustering tasks and is open to and interested in research on coalition formation games (in particular, hedonic games), algorithmics, and computational complexity. Ideally, this half-year project will start in December 2026.
TOPIC: There are fundamental connections between coalition formation games and clustering that illustrate 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.
APPLICATIONS: should be sent by email to rothe@hhu.de by September 21, 2026, along with all documents supporting the application, including a CV and a letter of motivation for this specific research project.
AWARD CRITERIA: are the qualifications mentioned above (fundemental knowledge of theoretical computer science, technical skills in programming and software development, and, if possible, expertise in Deep Generative Models for Image Classification and other clustering tasks). It is further expected that the applicant is open to and interested in research on coalition formation games (in particular, hedonic games), algorithmics, and computational complexity.
The fellowship will be awarded to the best applicant according to academic excellence (study performances and academic achievements), motivation for this project, and academic potential to successfully master a project in game theory (specifically, related to coalition formation games).
In case of equal qualification, female students are preferred. Applications from international students are welcome; sufficient proficiency in English is required. The successful applicant will be selected by the Stipend commission of the Faculty of Mathematics and Natural Sciences of Heinrich Heine University Düsseldorf and will receive a monthly fellowship for six months.