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. Definition. Formally, a  hedonic game is a pair formula_1 of a finite set formula_2 of players (or agents), and, for each player formula_3 a complete and transitive preference relation formula_4 over the set formula_5 of coalitions that player formula_6 belongs to. A "coalition" is a subset formula_7 of the set of players. The coalition formula_2 is typically called the "grand coalition". A "coalition structure" formula_9 is a partition of formula_2. Thus, every player formula_3 belongs to a unique coalition formula_12 in formula_9. 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. 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"".formula_49From these preferences, we can see that formula_50 and formula_51  like each other, but dislike the presence of player formula_52. Consider the partition formula_53. Notice that in formula_9, player 3 would prefer to join the coalition formula_55, because formula_56, and hence formula_9 is not Nash-stable. However, if player formula_52 were to join formula_55, player formula_50 (and also player formula_51) would be made worse off by this deviation, and so player formula_52's deviation does not contradict individual stability. Indeed, one can check that formula_9 is individually stable. We can also see that there is no group formula_7 of players such that each member of formula_15 prefers formula_15 to their  coalition in formula_9 and so the partition is also in the core. Another three-player example is known as ""two is a company, three is a crowd"".formula_68In this game, no partition is core-stable: The partition formula_69 (where everyone is alone) is blocked by formula_70; the partition formula_71 (where everyone is together) is blocked by formula_55; 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 formula_73 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. 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 formula_88 with formula_89 and formula_90. Here, we call player 2 the stalker. Notice that no coalition structure for this game is Nash-stable: in the coalition structure formula_91, where both players are alone, the stalker 2 deviates and joins 1; in the coalition  structure formula_92, 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 formula_93 for all formula_94), there always exists a Nash-stable coalition structure by a potential function argument. In particular, coalition structures that maximize social welfare are Nash-stable . A similar argument shows that a Nash-stable coalition structure always exists in the more general class of "subset-neutral hedonic games". 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. 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. 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 stable outcome. In many cases, this problem turns out to be computationally intractable. One exception is  hedonic games with common ranking property where a core coalition structure always exists, and it can be found in polynomial time. However, it is still NP-hard to find a Pareto optimal or socially optimal outcome. 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 formula_95 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, 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. 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 formula_96 of iterations, where formula_97 is the number of the robots and formula_98 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.