Hedonic game

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.

[4] In the case that the preference relations are represented by utility functions, one can also consider coalition structures that maximize social welfare.

Since the preference relations in a hedonic game are defined over the collection of all

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.

Not every hedonic game admits a coalition structure that is stable.

, where both players are alone, the stalker 2 deviates and joins 1; in the coalition structure

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

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

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

[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] 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

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

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

Here, the implication of SPAO is robots' social inhibition (i.e., reluctancy of being together), which normally arises when their cooperation is subadditive.

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.
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. [ 29 ] 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.