Sie sind hier

# Algorithmic Analysis of Hedonic Games with Diversity Preferences

Niclas Böhmer (University of Oxford)



Recently, Bredereck, Elkind, and Igarashi (2019) initiated the study of hedonic diversity games by considering a coalition formation setting in which each player is of one of two types and the players’ preferences depend solely on the fraction of players of their type in each coalition. In their work, Bredereck et al. already considered common hedonic games' solution concepts for this setting: They showed that while a core and Nash stable outcome is not guaranteed to exist in a hedonic diversity game, every single-peaked hedonic diversity game admits an individually stable outcome.

In this talk, we motivate hedonic diversity games as a meaningful restriction of the more general class of hedonic games and shortly summarise the work of Bredereck et al. Moreover, we extend their results in several ways: Firstly, we present a polynomial-time algorithm that computes an individually stable outcome in every hedonic diversity games. Secondly, we prove that it is NP-complete to decide whether a hedonic diversity game admits a Nash stable outcome. Finally, we consider two possible generalisations of the bicolour model of Bredereck et al. to more than two types of players and point towards possible further applications of diversity preferences.

Date
Speaker
Location
Language
05.09.2019
14:15
Niclas Böhmer
TEL 512
English

Back to the research colloquium site.

To top