Hedonic Coalition Nets

In hedonic games, players have the opportunity to form coalitions, and have preferences over the coalitions they might join. Such games can be used to model a variety of settings ranging from multi-agent coordination to group formation in social networks. However, the practical application of hedonic games is hindered by the fact that the naive representation for such games is exponential in the number of players. In this paper, we study hedonic coalition nets—a succinct, rule-based representation for hedonic games. This formalism is based on marginal contribution nets, which were developed by Ieong and Shoham for representing coalitional games with transferable utility. We show that hedonic coalition nets are universally expressive, yet are at least as succinct as other existing representation schemes for hedonic games. We then investigate the complexity of many natural decision problems for hedonic coalition nets. In particular, we provide a complete characterisation of the computational difficulty of problems related to coalitional stability for hedonic games represented with hedonic nets.

Authors

• Edith Elkind Northwestern University
• Michael Wooldridge University of Oxford

Keywords

• hedonic games
• marginal contribution nets
• complexity