Abstract

One of the results of this kind of game is a partition of the player set, also known as a coalition structure. This refers to a collection of coalitions, whose union is equal to the set of players, but which cannot be joined pairwise with one another. Marriage difficulties and roommate problems (Gale and Shapley (1962), Roth and Sotomayor (1990)) can both be viewed as special examples of hedonic coalition formation games. In these games, each agent solely considers who will be his or her partner. Problems can arise in both of these situations. In point of fact, hedonic games are only condensed versions of more general games involving the creation of coalitions. In these games, the manner in which a coalition's total payout is to be distributed among its members is predetermined and made transparent to all agents. Hedonic coalition formation games are a powerful tool to model agent behavior in a variety of circumstances. A classic example is the stable marriage problem which seeks to pair off men and women from two equally-sized groups. In the stable marriage problem, a pair is said to be stable if there is no man-woman pair who both want to leave their assigned partners to form a new pair.

Keywords

• Hedonic,
• Games,
• Theories

References

• Jos´eAlcaldeandAntonioRomero-Medina.Coalitionformationandstability.
• Social Choice and Welfare, 27(2):365–375, 2006.
• Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195:316 – 334, 2013.
• Haris Aziz, Felix Brandt, and Paul Harrenstein. Fractional hedonic games. In AAMAS, pages 5–12. International Foundation for Autonomous Agents and Mul- tiagent Systems, 2014.
• Harris Aziz and Rahul Savani. Handbook of computational social choice, chap- ter 15, pages 356–376. Cambridge University Press, 2016.
• CoralioBallester. NP-completeness in hedonic games. Games and Economic Behavior, 49(1):1 – 30, 2004.
• Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric. How long does it take for all users in a social network to choose their communities? Discrete Applied Mathematics, 270:37–57, 2019.
• Anna Bogomolnaia and Matthew O. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201–230, 2002.
• FelixBrandt,MartinBullinger,andAna¨elleWilczynski.Reaching individually stable coalition structures in hedonic games. In AAAI, 2021.
• SiminaBrˆanzei and Kate Larson. Social distance games. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.

This work is licensed under a Creative Commons Attribution 4.0 International License.