# Individual-Based Stability in Hedonic Diversity Games

arXiv: https://arxiv.org/abs/1911.08669 · HTML: https://mlsanity.com/paper/1911.08669/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

## Built on by (most cited first, 5 of 5)

- [Strategic Resource Selection with Homophilic Agents](https://mlsanity.com/paper/2305.00843/) (2023)
- [Single-Peaked Jump Schelling Games](https://mlsanity.com/paper/2302.12107/) (2023)
- [Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size](https://mlsanity.com/paper/2505.22384/) (2025)
- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)
- [The Bakers and Millers Game with Restricted Locations](https://mlsanity.com/paper/2501.05334/) (2025)

## Abstract (arXiv)

In hedonic diversity games (HDGs), recently introduced by Bredereck, Elkind and Igarashi (2019), each agent belongs to one of two classes (men and women, vegetarians and meat-eaters, junior and senior researchers), and agents' preferences over coalitions are determined by the fraction of agents from their class in each coalition. Bredereck et al. show that while an HDG may fail to have a Nash stable (NS) or a core stable (CS) outcome, every HDG in which all agents have single-peaked preferences admits an individually stable (IS) outcome, which can be computed in polynomial time. In this work, we extend and strengthen these results in several ways. First, we establish that the problem of deciding if an HDG has an NS outcome is NP-complete, but admits an XP algorithm with respect to the size of the smaller class. Second, we show that, in fact, all HDGs admit IS outcomes that can be computed in polynomial time; our algorithm for finding such outcomes is considerably simpler than that of Bredereck et al. We also consider two ways of generalizing the model of Bredereck et al. to k > 2 classes. We complement our theoretical results by empirical analysis, comparing the IS outcomes found by our algorithm, the algorithm of Bredereck et al. and a natural better-response dynamics.