Hedonic game
Hedonic game
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. 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". represent a hedonic game by explicitly listing the preference rankings of all agents, but only listing individually rational coalitions, that is coalitions <math>S</math> with <math>S \succcurlyeq_i \{i\}</math>. 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* represent hedonic games through weighted Boolean formulas. As an example, the weighted formula <math>j \land \lnot k \mapsto_i 5</math> means that player <math>i</math> receives 5 utility points in coalitions that include <math>j</math> but do not include <math>k</math>. This representation formalism is universally expressive and often concise In anonymous hedonic games, players only care about the size* of their coalition, and agents are indifferent between any two coalitions with the same cardinality: if <math>|S| = |T|</math> then <math>S \sim_i T</math>. These games are anonymous in the sense that the identities of the individuals do not influence the preference ranking. In Boolean hedonic games*, 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), 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.
Existence guarantees thumb|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 <math>N = \{1,2\}</math> with <math>\{1\}\succ_1 \{1,2\}</math> and <math>\{1,2\}\succ_2 \{2\}</math>. Here, we call player 2 the stalker. Notice that no coalition structure for this game is Nash-stable: in the coalition structure <math>\pi_1 = \{\{1\}, \{2\}\}</math>, where both players are alone, the stalker 2 deviates and joins 1; in the coalition structure <math>\pi_2 = \{\{1, 2\}\}</math>, 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. However, there are examples of symmetric additively separable hedonic games that have empty core. 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). 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 <math>v_i(j)</math> are given in binary; the problem is PLS-complete. 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, 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,
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).
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 <math>O(n_a^2 d_{G})</math> of iterations, where <math>n_a</math> is the number of the robots and <math>d_G</math> 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.