Hedonic game

In cooperative game theory, a hedonic game ^{[1] [2]} (also known as a hedonic coalition formation game) is a game that models the formation of coalitions (groups) of players when players have preferences over which group they belong to. A hedonic game is specified by giving a finite set of players, and, for each player, a preference ranking over all coalitions (subsets) of players that the player belongs to. The outcome of a hedonic game consists of a partition of the players into disjoint coalitions, that is, each player is assigned a unique group. Such partitions are often referred to as coalition structures.

Hedonic games are a type of non-transferable utility game. Their distinguishing feature (the "hedonic aspect" ^[3] ) is that players only care about the identity of the players in their coalition, but do not care about how the remaining players are partitioned, and do not care about anything other than which players are in their coalition. Thus, in contrast to other cooperative games, a coalition does not choose how to allocate profit among its members, and it does not choose a particular action to play. Some well-known subclasses of hedonic games are given by matching problems, such as the stable marriage, stable roommates, and the hospital/residents problems.

The players in hedonic games are typically understood to be self-interested, and thus hedonic games are usually analyzed in terms of the stability of coalition structures, where several notions of stability are used, including the core and Nash stability. Hedonic games are studied both in economics, where the focus lies on identifying sufficient conditions for the existence of stable outcomes, and in multi-agent systems, where the focus lies on identifying concise representations of hedonic games and on the computational complexity of finding stable outcomes. ^[2]

Definition

Formally, a hedonic game is a pair ${\displaystyle (N,(\succcurlyeq _{i})_{i\in N})}$ of a finite set ${\displaystyle N}$ of players (or agents), and, for each player ${\displaystyle i\in N}$ a complete and transitive preference relation ${\displaystyle \succcurlyeq _{i}}$ over the set ${\displaystyle \{S\subseteq N:i\in S\}}$ of coalitions that player ${\displaystyle i}$ belongs to. A coalition is a subset ${\displaystyle S\subseteq N}$ of the set of players. The coalition ${\displaystyle N}$ is typically called the grand coalition.

A coalition structure${\displaystyle \pi }$ is a partition of ${\displaystyle N}$. Thus, every player ${\displaystyle i\in N}$ belongs to a unique coalition ${\displaystyle \pi (i)}$ in ${\displaystyle \pi }$.

Solution concepts

Like in other areas of game theory, the outcomes of hedonic games are evaluated using solution concepts. Many of these concepts refer to a notion of game-theoretic stability: an outcome is stable if no player (or possibly no coalition of players) can deviate from the outcome so as to reach a subjectively better outcome. Here we give definitions of several solution concepts from the literature. ^{[1] [2]}

• A coalition structure ${\displaystyle \pi }$ is in the core (or is core stable) if there is no coalition ${\displaystyle S}$ whose members all prefer ${\displaystyle S}$ to ${\displaystyle \pi }$. Formally, a non-empty coalition ${\displaystyle S}$ is said to block${\displaystyle \pi }$ if ${\displaystyle S\succ _{i}\pi (i)}$ for all ${\displaystyle i\in S}$. Then ${\displaystyle \pi }$ is in the core if there are no blocking coalitions.
• A coalition structure ${\displaystyle \pi }$ is in the strict core (or is strictly core stable) if there is no weakly blocking coalition ${\displaystyle S}$ where all members weakly prefer ${\displaystyle S}$ to ${\displaystyle \pi }$ and some member strictly prefers ${\displaystyle S}$ to ${\displaystyle \pi }$. In other words, ${\displaystyle \pi }$ is in the strict core if ${\displaystyle \not \exists :S\subseteq N:(\forall i\in N:S\succeq \pi )\land (\exists i\in N:S\succ \pi )}$.
• A coalition structure ${\displaystyle \pi }$ is Nash-stable if no player wishes to change coalition within ${\displaystyle \pi }$. Formally, ${\displaystyle \pi }$ is Nash-stable if there is no ${\displaystyle i\in N}$ such that ${\displaystyle S\cup \{i\}\succ _{i}\pi (i)}$ for some ${\displaystyle S\in \pi \cup \{\emptyset \}}$. Notice that, according to Nash-stability, a deviation by a player is allowed even if members of the group ${\displaystyle S}$ that are joined by ${\displaystyle i}$ are made worse off by the deviation.
• A coalition structure ${\displaystyle \pi }$ is individually stable if no player wishes to join another coalition whose members all welcome the player. Formally, ${\displaystyle \pi }$ is individually stable if there is no ${\displaystyle i\in N}$ such that ${\displaystyle S\cup \{i\}\succ _{i}\pi (i)}$ for some ${\displaystyle S\in \pi \cup \{\emptyset \}}$ where ${\displaystyle S\cup \{i\}\succeq _{j}S}$ for all ${\displaystyle j\in S}$.
• A coalition structure ${\displaystyle \pi }$ is contractually individually stable if there is no player who belongs to a coalition willing to let him leave and who wants to join a coalition willing to have him. In other words, ${\displaystyle \pi }$ is contractually individually stable if ${\displaystyle \not \exists i\in N:(\forall j\in \pi (i):\pi (i)\setminus \{i\}\succeq _{j}\pi (i))~\land ~(\exists C\in \pi$ :(C\cup \{i\}\succ _{i}\pi (i))~\land ~(\forall j\in C:C\cup \{i\}\succeq _{j}C))}.

One can also define Pareto optimality of a coalition structure. ^[4] In the case that the preference relations are represented by utility functions, one can also consider coalition structures that maximize social welfare.

Examples

The following three-player game has been named "an undesired guest". ^[1]

$${\displaystyle {\begin{aligned}&\{1,2\}\succ _{1}\{1\}\succ _{1}\{1,2,3\}\succ _{1}\{1,3\},\\&\{1,2\}\succ _{2}\{2\}\succ _{2}\{1,2,3\}\succ _{2}\{2,3\},\\&\{1,2,3\}\succ _{3}\{2,3\}\succ _{3}\{1,3\}\succ _{3}\{3\}.\end{aligned}}}$$

From these preferences, we can see that ${\displaystyle 1}$ and ${\displaystyle 2}$ like each other, but dislike the presence of player ${\displaystyle 3}$.

Consider the partition ${\displaystyle \pi =\{\{1,2\},\{3\}\}}$. Notice that in ${\displaystyle \pi }$, player 3 would prefer to join the coalition ${\displaystyle \{1,2\}}$, because ${\displaystyle \{1,2,3\}\succ _{3}\{3\}}$, and hence ${\displaystyle \pi }$ is not Nash-stable. However, if player ${\displaystyle 3}$ were to join ${\displaystyle \{1,2\}}$, player ${\displaystyle 1}$ (and also player ${\displaystyle 2}$) would be made worse off by this deviation, and so player ${\displaystyle 3}$'s deviation does not contradict individual stability. Indeed, one can check that ${\displaystyle \pi }$ is individually stable. We can also see that there is no group ${\displaystyle S\subseteq N}$ of players such that each member of ${\displaystyle S}$ prefers ${\displaystyle S}$ to their coalition in ${\displaystyle \pi }$ and so the partition is also in the core.

Another three-player example is known as "two is a company, three is a crowd". ^[1]

$${\displaystyle {\begin{aligned}&\{1,2\}\succ _{1}\{1,3\}\succ _{1}\{1,2,3\}\succ _{1}\{1\},\\&\{2,3\}\succ _{2}\{2,1\}\succ _{2}\{1,2,3\}\succ _{2}\{2\},\\&\{3,1\}\succ _{3}\{3,2\}\succ _{3}\{1,2,3\}\succ _{3}\{3\}.\end{aligned}}}$$

In this game, no partition is core-stable: The partition ${\displaystyle \{\{1\},\{2\},\{3\}\}}$ (where everyone is alone) is blocked by ${\displaystyle \{1,2,3\}}$; the partition ${\displaystyle \{\{1,2,3\}\}}$ (where everyone is together) is blocked by ${\displaystyle \{1,2\}}$; and partitions consisting of one pair and a singleton are blocked by another pair, because the preferences contain a cycle.

Concise representations and restricted preferences

Since the preference relations in a hedonic game are defined over the collection of all ${\displaystyle 2^{|N|-1}}$ subsets of the player set, storing a hedonic game takes exponential space. This has inspired various representations of hedonic games that are concise, in the sense that they (often) only require polynomial space.

• Individually rational coalition lists ^[5] represent a hedonic game by explicitly listing the preference rankings of all agents, but only listing individually rational coalitions, that is coalitions ${\displaystyle S}$ with ${\displaystyle S\succcurlyeq _{i}\{i\}}$. For many solution concepts, it is irrelevant how precisely the player ranks unacceptable coalitions, since no stable coalition structure can contain a coalition that is not individually rational for one of the players. Note that if there are only polynomially many individually rational coalitions, then this representation only takes polynomial space.
• Hedonic coalition nets ^[6] represent hedonic games through weighted Boolean formulas. As an example, the weighted formula ${\displaystyle j\land \lnot k\mapsto _{i}5}$ means that player ${\displaystyle i}$ receives 5 utility points in coalitions that include ${\displaystyle j}$ but do not include ${\displaystyle k}$. This representation formalism is universally expressive and often concise ^[6] (though, by necessity, there are some hedonic games whose hedonic coalition net representation requires exponential space).
• Additively separable hedonic games ^[1] are based on every player assigning numerical values to the other players; a coalition is as good for a player as the sum of the values of the players. Formally, additively separable hedonic games are those for which there exist valuations ${\displaystyle v_{i}(j)\in \mathbb {R} }$ for every ${\displaystyle i,j\in N}$ such that for all players ${\displaystyle i}$ and all coalitions ${\displaystyle S,T\ni i}$, we have ${\displaystyle S\succcurlyeq _{i}T}$ if and only if ${\displaystyle \textstyle \sum _{j\in S}v_{i}(j)\geq \textstyle \sum _{j\in T}v_{i}(j)}$. A similar definition, using the average rather than the sum of values, leads to the class of fractional hedonic games. ^[7]
• In anonymous hedonic games, ^[8] players only care about the size of their coalition, and agents are indifferent between any two coalitions with the same cardinality: if ${\displaystyle |S|=|T|}$ then ${\displaystyle S\sim _{i}T}$. These games are anonymous in the sense that the identities of the individuals do not influence the preference ranking.
• In Boolean hedonic games, ^[9] each player has a Boolean formula whose variables are the other players. Each player prefers coalitions that satisfy its formula to coalitions that do not, but is otherwise indifferent.
• In hedonic games with preferences depending on the worst player (or W-preferences ^[10] ), players have a preference ranking over players, and extend this ranking to coalitions by evaluating a coalition according to the (subjectively) worst player in it. Several similar concepts (such as B-preferences) have been defined. ^{[11] [12] [13]}

Existence guarantees

This digraph describes an additively separable hedonic game whose core is empty. It has five players (displayed as circled vertices). Any two players not connected by an arc have valuation -1000 for each other.

Not every hedonic game admits a coalition structure that is stable. For example, we can consider the stalker game, which consists of just two players ${\displaystyle N=\{1,2\}}$ with ${\displaystyle \{1\}\succ _{1}\{1,2\}}$ and ${\displaystyle \{1,2\}\succ _{2}\{2\}}$. Here, we call player 2 the stalker. Notice that no coalition structure for this game is Nash-stable: in the coalition structure ${\displaystyle \pi _{1}=\{\{1\},\{2\}\}}$, where both players are alone, the stalker 2 deviates and joins 1; in the coalition structure ${\displaystyle \pi _{2}=\{\{1,2\}\}}$, where the players are together, player 1 deviates into the empty coalition so as to not be together with the stalker. There is a well-known instance of the stable roommates problem with 4 players that has empty core, ^[14] and there is also an additively separable hedonic game with 5 players that has empty core and no individually stable coalition structures. ^[15]

For symmetric additively separable hedonic games (those that satisfy ${\displaystyle v_{i}(j)=v_{j}(i)}$ for all ${\displaystyle i,j\in N}$), there always exists a Nash-stable coalition structure by a potential function argument. In particular, coalition structures that maximize social welfare are Nash-stable. ^[1] A similar argument shows that a Nash-stable coalition structure always exists in the more general class of subset-neutral hedonic games. ^[16] However, there are examples of symmetric additively separable hedonic games that have empty core. ^[8]

Several conditions have been identified that guarantee the existence of a core coalition structure. This is the case in particular for hedonic games with the common ranking property, ^{[17] [18]} with the top coalition property, ^[8] with top or bottom responsiveness, ^[19] with descending separable preferences, ^{[20] [21]} and with dichotomous preferences. ^[9] Moreover, common ranking property has been shown to guarantee the existence of a coalition structure which is core stable, individually stable and Pareto optimal at the same time. ^[22]

Computational complexity

When considering hedonic games, the field of algorithmic game theory is usually interested in the complexity of the problem of finding a coalition structure satisfying a certain solution concept when given a hedonic game as input (in some concise representation). ^[2] Since it is usually not guaranteed that a given hedonic game admits a stable outcome, such problems can often be phrased as a decision problem asking whether a given hedonic game admits any stable outcome. In many cases, this problem turns out to be computationally intractable. ^{[18] [23]} One exception is hedonic games with common ranking property where a core coalition structure always exists, and it can be found in polynomial time. ^[17] However, it is still NP-hard to find a Pareto optimal or socially optimal outcome. ^[22]

In particular, for hedonic games given by individually rational coalition lists, it is NP-complete to decide whether the game admits a core-stable, a Nash-stable, or an individually stable outcome. ^[5] The same is true for anonymous games. ^[5] For additively separable hedonic games, it is NP-complete to decide the existence of a Nash-stable or an individually stable outcome ^[15] and complete for the second level of the polynomial hierarchy to decide whether there exists a core-stable outcome, ^[24] even for symmetric additive preferences. ^[25] These hardness results extend to games given by hedonic coalition nets. While Nash- and individually stable outcomes are guaranteed to exist for symmetric additively separable hedonic games, finding one can still be hard if the valuations ${\displaystyle v_{i}(j)}$ are given in binary; the problem is PLS-complete. ^[26] For the stable marriage problem, a core-stable outcome can be found in polynomial time using the deferred acceptance algorithm; for the stable roommates problem, the existence of a core-stable outcome can be decided in polynomial time if preferences are strict, ^[27] but the problem is NP-complete if preference ties are allowed. ^[28] Hedonic games with preferences based on the worst player behave very similarly to stable roommates problems with respect to the core, ^[10] but there are hardness results for other solution concepts. ^[13] Many of the preceding hardness results can be explained through meta-theorems about extending preferences over single players to coalitions. ^[23]

Applications

Robotics

For a robotic system consisting of multiple autonomous intelligent robots (e.g., swarm robotics), one of their decision making issues is how to make a robotic team for each of given tasks requiring collaboration of the robots. Such a problem can be called multi-robot task allocation or multi-robot coalition formation problem. This problem can be modelled as a hedonic game, and the preferences of the robots in the game may reflect their individual favours (e.g., possible battery consumption to finish a task) and/or social favours (e.g., complementariness of other robots' capabilities, crowdedness for shared resource).

Some of the particular concerns in such robotics application of hedonic games relative to the other applications include the communication network topology of robots (e.g., the network is most likely partially connected network) and the need of a decentralised algorithm that finds a Nash-stable partition (because the multi-robot system is a decentralised system).

This figure shows how each of 320 robots makes a decision in terms of which task it has to work with whom, by using the decentralised algorithm in. Here, each circle represents each robot, and the lines between them represent the communication network of the robots. Each square and its size indicate each of the given tasks and its task demand, respectively. The final result is a Nash-stable partition, where the robots form task-specific coalitions.

Using anonymous hedonic games under SPAO(Single-Peaked-At-One) preference, a Nash-stable partition of decentralised robots, where each coalition is dedicated to each task, is guaranteed to be found within ${\displaystyle O(n_{a}^{2}d_{G})}$ of iterations, ^[29] where ${\displaystyle n_{a}}$ is the number of the robots and ${\displaystyle d_{G}}$ is their communication network diameter. Here, the implication of SPAO is robots' social inhibition (i.e., reluctancy of being together), which normally arises when their cooperation is subadditive.

References

1. Bogomolnaia, Anna; Jackson, Matthew O. (Feb 2002). "The Stability of Hedonic Coalition Structures". Games and Economic Behavior. 38 (2): 201–230. CiteSeerX   10.1.1.42.8306 . doi:10.1006/game.2001.0877.
2. Haris Aziz and Rahul Savani, "Hedonic Games". Chapter 15 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN   9781107060432. ( free online version )
3. Drèze, J. H.; Greenberg, J. (1980). "Hedonic Coalitions: Optimality and Stability". Econometrica. 48 (4): 987–1003. doi:10.2307/1912943. JSTOR   1912943.
4. Aziz, Haris; Brandt, Felix; Harrenstein, Paul (Nov 2013). "Pareto optimality in coalition formation". Games and Economic Behavior. 82: 562–581. CiteSeerX   10.1.1.228.6696 . doi:10.1016/j.geb.2013.08.006. S2CID   6441501.
5. Ballester, Coralio (Oct 2004). "NP-completeness in hedonic games". Games and Economic Behavior. 49 (1): 1–30. doi:10.1016/j.geb.2003.10.003.
6. Elkind, Edith; Wooldridge, Michael (2009). Hedonic Coalition Nets. pp. 417–424. ISBN   978-0-981-73816-1.{{cite book}}: |journal= ignored (help)
7. Aziz, Haris; Brandt, Felix; Harrenstein, Paul (2014). Fractional Hedonic Games. pp. 5–12. ISBN   978-1-450-32738-1.{{cite book}}: |journal= ignored (help)
8. Banerjee, Suryapratim; Konishi, Hideo; Sönmez, Tayfun (2001). "Core in a simple coalition formation game". Social Choice and Welfare. 18 (1): 135–153. CiteSeerX   10.1.1.18.7132 . doi:10.1007/s003550000067. ISSN   0176-1714. S2CID   2822109.
9. Aziz, Haris; Harrenstein, Paul; Lang, Jérôme; Wooldridge, Michael (2016-04-25). "Boolean hedonic games". KR'16 Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning. International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press. pp. 166–175. arXiv: 1509.07062 .
10. Cechlárová, Katarína; Hajduková, Jana (2004-04-15). "Stable partitions with W-preferences". Discrete Applied Mathematics. 138 (3): 333–347. doi:10.1016/S0166-218X(03)00464-5.
11. Hajduková, Jana (2006-12-01). "Coalition formation games: a survey". International Game Theory Review. 08 (4): 613–641. doi:10.1142/S0219198906001144. ISSN   0219-1989.
12. Cechlárová, Katarı´na; Hajduková, Jana (2003-06-01). "Computational complexity of stable partitions with B-preferences". International Journal of Game Theory. 31 (3): 353–364. doi:10.1007/s001820200124. ISSN   0020-7276. S2CID   206890693.
13. Aziz, Haris; Harrenstein, Paul; Pyrga, Evangelia (2012). Individual-based Stability in Hedonic Games Depending on the Best or Worst Players. pp. 1311–1312. arXiv: 1105.1824 . Bibcode:2011arXiv1105.1824A. ISBN   978-0981738130.{{cite book}}: |journal= ignored (help)
14. Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". The American Mathematical Monthly. 69 (1): 9–15. doi:10.2307/2312726. JSTOR   2312726.
15. Sung, Shao-Chin; Dimitrov, Dinko (Jun 2010). "Computational complexity in additive hedonic games". European Journal of Operational Research. 203 (3): 635–639. CiteSeerX   10.1.1.318.6242 . doi:10.1016/j.ejor.2009.09.004.
16. Suksompong, Warut (Nov 2015). "Individual and group stability in neutral restrictions of hedonic games". Mathematical Social Sciences. 78: 1–5. arXiv: 1804.03315 . doi:10.1016/j.mathsocsci.2015.07.004. S2CID   4749111.
17. Farrell, Joseph; Scotchmer, Suzanne (1988). "Partnerships". The Quarterly Journal of Economics. 103 (2): 279–297. doi:10.2307/1885113. JSTOR   1885113.
18. Woeginger, Gerhard J. (2013). "Core Stability in Hedonic Coalition Formation". In Boas, Peter van Emde; Groen, Frans C. A.; Italiano, Giuseppe F.; Nawrocki, Jerzy; Sack, Harald (eds.). SOFSEM 2013: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 7741. Springer Berlin Heidelberg. pp. 33–50. arXiv: 1212.2236 . doi:10.1007/978-3-642-35843-2_4. ISBN   978-3-642-35842-5. S2CID   13229559.
19. Aziz, Haris; Brandl, Florian (2012). Existence of Stability in Hedonic Coalition Formation Games. pp. 763–770. arXiv: 1201.4754 . Bibcode:2012arXiv1201.4754A. ISBN   978-0981738123.{{cite book}}: |journal= ignored (help)
20. Burani, Nadia; Zwicker, William S. (Feb 2003). "Coalition formation games with separable preferences". Mathematical Social Sciences. 45 (1): 27–52. CiteSeerX   10.1.1.329.7239 . doi:10.1016/S0165-4896(02)00082-3.
21. Karakaya, Mehmet (May 2011). "Hedonic coalition formation games: A new stability notion". Mathematical Social Sciences. 61 (3): 157–165. doi:10.1016/j.mathsocsci.2011.03.004. hdl: 11693/21939 .
22. Caskurlu, Bugra; Kizilkaya, Fatih Erdem (2019). "On Hedonic Games with Common Ranking Property". Algorithms and Complexity. CIAC 2019. Vol. 11485. Rome, Italy: Springer, Cham. pp. 137–148. arXiv: 2205.11939 . doi:10.1007/978-3-030-17402-6_12. ISBN   978-3-030-17402-6. S2CID   159041690.
23. Peters, Dominik; Elkind, Edith (2015). Simple Causes of Complexity in Hedonic Games. pp. 617–623. arXiv: 1507.03474 . Bibcode:2015arXiv150703474P. ISBN   978-1-577-35738-4.{{cite book}}: |journal= ignored (help)
24. Woeginger, Gerhard J. (Mar 2013). "A hardness result for core stability in additive hedonic games". Mathematical Social Sciences. 65 (2): 101–104. doi:10.1016/j.mathsocsci.2012.10.001.
25. Peters, Dominik (2015-09-08). "${\displaystyle \Sigma _{2}^{p}}$-complete Problems on Hedonic Games". arXiv: 1509.02333 [cs.GT].
26. Gairing, Martin; Savani, Rahul (2010). "Computing Stable Outcomes in Hedonic Games". In Kontogiannis, Spyros; Koutsoupias, Elias; Spirakis, Paul G. (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 6386. Springer Berlin Heidelberg. pp. 174–185. Bibcode:2010LNCS.6386..174G. doi:10.1007/978-3-642-16170-4_16. ISBN   978-3-642-16169-8.
27. Irving, Robert W. (Dec 1985). "An efficient algorithm for the "stable roommates" problem". Journal of Algorithms. 6 (4): 577–595. doi:10.1016/0196-6774(85)90033-1.
28. Ronn, Eytan (Jun 1990). "NP-complete stable matching problems". Journal of Algorithms. 11 (2): 285–304. doi:10.1016/0196-6774(90)90007-2.
29. Jang, I.; Shin, H.; Tsourdos, A. (December 2018). "Anonymous Hedonic Game for Task Allocation in a Large-Scale Multiple Agent System". IEEE Transactions on Robotics. 34 (6): 1534–1548. arXiv: 1711.06871 . doi:10.1109/TRO.2018.2858292. ISSN   1552-3098. S2CID   124328.