Hedonic game

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 }$.

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\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.

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.

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]

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]

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]