Simple Causes of Complexity in Hedonic Games

1 Introduction

Hedonic games [Dr`eze and Greenberg, 1980; Banerjee et al., 2001; Bogomolnaia and Jackson, 2002] provide an elegant and versatile model of coalition formation among strategic agents. In such games, each agent has preferences over coalitions (subsets of players) that she can be a part of, and an outcome of the game is a partition of agents into coalitions. Clearly, the quality of an outcome depends on how well it reflects the agents' preferences. In particular, it is desirable to have outcomes that are stable, i.e., do not offer the agents an opportunity to profitably deviate. Many different concepts of stability have been proposed in the hedonic games literature (see Section 2 for a brief summary, and [Aziz and Savani, 2015] for an in-depth discussion), and for each of them a natural computational question is whether a given game admits an outcome that is stable in that sense.

The complexity of this question depends on how the game is represented: while every hedonic game can be described by explicitly listing each agent's preference relation over all coalitions that may contain her, in recent years there has been a considerable amount of research on succinct representation formalisms for hedonic games, i.e., ones where a game description size scales polynomially with the number of agents n. Typically, such formalisms are not universally expressive, but capture important classes of hedonic games. For instance, if the utility that an agent assigns to a coalition is given by the sum/average/minimum/maximum of the utilities she assigns to individual members of that coalition, the entire game can be described by n(n-1) numbers (such games are known as, respectively, additively separable games [Bogomolnaia and Jackson, 2002], fractional hedonic games [Aziz et al., 2014], and games with W- and B-preferences [Cechl´arov´a and Hajdukov´a, 2003; 2004b]). There are also representation formalisms that are universally expressive (and hence exponentially verbose in the worst case), but provide succinct descriptions of hedonic games that have certain structural properties; examples include Individually Rational Coalition Lists [Ballester, 2004] and Hedonic Coalition Nets [Elkind and Wooldridge, 2009]. The complexity of stability-related problems under these and other representations for hedonic games has been investigated by a number of researchers (see [Woeginger, 2013a] for a survey); with a few exceptions, checking whether a game admits a stable outcome turns out to be computationally hard.

In this paper, we unify and extend several known hardness results for this family of problems in order to uncover common causes of complexity of stability-related questions in hedonic games. In their simplest form, our results imply that if in a given representation formalism, agents are able to rank coalitions of size two in any way they wish, and if agents are to some extent averse to the presence of enemies, then the problem of checking whether a game admits a stable outcome is NP-hard. The precise meaning of being averse to enemies depends on the stability concept in question. We also introduce intuitively appealing conditions on how agents rank coalitions of size three, which turn out to entail NP-hardness even if the underlying preferences are strict. Our approach enables us to automatically derive new hardness results for hedonic games: instead of coming up with a hardness reduction, one can simply check whether the representation in question satisfies the relevant conditions on enemy-aversion and coalitions of size two or three. By doing so, we answer several questions that were left open by prior work, and substantially contribute to the understanding of computational complexity of somewhat less explored solution concepts: to the best of our knowledge, we are the first to obtain NP-hardness results for strong Nash stability (SNS), strict strong Nash stability (SSNS), and strong individual stability (SIS).

To provide further evidence of the power of our approach, we also consider several classes of hedonic games whose complexity has not been investigated before, and derive NPhardness results for them using our methodology. Perhaps the most interesting of them is the class of median games, proposed by [Hajdukov´a, 2006], where each agent assigns a utility to every other agent, and her utility for a coalition is the utility she assigns to the median agent in that coalition.

The complexity results implied by our analysis are summarized in Table 1. However, we believe that the sufficient conditions for hardness identified in our work are at least as important as the specific new results we have established. Indeed, these conditions indicate which additional constraints should be placed on a representation formalism to avoid the complexity trap, and may guide researchers towards identifying formalisms that adequately describe their application scenario, yet admit efficient algorithms for finding stable outcomes.

2 Preliminaries

Given a finite set of agents N = {1, . . . , n}, a hedonic game is a pair G= 〈N, (≽i)i∈N〉, where ≽i is a complete and transitive preference relation over Ni = {S ⊆ N : i ∈ S}. We write S ≻i T when S ≽i T, but T ̸≽i S. A class C of hedonic games is any collection of hedonic games. We say that a class C is polynomially representable if there exists a polynomial p(x) and a poly-time algorithm A such that each 〈N,(≽i)i∈N〉 ∈ C can be represented by a binary string of length at most p(|N|), and, given this string, an agent i ∈ N, and a pair of coalitions S, T ∈ Ni, algorithm A can decide whether S ≽i T . For example, additively separable hedonic games mentioned in Section 1 form a polynomially representable class.

An outcome of a hedonic game is a partition π of N into disjoint coalitions. We write π(i) for the coalition of π that contains i. For partitions π and π′ , we write π ≽i π′ to mean π(i) ≽i π′ (i).

We are mainly interested in the stability of a given partition π of N. We will consider seven stability concepts for hedonic games: two that are based on individual deviations, and five that are based on group deviations. The former group comprises Nash stability (NS) and individual stability (IS). A partition π is NS if no player can benefit from moving to another (possibly empty) coalition S in π, i.e., π(i) ≽i S∪{i} for all S ∈ π∪{∅}. Partition π satisfies IS if no player can make such a beneficial move without making an agent in S worse off, i.e., for each S ∈ π∪{∅} it holds that π(i) ≽i S∪{i} or S ≻j S∪{i} for some j ∈ S.

The classic solution concept for group deviations is the core (CR). We say that a non-empty coalition S CR-blocks π if S ≻i π(i) for all i ∈ S; it SCR-blocks π if S ≽i π(i) for all i ∈ S and, moreover, S ≻i π(i) for some i ∈ S. If no coalition CR-blocks π, it is in the core (CR); if no coalition SCR-blocks it, it is in the strict core (SCR).

Karakaya [2011] introduced strong Nash stability (SNS), and Aziz and Brandl [2012] introduced the derived notions of strict strong Nash stability (SSNS) and strong individual stability (SIS). These solution concepts deal with deviations where the deviators do not necessarily form a single coalition. Given two partitions π, π′ , we say that a

coalition H ⊆N can reach π′ from π if for all i, j ̸∈H we have π(i) = π( j) if and only if π′ (i) = π′ ( j). Coalition H SSNSblocks π if it can reach some π′ with π′ ≽i π for all i ∈H and π′ ≻i π for some i ∈H. If H can reach some π′ with π′ ≻i π for all i ∈H then H is said to SNS-block π. If H SNS-blocks π by reaching π′ and, moreover, for each i ∈H and each j ∈ π′ (i) we have π′ ≽j π, then H is said to SIS-block π. A partition π is a-stable (where a ∈ {SSNS, SNS, SIS}) if no coalition a-blocks it. Intuitively, SNS-blocking coalitions allow groups of agents to swap places with each other. For SIS-blocking coalitions, agents joined by a deviator must consent to the changes.

The diagram above shows implication relationships among these concepts. A partition that is SSNS-stable is also stable under every other solution concept considered here. A coalition S ∋ i is individually rational (IR) for i if S ≽i {i}. A partition π is said to be IR if π(i) is IR for all i ∈N.

3 Properties of Preferences

Our hardness results require a given class C of hedonic games to be expressive enough to include hard instances. To this end, agents should have some freedom in how they order small coalitions. Our results apply to formalisms that enable each agent i to express arbitrary preferences over coalitions of the form {i, j}, as well as satisfy a few other constraints. Thus, in a sense, our results are about the hardness of finding stable outcomes in hedonic games obtained by lifting preferences over individual players to preferences over coalitions.

We associate each agent i ∈ N with a complete and transitive order ⩾i over N. We interpret ⩾i as i's preference order over the set of players. We write j >i k if j ⩾i k but not k ⩾i j, and we write j ∼i k if both j ⩾i k and k ⩾i j. We call Fi = { j ̸= i : j ⩾i i} and Ei = { j ̸= i : j <i i} the friends and the enemies of i. In what follows, it will not matter how⩾i orders Ei-only its restriction on Fi will be of interest.

We now describe a series of properties that relate i's preferences ≽i over the coalitions in Ni to her preferences ⩾i over the agents in N. These properties express various ways in which ≽i can be said to extend ⩾i. The numerical examples in brackets aim to illustrate the intuition behind these properties.

Consistent on pairs. For all j,k ∈Fi ∪{i} it holds that {i, j}≽i {i,k} iff j ⩾i k.

Monotone on triangles ('7+6 >7+5'). If j, j′ ,k,k′ ∈ Fi are such that j ⩾i j′ >i k >i k′ , then {i, j,k}≻i {i, j′ ,k′}.

Triangle-appreciating ('7 +5 > 7'). Two almost equally good friends together are preferable to the better friend alone: If j,k,ℓ ∈ Fi are ranked j >i k >i ℓ and they are immediate successors under >i, then {i, j,ℓ}≻i {i, j}.

Only few polynomial-time algorithms for finding stable outcomes in hedonic games are known, mainly confined to matching problems and the (structurally similar) W-hedonic games. Notably these classes of games fail to be triangleappreciating, and in view of our results in Section 4 this is a key reason why they admit easiness results.

The following properties express that agents do not like coalitions that contain too many enemies.

{a-b}-toxic. If |S∩Fi| =a, but |S∩Ei| ⩾b then {i}≽i S.

Strictly {a-b}-toxic. Same as above with {i} ≻i S.

Weakly {a-b}-toxic. Same as above with {i, j} ≻i S for all j ∈ Fi.

Intolerant in triangles. If E ′ i ⊆Ei is non-empty and j,k ∈ Fi are distinct then {i, j,k}≻i {i, j,k}∪E ′ i .

We write '(strictly/weakly) {a1-b1, . . . , am-bm}-toxic' for preferences that are (strictly/weakly) {at -bt }-toxic for t = 1, . . . ,m.

Given a collection (⩾i)i∈N of orderings, we say that a hedonic game 〈N, (≽i)i∈N〉 satisfies one of the properties above if each ≽i satisfies it with respect to ⩾i. We say that the collection is strict if each ⩾i is antisymmetric, so j ̸= k implies j ̸∼i k. The collection is mutual if j ∈Fi if and only if i ∈Fj for all i, j. For a mutual collection of orderings, we may consider the friendship graph with vertex set N, where an (unweighted) edge connects mutual friends. We will use standard terminology of graph theory when talking about hedonic games, and, in particular, speak of cliques, trees, and cycles of agents.

4 Hardness Results

Let C be a polynomially representable class of hedonic games. For every stability concept a defined in Section 2, we will consider the following decision problem associated with C.

a-EXISTENCE FOR C

Instance: Game 〈N, (≽i)i∈N〉 from C in its binary encoding.

Question: Is there an a-stable partition π of N?

To avoid difficulties with binary representations that are very short, we will assume that the binary encoding of 〈N, (≽i)i∈N〉 lists the names of agents in N, and hence contains at least |N| bits. Furthermore, when in the following theorems we assume that C contains various hedonic games 〈N,(≽i)i∈N〉 derived from orderings (⩾i)i∈N, we require that such games (i.e., their binary descriptions) can be constructed in time polynomial in |N|; this property is necessary for our hardness reductions to work in polynomial time and is satisfied by all classes of hedonic games considered in this paper.

Our first result has mild assumptions and applies to a large number of classes C.

Theorem1. CR-EXISTENCE FOR C is NP-hard if for all N and every mutual collection of orderings (⩾i)i∈N in which each agent has at most 3 friends, there is a game 〈N, (≽i)i∈N〉 ∈ C that is consistent on pairs, {0-1}-toxic and weakly {1-1,2-2}- toxic with respect to (⩾i)i∈N.

REMARK I. Under the same set of conditions SIS-EXISTENCE FOR C is also NP-hard; we obtain a hardness result for SNSEXISTENCE FOR C by strengthening weak {1-1}-toxicity to {1-1}-toxicity.

Effectively, Theorem 1 says that if agents are allowed to rank pairs as they wish, and if they do not have to like everyone, then finding a core-stable outcome is hard.

The assumptions are chosen so as to guarantee that a game like the pentagon displayed on the right has empty core. In this game, each agent has exactly two friends, the clockwise successor being preferred to the clockwise predecessor. All

other agents are enemies. It can be checked that if agents' preferences satisfy weak {1-1,2-2}-toxicity then this game has empty core. We use the 9-player version of this game as a gadget in our hardness reductions (see Figure 1).

A similar result holds for solution concepts based on individual deviations.

Theorem 2. NS- and IS-EXISTENCE FOR C are NP-complete if for all N and every strict and mutual collection of orderings (⩾i)i∈N in which each agent has at most 3 friends, there is a game 〈N, (≽i)i∈N〉 ∈ C that is consistent on pairs and strictly {0-1,1-1,2-5}-toxic with respect to (⩾i)i∈N.

In the case of NS-EXISTENCE, the theorem remains true even if the orderings (⩾i)i∈N are strict and bipartite (but not mutual), i.e. the friendship graph is bipartite. Thus, its conclusion also applies to NS-EXISTENCE for the stable marriage problem with unacceptabilities. For the case with ties allowed, this result is also obtained by Aziz [2013].

The reduction establishing Theorem 1 makes essential use of indifferences in the underlying orderings (⩾i)i∈N (this is also the reason why it does not go through for the strict core). To cut off this cause of hardness, we need to make use of conditions on triangles.

Theorem 3. CR- and SCR-EXISTENCE FOR C are NP-hard if for all N and every collection of strict and mutual orderings (⩾i)i∈N in which each agent has at most 4 friends, there is a game 〈N,(≽i)i∈N〉 ∈ C that is consistent on pairs, triangleappreciating, monotone on triangles, {0-1}-toxic, weakly {1-1,2-2,3-3}-toxic, and intolerant in triangles with respect to (⩾i)i∈N.

REMARK II. The same result holds for SIS-EXISTENCE FOR C. It applies to SNS-EXISTENCE FOR C if we add {1-1}-toxicity and weak {2-1}-toxicity. It applies to SSNS-EXISTENCE FOR C if we add strict {0-1, 1-1}-toxicity and weak {2-1}-toxicity.

5 The Reductions

The proofs of our results are by reduction from a restricted version of 3SAT. The reduction behind Theorem 1 is inspired by an argument of Ronn [1990] showing that STABLEROOMMATES with ties is NP-complete. Theorem 3 introduces triangles into this reduction to allow strict preferences.

We sketch the proof of Theorem 1 but omit proofs of the other claims due to space constraints. The omitted arguments are similar to the one given, but more complicated due to SNS-like stability concepts imposing little structure. Full proofs are given in an extended version of this paper, available on arXiv.org [Peters and Elkind, 2015].

PROOF OF THEOREM 1 (SKETCH). We reduce from (3,B2)- SAT, which is 3SAT restricted to formulas in which each clause contains exactly 3 literals, and each variable occurs exactly twice positively and twice negatively [Berman et al., 2003].

Given an instance formula ϕ with variable set X and clause set C, we construct the following agent set N:

The four occurrences (two positive ones and two negative ones) of a variable x ∈ X are called x1,x2,x1,x2. respectively. For a clause c = ℓ1 ∨ℓ2 ∨ℓ3, we write c(ℓ1) := c1, c(ℓ2) := c4, c(ℓ3) = c7. Construct orderings (⩾i)i∈N as follows:

For each agent i we have only listed i's friends Fi, each friend being strictly better than i. Any agent not mentioned in i's list is an enemy, i.e., an element of Ei. Figure 1(a) illustrates the orderings (⩾i)i∈N. Note that no agent has more than 3 friends, and that these orderings are mutual.

By the assumptions of Theorem 1, there is a poly-time many-one reduction that takes a formula ϕ as input and outputs the binary encoding of a game G = 〈N, (≽i)i∈N〉 ∈ C that is consistent on pairs, {0-1}-toxic and weakly {1-1,2-2,3-3}- toxic with respect to the (⩾i)i∈N given above. We show that ϕ is satisfiable if and only if G admits a CR-stable partition.

Let A be a satisfying assignment of ϕ. Take the partition

In the last line we partition clause players that are not matched to true variables into pairs and singletons in some stable way as in Figure 1(a), see full proof for details.

We show that π is CR-stable in G. Since π is IR, no singleton blocks. By consistency on pairs, it can be checked that no coalition of size 2 blocks. Now let S be a coalition with |S| ⩾ 3. Consider the friendship graph on N with friends connected by an edge. This graph has girth 6 and does not contain a cubic subgraph. If S contained an isolated agent or a leaf (a member with at most 1 friend in S), then S is not blocking by {0-1}- toxicity and weak {1-1}-toxicity. So S contains a cycle and thus |S| ⩾ 6. Since S is not cubic, there is an agent, matched in π, who has 2 friends in S and so by weak {2-2}-toxicity is worse off in S, so S does not block. Hence there are no blocking coalitions and π is in the core.

Let π be a CR-stable partition of G. We sketch an argument giving a satisfying assignment of ϕ. Because the players {c1, . . . ,c9} of a clause are unstable on their own (toxicity limits coalitions within them to size 2, no agent wants to be clockwise last in a coalition, and the number of members is odd), stability of π implies that for each clause one of its players must be in a coalition with the literal connected to it. Define a propositional assignment A so that all literals in a coalition with a c-player are set true, and set other variables arbitrarily. This assignment is well-defined. Indeed, suppose variable x is to be set both true and false. Then WLOG either both x1 and x1 or both x1 and x2 are matched with their c1. Either {xa,x1} or {x1,x2} will then end up blocking, a contradiction. Clearly, A satisfies ϕ.

6 Applications

Our NP-hardness results have implications for many wellknown classes of hedonic games. In this section we briefly describe some of these (see [Aziz and Savani, 2015] for details) and check which of our conditions they satisfy. In this way, we recover-and sometimes strengthen-a number of known hardness results for these games. We also introduce five new classes of games, and show how our framework allows us to deduce hardness results for them with ease.

The extended version [Peters and Elkind, 2015] of this paper gives further details on constructions outlined here.

Individually Rational Coalition Lists (IRCL). Ballester [2004] proposes to represent a hedonic game by listing the agent preferences ≽i explicitly from best to worst, but cutting the list off after the entry {i}. This representation is complete, but not always succinct. Ballester proves that for a ∈ {CR,NS,IS} deciding a-EXISTENCE is NP-complete under this representation. We deduce these results by considering IRCLs that list the pairs {i, j} for j ∈Fi. Since Theorems 1 and 2 apply even if each agent has only 3 friends, we therefore have a hardness result for a ∈ {SNS,SIS,CR,NS,IS} even if the list of each agent includes at most 3 entries, each of which is a pair. A similar result is shown by Deineko andWoeginger [2013]. They prove that CR-EXISTENCE FOR IRCL is hard even for lists of length 2, with entries being coalitions of size 3. Theorem 3 applies if we allow lists up to length 9, which can encode a triangle-appreciating game where agents have up to 4 friends.

Hedonic Coalition Nets. Elkind and Wooldridge [2009] study a rule-based representation for hedonic games in which agents' preferences are described by weighted boolean formulas. It can be shown that polynomial size nets are sufficient to describe, for any collection of orderings (⩾i)i∈N, a game satisfying all our conditions, implying hardness of a-EXISTENCE for all a considered in this work. This is perhaps not surprising: while Elkind and Wooldridge only establish the hardness of CR-EXISTENCE in their work, they show that one can compile an IRCL representation into a hedonic coalition net representation with at most polynomial overhead. Because our hardness results hold even if each player is only allowed 3 or 4 friends, we can say in addition that a-EXISTENCE for hedonic coalition nets remains hard even if we restrict each player's preferences to be described by at most 4 or 5 formulas, and even if the weights of these formulas are given in unary.

Stable Roommates. The reduction behind Theorem 1 is a modified version of Ronn's construction showing that CREXISTENCE FOR SRT, the stable roommate problem with ties, is NP-complete [Ronn, 1990]. It is thus no surprise that the class of stable roommate problems, considered as hedonic games in which sets with 3 or more members are unacceptable, fulfills the conditions of Theorem 1 (but note that this formulation corresponds to SRTI, not SRT). Indeed, CR-EXISTENCE FOR SRTI remains hard even if the preference list of each agent has length at most 3, and by Theorem 2 this is also true of NS- and IS-EXISTENCE. Now, consider a generalization of STABLE-ROOMMATES where rooms have capacity 1, 2, or 3, and rooms with capacity 3 are generally preferred because they are cheaper per person. Then it can be checked that the conditions of Theorems 2 and 3 are satisfied, giving hardness of a-EXISTENCE for all a for this model.

Stable Marriages. A version of Theorem 2 implies that NSEXISTENCE FOR SMI, the stable marriage problem with incomplete lists, is NP-complete. This extends the NPcompleteness result for SMTI obtained by [Aziz, 2013].

Aziz also notes that it is possible to embed SMTI into other classes C of hedonic games, and thus to deduce hardness of NS-EXISTENCE FOR C; this observation provides an (alternative) method of deriving hardness results for several classes of hedonic games.

W-preferences. Cechl´arov´a and Hajdukov´a [2004b] consider hedonic games where each agent first ranks all other agents and then compares coalitions based on their worst member under this ranking. Clearly, the game so obtained is consistent on pairs and strictly {k-1}-toxic for all k. It follows that (with ties allowed) CR-EXISTENCE is NP-hard by Theorem 1 (a result first obtained by [Cechl´arov´a and Hajdukov´a, 2004b]), and that NS- and IS-EXISTENCE are NP-complete by Theorem 2, first shown by Aziz et al. [2012]. NS- and IS-EXISTENCE are hard even if preferences are strict; the latter result was previously unknown.

WB-preferences. Noting that agents inW-hedonic games are extremely pessimistic, Cechl´arov´a and Hajdukov´a [2004a] propose a compromise: Agents still rank coalitions according to their worst member, but break ties in favor of the coalition with better best member. Again the game obtained is consistent on pairs and strictly {k-1}-toxic for all k, so CR-, NS-, and IS-EXISTENCE are hard.

W- and B-hedonic games. In these two classes of games [Aziz et al., 2012; 2013], agents rank coalitions according to their worst or best member, but coalitions containing an enemy are not individually rational. As for W-preferences, we see that CR-, NS-, and IS-EXISTENCE are hard.

In all of the following classes of games, agents first assign cardinal utilities vi( j) ∈ R to all agents in N = {1, . . . , n}, and then lift these utilities to coalitions (e.g., by computing the sum or average of the utilities of coalition members).

The following method of constructing integer-valued functions vi : N →R from orderings (⩾i)i∈N will be used repeatedly: given x,y ∈Z, we set vi(i) =0, vi( j) = x for j ∈Ei and let y ⩽ vi( j) ⩽ y+n for j ∈ Fi so that for each j,k ∈ Fi we have vi( j) ⩾ vi(k) iff j ⩾i k (this is accomplished by assigning utility y+k+1 to friends at the k-th 'preference level'). We refer to such utilities as Jx,yK-utilities.

Additively Separable Games (ASGs). In these games, preferences are given by S ≽i T iff �j∈S vi( j) ⩾�j∈T vi( j). This class of games satisfies all our theorems, so a-EXISTENCE is hard for all a we consider. Indeed, given N = {1, . . . , n} and (⩾i)i∈N, we consider the ASG with J-(n 2+2n), 4K-utilities. Then a coalition containing an enemy of i is not individually rational for i, so this game is strictly {k-1}-toxic for all k, and it is obviously consistent on pairs, triangle-appreciating and monotone on triangles. a-EXISTENCE remains hard even if players are allowed at most 3 or 4 friends (depending on a), so for ASGs, it remains hard even if vi( j) is positive for at most 3 or 4 agents j. This improves on the reduction in [Sung and Dimitrov, 2010], where agents have up to 11 friends.

Fractional Hedonic Games (FHGs). This class of games was recently proposed by Aziz et al. [2014]. Preferences are given by S ≽i T iff 1/|S|�j∈S vi( j) ⩾ 1/|T|�j∈T vi( j). Brandl et al. [2015] have shown hardness of CR-, NS-, and IS-EXISTENCE. We recover these results and complement them by showing hardness of SSNS-, SNS-, SIS- and SCR-EXISTENCE; all these results hold even if the underlying preferences are strict. FHGs with J-(n 2+5n), 5K-utilities satisfy all of our properties; choosing y = 5 ensures triangleappreciation.

Social FHGs. An FHG is social if agents' utilities for each other are non-negative. Theorem 3 applies to the class of social FHGs. Indeed, given (⩾i)i∈N we can construct a social FHG with J0,7nK-utilities. Toxicity follows from vi( j) ⩾ 7n for j ∈ Fi, and other properties can be checked as for FHGs. To ensure that our framework applies to social FHGs, we carefully crafted our constructions to only require weak toxicity whenever possible.

The next five classes of hedonic games are based on fairly intuitive ways of deriving utilities for coalitions from utilities for individual players; however, to the best of our knowledge we are the first to consider the computational complexity of stability-related probems for these games (median games have been suggested by [Hajdukov´a, 2006] as an interesting topic; the other four classes appear to be entirely new).

Median Games. Agents evaluate coalitions according to their median value, which in odd-size coalitions is the middle element, and in even-size coalitions is the mean of the middle two elements. Median games with J0,5K-utilities satisfy Theorem 3. Notice that in this construction vi( j) are nonnegative, so hardness holds even for 'social median games' with non-negative underlying utilities. There are various other ways of defining median games. In particular, we can use a purely ordinal version by taking the worse of the middle two players in even-sized coalitions, satisfying Theorem 1;

if agents take either the ordinal or cardinal median of the coalition S \ {i} then both Theorems 1 and 2 apply.

Geometric Mean Games. In these games agents evaluate coalitions according to the geometric mean |S|√�vi( j) of member utilities. We obtain the same hardness results as for FHGs by taking logs.

Nash Product Games. This is the class of games that are 'multiplicatively separable'; agents evaluate coalitions according to �j∈S vi( j). As far as hardness is concerned these games behave identically to additively separable games, again by taking logs.

Midrange ( 1 2 B+ 1 2 W). In this case, agents evaluate a coalition by averaging the maximum and minimum utility in it. With J-3n,1K-utilities, these games are strictly {k-1}-toxic for all k and consistent on pairs, so Theorems 1 and 2 apply.

r-Approval. Starting with cardinal utilities, sum the (up to) r highest elements of a coalition. If r ⩾ 3, then games with J-6rn,4K-utilities satisfy the conditions of Theorems 1 and 2. If r ⩾ 4, they satisfy the conditions of Theorem 3.

7 Conclusions

We have developed a framework that enables us to prove NP-hardness of a-EXISTENCE FOR C for many choices of a and C. Our results show that problems in this family tend to be hard even for representation formalisms with very limited expressivity, and, moreover, are unlikely to admit an efficient parametrized algorithm for many natural choices of parameter (such as length and coalition size in the IRCL representation or number of formulas per agent in the hedonic coalition nets representation). However, they also indicate which features of hedonic games may lead to tractability of stability-related problems. In particular, restricting the number of different 'preference intensities' (e.g., the range of vi( j) in ASGs, FHGs, and median games) rules out consistency on pairs, so one may hope for easiness results when this number is small.

While we focused on the problem of checking whether a stable partition exists, another important stability-related problem is checking whether a specific partition is stable. This problem is in P for IS and NS for all classes of hedonic games considered here, simply because the number of possible deviations is polynomially bounded; however, for notions of stability that are based on group deviations it is often coNPcomplete. It would be interesting to extend our framework to handle this problem as well.

Since verifying stability is often hard, a-EXISTENCE FOR C is usually not known to be in NP for stability notions based on group deviations. Thus most of our hardness results do not have a tight complexity upper bound. For all representation formalisms we consider, these problems are in S p 2 , and CREXISTENCE FOR ASGS is known to be complete for this complexity class [Woeginger, 2013b]. A natural open question is whether our framework can be extended from NP-hardness proofs to S p 2 -hardness proofs.

Acknowledgements

We thank the anonymous reviewers from IJCAI and CoopMAS for their helpful comments and pointers to the literature.