Hedonic game - Alchetron, The Free Social Encyclopedia

In cooperative game theory, a hedonic game (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") 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.

Definition

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

A coalition structure π is a partition of N . Thus, every player i ∈ N belongs to a unique coalition π ( i ) in π .

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.

A coalition structure π is in the core if there is no coalition S all whose members prefer S to π . Formally, a non-empty coalition S is said to block π if S ≻ i π ( i ) for all i ∈ S . Then π is in the core if there are no blocking coalitions.

A coalition structure π is Nash-stable if no player wishes to change coalition within π . Formally, π is Nash-stable if there is no i ∈ N such that S ∪ { i } ≻ i π ( i ) for some S ∈ π ∪ { ∅ } . Notice that, according to Nash-stability, a deviation by a player is allowed even if members of the group S that are joined by i are made worse off by the deviation.

A coalition structure π is individually stable if no player wishes to join another coalition all whose members welcome the player. Formally, π is individually stable if there is no i ∈ N such that S ∪ { i } ≻ i π ( i ) for some S ∈ π ∪ { ∅ } where S ∪ { i } ≽ j S for all j ∈ S .

One can also define Pareto optimality of a coalition structure. 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 2 3

Consider the partition π = { { 1 , 2 } , { 3 } } . Notice that in π , player 3 would prefer to join the coalition { 1 , 2 } , because { 1 , 2 , 3 } ≻ 3 { 3 } , and hence π is not Nash-stable. However, if player 3 were to join { 1 , 2 } , player 1 (and also player 2 ) would be made worse off by this deviation, and so player 3 's deviation does not contradict individual stability. Indeed, one can check that π is individually stable. We can also see that there is no group S ⊆ N of players such that each member of S prefers S to their coalition in π 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 } , { 2 } , { 3 } } { 1 , 2 , 3 } { { 1 , 2 , 3 } } { 1 , 2 }

Existence guarantees

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 N = { 1 , 2 } with { 1 } ≻ 1 { 1 , 2 } and { 1 , 2 } ≻ 2 { 2 } . Here, we call player 2 the stalker. Notice that no coalition structure for this game is Nash-stable: in the coalition structure π 1 = { { 1 } , { 2 } } , where both players are alone, the stalker 2 deviates and joins 1; in the coalition structure π 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, and there is also an additively separable hedonic game with 5 players that has empty core and no individually stable coalition structures.

For symmetric additively separable hedonic games (those that satisfy v i ( j ) = v j ( i ) for all i , j ∈ 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. However, there are examples of symmetric additively separable hedonic games that have empty core.

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, with the top coalition property, with top or bottom responsiveness, with descending separable preferences, and with dichotomous preferences.

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

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. The same is true for anonymous games. For additively separable hedonic games, it is NP-complete to decide the existence of a Nash-stable or an individually stable outcome and complete for the second level of the polynomial hierarchy to decide whether there exists a core-stable outcome, even for symmetric additive preferences. 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 v i ( j ) are given in binary; the problem is PLS-complete. For the stable marriage problem, a core-stable outcome can be found in polynomial 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, but the problem is NP-complete if preference ties are allowed. Hedonic games with preferences based on the worst player behave very similarly to stable roommates problems with respect to the core, but there are hardness results for other solution concepts. Many of the preceding hardness results can be explained through meta-theorems about extending preferences over single players to coalitions.

References

Hedonic game Wikipedia

(Text) CC BY-SA