# finding_and_recognizing_popular_coalition_structures__12ca20e6.pdf Journal of Artificial Intelligence Research 74 (2022) 569-626 Submitted 11/2021; published 06/2022 Finding and Recognizing Popular Coalition Structures Felix Brandt brandtf@in.tum.de Martin Bullinger bullinge@in.tum.de Technical University of Munich, Boltzmannstr 3, 85748 Munich, Germany An important aspect of multi-agent systems concerns the formation of coalitions that are stable or optimal in some well-defined way. The notion of popularity has recently received a lot of attention in this context. A partition is popular if there is no other partition in which more agents are better off than worse off. In this paper, we study popularity, strong popularity, and mixed popularity (which is particularly attractive because existence is guaranteed by the Minimax Theorem) in a variety of coalition formation settings. Extending previous work on marriage games, we show that mixed popular partitions in roommate games can be found efficiently via linear programming and a separation oracle. This approach is quite universal, leading to efficient algorithms for verifying whether a given partition is popular and for finding strongly popular partitions (resolving an open problem). By contrast, we prove that both problems become computationally intractable when moving from coalitions of size 2 to coalitions of size 3, even when preferences are strict and globally ranked. Moreover, we show that finding popular, strongly popular, and mixed popular partitions in symmetric additively separable hedonic games and symmetric fractional hedonic games is NP-hard. Together, these results indicate strong boundaries to the tractability of popularity in both ordinal and cardinal models of hedonic games. 1. Introduction Coalitions and coalition formation have been a central concern of game theory, ever since the publication of von Neumann and Morgenstern s Theory of Games and Economic Behavior in 1944. The traditional models of coalitional game theory, in particular TU (transferable utility) and NTU (non-transferable utility) coalitional games, involve a formal specification of what each group of agents can achieve on their own. Dr eze and Greenberg (1980) noted that in many situations this is not feasible, possible, or even relevant to the coalition formation process, as, e.g., in the formation of social clubs, teams, or societies. Instead, in coalition formation games, the agents preferences are defined directly over the coalition structures, i.e., partitions of the agents in disjoint coalitions. Formally, coalition formation can thus be considered as a special case of the general social choice setting, where the agents entertain preferences over a special type of alternatives, namely coalition partitions of themselves, from which one or more need to be selected. In most situations it is natural to assume that an agent s appreciation of a partition only depends on the coalition he is a member of and not on how the remaining agents are grouped. Popularized by Bogomolnaia and Jackson (2002), much of the work on coalition formation now concentrates on these so-called hedonic games. The main focus in hedonic games has been on finding and recognizing partitions that satisfy various notions of stability such as Nash stability, individual stability, or core 2022 AI Access Foundation. All rights reserved. Brandt & Bullinger stability or optimality such as Pareto optimality, utilitarian welfare maximality, or egalitarian welfare maximality (see Aziz & Savani, 2016, for an overview). In this paper, we focus on the notion of popularity (G ardenfors, 1975), which has the flavor of both stability and optimality. A partition is popular if there is no other partition that is preferred by a majority of the agents. Moreover, a partition is strongly popular if it is preferred to every other partition by some majority of agents. Popularity thus corresponds to the notion of weak and strong Condorcet winners in social choice theory, i.e., candidates that are at least as good as any other candidate in pairwise majority comparisons. Just like stability notions, popularity is based on the idea that a subset of agents breaks off in order to increase their well-being. However, since the new partition has to make at least as many agents better off than worse off, popularity also has the flavor of optimality. According to the standard reference Algorithmics of Matching Under Preferences, popular matchings [. . . ] have been an exciting area of research in the last few years (Manlove, 2013, p. 333). A recent survey on popular matchings is provided by Cseh (2017). In contrast to Pareto optimal partitions, popular partitions are not guaranteed to exist. We therefore also consider mixed popular partitions, as proposed by Kavitha, Mestre, and Nasre (2011) and whose existence follows from the Minimax Theorem. A mixed popular partition is a probability distribution over partitions p such that there is no other mixed partition q such that the expected number of agents who prefer the partition returned by p to q is at least as large as the other way round. Mixed popular partitions are a special case of maximal lotteries, a randomized voting rule that has recently gathered increased attention in social choice theory (Fishburn, 1984; Brandl, Brandt, & Seedig, 2016; Brandl & Brandt, 2020; Brandl, Brandt, & Stricker, 2022). We study the computational complexity of popular, strongly popular, and mixed popular partitions in a variety of hedonic coalition formation settings including additively separable hedonic games, fractional hedonic games as well as hedonic games where the coalition size is bounded. The latter includes flatmate games (which only allow coalitions of up to three agents) and roommate games (which only allow coalitions of up to two agents). Our main findings can also be found in Tables 1 and 2 in the conclusion and are summarized as follows. Generalizing earlier results by Kavitha et al. (2011), we show how mixed popular partitions in roommate games can be computed in polynomial time via linear programming and a separation oracle on a subpolytope of the matching polytope for non-bipartite graphs.1 This stands in contrast to a recent result showing that computing popular partitions in roommate games is NP-hard (Faenza, Kavitha, Power, & Zhang, 2019; Gupta, Misra, Saurabh, & Zehavi, 2019). As corollaries we obtain that verifying popular partitions (Bir o, Irving, & Manlove, 2010), finding Pareto optimal partitions (Aziz, Brandt, & Harrenstein, 2013a), and finding strongly popular partitions can all be done in polynomial time in roommate games, even when preferences admit ties. The latter statement resolves an acknowledged open problem.2 1. The results by Kavitha et al. (2011) only hold for house allocation and marriage markets and require extra work to be extended to roommate markets. See Section 2 for more details. 2. See, for example, Bir o et al. (2010) and Manlove (2013): A third open problem is the complexity of finding a strongly popular matching (or reporting that none exists), for an instance of RPT [Roommate Finding and Recognizing Popular Coalition Structures We provide the first negative computational results for mixed popular partitions and strongly popular partitions by showing that finding these partitions in flatmate games is NP-hard. Moreover, it turns out, that verifying whether a given partition is popular, strongly popular, or mixed popular in flatmate games is co NP-complete. All of these results hold for strict and globally ranked preferences, where coalitions appear in the same order in each individual preference ranking. This is interesting insofar as finding popular partitions in roommate games becomes tractable under the same restrictions. We prove that computing popular, strongly popular, and mixed popular partitions is NP-hard in symmetric additively separable hedonic games and symmetric fractional hedonic games. Furthermore, we show co NP-completeness of all corresponding verification problems. Many of our hardness reductions follow a general scheme that might be of broader interest beyond the scope of popularity. Specifically, we merely embed the combinatorial structure of an NP-hard problem (in our case the incidence structure of a covering instance) into the leaves of an object similar to a binary tree. Within this tree, we can propagate all relevant information for the property under consideration (e.g., popularity) to the root agent of the tree, which then acts as a decision taker in our reduction. Hence, checking exponentially many partitions relevant to popularity reduces to checking one specific agent. 2. Related Work G ardenfors (1975) first proposed the notions of popularity and strong popularity in the context of marriage games. He showed that popular matchings (or majority assignments in his terminology) need not exist when preferences are weak, but that existence is guaranteed for strict preferences because every stable matching is popular. As a consequence, the well-known Gale-Shapley algorithm efficiently identifies popular matchings in marriage games with strict preferences. Kavitha and Nasre (2009), Huang and Kavitha (2011), and Kavitha (2014) provide efficient algorithms for computing popular matchings that satisfy additional properties such as rank maximality or maximum cardinality. For weak preferences, computing popular matchings is NP-hard, even when all agents belonging to one side have strict preferences (Bir o et al., 2010; Cseh, Huang, & Kavitha, 2015). In the more restricted setting of house allocation (henceforth housing games), Abraham, Irving, Kavitha, and Mehlhorn (2007) proposed efficient algorithms for finding popular allocations of maximum cardinality for both weak and strict preferences. Mahdian (2006) proved an interesting threshold for the existence of popular allocations: if there are n agents and the number of houses exceeds αn with α 1.42, then the probability that there is a popular allocation converges to 1 as n goes to infinity. For roommate games with weak preferences, NP-hardness of computing popular matchings follows from the above-mentioned hardness results for marriage games. It was recently Problem with Ties] (Bir o et al., 2010, p. 107); Our last open problem concerns the complexity of the problem of finding a strongly popular matching, or reporting that none exists, given an instance of SRTI [Stable Roommates with Ties and Incomplete lists], which is unknown at the time of writing (Manlove, 2013, p. 380). Brandt & Bullinger shown that this problem is still NP-hard when preferences are strict (Gupta et al., 2019; Faenza et al., 2019; Cseh & Kavitha, 2018). Also, finding a maximum-cardinality popular matching in instances where popular matchings are guaranteed to exist is NP-hard (Brandl & Kavitha, 2018). There are less results on strongly popular matchings. It is known from G ardenfors (1975) that a strongly popular matching has to be a unique popular matching and that every strongly popular matching is stable in roommate and marriage games. Based on these insights, Bir o et al. (2010) showed that strongly popular matchings in roommate games and marriage games with strict preferences can be found efficiently by first computing an arbitrary stable matching and then checking whether it is strongly popular. The case of weak preferences was left open and little progress has been made since then. Kir aly and M esz aros-Karkus (2017) recently gave an algorithm for finding strongly popular matchings in marriage games where preferences are strict, except that agents belonging to one side may be completely indifferent. In housing games, a matching is strongly popular if and only if it is a unique perfect matching. Hence, strongly popular matchings in housing games can be found in polynomial time. All of the above mentioned results on strong popularity, including the open problem, follow from our Corollary 3. Mixed popular matchings were introduced by Kavitha et al. (2011) who also showed how to compute a fractional popular matching in housing games and marriage games, which can then be translated into a mixed popular matching via a Birkhoff-von Neumann decomposition. This is possible in bipartite settings because every fractional matching is implementable as a probability distribution over deterministic matchings. When moving from marriage markets to roommate markets, this does not hold anymore. For example, a matching involving three agents where every pair of agents is matched with probability 1/2 is not implementable. Huang and Kavitha (2017) have shown that in marriage games with strict preferences, the popular matching polytope is half-integral and that half-integral mixed popular matchings can be computed in polynomial time. No such matchings are guaranteed to exist when preferences are weak. They also apply the same techniques to roommate games in order to compute an optimal half-integral solution over the bipartite matching polytope in the case of strict preferences. However, the resulting solutions may again fail to be implementable. Apart from that, their methods heavily rely on computing stable matchings, which may be intractable when preferences are weak. By contrast, our results in Section 4.2.1 are based on the matching polytope for non-bipartite graphs via odd-set constraints and allow both to deal with ties and to efficiently compute a solution that is implementable using LP methods (Proposition 5).3 The axiomatic properties of mixed popular matchings such as efficiency and strategyproofness were investigated by Aziz, Brandt, and Stursberg (2013c), Brandt, Hofbauer, and Suderland (2017), and Brandl, Brandt, and Hofbauer (2017). To the best of our knowledge, popularity, strong popularity, and mixed popularity have not been studied for coalition formation settings that go beyond coalitions of size 2 except for 3. The journal version of the paper by Huang and Kavitha (2017), which appeared after the conference version of our paper, also independently considers the non-bipartite matching polytope and briefly outlines how to compute mixed popular matchings (Huang & Kavitha, 2021). However, some important subtleties such as how to retain deterministic matchings from the fractional solution (our Proposition 5) are not considered. Finding and Recognizing Popular Coalition Structures a theorem by Aziz, Brandt, and Seedig (2013b, Th. 15) who claimed that checking whether a partition is popular in ASHGs is NP-hard and that verifying whether a partition is popular is co NP-complete. However, the proof of the first statement is incorrect.4 We substantially modified the reduction to prove a stronger statement and independently proved a stronger statement for the verification problem. 3. Preliminaries Let N be a finite set of agents. A coalition is a non-empty subset of N. By Ni we denote the set of coalitions agent i belongs to, i.e., Ni = {S N : i S}. A coalition structure, or simply a partition, is a partition π of the agents N into coalitions, where π(i) is the coalition agent i belongs to. A mixed partition is a set p = {(π1, p1), . . . , (πk, pk)}, where πi s a partition for every i {1, . . . , k}, and (p1, . . . , pk) represents a probability distribution. A mixed partition is interpreted as a randomization over partitions. A hedonic game is a pair (N, ), where = ( i)i N is a preference profile specifying the preferences of each agent i as a complete and transitive preference relation i over Ni. If i is also anti-symmetric we say that i s preferences are strict. Otherwise, we say that preferences are weak. We denote by S i T if S i T but not T i S i.e., i strictly prefers S to T and by S i T if both S i T and T i S i.e., i is indifferent between S and T. In hedonic games, agents are only concerned about their own coalition. Accordingly, preferences over coalitions naturally extend to preferences over partitions as follows: π i π if and only if π(i) i π (i). Sometimes, we consider strict preferences, which are obtained from weak preferences by breaking ties arbitrarily. To express such preferences succinctly, given a set X of alternatives, we denote by X an arbitrary, but fixed strict preference order of the alternatives in X. For example, a {b, c} d could be replaced by a b c d. For simplicity, one can assume that ties are broken lexicographically. When referring to index sets, such as sets of players, we use the shorthand [k] for {1, . . . , k} and [k, l] for {k, . . . , l}. Two basic properties of partitions are Pareto optimality and individual rationality. Given a hedonic game (N, ), a partition π is Pareto optimal if there is no partition π such that π j π for all agents j and π i π for at least one agent i. A coalition S Ni is individually rational for agent i if she prefers the coalition to staying alone, i.e., C i {i}. A Partition π is individually rational if π(i) i {i} for all i N. The rationale behind individual rationality is that agents cannot be forced into a coalition. Individual rationality is also the crucial ingredient of a succinct representation of hedonic games where only the preferences over individually rational coalitions are considered (Ballester, 2004). A hedonic game (N, ) is represented by Individually Rational Lists of Coalitions (IRLC) via the game (N, ) where is a preference profile such that i is the restriction of i to individually rational coalitions in Ni. In this case, (N, ) is called a completion of (N, ). This representation of games is useful to obtain meaningful hardness results because the size of the naive representation of a hedonic game is exponential in the 4. The reduction fails because for a Yes-instance of Exact 3-Cover, the partition π claimed to be popular for the ASHG it maps to is not popular: the partition π = {{ys, zs 1, zs 2}: s S} {{br 1, ar 2}: r R} {{br 2, ar 1, ar 3}: r R} is more popular. Brandt & Bullinger number of agents while the IRLC representation may only require polynomial space if the number of individually rational coalitions is small enough. In order to define popularity and strong popularity, let N(π, π ) be the set of agents who prefer π over π , i.e., N(π, π ) = {i N : π(i) i π (i)}, where π, π are two partitions of N. For any subset M N of agents and partitions π, π of N, ϕM(π, π ) = |N(π, π ) M| |N(π , π) M| is called the popularity margin on M with respect to π and π . If M = {i} is a singleton set, we use the shorthand notation ϕi instead of ϕ{i}. On top of that, we define the popularity margin of π and π as ϕ(π, π ) = ϕN(π, π ). Then, π is called more popular than π if ϕ(π, π ) > 0. Furthermore, π is called popular if, for all partitions π , ϕ(π, π ) 0, i.e., no partition is more popular than π. Also, π is called strongly popular if, for all partitions π = π, ϕ(π, π ) > 0, i.e., π is more popular than every other partition. Note that there can be at most one strongly popular partition in any hedonic game. For a hedonic game (N, ) in IRLC representation, a partition π is called popular if it is popular in the completion of (N, ) where, for each agent, all coalitions that are not individually rational are gathered in a single indifference class that is less preferred than the singleton coalition. This definition of popularity generalizes the definition of popularity that is used for marriage games by Kavitha et al. (2011), and adds the appropriate perspective on individual rationality.5 Note that a popular partition need not be individually rational. Many hedonic games do not admit a popular partition. However, existence can be guaranteed by introducing randomization via mixed partitions, i.e., probability distributions over partitions. Let therefore two mixed partitions p = {(π1, p1), . . . , (πk, pk)} and q = {(σ1, q1), . . . , (σl, ql)} be given, where (p1, . . . , pk), (q1, . . . .ql) are probability distributions. We define the popularity margin of p and q as their expected popularity margin, i.e., j=1 piqjϕ(πi, σj). Clearly, the definition of popularity carries over to the extension of ϕ. As first observed by Kavitha et al. (2011), mixed popular partitions always exist, because they can be interpreted as maximin strategies of a symmetric zero-sum game (see also Fishburn, 1984; Aziz et al., 2013c). Proposition 1. Every hedonic game admits a mixed popular partition. Proof. Every hedonic game can be viewed as a finite two-player symmetric zero-sum game where the rows and columns of the two players are indexed by all possible partitions π1, . . . , πB|N| and the entry at position (i, j) of the game matrix is ϕ(πi, πj). There, B|N| denotes the Bell number. By the Minimax Theorem (von Neumann, 1928), the value of this game is 0 and therefore, any maximin strategy, whose existence is guaranteed, is popular. 5. The IRLC representation ignores preferences over coalitions that are not individually rational. However, in contrast to core stability or Nash stability, these preferences can affect whether a partition is popular or not. In order to circumvent this problem, one could strengthen the definition of popularity by requiring that a coalition needs to be popular for all extensions of the IRLC represented preferences. All our results also hold for this notion, because we construct individually rational partitions for which the two notions of popularity coincide. Finding and Recognizing Popular Coalition Structures Before stating and proving our results, we illustrate the most important concepts by means of an example. Example 1. Consider a hedonic game (N, ) with N = {a, b, c, d} where preferences are given in IRLC representation: N a {a, b} a {a, c} a {a, d} a {a} N b {b, c} b {b, a} b {b, d} b {b} {c, a} c {c, b} c {c, d} c N c {c} {d, a} d {d, b} d {d, c} d N d {d} Then, the Pareto optimal partitions (which are the only ones relevant for popularity) are π0 = {N}, π1 = {{a, b}, {c, d}}, π2 = {{a, c}, {b, d}}, and π3 = {{a, d}, {b, c}}. Their popularity margins are depicted right of the preferences, where a dashed line denotes indifference with respect to popularity. In particular, π0 is the only (deterministic) popular partition and there is no strongly popular partition. Further, the mixed partition p = {(π1, 1/3), (π2, 1/3), (π3, 1/3)} is mixed popular. It holds that ϕ(p, π0) = ϕ(p, π1) = ϕ(p, π2) = ϕ(p, π3) = 0. Our results are divided into three subsections. We first show some basic properties and relationships between the different notions of popularity. Then, we analyze popularity in ordinal hedonic games (such as flatmate and roommate games) and cardinal hedonic games (such as additively separable and fractional hedonic games), respectively. 4.1 Basic Relationships Clearly, a strongly popular partition is also popular and a popular partition, interpreted as a probability distribution with singleton support, is mixed popular. Furthermore, every coalition structure in the support of a mixed popular partition is Pareto optimal. This already follows from a more general statement by Fishburn (1984, Prop. 3). We give a simple proof for completeness. Proposition 2. Let p = {(π1, p1), . . . , (πk, pk)} be a mixed popular partition. Then, for every i [k] with pi > 0, πi is Pareto optimal. Proof. Let p = {(π1, p1), . . . , (πk, pk)} be a mixed popular partition and fix i [k] such that pi > 0. Assume for contradiction that π i is a Pareto improvement over πi. Define p = {(π1, p1), . . . , (πi 1, pi 1), (π i, pi), (πi+1, pi+1), . . . , (πk, pk)}. Note that ϕ(π i, p) = Pk j=1,j =i pjϕ(π i, πj)+piϕ(π i, πi) Pk j=1,j =i pjϕ(πi, πj)+piϕ(π i, πi) > Pk j=1,j =i pjϕ(πi, πj)+ piϕ(πi, πi) = ϕ(πi, p). Then, ϕ(p , p) = Pk j=1,j =i pjϕ(πj, p) + piϕ(π i, p) > Pk j=1,j =i pjϕ(πj, p) + piϕ(πi, p) = ϕ(p, p) = 0. Hence, p is not mixed popular, a contradiction. Brandt & Bullinger We thus have the following relationships between strong popularity (s Pop), popularity (Pop), partitions in the support of any mixed popular partition (supp(m Pop)), and Pareto optimality (PO): s Pop = Pop = supp(m Pop) = PO. The concepts printed in boldface are guaranteed to exist. As a consequence, hardness results for computing Pareto optimal partitions imply hardness of computing mixed popular partitions (though not for popular partitions since they need not exist). Mixed popular partitions also satisfy probabilistic strengthenings of Pareto optimality based on stochastic dominance and pairwise comparisons (Aziz, Brandl, Brandt, & Brill, 2018). The existence problems for popular and strongly popular partitions are naturally contained in the complexity class Σp 2. The verification problems are contained in co NP. The following relationship turns out to be helpful for deducing the complexity of verifying mixed popular partitions from the respective result for popular partitions. Proposition 3. Let a class of hedonic games be given such that the verification problem of popular partitions is co NP-hard. Then, the verification problem of mixed popular partitions is co NP-hard. Proof. Let C be a class of hedonic games and let (G, π) be an instance of the deterministic verification problem, i.e. G C is a hedonic game and π a partition of the agents of G. By linearity of π 7 ϕ(π, π ), π is popular if, and only if, it is mixed popular. Hence, the embedding of the deterministic into the mixed case gives the desired reduction for co NPhardness. Hence, whenever hardness results are obtained for the verification of popularity, they transfer automatically to mixed popularity. Conversely, polynomial-time algorithms for mixed popularity can be used to efficiently verify whether a partition is popular. Also, since partitions have polynomial size (with respect to the number of agents), we can use more popular partitions as polynomial-size certificates to No-instances of the verification problem. This shows membership in co NP in the deterministic case and can also be applied for mixed popularity. Indeed, whenever there exists a more popular mixed coalition, then there exists also a more popular deterministic one. If p is a mixed partition for a game G and p = {(π 1, p 1), . . . , (π k, p k)} is more popular, then 0 < ϕ(p , p) = Pk i=1 p iϕ(π i, p). Consequently, for some i [k], ϕ(π i, p) > 0. Popular partitions are not only Pareto optimal, but it also suffices to compare a partition against Pareto optimal partitions when checking for popularity. This is useful when proving popularity of a given partition, for example in hardness reductions. Proposition 4. A partition π is popular if and only if, for all Pareto optimal partitions π , ϕ(π, π ) 0. In addition, π is strongly popular if and only if, for all Pareto optimal partitions π = π, ϕ(π, π ) > 0. Proof. We show that the respective popularity margin with Pareto optimal partition determine popularity. This follows from the fact that for every two partitions π, ˆπ, and a Pareto optimal Pareto improvement π of ˆπ, it holds that ϕ(π, ˆπ) ϕ(π, π ). If we investigate strong popularity, it can happen that π = π, but in this case ϕ(π, ˆπ) > 0 by Pareto dominance. Finding and Recognizing Popular Coalition Structures 4.2 Ordinal Hedonic Games In this section we investigate hedonic games in IRLC representation. Important subclasses of these games are defined by restricting the size of individually rational coalitions using a global constant. We thus obtain flatmate games as games in which only coalitions of up to three agents are individually rational and roommate games as games in which only coalitions of size 2 are individually rational. More restrictions are obtained by partitioning the set of agents into two groups, say, into males and females, and even further by additionally demanding that one group of agents is completely indifferent, say, by assuming that they are objects such as houses. A marriage game is a roommate game where the agents can be partitioned in two sets such that the only individually rational partitions are formed with agents from the other set. A housing game is a marriage game where all agents belonging to one set of the partition are completely indifferent. In roommate games (and their subclasses), partitions are referred to as matchings. All of these classes permit IRLC representations with size bounded polynomially with respect to the number of the agents. We have the following inclusion relationships.6 Housing Marriage Roommates Flatmates IRLC. Finally we consider a severe preference restriction in coalition formation. A preference profile admits globally ranked preferences if there exists a common (global) ranking of all coalitions in 2N \ { } and each individual preference relation i is the restriction of to Ni. Under globally ranked preferences, the intractability of computing popular matchings in roommates games with strict preferences (Gupta et al., 2019; Faenza et al., 2019; Cseh & Kavitha, 2018) breaks down. In fact, it is known that under these preferences, every roommate game admits a stable matching, which can furthermore be efficiently computed (Abraham, Leravi, Manlove, & O Malley, 2008). Since every stable matching also happens to be popular for strict preferences (see Section 2), this implies that computing popular matchings in roommates games becomes tractable. By contrast, all hardness results for flatmate games that will be shown in Section 4.2.2 hold even when preferences are globally ranked. This confirms the robustness of these results and underlines the crucial difference between settings with coalitions of size 2 and coalitions of size 3. In our reductions, we consider hedonic games in globally ranked IRLC representation that are further restricted. All coalitions C in the reduced instances are either individually rational for all agents in C or for none. Hence, the global ranking of coalitions can be compactly represented by omitting all coalitions C that are ranked below any of the singleton coalitions consisting of one of the members of C. Any such coalition is Pareto dominated and therefore irrelevant for popularity (Proposition 4). When defining global rankings we will often connect rankings over subsets of coalitions with each other. To simplify the exposition, we introduce the notion of the join of two preference relations 1 and 2 over two disjoint sets (of coalitions) C1 and C2, respectively, as the preference relation join( 1, 2) = 1 2 C1 C2 over the set C1 C2. In other words, two sets X, Y C1, C2 are in relation join( 1, 2) if X, Y Ci and X i Y for some i [2], or if X C1 and Y C2. We extend this definition recursively to the 6. Note that the inclusion between housing games and marriage games does not hold for strict preferences. Brandt & Bullinger join of relations 1, . . . , k over pairwise disjoint sets C1, . . . , Ck as join(C1, . . . , Ck) = join(join(C1, . . . , Ck 1), Ck) for k 3. Note that the join operation is not commutative. 4.2.1 Roommate Games We start by investigating mixed popularity in roommate games by an LP-based approach, which will later have important consequences for popular and strongly popular matchings. Kavitha et al. (2011) showed that mixed popular matchings in housing games and marriage games can be found in polynomial time. However, as explained in Section 2, their algorithm cannot directly be applied to roommate games. In this section, we show how to obtain an algorithm for the more general class of roommate games. To introduce our matching notation, we fix a graph G = (N, E) where the vertex set is the set of agents and there is an edge between two vertices if the corresponding coalition of size 2 is individually rational for both agents. For technical reasons, it is useful to restrict attention to the case of perfect matchings, i.e., matchings in which every vertex is matched with some vertex. Similarly to the construction by Kavitha et al. (2011), this can be achieved by introducing worst-case partners wa for every agent a with {a, wa} a {a}. These worst-case partners are not individually rational for all other original agents, and are indifferent among all other agents themselves. They mimic the case when an agent remains unmatched and do not affect the popularity of a partition. In graph-theoretic terms, this is equivalent to adding a loop to every vertex. If some loop is contained in a perfect matching, this means that the agent is matched to herself, or in other words, remains unmatched. We now establish a relationship between mixed matchings and fractional matchings, where the latter are defined as points in the (perfect) matching polytope PMat [0, 1]E, defined as follows (Edmonds, 1965). PMat = {x RE : X e E,v e x(e) = 1 v N, e {{v,w} E : v,w C} x(e) |C| 1 2 C N, |C| odd, x(e) 0 e E} The main constraint is often called odd set constraint and ensures that, for every odd set of agents C, the weight of the fractional matching restricted to these agents is at most (|C| 1)/2, where this quantity is equal to the maximum cardinality that any matching on the set C may have. Given a matching M, denote by χM PMat its incidence vector. We obtain a correspondence of mixed matchings and fractional matchings by mapping a mixed matching p = {(M1, p1), . . . , (Mk, pk)} to the fractional matching xp = Pk i=1 piχMi. Note that xp PMat by convexity. Since we only want to operate on the more concise matching polytope, we need to ensure that we can recover a mixed matching efficiently. The following proposition, which is based on general LP theory, can be seen as an extension of the Birkhoff-von Neumann theorem to non-bipartite graphs. Finding and Recognizing Popular Coalition Structures Proposition 5. Let G = (N, E) be a graph and x PMat a vector in the associated matching polytope. Then, a mixed matching p = {(M1, p1), . . . , (Mk, pk)} such that xp = x can be found in polynomial time. Proof. The separation problem for the matching polytope PMat can be solved in polynomial time, i.e., the class of matching polytopes is solvable. Therefore, given a graph G = (N, E) and a vector x PMat we can find a convex combination of extreme points of PMat that yield x in polynomial time (Gr otschel, Lov asz, & Schrijver, 1981, Th. 3.9). A combinatorial algorithm to address this problem was proposed by Padberg and Wolsey (1984). Since the extreme points of the matching polytope are the incidence vectors of matchings (Edmonds, 1965), this is a mixed matching whose corresponding fractional matching is x. To be able to operate on fractional matchings only, we seek to define popularity of fractional matchings equivalent to popularity of mixed matchings that induce them. Popular fractional matchings can be described as feasible points of a (non-empty) subpolytope of the matching polytope. The separation problem for the subpolytope can be solved efficiently using a modification of Mc Cutchen s algorithm for determining the unpopularity margin of a matching (Mc Cutchen, 2008). To this end, we need to define the popularity margin for fractional matchings. Given x, y PMat, we define their popularity margin as ϕ(x, y) = X i,j NG(a) x(a, i)y(a, j)ϕa(i, j) where NG(a) = {v N : {v, a} E} is the neighborhood of a in G and 1 if i a j 1 if i a j 0 if i a j Imagine that the matchings x and y independently match agent a to agent i and j with probability x(a, i) and y(a, j), respectively. Then, we can interpret the quantity x(a, i)y(a, j)ϕa(i, j) as the probability of agent a being matched to i through x and to j through y times the characteristic function of agent a s binary preference between these two matching partners. Then, P i,j NG(a) x(a, i)y(a, j)ϕa(i, j) is the expected preference of agent a between matchings x and y, and ϕ(x, y) is the expected popularity margin of the preferences of all agents. Next, we relate the popularity margins of both worlds. The proof of the next proposition is identical to the corresponding statement for marriage games by Kavitha et al. (2011). For the sake of self-containment, we state its proof in the appendix. All other missing proofs can also be found in the appendix. Proposition 6. Let p and q be mixed matchings. Then, ϕ(p, q) = ϕ(xp, xq). In particular, p is popular if and only if for all matchings M, ϕ(xp, χM) 0. Brandt & Bullinger As a consequence, mixed popular matchings correspond precisely to the feasible points of the polytope PPop = {x PMat : ϕ(x, χM) 0 for all matchings M}. It remains to find a feasible point of the popularity polytope PPop. By adopting the auxiliary graph in Mc Cutchen s algorithm for non-bipartite graphs, we can find a matching M minimizing ϕ(x, χM) by solving a maximum weight matching problem (Mc Cutchen, 2008). This solves the separation problem for PPop. Proposition 7. The separation problem for PPop can be solved in polynomial time. We are now ready to prove the following theorem. Theorem 1. Mixed popular matchings in roommate games with weak preferences can be found in polynomial time. Proof. By Proposition 7 and by means of the Ellipsoid method (Khachiyan, 1979), we can find a fractional popular matching in polynomial time. This can be translated into a mixed popular matching by leveraging Proposition 5. Theorem 1 has a number of interesting consequences. Since every mixed popular matching is Pareto optimal, we now have an LP-based algorithm to find Pareto optimal matchings for weak preferences as an alternative to combinatorial algorithms like the Preference Refinement Algorithm by Aziz et al. (2013a). Corollary 1. Pareto optimal matchings in roommate games with weak preferences can be found in polynomial time. Bir o et al. (2010) provided a sophisticated algorithm for verifying whether a given matching is popular. An efficient LP-based algorithm for this problem follows from Theorem 1. Corollary 2. It can be verified in polynomial time whether a given matching in a roommate game is popular. Finally, the linear programming approach allows us to resolve the open problem of finding strongly popular matchings when preferences are weak. Corollary 3. Finding a strongly popular matching or deciding that no such matching exists in roommate games with weak preferences can be done in polynomial time. Proof. If a strongly popular matching exists, it is unique. In particular, it is the unique mixed popular matching. Given a (deterministic) matching M, we can check in polynomial time if it is strongly popular. We can apply the reduction of Proposition 7 and check whether the maximum weight matching amongst the matchings different to M on the auxiliary graph has negative weight (in which case the matching M is strongly popular) or not. Note that every matching different to M is contained in at least one (incomplete) graph obtained by deleting an edge from M, while M is not contained in any such graph. Hence, we simply compute a maximum weight matching for every graph obtained by deleting exactly one edge Finding and Recognizing Popular Coalition Structures from M in the auxiliary graph. The maximum weight matching amongst these matchings has the highest weight amongst matchings different from M. The algorithm to compute a strongly popular matching if one exists first computes a fractional popular matching. If it does not correspond to a deterministic matching, there exists no strongly popular matching. Otherwise, it is deterministic and, as described above, we can check if it is strongly popular. If this is the case, we return it. If not, there exists no strongly popular matching. As shown in the previous proof, the verification problem for strongly popular matchings in roommate games can also be solved efficiently. 4.2.2 Flatmate Games It turns out that moving from coalitions of size 2 to size 3 renders all search problems related to popular partitions intractable. For mixed popular partitions, we can leverage the relationship to Pareto optimal partitions. Aziz et al. (2013a, Th. 5) have shown that finding Pareto optimal partitions in flatmate games with weak preferences is NP-hard. Since mixed popular partitions are guaranteed to exist (Proposition 1) and satisfy Pareto optimality (Proposition 2), this immediately implies the NP-hardness of computing mixed popular partitions by means of a Turing reduction.7 Theorem 2. Computing a partition in the support of a mixed popular partition in flatmate games with weak preferences is NP-hard. For strict preferences, the same method does not work. Pareto optimal partitions can always be found efficiently by serial dictatorship. Therefore, we will give direct reductions that yield hardness for strong popularity and mixed popularity in flatmate games with strict preferences. The reduction for popularity is a bit more involved and will be given afterwards. All of these reductions are based on a common type of flatmate games that evolve from instances of the NP-complete problem Exact 3-Cover (Karp, 1972). An instance (R, S) of Exact 3-Cover (X3C) consists of a ground set R together with a set S of 3-element subsets of R. A Yes-instance is an instance such that there exists a subset S S that partitions R. Before presenting the proof, we want to discuss our proof strategy which is very generic and also key to many hardness reductions for cardinal hedonic games in Section 4.3. We want to describe the essential properties satisfied by reduced instances of our reduction. We say that a class of games satisfies property PP (for popularity propagation) if there exists a polynomial-time reduction from X3C that constructs for every instance (R, S) a game (N, ) together with a special agent x N, and a partition π such that for every partition π = π , it holds that 1. ϕ(π , π) 1, 2. if π (x) π(x) = {x}, then ϕ(π , π) 3 or (R, S) is a Yes-instance, 3. for all y N, π (y) y {y}, and 7. Using the same argument, one can transfer further results on Pareto optimality (Aziz et al., 2013a), e.g., for room-roommate games or three-cyclic matching games. Brandt & Bullinger 4. π (x) x C for all C Nx \ {π (x)}. In addition, if (R, S) is a Yes-instance, then there exists a partition π with 5. ϕ(π , π ) = 1, and 6. π (x) = {x}. The first condition guarantees that π is strongly popular and with the second condition, strong popularity is unaffected when adding one or two auxiliary agents that only have an effect on x. The third condition is only needed for the proofs concerning fractional hedonic games with non-negative utility functions, but it also holds for all other classes investigated. It ensures that every agent is part of an individually rational coalition, and in fact prefers her coalition in π over staying alone. The forth condition says that x is in her unique topranked coalition under the partition π . The last two properties ensure that we can obtain a more popular partition by adding auxiliary agents that form a new coalition with x. In this section, we will exemplify a reduction satisfying property PP for flatmate games. We will first describe the reduced flatmate games, then prove the first two items of property PP in Lemma 1. Then, we provide a lemma for global rankedness of the game, and finally give the actual reductions which implicitly construct the partition π from property PP. To this end, consider an instance (R, S) of X3C. Let k = min{k N: 2k |R|} be the smallest power of 2 that is larger than the cardinality of R. We define a flatmate game on vertex set N = Sk j=0 Nj, where Nj = S2j i=1 Ai j consists of 2j sets of agents Ai j. We define the sets of agents as Ai k = {ai k, bi k, ci k} for i [|R|], Ai k = {ai k, bi k, ci k, yi 1, yi 2} for i [|R| + 1, 2k], and Ai j = {ai j, bi j, ci j, αi j, βi j, γi j, δi j} for j [0, k 1], i [2j]. Similar names of agents suggest that these agents are going to play the same role in the reduction. The preferences are designed in a way such that if there exists no 3-partition of R through sets in S, then there exists a unique best partition that assigns more than half of the agents a top-ranked coalition. Otherwise, there exists a partition that puts exactly all the other agents in one of their top coalitions. We order the set R in an arbitrary but fixed way, say R = {r1, . . . , r|R|} and for a better understanding of the proof and the preferences, we label the agents bi k = ri for i [|R|]. If we view the set of agents N as k + 1 levels of agents, then the ground set R of the instance of X3C is identified with some specific agents in the top level k. Preferences of the agents are as follows. Recall that X denotes an arbitrary, but fixed strict preference order of the alternatives in X. We define {yi 1, yi 2} yi 1 {yi 1}, i [|R| + 1, 2k], {bi k, yi 2} yi 2 {yi 1, yi 2} yi 2 {yi 2}, i [|R| + 1, 2k], {ai k, bi k, ci k} ai k {ai k, ai+1 k , δ(i+1)/2 k 1 } ai k {ai k}, i [2k] odd, Finding and Recognizing Popular Coalition Structures {ai k, bi k, ci k} ai k {ai k, ai 1 k , δi/2 k 1} ai k {ai k}, i [2k] even, {ai j, βi j, γi j} ai j {ai j, bi j, ci j} ai j {ai j}, j [0, k 1], i [2j], {{bi k, bv k, bw k }: {ri, rv, rw} S for v, w [|R|]} bi k {ai k, bi k, ci k} bi k {bi k}, i [|R|], {bi k, yi 2} bi k {ai k, bi k, ci k} bi k {bi k}, i [|R| + 1, 2k], {bi j, c2i 1 j+1 , c2i j+1} bi j {ai j, bi j, ci j} bi j {bi j}, j [0, k 1], i [2j], {ai j, bi j, ci j} ci j {ci j, ci+1 j , b(i+1)/2 j 1 } ci j {ci j}, j [k], i [2j] odd, {ai j, bi j, ci j} ci j {ci j, ci 1 j , bi/2 j 1} ci j {ci j}, j [k], i [2j] even, {a1 0, b1 0, c1 0} c1 0 {c1 0}, {αi j, βi j} αi j {αi j, αi+1 j , δ(i+1)/2 j 1 } αi j {αi j}, j [k 1], i [2j] odd, {αi j, βi j} αi j {αi j, αi 1 j , δi/2 j 1} αi j {αi j}, j [k 1], i [2j] even, {α1 0, β1 0} α1 0 {α1 0}, {βi j, γi j, ai j} βi j {βi j, αi j} βi j {βi j}, j [0, k 1], i [2j], {γi j, δi j} γi j {βi j, γi j, ai j} γi j {γi j}, j [0, k 1], i [2j], {δi j, α2i 1 j+1 , α2i j+1} δi j {δi j, γi j} δi j {δi j}, j [0, k 2], i [2j], and {δi k 1, a2i 1 k , a2i k } δi k 1 {δi k 1, γi k 1} δi k 1 {δi k 1}, i [2k 1]. The structure of the flatmate game is illustrated in Figure 1 for the case k = 3. We will be particularly interested in coalitions of the types {ai j, bi j, ci j}, {αi j, βi j}, {γi j, δi j}, and {yi 1, yi 2} which are marked by undirected edges. These coalitions form the partition π of Lemma 1 that we need later to investigate for strong and mixed popularity in the respective reductions. The directed edges indicate that an agent at the tail of the arrow needs to form a coalition with the agent at the tip of the arrow in order to improve from her coalition of the above type. The ground structure of the set of agents can be viewed as a binary tree of triangles depicted by the circular-shaped vertices. The important property of this tree is that whenever a coalition of the type {ai j, bi j, ci j} gets dissolved, there can only be an improvement in popularity for the agents in Ai j if they propagate changes in the partition upwards within this tree. This is achieved for agents bi j directly through the binary tree and for agents ai j with help of the auxiliary agents {αi j, βi j, γi j, δi j} that are depicted as diamond-shaped vertices. Brandt & Bullinger {r1, r3, r4} S Figure 1: Schematic of the reduction for flatmate games with strict preferences. There is an edge between two agents if they are in the coalition π defined in Lemma 1. Directed edges indicate improvements from π . The gray edges suggest a 3elementary set in S. Lemma 1. Let an instance (R, S) of X3C be given and define the corresponding flatmate game as above. Consider the partition π = {{ai j, bi j, ci j}: j [0, k], i [2j]} {{αi j, βi j}, {γi j, δi j}: j [0, k 1], i [2j]} {{yi 1, yi 2}: i [|R| + 1, 2k]}. Let π = π be an arbitrary partition of agents distinct from π . Then ϕ(π , π) 1. In addition, if c1 0 N(π , π), then ϕ(π , π) 3 or {bi k : i [2k]} N(π, π ). Proof. Let an instance (R, S) of X3C be given and define the corresponding flatmate game as above. Let π be defined as in the lemma and π = π another partition. We recursively define the following sets of agents: for i [2k], T i k = Ai k and for j = k 1, . . . , 0, i [2j], T i j = Ai j T 2i 1 j+1 T 2i j+1. We will prove the following claim by induction over j = k, . . . , 0. For every i [2j] holds: Assume there exists an agent x T i j with π(x) = π (x). Then ϕT i j (π , π) 1. If even π(ai j) = π (ai j), then ϕT i j (π , π) 3 {bi k : i [2k]} T i j N(π, π ). Note that the claim implies ϕT i j (π , π) 0 in any case. Clearly, the assertion of the lemma follows from the case j = 0. We frequently use the facts that for all j [0, k 1], i [2j], αi j / N(π, π ) and if βi j N(π, π ), then αi j N(π , π), and Finding and Recognizing Popular Coalition Structures γi j / N(π, π ) and if δi j N(π, π ), then γi j N(π , π). The case j = k and i [2k] is immediate (using a similar fact for agents yi 1 and yi 2 in the case i {|R| + 1, . . . , 2k}). For the induction step, let j {k 1, . . . , 0} and fix i [2j]. We will essentially prove that changing the coalitions in Ai j causes severe loss in popularity, unless we propagate changes to substructures via bi j or δi j. Assume first that there exists an agent x T i j with π(x) = π (x) but no such agent in Ai j. Then, x T 2i 1 j+1 x T 2i j+1 and the claim follows by induction. Assume therefore that there exists an agent x Ai j with π(x) = π (x). Note that ϕAi j(π, π ) 1. First consider the case that π(ai j) = π (ai j). If bi j N(π, π ), we can apply induction for T 2i 1 j+1 and T 2i j+1 and we are done, because by induction ϕT 2i 1 j+1 T 2i j+1(π , π) 4 {bi k : i [2k]} (T 2i 1 j+1 T 2i j+1) N(π, π ). We may therefore assume that bi j N(π , π). Then, ϕAi j(π , π) 3 or ai j N(π, π ). In the latter case, ϕAi j(π , π) 3 unless δi j N(π, π ). Finally, if δi j N(π, π ), then the claim follows by induction for T 2i 1 j+1 and T 2i j+1, because ϕT i j (π , π) = ϕAi j(π , π) + ϕT 2i 1 j+1 (π , π) + ϕT 2i j+1(π , π) 1 + 1 + 1 = 3. It remains the case that π(x) = π (x) for x {αi j, γi j} while π(ai j) = π (ai j). If π(αi j) = π (αi j), then ϕAi j(π , π) 2. If π(γi j) = π (γi j), then ϕAi j(π , π) 2 or ϕAi j(π , π) 0 π(δi j) = {δi j, α2i 1 j+1 , α2i j+1} and the claim follows by induction. In the next lemma, we prove that the preferences used in the construction are even globally ranked. Lemma 2. Let an instance (R, S) of X3C be given and define the corresponding flatmate game as above. Then, the preferences are globally ranked. Proof. The global preferences are composed of preferences 0, . . . , k over the sets of coalitions C0, . . . , Ck, where Cj is essentially the set of coalitions that is individually rational for some agent in Ai j for some i [2j]. More formally, Ck = S2k i=1{C N : v Ai k : C v {v}} and, for j = k 1, . . . , 0, Cj = S2j i=1{C N : v Ai j : C v {v}} \ Cj+1. Note that this separates coalitions by level, and Cj Cj = for j = j . In particular, coalitions of the types {δi j, α2i 1 j+1 , α2i j+1}, {δi k 1, a2i 1 k , a2i k }, and {bi j, c2i 1 j+1 , c2i j+1} that involve agents of two levels are added to the coalitions of the higher level. The global ranking is given in succinct form over Sk j=0 Cj as join( 0, . . . , k). It can be extended to a full global ranking by adding coalitions that are not individually rational for one of its members at the bottom. It remains to specify these subrankings. The preferences over sets of coalitions can always Brandt & Bullinger be arbitrary. The ranking k is given as {{yi 1, yi 2}: i [|R| + 1, 2k]} k{{bi k, yi 2}: i [|R| + 1, 2k]} k{{yi 1}, {yi 2}: i [|R| + 1, 2k]} k{{bi k, bv k, bw k }: {ri, rv, rw} S for v, w [|R|]} k{{bi k}: i [2k]} k{{ai k, bi k, ci k}: i [2k]} k{{bi k 1, c2i 1 k , c2i k }, {δi k 1, a2i 1 k , a2i k }: i [2k 1]} k{{ai k}, {ci k}: i [2k]} For j [k 1], the ranking j is given as {{γi j, δi j}: i [2j]} j{{ai j, βi j, γi j}: i [2j]} j{{ai j, bi j, ci j}, {αi j, βi j}: i [2j]} j{{bi j 1, c2i 1 j , c2i j }, {δi j 1, α2i 1 j , α2i j }: i [2j 1]} j{{ai j}, {bi j}, {ci j}, {αi j}, {βi j}, {γi j}, {δi j}: i [2j]} Finally, 0 is given as {γ1 0, δ1 0} 0 {a1 0, β1 0, γ1 0} 0 {{a1 0, b1 0, c1 0}, {α1 0, β1 0}} 0{{a1 0}, {b1 0}, {c1 0}, {α1 0}, {β1 0}, {γ1 0}, {δ1 0}} The individual preferences are clearly induced by the global ranking. We are now ready to apply the two lemmas for the desired reductions. Theorem 3. Deciding whether there exists a strongly popular partition in flatmate games is co NP-hard, even if preferences are strict and globally ranked. Proof. The reduction is from X3C. Given an instance (R, S) of X3C, we define a hedonic game on agent set N = N {z} where the agents N are as in the above construction with the identical preferences except changing the preferences of c1 0 to {a1 0, b1 0, c1 0} c1 0 {c1 0, z} c1 0 {c1 0}, and {c1 0, z} z {z}. In particular, for every agent in N \{c1 0}, coalitions together with z are not individually rational. Note that |N | = 3 Pk j=0 2j +4 Pk 1 j=0 2j +2(2k |R| 1)+1 = 12 2k 2 |R| 8 = O(|R|) and the reduction is in polynomial time. Consider the partition σ = {{ai j, bi j, ci j}: j [0, k], i [2j]} {{αi j, βi j}, {γi j, δi j}: j [0, k 1], i [2j]} {{yi 1, yi 2}: i [|R|+1, 2k]} {{z}} = π {{z}} for the partition π from Lemma 1. Let σ = σ be given and define π = (σ \ σ(z)) {σ(z) \ {z}}, i.e. the partition on the agent set N, where z left her coalition. Note that due to the preferences of agents in N, ϕ(π , π) ϕN(σ , σ). We investigate the popularity margin of σ and σ by a case distinction over the possible coalitions for agent z using the knowledge of Lemma 1 about Finding and Recognizing Popular Coalition Structures the relationship of the partitions π and π. If σ(z) = {z}, then ϕ(σ , σ) = ϕ(π , π) 1. If σ(z) = {c1 0, z}, then ϕ(σ , σ) 1 + ϕ(π , π) 1 + 1 0. Otherwise, ϕ(σ , σ) = 1 + ϕ(π , π) 1. It follows directly that σ is popular and hence there exists a strongly popular partition if and only if σ is strongly popular. We will prove that this is the case if and only if the instance of X3C is a No-instance. Assume that there exists no 3-partition of R through sets in S. The only case above, where the popularity margin is not strictly positive, is if σ(z) = {z, c1 0}, but in this case π(c1 0) = {c1 0} and it follows that ϕ(σ , σ) 1 + ϕ(π , π) 1 + 3 2. Hence, σ is strongly popular. Conversely, assume that there exists a 3-partition S S of R. Define σ ={{bv k, bw k , bx k}: {rv, rw, rx} S } {{bi k, yi 2}, {yi 1}: i [|R| + 1, 2k]} {{δi k 1, a2i 1 k , a2i k }: i [2k 1]} {{bi j, c2i 1 j+1 , c2i j+1}, {ai j, βi j, γi j}: j [k 1], i [2j]} {{δi j, α2i 1 j+1 , α2i j+1}: j [k 2], i [2j]} {{α1 0}, {z, c1 0}}. It is easily checked that ϕ(σ , σ ) = 0. Indeed, N(σ , σ ) = {bi k : i [2k]} {βi j, δi j, ai j : j [0, k 1], i [2j]} {yi 2 : i [|R|+1, 2k]} {z}. Therefore, |N(σ , σ )| = 2k+4 Pk 1 j=1 2j+2k (|R|+1)+1 = 6 2k |R| 4 = 1 2|N |. Hence, ϕ(σ , σ ) 0 and equality follows from popularity of σ . Therefore, there exists no strongly popular partition. A similar reduction as in Theorem 3 also works for mixed popularity. Then, however, we need two auxiliary agents to control the switch between a strongly popular and non-popular partition. Theorem 4. Computing a mixed popular partition in flatmate games is NP-hard, even if preferences are strict and globally ranked. Popular partitions are guaranteed to exist in roommate games with strict and globally ranked preferences (Abraham et al., 2008). We show by means of a counterexample that this is no longer the case when moving from roommate to flatmate games. This example game will serve as a crucial gadget to prove the hardness of computing popular partitions. Proposition 8. There exists a flatmate game with strict and globally ranked preferences which does not admit a popular partition. Proof. Consider N = {x1, x2, x3} {zj 1, zj 2 : j [4]}, and preferences induced by the global ranking given by {{x1, zj 1, zj 2}: j [4]} {{x2, zj 1, zj 2}: j [4]} {{x3, zj 1, zj 2}: j [4]} ({{xi}: i [3]} {{zj k}: k [2], j [4]}) . We claim that there exists no popular partition. By Proposition 2, we only need to consider Pareto optimal partitions. Let π be any Pareto optimal partition. Then π is individually rational. We will show how to obtain a more popular partition. By the pigeon hole principle, there exists j [4] with {zj 1}, {zj 2} π. If there exists i [3] with {xi} π, then creating the coalition {xi, zj 1, zj 2} is more popular. Otherwise, we may assume that for some {j1, j2, j3} [4], π(xi) = {xi, zji 1 , zji 2 }, for i [3]. Let j4 [4] \ {j1, j2, j3} be the remaining index. We obtain a new partition π by forming π (xi) = {xi, zji+1 1 , zji+1 2 }, leaving zj1 1 and zj1 2 in singleton coalitions. Brandt & Bullinger Then, N(π , π) {zji 1 , zji 2 : i [2, 4]} while N(π, π ) {x1, x2, x3, zj1 1 , zj1 2 }. Hence, ϕ(π , π) 1. The idea is to replace the agents xi of this example by the gadget of Lemma 1 to obtain a hardness result. Theorem 5. Deciding whether there exists a popular partition in flatmate games with strict and globally ranked preferences is co NP-hard. Proof. Given an instance (R, S) of X3C, we construct the flatmate game (N, ) with strict and globally ranked preferences as follows. We take 3 copies (Ni, i) of the game of Lemma 1, where i are the strict and globally ranked preferences of Lemma 2. Denote the special partition and agent of the lemma by π i and xi = c1 0i, respectively. Also, denote the set of coalitions ranked by i with C i and define Ci = C i \ {{xi}}. We set N = N1 N2 N3 {zj 1, zj 2 : j [4]}. To define global preferences, we define preferences over C4 = {{xi, zj 1, zj 2}: i [3], j [4]} {{xi}: i [3]} {{zj k}: k [2], j [4]}. {{x1, zj 1, zj 2}: j [4]} 4{{x2, zj 1, zj 2}: j [4]} 4{{x3, zj 1, zj 2}: j [4]} 4({{xi}: i [3]} {{zj k}: k [2], j [4]}) The global ranking is given over S4 j=1 Cj as = join( 1, 2, 3, 4) in succinct form. We claim that there exists a popular partition if and only if (R, S) is a No-instance of X3C. If (R, S) is a No-instance, consider π = S3 i=1 π i {{zj k}: k [2], j [4]}. Let π be any other partition. Let I = {i [3]: π (xi) = π(xi) and define N = N1 N2 N3 and Z = {zj 1, zj 2 : j [4]}. We have ϕN (π , π) 3|I| (due to Lemma 1) while ϕZ(π, π ) 2|I|. Hence, π is more popular than π if |I| 1. In the case |I| = 0, it holds ϕN (π, π ) 0 while ϕZ(π, π ) 0 and as π = π , one of the inequalities must be strict. Now assume that (R, S) is a Yes-instance of X3C and assume for contradiction that π is popular (and hence Pareto optimal). Then, for i [3], i I. Indeed, if i / I, then π restricted to Ni must be π i (otherwise, π i is more popular). There exists j [4] with π(zj 1) = {x1, zj 1, zj 2} and by Pareto optimality {zj 1}, {zj 2} π. We obtain a more popular partition π by replacing the coalitions of Ni {zj 1, zj 2} by the partition of the proof of Theorem 4 for the subgame (Ni, i). It remains the case that I = [3]. We may assume that for some {j1, j2, j3} [4], π(xi) = {xi, zji 1 , zji 2 }, for i [3]. Let j4 [4] \ {j1, j2, j3} be the remaining index. We obtain a new partition π by removing zj4 1 , zj4 2 from their coalitions and forming π (xi) = {xi, zji+1 1 , zji+1 2 }, leaving zj1 1 and zj1 2 in singleton coalitions. Then, N(π , π) {zji 1 , zji 2 : i [2, 4]} while N(π, π ) {x1, x2, x3, zj1 1 , zj1 2 }. Hence, ϕ(π , π) 1, a contradiction. Finding and Recognizing Popular Coalition Structures To conclude the section, we deal with the problem of verifying whether a given partition is popular or strongly popular. The respective results follow directly from the constructions of the hardness of existence. Theorem 6. Verifying whether a given partition in a flatmate game with strict and globally ranked preferences is popular is co NP-complete. Proof. In the proof of Theorem 5, the partition π is popular if and only if (R, S) is a No-instance of X3C. Theorem 7. Verifying whether a given partition in a flatmate game is strongly popular is co NP-complete, even if preferences are strict and globally ranked. Proof. In the proof of Theorem 3, the partition π is strongly popular if and only if (R, S) is a No-instance of X3C. We would like to remark a strong relationship of the existence and verification problems. Our general proof strategy for the co NP-hardness of existence problems is to provide an instance of a game together with a partition that is (strongly) popular if and only if the constructed game arises from a No-instance of the NP-hard source problem (this is the partition π of property PP). If the game is based on a Yes-instance, there is no (strongly) popular partition. In other words, all relevant questions on (strong) popularity can be answered with this given partition. Consequently, we actually prove co NP-hardness for a restriction of the verification problem that is only allowed to ask for verification of partitions that have to be (strongly) popular if such a partition exists. Clearly, the hardness of this restricted problem implies both hardness of the verification and the existence problem. The latter follows from the simple reduction that maps tuples (G, π) of a game and a partition to the game G. Instead of giving the reduction for this unifying problem, we prefer not to introduce this restricted verification problem, and to keep the focus on the problems that we are actually interested in. Still, the same phenomenon will occur again for the proofs regarding cardinal hedonic games in the next section. 4.3 Cardinal Hedonic Games Important subclasses of hedonic games that admit succinct representations are based on cardinal utility functions. For one, there are additively separable hedonic games (Bogomolnaia & Jackson, 2002), where the utility that an agent associates with a coalition is the sum of utilities he ascribes to each member of the coalition. On the other hand, there are fractional hedonic games (Aziz, Brandl, Brandt, Harrenstein, Olsen, & Peters, 2019), where the sum of utilities is divided by the number of agents contained in the coalition. In the following, let vi(j) denote the utility that agent i associates with agent j. Based on these utilities and the underlying class of games, we will deduce the utility vi(S) that i associates with some coalition S Ni. The preferences of i over two coalitions S, T Ni are then given by assuming that S i T if and only if vi(S) vi(T). A hedonic game (N, ) is an additively separable hedonic game (ASHG) if there is (vi(j))i,j N such that, for every agent i, the preferences i are induced by the cardinal utilities given by vi(S) = P j S vi(j). Brandt & Bullinger a1 a2 a3 b1 b2 Figure 2: Instance of an additively separable hedonic game with no popular partition. Omitted edges have weight K. The hedonic game (N, ) is a fractional hedonic game (FHG) if there exists (vi(j))i,j N such that, for every agent i, the preferences i are induced by the cardinal utilities given by vi(S) = (P j S vi(j))/|S|, for S N. We focus on symmetric ASHGs and FHGs, i.e., games for which vi(j) = vj(i) for all i, j N and denote the symmetric utilities by v(i, j) = vi(j) = vj(i). All hardness results in this section are obtained by rather involved reductions from X3C. 4.3.1 Additively separable hedonic games We start by having a look at an example of an ASHG that contains no popular partition and that will be used as a gadget in the hardness construction. There are smaller ASHGs without a popular partition, but the instance of the proposition satisfies further properties required for the reduction of Theorem 8 to work. All games considered in this section only contain a single negative weight, whose absolute value is large enough to ensure that certain coalitions will not form. Proposition 9. Let 0 < ϵ < 1 and K 4. Consider the following ASHG, depicted in Figure 2 with agent set N = {a1, a2, a3, b1, b2, b3, c1, c2} and utilities given by v(ai, c1) = 2, v(ai, c2) = 1, v(ai, bi) = ϵ, v(bi, c2) = 0 for all i [3] and v(x, y) = K for all other values not defined, yet. Then, there exists no popular partition. Proof. Assume for contradiction that π was a popular partition. Then the following facts hold: ai / π(aj), i = j, ai / π(bj), i = j, bi / π(bj), i = j, and c1 / π(c2), c1 / π(bj). Finding and Recognizing Popular Coalition Structures In all of these cases, dissolving the coalition in question would be more popular, because all but possibly one agent in the coalition have negative utility and an agent with non-negative utility can only be contained in the coalition if it contains at least 3 agents. Note that K is larger than the sum of positive weights incident to any agent and therefore its utility is negative once it is in a coalition with an agent that gives negative utility. Now, for every j, exactly one of the following holds: c1 π(aj) or bj π(aj). In fact, both cannot hold as excluded above. If none holds, then π(aj) {aj, c2} and we could delete bj from her coalition (making no agent worse) and add it to π(aj), resulting in a more popular partition. Next, for i [2], there exists j with ci π(aj). Otherwise, there existed k with π(ak) {ak, bk} and removing bk and adding ci is more popular. Thus, up to symmetry, the only possibility is π = {{a1, c1}, {b1}, {a2, c2, b2}, {a3, b3}}. But then {{a2, c1}, {b2}, {a3, c2, b3}, {a1, b1}} is more popular. Hence, π was not popular. We now discuss the proof strategy for showing that computing popular partitions in symmetric ASHGs is NP-hard. For a reduction from X3C, given an instance (R, S), we have R-gadgets for every element of the ground set R and S-gadgets for every 3-elementary set in S. The gadgets for elements of R rely on the ASHG of Proposition 9. The gadget for a set s S consists of three agents that are very happy in a coalition of their own, but one of them is linked to the R-gadgets corresponding to the agents in s and can simultaneously prevent the agents in these Rgadgets from voting down a partition. This is of course at the expense of the happiness of agents in the S-gadgets and can only happen if all three R-gadgets are simultaneously dealt with. This is where we achieve the correspondence of the covering with 3-partitions, which we can read off from the coalitions of the agents in S-gadgets. Theorem 8. Checking whether there exists a popular partition in a symmetric ASHG is NP-hard. The verification problem for ASHGs turns out to be co NP-complete. The proof of Theorem 9 is simpler than Aziz et al. s ((2013b)) proof of a weaker statement for ASHGs that do not have to be symmetric. Theorem 9. Checking whether a given partition in a symmetric ASHG is popular is co NPcomplete. The reductions for co NP-hardness of mixed and strong popularity as well as popularity on ASHGs rely on the idea of property PP which we already employed in Lemma 1. The next lemma establishes this property and is subsequently applied to prove the next four theorems. Note that it is not possible to leverage the relationship of mixed popularity and Pareto optimality, because Pareto optimal partitions can be found in polynomial time for symmetric ASHGs (Bullinger, 2020). Lemma 3. The class of symmetric ASHGs satisfies property PP. We obtain several hardness results. Brandt & Bullinger Theorem 10. Checking whether there exists a strongly popular partition in a symmetric ASHG is co NP-hard. Theorem 11. Verifying whether a given partition in a symmetric ASHG is strongly popular is co NP-complete. Theorem 12. Computing a mixed popular partition in a symmetric ASHG is NP-hard. We even obtain co NP-hardness of the existence of popular partitions which makes it unlikely that the existence problem for symmetric ASHGs is in NP (otherwise co NP = NP) and, together with Theorem 8, might be seen as evidence that this problem is even Σp 2-complete. Theorem 13. Checking whether there exists a popular partition in a symmetric ASHG is co NP-hard. 4.3.2 Fractional hedonic games We now turn to FHGs. In general, reduction proofs for FHGs tend to be more complicated than for ASHGs, because utility functions are not additive. On top of that, negative utilities have very different consequences in ASHGs and FHGs. In ASHGs with non-negative utility functions, the grand coalition will form under any set of reasonable assumptions because it is the best possible coalition for all agents. The same is not true for FHGs, which incentivize small coalitions by having the size of a coalition in the denominator of utility functions. Hence, in contrast to ASHGs, FHGs are meaningful in the absence of negative utilities and it is therefore desirable to prove hardness results that even hold for non-negative utilities. Before investigating popularity, we quote a useful proposition about the structure of top-ranked coalitions in FHGs. Proposition 10 (Bullinger (2020)). Let a FHG (N, ) be given and let i N be an agent. Let µ be the utility of a top-ranked coalition of agent i. Then, the top-ranked coalitions of agent i are precisely the coalitions of the form {i} {j N : vi(j) > µ} W for W {j N : vi(j) = µ}. In other words, every top-ranked coalition of agent i consists precisely of all agents j whose utility vi(j) exceeds a certain threshold. Now, we consider the existence and verification problem for popular partitions in fractional hedonic games. The strategy is similar to the case of ASHGs. Again, there exist gadgets for every element of R and the sets in S. The R-gadgets rely on rather simple graphs, namely stars. We define by Sk the star graph with k leaves, i.e., Sk = G, where G = (V, E) with V = {c, l1, . . . , lk}, E = {{c, lj}: j [k]}. We say that an FHG is induced by Sk if its agent set is N = V , and symmetric, binary utilities are given by v(i, j) = 1 if {i, j} E and v(i, j) = 0, otherwise, where i, j N. The next proposition classifies, which star graphs induce FHGs admitting popular partitions. The boundary cases are illustrated in Figure 3. Proposition 11. Let k N and consider the FHG induced by Sk. For k 5, the (sub-)partition (of) π = {{c, l1, l2, l3}, {l4}, {l5}} is popular. For k 6, Sk admits no popular partition. Finding and Recognizing Popular Coalition Structures Figure 3: FHGs induced by stars. For stars with 5 leaves, a popular partition π exists (left). This is not the case for stars with more leaves (right). For instance, the grand coalition is more popular than partition π . Proof. The first part is easily seen. For the second assertion, let k 6 and assume that π was a popular partition. Then, |π(c)| 4, since otherwise we obtain a more popular partition if one leaf leaves π(c). But in this case, the grand coalition is more popular (having c and at least k 3 leaves better off). Using stars as gadgets, we can prove the next theorem. Theorem 14. Checking whether there exists a popular partition in a symmetric FHG is NP-hard, even if all utilities are non-negative. The hardness proof for the verification problem for FHGs is a more involved version of the proof for ASHGs. Theorem 15. Checking whether a given partition in a symmetric FHG is popular is co NPcomplete, even if all utilities are non-negative and the underlying graph is bipartite. The graphs used in the proof of Theorem 15 have girth 6. This is in contrast to the polynomial-time algorithm by Aziz et al. (2019) for computing the core in FHGs with girth at least 5. As in the case of ASHGs, we now consider strong and mixed popularity for FHGs. First, we derive property PP for FHGs. The underlying graph is almost identical to the one for ASHGs, which might be surprising, because the utilities for ASHGs and FHGs induced by the same graph will in general cause very different preferences over coalitions. However, all coalitions that actually matter for the particular instance we consider are of size 2 and 3 and therefore the different game models behave very similarly. Lemma 4. The class of symmetric FHGs with non-negative utility functions satisfies property PP. Brandt & Bullinger The proof of the hardness of the existence of strongly popular partitions on FHGs is very similar to the case of ASHGs, but there are some subtle differences regarding the preferences of the additional agent. Theorem 16. Checking whether there exists a strongly popular partition in a symmetric FHG is co NP-hard, even if all utilities are non-negative. Theorem 17. Verifying whether a given partition in a symmetric FHG is strongly popular is co NP-complete, even if all utilities are non-negative. Theorem 18. Computing a mixed popular partition in a symmetric FHG is NP-hard, even if all utilities are non-negative. As for ASHGs, we can pinpoint the complexity of the existence of popular partitions more exactly. The general proof idea is the same, but the case analyses are simpler, because we can choose positive utilities of the auxiliary agents, which can never help the original agents in the copies of the game in Lemma 4. Theorem 19. Checking whether there exists a popular partition in a symmetric FHG is co NP-hard, even if all utilities are non-negative. 5. Conclusion We have investigated the computational complexity of finding and recognizing popular, strongly popular, and mixed popular partitions in various types of ordinal hedonic games and cardinal hedonic games. Tables 1 and 2 summarize our results and give an overview of the complexity for computing a respective partition. In the tables, NP-hardness refers to intractability of the corresponding search problem, which follows directly from NP-hardness or co NP-hardness of the existence problem via a Turing reduction. Note that both NPhardness and co NP-hardness of the existence problem for popularity hold for flatmate games, ASHGs, and FHGs, where the NP-hardness for flatmate games follows from the hardness for roommate games. It is open whether these problems are even Σp 2-complete. Whenever we obtain hardness of an existence problem, the corresponding verification problem is co NP-complete. For mixed popularity, this follows from Proposition 3. Two important factors that govern the complexity of computing these partitions in ordinal hedonic games are whether preferences may contain ties and whether coalitions of size 3 are allowed. When preferences are weak, computing mixed popular and strongly popular partitions is only difficult for representations for which we cannot even compute Pareto optimal partitions efficiently. For strict preferences, however, Pareto optimal partitions can be found efficiently while computing popular, mixed popular, and strongly popular partitions remains intractable. These results are quite robust and all results for flatmate games hold even when preferences are globally ranked, while this restriction allows for tractability of popularity under strict preferences in roommate games. It can be shown that our hardness results remain intact for tripartite matching (with strict and globally ranked preferences), where the agents can be partitioned into three groups and individually rational coalitions Finding and Recognizing Popular Coalition Structures weak preferences strict preferences PO m Pop s Pop Pop PO m Pop s Pop Pop IRLC in P Flatmates NP-h.a NP-h. (Th. 2) NP-h. (Th. 3) NP-h. (Th. 4) NP-h. (Th. 3) Roommates in Pb in P (Th. 1) in P (Cor. 3) in P (Th. 1) in Pd NP-h.g Marriage NP-h.e in Pf Housing in Pc in P in Ph in P in Pc Table 1: Complexity of finding popular and Pareto optimal partitions in various classes of hedonic games. New results are highlighted in gray and implications are marked by gray arrows. NP-hardness of computing a popular or strongly popular partition always follows by a Turing reduction from the existence problem. a: Aziz et al. (2013a, Th. 5), b: Aziz et al. (2013a, Th. 7), c: Abraham et al. (2007, Th. 3.9), d: Bir o et al. (2010, Th. 6), e: Bir o et al. (2010, Th. 11), Cseh et al. (2015, Th. 2), f: G ardenfors (1975, Th. 3), g: Gupta et al. (2019, Th. 1.1), Faenza et al. (2019, Th. 4.6), Cseh and Kavitha (2018, Th. 2), h: Kavitha et al. (2011, Th. 2); the result by Kavitha et al. also holds for marriage games and weak preferences; these cases are implied by our Th. 1. PO PO/IR m Pop s Pop Pop symmetric ASHGs in Pa NP-h.a NP-h. (Th. 12) NP-h. (Th. 10) NP-h. (Th. 8, 13) symmetric FHGs in P (0/1)a NP-h.a NP-h. (Th. 18) NP-h. (Th. 16) NP-h. (Th. 14, 19) Table 2: Complexity of finding popular and Pareto optimal partitions in cardinal hedonic games. New results are highlighted in gray. NP-hardness of computing a popular or strongly popular partition always follows by a Turing reduction from the existence problem. Pareto optimal partitions in FHGs can be computed in polynomial time for (0/1)-preferences. a: Bullinger (2020, Th. 5.1, 5.1, 6.2, 6.4) may only contain at most one agent of each group.8 An interesting avenue for future research is to consider the three notions of popularity in further restrictions of flatmate games such as room-roommate games or three-cyclic matching games.9 Notably, the related existence problem for stable three-dimensional matchings has also been shown to be NP-hard (Lam & Plaxton, 2019). Our positive results for roommate games are obtained via a single linear programming approach that unifies a number of existing results and exploits the relationships between the different types of popularity. On the other hand, both in flatmate games and cardinal hedonic games, our hardness results are based on the same central idea, formalized via 8. The reduction for this result changes the source problem for the reduction in Lemma 1 to 3-Dimensional Matching instead of Exact 3-Cover, and consists essentially of finding the tripartition of the agent set in the existing reduction by placing the agents corresponding to the elements of the ground set of a source instance the right way in the top layer in Figure 1. 9. Some advances in this direction were recently made by Cseh and Peters (2022). Brandt & Bullinger property PP. All of these classes of hedonic games contain games with a strongly popular partition together with an agent that can govern the switch between strong popularity and non-popularity by joining different sets of additional auxiliary agents. As a consequence, results for all types of popularity and for both existence and verification problems can be extracted from the same reduction.10 Since mixed popular partitions always exist, the natural computational problem is the search problem. We have shown that intractability of this problem can be inferred from corresponding results on Pareto optimality. Moreover, we prove the hardness of computing mixed popular partitions in classes of games in which Pareto optimal partitions can be found efficiently.11 In all our reductions, it is already hard to compute some (deterministic) partition in the support of a mixed popular partition, i.e., a subset of Pareto optimal partitions. Acknowledgments This material is based on work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/12-1. The authors thank Stefan Weltge and three anonymous reviewers for providing valuable feedback. Preliminary results of this paper were presented at the 19th International Conference on Autonomous Agents and Multi-Agent Systems (May, 2020). Appendix A. Omitted Proofs The appendix contains all omitted proofs. A.1 Ordinal Hedonic Games We introduce a useful notation for the next two propositions. Given a matching M and an agent a, denote by M(a) the agent, a is matched with. Proposition 6. Let p and q be mixed matchings. Then, ϕ(p, q) = ϕ(xp, xq). In particular, p is popular if and only if for all matchings M, ϕ(xp, χM) 0. Proof. Let p and q be two mixed matchings. By extending them with some matchings of probability 0, we may assume that both are defined on the same set of matchings M1, . . . , Mk as p = {(M1, p1), . . . , (Mk, pk)} and q = {(M1, q1), . . . , (Mk, qk)}. We derive that 10. The careful reader might have noticed that we do not extract the proofs of the verification problem for ASHGs and FHGs from this general approach. While this is also possible, we have obtained independent proofs which hold for a more restrictive variant of FHGs, and allow the comparison with existing results about the complexity of computing partitions in the core. 11. Note that the complexity of Pareto optimality in FHGs under arbitrary symmetric weights is still open. As indicated in Table 2, Bullinger (2020) only settles the problem for some restricted classes of FHGs including binary utilities. Finding and Recognizing Popular Coalition Structures s,t=1 psqtϕ(Ms, Mt) s,t=1 psqt X a N ϕa(Ms(a), Mt(a)) s,t=1 psqt X i,j NG(a) χMs(a, i)χMt(a, j)ϕa(i, j) s=1 psχMs(a, i) t=1 qtχMt(a, j) i,j NG(a) xp(a, i)xq(a, i)ϕa(i, j) = ϕ(xp, xq). This proves the desired equality. Proposition 7. The separation problem for PPop can be solved in polynomial time. Proof. Assume that a vector x RE is given. The separation problem for the matching polytope can be solved in polynomial time. For the popularity constraints, we assign weights wx to the edges of the underlying graph such that for all matchings M on G, wx(M) = ϕ(χM, x). Therefore, their separation problem turns into finding a maximum weight matching, which can be done in polynomial time. We define the weights by letting wx(i, j) = X a NG(i) x(i, a)ϕi(j, a) + X a NG(j) x(j, a)ϕj(i, a) and compute ϕ(χM, x) = X i,j NG(a) χM(a, i)x(a, j)ϕa(i, j) i,j NG(a) χM(a, i)x(a, j)ϕa(i, j) j NG(a),i=M(a) x(a, j)ϕa(i, j). Brandt & Bullinger On the other hand, b NG(i) x(i, b)ϕi(j, b) + X b NG(j) x(j, b)ϕj(i, b) b NG(i),j=M(i) x(i, b)ϕi(j, b) + X b NG(j),i=M(j) x(j, b)ϕj(i, b) a N,a matched j NG(a),i=M(a) x(a, j)ϕa(i, j) j NG(a),i=M(a) x(a, j)ϕa(i, j) The last equation is due to the fact that the inner sum is empty for unmatched agents in M. Putting everything together, we conclude that ϕ(χM, x) = wx(M), which completes the proof. Theorem 4. Computing a mixed popular partition in flatmate games is NP-hard, even if preferences are strict and globally ranked. Proof. We provide a Turing reduction from X3C to the problem of finding a partition in the support of a mixed popular partition together with its probability in this mixed partition. Given an instance X3C, we construct a very similar game as in the proof of Theorem 3. We have N = N {z1, z2} where the agents N are as in the above construction with identical preferences, except for changing the preferences of agent c1 0 to {a1 0, b1 0, c1 0} c1 0 {c1 0, z1, z2} c1 0 {c1 0}, and {c1 0, z1, z2} zi {zi} for i [2]. By a case distinction similar to the one in the proof of Theorem 3 and using Lemma 1, it follows that the partition π = {{ai j, bi j, ci j}: j [0, k], i [2j]} {{αi j, βi j}, {γi j, δi j}: j [0, k], i [2j] odd} {{yi 1, yi 2}: i [|R| + 1, 2k]} {{z1}, {z2}} is strongly popular if there exists no 3-partition of R through sets in S. Therefore the unique mixed popular partition assigns probability 1 to π . On the other hand, assume that there exist a 3-partition S S of R. Define π = {{bv k, bw k , bx k}: {rv, rw, rx} S } {{bi k, yi 2}, {yi 1}: i [|R| + 1, 2k]} {{δi k 1, a2i 1 k , a2i k }: i [2k 1]} {{bi j, c2i 1 j+1 , c2i j+1}, {ai j, βi j, γi j}: j [k 1], i [2j]} {{δi j, α2i 1 j+1 , α2i j+1}: j [k 2], i [2j]} {{α1 0}, {z1, z2, c1 0}}. It is easily checked that ϕ(π, π ) = 1. Therefore, there exists no mixed popular partition that assigns probability 1 to π . We can solve X3C by computing a partition π in the support of a mixed popular partition and checking its probability in case π = π . A.2 Additively separable hedonic games Next, we consider the existence problem for ASHGs. Theorem 8. Checking whether there exists a popular partition in a symmetric ASHG is NP-hard. Finding and Recognizing Popular Coalition Structures V k zs 1 zs 2 10 10 s = {i, j, k} Figure 4: Schematic of the reduction of the existence problem for ASHGs. Edges of weight 0 and of negative weight are omitted. Proof. The reduction is from X3C to deciding whether there exists a popular partition. Let (R, S) be an instance of X3C. This can be reduced to an instance (N, ), where (N, ) is an ASHG defined in the following way. Let N = {ar 1, ar 2, ar 3, br 1, br 2, br 3, cr 1, cr 2 : r R} {ys, zs 1, zs 2 : s S} and edge weights as v(ar i , cr 1) = 2 and v(ar i , cr 2) = 1, v(ar i , br i ) = ϵ, v(br i , cr 2) = 0 for all i [3] and r R, v(ar 3, ar 3 ) = 0, v(br 3, ar 3 ) = 0, v(br 3, br 3 ) = 0 for all s S and r, r s, v(ar 3, ys) = 5 and v(br 3, ys) = 0 for all s S and r R such that r s, v(ys, zs 1) = v(ys, zs 2) = 10 and v(zs 1, zs 2) = 0 for all s S, and v(x, y) = 40 for all other valuations not defined. In order to enable the reduction, we can, for example, choose ϵ = 1 2. A schematic of the reduction for a certain set s = {i, j, k} S is depicted in Figure 4. We abbreviate in the figure and the rest of the proof V r = {ar 1, ar 2, ar 3, br 1, br 2, br 3, cr 1, cr 2}, where r R, and W s = {ys, zs 1, zs 2}, where s S. Also denote V R = r RV r, W S = s SW s and A3 = {ar 3 : r R}. We show that there exists a popular partition of (N, ) if and only if (R, S) is a Yesinstance of X3C. Assume (R, S) is a Yes-instance of X3C. Then, there exists S S such that S is a partition of R. Consider the partition π = {{ar 1, cr 1}: r R} {{ar 2, br 2, cr 2}: r R} {{br 1}: r R} {{ys, ai 3, aj 3, ak 3, bi 3, bj 3, bk 3}: s = {i, j, k} S } {W s : s N \ S } {{zs 1, zs 2}: s S }. We claim that π is popular. Assume for contradiction that π is more popular than π. We first prove the following two claims: Brandt & Bullinger 1. Let r R such that for all s S with r s holds that ys / π (ar 3). Then, |N(π, π ) V r| |N(π , π) V r| 1. 2. Let r R. If |{ys : s S} π (ar 3)| 1 then, |N(π, π ) V r| |N(π , π) V r| 0. If |{ys : s S} π (ar 3)| 2 then, |N(π, π ) V r| |N(π , π) V r| 1. We start with the proof of the first claim. Let therefore r R such that for all s S with r s holds that ys / π (ar 3). Since r R is fixed, we omit the superscript r for proving this claim. We know that a3 N(π, π ) and b2, b3 / N(π , π) We distinguish several cases: First, consider the case that c1 π (a1). Then, b1, a2 / N(π , π). In addition, we may assume a1 / N(π , π), because otherwise c1, c2 N(π, π ) and the claim is true. If ci N(π , π), then c3 i / N(π , π) and either (a1 N(π, π ) a2 N(π, π )) b3 N(π, π ) or a1, a2 N(π, π ). In every case, |N(π , π)| 2 and |N(π, π )| 3 and the claim follows. Hence, we may assume that ci / N(π , π) and no agent can be in N(π , π). In this case, the claim follows. Second, assume c1 π (a2). Then, a1, b2 N(π, π ). If a2 / N(π , π), then it has a negative neighbor, i.e., a2 N(π, π ). We have |N(π, π )| 4, |N(π , π)| 3. Hence, a2 N(π , π). As a consequence, c1 / N(π , π) and c2 / N(π , π) b1 / N(π , π) and we conclude with |N(π, π )| 3, |N(π , π)| 2. Third, assume c1 π (a3). Then, a1, b3 N(π, π ). If c2 π (a3), then c1, c2, a2 N(π, π ) and we conclude with |N(π, π )| 6. If c2 / π (a3), then {a1, a3, b3} N(π, π ) and a2, b2 / N(π , π) and either b2 N(π, π ) or c2 / N(π , π). Finally, assume c1 / π (a1) π (a2) π (a3). Then a1, c1 N(π, π ) and a2 / N(π , π) c2 / N(π , π). Hence, |N(π, π )| 3, |N(π , π)| 2. This concludes the proof of the first claim. Before we prove the second claim, we argue that we can assume without loss of generality that for all r R, π (ar 3) V r {ar 3, br 3} {ys : s S} π (ar 3) = . Indeed, if both conditions are not met, then leaving with ys {ys : s S} π (ar 3) and forming a coalition with W s yields a partition π with the following properties: |N(π , π) (N \ W s)| |N(π , π) (N \ W s)| 1 (Note that the only agent that is not still better off is possibly ar 3 since the other ar 3 are worse off since they would get negative utility in π (ar 3).), |N(π, π ) (N \ W s)| |N(π, π ) (N \ W s)| + 1 (the only candidate is again ar 3), |N(π , π) W s| |N(π , π) W s| + 3 if π(ys) = W s, and |N(π, π ) W s| |N(π, π ) W s| 3 if π(ys) = W s. Finding and Recognizing Popular Coalition Structures Other changes in W s cannot occur at the same time and we conclude ϕ(π , π) ϕ(π , π) (in fact the inequality is strict). For the second claim, this means that if some ys π (ar 3) we can consider π modified such that ys leaves her coalition. This can only decrease the size of N(π , π) V r if |{ys : s S} π (ar 3)| 2 and cannot increase the size of N(π, π ) V r by more than 1. Hence, the claim follows from the first case. We define the set of critical subsets s S as Y c = {s S : r R with ys π (ar 3)} and the set of happy R gadgets as Rh = {r R: |{ys : s S} π (ar 3)| 2}. We know that for every ys Y c at most 3 of the ar 3 do not satisfy the condition of the first claim. Hence, a total of max{|R| 3|Y c| + |Rh|, 0} of the agents ar 3 does so. Putting together the claims yields |N(π, π ) V R| |N(π , π) V R| max{|R| 3|Y c| + |Rh|, 0} |Rh| |R| 3|Y c|. (1) We claim that in addition |N(π , π) W S| |N(π, π ) W S| |R| 3|Y c|. (2) The idea to prove this inequality is that every agent ys has to decide whether the agents in W s or the ar 3 with r s should be happy. Without loss of generality, we can assume that for all s S, π(ys) A3 = or π(ys) W s = {ys}. Indeed, if both conditions are not met, then leaving with ys and forming a coalition with W s yields a partition π with ϕ(π , π) ϕ(π , π). To prove Equation (2) note that W s N(π, π ) W S for every s Y c such that π(ys) = W s. In other words, |N(π, π ) W S| 3|{s Y c : π(ys) = W s}|. In addition, the only agents that get better in W S can be in a W s such that π(ys) = W s and ys / Y c. This is, |N(π , π) W S| 3|{s / Y c : π(ys) = W s}|. Combining the inequalities yields |N(π , π) W S| |N(π, π ) W S| 3(|{s / Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}|) = 3(|{s / Y c : π(ys) = W s}| + |{s Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}|) = 3|S | 3|Y c| = |R| 3|Y c|. Combining Equation (1) and Equation (2) yields |N(π, π )| |N(π , π)| 0, contradicting the assumption that π was more popular than π. It remains to prove that every popular partition yields a 3-partition of R with sets in S. Therefore, assume that π is a popular partition in (N, ). The partition will be found by checking intersections of π(ys) A3 as captured in the following claims: 1. For all r R there exists a unique s S with ys π(ar 3). For this s holds that r s. 2. For all s S holds: ( i s : ai 3 π(ys)) ( j s, aj 3 π(ys)). Brandt & Bullinger If the claim is true, S = {s S : A3 π(ys) = } covers R due to existence and is a partition due to uniqueness and the second claim that ensures that either all three or none of the agents in A3 corresponding to elements in s are present in a coalition π(ys). We start to show the existence part of the first claim which will follow directly from the property that N|V r contains no popular partition (Proposition 9). Assume for contradiction that there exists a r R such that for all s S holds ys / π(ar 3). We obtain a more popular partition in two steps. First, we modify π such that for all agents in v V r we split their coalition into π(v) V r and V r \ π(v). This cannot decrease the utility of any agent. Application of Proposition 9 yields a more popular partition locally on V r that can be extended to the whole N via the remaining (modified) coalitions in π. For the uniqueness part assume for contradiction that there is r R and s = s S with {ys, ys } π(ar 3). We distinguish two cases. First, assume that |π(ar 3) A3| 3. Then, there exists (without loss of generality using symmetry amongst s and s ) an agent r R with r s and ar 3 / π(ar 3). Then, the partition π obtained from π by removing the agents in W s from their partitions in π and letting them form a coalition is more popular. Indeed, |N(π, π )| 2 (the two remaining agents at 3 with t = r and t s are the only ones to possibly loose utility) and W s N(π , π). Second, assume that |π(ar 3) A3| 4. Then, there exists an agent u A3 π(ar 3) with u / s. The same partition π as in the first case yields |N(π, π )| 3 and |N(π , π)| |W s {u}| = 4. In both cases, we have found a more popular partition, a contradiction. Finally, for the second claim, in the case that there exists a s S with 1 |{j s : aj 3 π(ys)}| 2, the same rearrangement of coalitions (i.e., forming the coalition W s) is more popular. Theorem 9. Checking whether a given partition in a symmetric ASHG is popular is co NPcomplete. Proof. The problem is in co NP, because a more popular partition serves as a polynomialtime certificate for a No-instance. For hardness, we reduce again from X3C. Given an instance (R, S) of X3C, we assume without loss of generality that |R| 6. We define an ASHG (N, ) given by N = R {s1, s2, s3 : s S} {b1, b2, b3} and weights as v(i, s3) = 1 for i s, s S, v(s1, s3) = v(s2, s3) = 4 for s S, v(sj, bj) = 1 for s S, j [2], v(b1, b3) = v(b2, b3) = α for |R| 3 1 < α < |R| v(i, j) = 0 for i, j R, v(s1, s2) = 0 for s S, and v(b1, b2) = 0, and v(x, y) = max{12, |S|+|R|/3} for all agents x, y N such that no utility is defined, yet. Finding and Recognizing Popular Coalition Structures i j k x y z 4 4 s = {i, j, k} 4 4 t = {x, y, z} V Figure 5: Schematic of the reduction for the verification problem of popular partitions on symmetric ASHGs. Edges without explicit weight have weight 1. Omitted edges for agents in R have weight 0. All other omitted edges have weight 12. The partition π marked in gray is the one under consideration for verification. One can choose, e.g., α = (|R| 1)/3, but for the reduction, only the above bounds matter. We introduce some useful notation for the proof. Denote V s = {s1, s2, s3} for s S, B = {b1, b2, b3}, and V = s SV s. The partition in question is π = {V s : s S} {{r}: r R} {B}. We claim that (R, S) is a Yes-instance of X3C if and only if π is not popular for the ASHG given by G. If (R, S) is a Yes-instance, there exists a subset S S that partitions R. In particular |R| = 3|S |. Consider the partition given by π = {V s : s S \ S } {{s3, i, j, k}: {i, j, k} = s S } {{bj, sj : s S }: j [2]} {{b3}}. Then, N(π , π) = R {b1, b2} and N(π, π ) = s S V s {b3}. Hence, π is more popular than π. Conversely, assume that there exists a more popular partition π and fix one that maximizes ϕ(π , π). We have to prove that there exists a subset S S that yields a partition of R. Note that the negative weight is chosen so large that agents in a coalition linked by negative utility are always worse off. First, we claim that for all s S, N(π , π) V s = . Assume for contradiction that for j [2], sj N(π , π). Then, {sj, s3, bj} π (sj) V s {bj}. Thus, s3 j, s3, bj, b3 N(π, π ). We form a new coalition π from π by having the coalitions V s and B (these agents leave their coalitions in π ) and all other coalitions remain the same. We consider two cases: If |π (b3 j) V | 1, then b3 j N(π, π ). (We used that |R| 6.) We have that s3, s3 j, b1, b2, b3 N(π, π )\N(π, π ), s2 N(π , π)\N(π, π ) and possibly the agent t π (b3 j) V yields t N(π , π) N(π, π ). Hence, ϕ(π , π) > ϕ(π , π). Brandt & Bullinger Otherwise, π (b3 j) V N(π, π ), but possibly b3 j N(π , π)\N(π, π ) in addition. However, ϕ(π , π) > ϕ(π , π) remains valid. In any case, we derived a contradiction to the maximality condition on π . If s3 N(π , π), then {s1, s2} π (s3), s π (s3) = , and π (s3) V s s (here s R is the set of R-agents corresponding to elements of the set s). Hence, forming a coalition π by leaving with the agents in s moves these agents and s1, s2 out of N(π, π ), while only removing s3 from N(π , π). Hence, we again contradict the maximality of ϕ(π , π). For the rest of the analysis, we narrow down the possible more popular partitions to a very specific situation that corresponds to 3-partitions. The idea is basically that whenever we sacrifice a set V s of agents, we can improve only 3 agents in R. Due to the boundaries on α, we will cross the threshold, where we can have a popularity margin of precisely 1 exactly at the moment when we gathered |R| 3 neighbors for b1 and b2 in order to improve these. We introduce the sets RI = R N(π , π) and SC = {s S : π (s3) R = }. Our goal is to prove |R| = |RI| = 3|SC|. For s SC holds V s N(π, π ) (which follows for s3 since s3 / N(π , π)). Consequently, |N(π, π ) V | 3|SC|. In addition, |N(π , π) R| = |RI| 3|SC| and ϕB(π , π) 1. If |RI| < 3|SC|, then ϕ(π, π ) = ϕB(π, π )+ϕV (π, π )+ϕR(π, π ) 1+3|SC| (|RI|) = 3|SC| |RI| 1 0 and π is not more popular. We conclude that |RI| = 3|SC|. Before we conclude the proof, we show two auxiliary claims: 1. If B π (b3), then b1 / N(π , π) or b2 / N(π , π). 2. For j [2], if bj N(π , π), then bj π (b3) or |{s S : sj π (bj)}| |R| The first claim follows from the fact that if bj forms a coalition with an agent outside B that gives her positive utility, then b3 j cannot be both in this coalition and improve her utility. The second claim follows from vπ(bj) = α > |R| 3 1. We are ready to prove |R| = 3|SC|. We consider the agents in B. The only possibility for ϕ(π , π) > 0 is that ϕB(π , π) 1 which can only happen if {b1, b2} N(π , π). Due to the auxiliary claims, there exists j {1, 2} with |{s S : sj π (bj)} π (bj)| |R| 3 . If s {s S : sj π (bj)} \ SC, then s j N(π, π ) (using |R| 6, i.e., |π (bj) {s S : sj π (bj)}| 2).12 Consequently, ϕ(π, π ) = ϕB(π, π )+ϕV (π, π )+ϕR(π, π ) 1+(3|SC|+1) 3|SC| 0, a contradiction. Therefore, {s S : sj π (bj)} SC and |R| 3 |{s S : sj π (bj)}| |SC| = |RI| 3 . Consider the set S = SC. Then, SC covers R since RI = R. In addition, since |R| = 3|SC|, every agent r R is present in exactly one s SC. Hence, S is a partition of R with sets in S. In total, (R, S) is a Yes-instance of X3C. We first prove the existence of the graph that underlies the subsequent reductions for ASHGs. It satisfies similar properties as the flatmate game considered in Lemma 1. However, for the reduction to work, we need two sets of auxiliary agents. The first set corresponds to the 3-elementary sets in S of an instance (R, S) of X3C, while the second set 12. This argument is stronger than what is needed for ASHGs, but it is needed for the case of FHGs. Finding and Recognizing Popular Coalition Structures consists of two agents that allow the agents in the top-level not corresponding to elements of R to improve their coalition. Lemma 3. The class of symmetric ASHGs satisfies property PP. Proof. Let (R, S) be an instance of X3C. We construct the following game. Let k = min{k N: 2k |R|} define the smallest power of 2 that is larger than the cardinality of R. We define an ASHG on vertex set N = {ys 1, ys 2 : s S} {y1, y2} Sk j=0 Nj, where Nj = S2j i=1 Ai j consists of 2j sets of agents Ai j. We define the sets of agents as Ai k = {ai k, bi k, ci k} for i [2k], and Ai j = {ai j, bi j, ci j, αi j, βi j, γi j, δi j} for j [0, k 1], i [2j]. We order the set R in an arbitrary but fixed way, say R = {r1, . . . , r|R|}, and for a better understanding of the proof and the preferences, we label the agents bi k = ri for i [|R|]. If we view the set of agents N as k + 1 levels of agents, then the ground set R of the instance of X3C is identified with some specific agents in the top level k. We are ready to define the symmetric preferences as v(ys 1, ys 2) = 6k + 8 for all s S, v(ys 2, bi k) = 2k + 3 if there exists s S with ri s, v(y1, y2) = 1, v(y2, bi k) = 2k + 3, i [|R| + 1, 2k], v(bi k, bi k ) = 0, i, i [|R| + 1, 2k], v(bi k, bi k ) = 0, i, i [|R|], v(ai k, bi k) = v(ai k, ci k) = v(bi k, ci k) = k + 1, i [2k], For j [0, k 1], i [2k], v(ai j, bi j) = v(ai j, ci j) = j + 1, v(bi j, ci j) = j + 1.5, v(bi j, c2i 1 j+1 ) = v(bi j, c2i j+1) = j + 1.5, v(αi j, βi j) = j + 1, v(βi j, γi j) = 0, v(βi j, ai j) = j + 1.75, v(γi j, ai j) = j + 1.25, v(γi j, δi j) = j + 2, v(δi j, α2i 1 j+1 ) = v(δi j, α2i j+1) = j + 1.5, and v(g, h) = M 1 for all g, h N such that the utility is not defined, yet, where M is the maximum utility any agents could receive by the previous utilities. Brandt & Bullinger Let π = {{ai j, bi j, ci j}: j [0, k], i [2j]} {{αi j, βi j}, {γi j, δi j}: j [0, k 1], i [2j]} {{y1, y2}} {{ys 1, ys 2}: s S} and x = c1 0. Now consider a partition π = π . We will prove the following claim by induction over j = k, . . . , 0. For every i [2j] holds: 1. If {bi j, ai j} π(ci j) = , then ϕT i j (π , π) 1 and ϕT i j (π , π) 3 or {bi k : i [2k]} T i j N(π, π ). 2. If αi j / N(π, π ) and there exists an agent z T i j with π(z) = π (z). Then ϕT i j (π , π) 1. We will start by arguing, how the first part of the lemma follows from the induction claim. First, note that y1 / N(π, π ) and if y2 N(π, π ), then y1 N(π , π). Similarly, for all s S, ys 1 / N(π, π ) and if ys 2 N(π, π ), then ys 1 N(π , π). We can therefore focus on T 1 0 and have ϕ(π , π) ϕT 1 0 (π , π). Define ρ = {C T 1 0 : C π} and ρ = {C T 1 0 : C π }, which are the partitions π and π restricted to agents in T 1 0 . If ρ = ρ , then π = π can only happen if some agent outside T 1 0 forms a coalition with a former coalition of π in T 1 0 . Note that the only agents in T 1 0 that can improve by that are the agents of the type bi k. In every case, this will lead to ϕT 1 0 (π , π) 1. As we have argued above, this implies ϕ(π , π) 1. If ρ = ρ , we use the claim for the case j = 0 and observe that αi 0 / N(π, π ). Hence, ϕ(π , π) 1 also holds in this case. It needs still to be shown that if π(x) π (x) = {x}, then ϕ(π , π) 3 or (R, S) is a Yesinstance. Assume therefore that π(x) π (x) = {x}. By the first part of the induction claim, we conclude that ϕT 1 0 (π , π) 3 or {bi k : i [2k]} N(π, π ). Since we are done in the former case, we assume that {bi k : i [2k]} N(π, π ). This can only happen if, for every i 1, . . . , |R|, there exists an si S with ysi 2 π(bi k). Define S = {s S : π(ys 2) {bi k : i [2k]} = }. Now fix s S . Then, it holds that ys 1 / π(ys 2), because otherwise agents bi k π(ys 1) are worse off than in π . In particular, ys 1 N(π , π). Now, if at most two of the agents bi k corresponding two elements i s are in the coalition of ys 2, then ys 2 N(π , π). Together, ϕ(π , π) ϕ{y1,y2}(π , π) + ϕ{ys 1,ys 2}(π , π) + P s S\{s} +ϕ{ys 1 ,ys 2 }(π , π) + ϕT 1 0 (π , π) 0 + 2 + 0 + 1 = 3. It remains the case that π(ys 2) = {ys 2, bi k, bj k, bw k } for every s S with s = {i, j, w}. But then, S is a 3-partition of R by sets in S. We will now proceed with the proof of the induction claim. For the base case j = k, we observe that if Ai k N(π, π ) = , then clearly ϕAi k(π , π) 1. In addition, if {bi k, ai k} π(ci k) = , then {ai k, ci k} N(π , π) and bi k N(π , π) N(π, π ). For the induction step, let j {k 1, . . . , 0} and fix i [2j]. Assume first that there exists an agent z T i j with π(z) = π (z) but no such agent in Ai j. The premise of the first claim is vacuous and this part is therefore true. Since z T 2i 1 j+1 z T 2i j+1, we can apply induction for the second claim since the premise of the second claim for T 2i 1 j+1 or T 2i j+1 is true. Assume therefore that there exists an agent z Ai j with π(z) = π (z). We make the following observations. If αi j N(π, π ), then βi j N(π , π). Finding and Recognizing Popular Coalition Structures If βi j N(π, π ), then αi j N(π , π). If γi j N(π, π ), then δi j N(π , π). If δi j N(π, π ), then γi j N(π , π). Now, we consider the case that π(ai j) = π (ai j). We consider first the subcase that bi j N(π, π ). Then ci j N(π , π). If π(bi j) {c2i 1 j+1 , c2i j+1}, then ϕAi j(π, π ) 1 (with the above observations), while by induction ϕT 2i 1 j+1 T 2i j+1(π , π) 2 and ϕT 2i 1 j+1 T 2i j+1(π , π) 4 {bi k : i [2k]} (T 2i 1 j+1 T 2i j+1) N(π, π ) and we are done. Otherwise, ci j π(bi j). Then ϕAi j(π , π) 1 or ai j N(π, π ). The second case can only occur for π(ai j) = {ai j, βi j, γi j}. Hence, ϕAi j(π , π) 1 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1}. But then ϕAi j(π , π) 1 and ϕT 2i 1 j+1 T 2i j+1(π , π) 2 and we are done. We can even assume that bi j N(π , π), since otherwise ai j π(bi j) and ai j, ci j N(π , π) and it follows ϕAi j(π , π) 1. If ci j N(π, π ), then ai j, bi j N(π , π) and therefore ϕAi j(π , π) 1 and we are done. Since π(ci j) = π (ci j), we can assume that ci j N(π , π). Next, consider the case that ai j N(π, π ) and, by the previous cases, ci j, bi j N(π , π). If π(ai j) = {ai j, βi j, γi j}, then ϕAi j(π , π) 3 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1}. In the latter case, ϕAi j(π , π) 1 and ϕT 2i 1 j+1 T 2i j+1(π , π) 2 by induction and we are done. Otherwise, βi j π(ai j) N(π , π) or γi j π(ai j) N(π , π). In the former case, αi j N(π , π) and in total ϕAi j(π , π) 3. In the latter case, again, ϕAi j(π , π) 3 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1} and the case is similar as before. It remains that ai j, bi j, ci j N(π , π) in which case ϕAi j(π , π) 3. We may therefore assume that π(ai j) = π (ai j). Only for the remaining cases, we need that αi j / N(π, π ). If π(αi j) = π (αi j), then αi j, βi j N(π , π) and consequently ϕAi j(π , π) 2. If π(γi j) = π (γi j), then ϕAi j(π , π) 2 or ϕAi j(π, π ) 0 π(δi j) {α2i 1 j+1 , α2i j+1} = and the claim follows by induction. Brandt & Bullinger For the second part of the lemma, assume that S is a 3-partition of R through sets in S. Define π ={{bv k, bw k , bx k, ys 2}, {ys 1}: {rv, rw, rx} = s S } {{ys 1, ys 2}: s S \ S } {{b|R|+1 k , . . . , b2k k , y2}, {y1}} {{δi k 1, a2i 1 k , a2i k }: i [2k 1]} {{bi j, c2i 1 j+1 , c2i j+1}, {ai j, βi j, γi j}: j [k 1], i [2j]} {{δi j, α2i 1 j+1 , α2i j+1}: j [k 2], i [2j]} {{α1 0}, {c1 0}}. It is easily checked that ϕ(π , π ) = 1 and c1 0 forms a singleton coalition with c1 0 N(π , π ). Theorem 10. Checking whether there exists a strongly popular partition in a symmetric ASHG is co NP-hard. Proof. The reduction is from X3C. Given an instance (R, S) of X3C, we consider the symmetric ASHG of Lemma 3 on agent set N with utility function v together with the partition π and the special agent x N. Set M = max{P w N : v(y,w)>0 v(y, w): y N} and α = minw N : v(x,w)>0 v(x, w) > 0. We define a symmetric ASHG on agent set N = N {z} where the utilities are given by v (y, w) = v(y, w) if y, w N, v (z, x) = α/2, and v (z, y) = M 1 for y N \ {x}. Note that by Lemma 3, this reduction is in polynomial time. Consider the partition σ = π {{z}} and let σ = σ be given and define π = (σ \ σ(z)) {σ(z) \ {z}}, that is, the partition of agent set N where z leaves her coalition. We argue first that ϕN(σ , σ) ϕ(π , π) unless π(x) = π (x). Clearly, if z leaves a coalition, only the agent x can be worse. Now recall that x receives her unique top-ranked coalition in π , which means that x forms a coalition precisely with all agents that yield her positive utility. By the choice of v(x, z), the only coalition of x that z is part of and that is not worse for x, is π (x) {z}. Hence, the only case that the preferences of x over σ and σ is affected by z is if π(x) = π (x). We perform a case distinction over the coalitions of z to investigate the popularity margin between σ and σ. First, if σ(z) = {z}, then ϕ(σ , σ) > 0 by Lemma 3. If σ(z) = {z, x}, then ϕ(σ , σ) 1 + ϕ(π , π) 0 There, we can use the lemma again to see that the latter inequality is strict if (R, S) is a No-instance. Otherwise, z N(σ , σ). If π(x) = π (x), then ϕ(σ , σ) 1 + ϕ(π , π) 1. We can therefore assume that π(x) = π (x). If π = π , then ϕ(σ , σ) = ϕσ (z)(σ , σ) > 0. If π = π , then ϕ(σ , σ) 1 1 + ϕ(π , π) > 0, where the 1 accounts for the case that x may be worse off in π compared to σ. Note that it can not be the case that x is both better off in σ and worse off in π, since the only relevant coalition σ(x) = π (x) {z}. Together, it follows that σ is popular and it is a strongly popular partition if (R, S) is a No-instance. If (R, S) is a Yes-instance, then σ is the only candidate that might be strongly popular. Consider the partition π from Lemma 3 and define σ = (π \ {{x}}) {{x, z}}. Then, x N(π , π ) N(σ , σ ), whereas z N(σ , σ ). Therefore, ϕ(σ , σ ) = 1 + ϕ(π , π ) = 0. Hence, π is not strongly popular and there exists no strongly popular partition. Theorem 11. Verifying whether a given partition in a symmetric ASHG is strongly popular is co NP-complete. Finding and Recognizing Popular Coalition Structures Proof. In the proof of Theorem 10, the partition σ is strongly popular if, and only if, (R, S) is a No-instance of X3C. Theorem 12. Computing a mixed popular partition in a symmetric ASHG is NP-hard. Proof. We give a Turing reduction from X3C. Given an instance (R, S) of X3C, we consider the symmetric ASHG of Lemma 3 on agent set N with utility function v together with the partition π and the special agent x N. Set M = max{P w N : v(y,w)>0 v(y, w): y N} and α = minw N : v(x,w)>0 v(x, w) > 0. We define a symmetric ASHG on agent set N = N {z1, z2} where the utilities are given by v (y, w) = v(y, w) if y, w N, v (z1, z2) = v (z1, x) = v (z2, x) = α/3 > 0, and v (zi, y) = M 1 for i [2], y N \ {x}. Note that by Lemma 3, this reduction is in polynomial time. Consider the partition σ = π {{z1, z2}} and let σ = σ be given and define π = (σ \ (σ(z1) σ(z2))) {σ(z1) \ {z1, z2}, σ(z2) \ {z1, z2}}, that is, the partition of agent set N where z1 and z2 leave their coalitions. Assume that (R, S) is a No-instance. We will prove that ϕ(σ , σ) > 0, and therefore that σ is strongly popular. We may assume that σ(z1) = {z1, z2} or x σ(zi) for some i, because otherwise it is a Pareto improvement if z1 and z2 leave their coalitions and form a coalition of their own. If σ(z1) = {z1, z2}, then by Lemma 3, ϕ(σ , σ) = ϕ(π , π) > 0, because π = π . Otherwise, assume without loss of generality that x σ(z1). Since x receives her topranked coalition in π and the utility provided by agents zi is sufficiently small, ϕN(σ , σ) ϕ(π , π) 1, where equality can only hold for π (x) = π(x). Now, if π(z1) {x, z1, z2}, then ϕ(σ , σ) 2 + ϕ(π , π) 1. If there exists y N \ {x} with y σ(z1), then z1, z2 N(σ , σ) and it follows ϕ(σ , σ) 2 1 + ϕ(π , π) > 0. In particular, the unique mixed popular partition consists of σ with probability 1. Now assume that (R, S) is a Yes-instance. Consider the partition π from Lemma 3 and define σ = (π \ {{x}}) {{x, z1, z2}}. Then, x N(π , π ) N(σ , σ ), whereas z1, z2 N(σ , σ ). Therefore, ϕ(σ , σ) = 2 + ϕ(π , π ) = 1. Hence, the pure mixed partition {σ } is not mixed popular. We can solve X3C by computing a partition σ in the support of a mixed popular partition and checking its probability in case σ = σ . Theorem 13. Checking whether there exists a popular partition in a symmetric ASHG is co NP-hard. Proof. We provide a reduction from X3C. Given an instance (R, S) of X3C, we consider the symmetric ASHG of Lemma 3 on agent set N with utility function v together with the partition π and the special agent x N. Set M = max{P w N : v(y,w)>0 v(y, w): y N} and α = minw N : v(x,w)>0 v(x, w) > 0. For i [2], let Ni = {yi : y N} be two copies of N. Accordingly, let π i be their respective copies of π . We define a symmetric ASHG on agent set N = N1 N2 Z where Z = {zj k : k [2], j [3]}. Define Zj = {zj 1, zj 2}. Utilities are as follows. v (yi, wi) = v(y, w) if y, w Ni for i [2], v (zj k, x1) = α/7, v (zj k, x2) = α/8 for k [2], j [3], Brandt & Bullinger v (zj 1, zj 2) = α for j [3], and v (u, y) = M 1 for every pair of agents u, y N such that their utility is not defined, yet. Note that by Lemma 3, this reduction is in polynomial time. First assume that (R, S) is a No-instance. Then, σ = π 1 π 2 {Zj : j [3]} is popular. To prove this, let σ be an arbitrary partition and define πi = {σ(y) Ni : y Ni} be the coalitions restricted to Ni. For each j [3], we can assume that σ(zj k) = Zj or there exists a i [2] with Zj σ(xi) = . Otherwise, one can obtain a Pareto-improvement σ over σ and it suffices to prove that ϕ(σ , σ ) 0. Indeed, if σ(zj k) = {zj k} for k [2], then creating Zj is a Pareto-improvement. On the other hand, if {z3 k, x1, x2} σ(zj k) = and |σ(zj k)| 2, then leaving her coalition with zj k yields a Pareto-improvement over σ. Hence, if x1, x2 / σ(zj k), then zj 3 k σ(zj k) and putting all potential further agents in the coalition into a singleton coalition would yield a Pareto improvement. Hence, we have already substantially restricted the coalitions of agents in a Zj. Next, we argue that we may assume that it does not happen that σ(zj k) = {zj k}. In this case, there exists an i [2] with zj 3 k σ(xi). We form a partition σ by adding zj k to σ(zj 3 k) = σ(xi). This yields a Partition with N(σ , σ) N(σ , σ ) and N(σ , σ ) N(σ, σ ), hence ϕ(σ , σ ) ϕ(σ , σ), and it suffices to consider the popularity margin between σ and σ . By a similar argument, we can assume that σ(xi) Z Ni (putting all agents outside Z Ni into singleton coalitions has the same effect). We can therefore partition the agent set N into sets of the type Zj such that σ(zj 1) = Zj, of the type Ni such that Z σ(xi) = , and of the type Ni σ{xi} such that Z σ(xi) = . For the first type, ϕZj(σ , σ) = 0 and by Lemma 3, ϕNi(σ , σ) 0 for the second type of sets. We prove that ϕNi σ{xi}(σ , σ) 0 if Z σ(xi) = . If σ(xi) Z {xi}, then xi N(σ , σ) and ϕσ(xi)\{xi}(σ , σ) 2. As a consequence, ϕNi σ(xi)(σ , σ) 2 + ϕ(π i , πi) 0 by Lemma 3. Otherwise, Z σ(xi) N(σ , σ) and the only agent in Ni that can be worse off in πi compared to σ is xi. Note that the utilities are designed so that xi / N(σ, σ ) N(π , π). It follows ϕNi σ(xi)(σ , σ) = ϕNi(σ , σ)+ϕσ(xi) Z(σ , σ) ϕNi(σ , σ)+1 1+ϕ(π i , πi)+1 0. Together, it is shown that σ is popular. Conversely, assume that (R, S) is a Yes-instance and assume for contradiction that σ is popular and define πi = {σ(y) Ni : y Ni} as above. The Pareto-improvements of the first implication show that for all j, Zj σ or σ(xi) Zj = . Define I = {i [2]: Z σ(xi) = }. The first crucial step is to prove that for all i I, it holds that there exists a j [3] with σ(xi) = {xi} Zj. Let therefore i I. First, σ(xi) Ni = {xi} since otherwise splitting σ(xi) into singleton coalitions is more popular. In addition, x3 i / σ(xi). If this happens and |σ(xi) Z| = 2, then splitting into singleton coalitions is more popular. On the other hand, if |σ(xi) Z| = 2, there exists j [3] with Zj σ. We form the partition σ by leaving her coalition with x1 and forming {x1, zj 1 , zj 2 }. Then, {x1, x2, zj 1 , zj 2 } N(σ , σ) while N(σ, σ ) σ(xi) Z. Hence, σ is more popular. Finding and Recognizing Popular Coalition Structures Hence, σ(xi) Z {xi}. If for j = j , Zj σ(xi) = and Zj σ(xi) = , then dissolving σ(xi) is again more popular. Finally, if |σ(xi) Z| = 1, we find again a j [3] with Zj σ. We form the partition σ by forming π(xi) Z and {xi, zj 1 , zj 2 } which is more popular. The next step is to show that I = {1, 2}. Assume for contradiction that Z σ(xi) = . Then we can assume that for all y Ni, σ(y) Ni. If πi = π i , then replacing πi by π i is more popular (by Lemma 3). Otherwise πi = π i and we consider the partition π i of the last part of Lemma 3 for Ni. By the pigeon hole principle, there exists a j [3] with Zj σ. We obtain σ = (σ \ (πi {Zj })) ((π i \ {{xi}}) {{xi, zj 1 , zj 2 }}). Then, ϕ(σ , σ) = ϕNi Zj (σ , σ) = 1 + 2 = 1 and σ is more popular. Together, we can assume that there exist j1, j2 [3] with σ(xi) = {xi, zji 1 , zji 2 }, for i [2]. Let j3 [3] \ {j1, j2} be the third index. Note that Zj3 σ. Define σ = (σ \ {σ(zj 1): j [3]}) {{x1, zj2 1 , zj2 2 }, {x2, zj3 1 , zj3 2 }, Zj1}. Then, N(σ , σ) = Zj2 Zj3 while N(σ, σ ) = Zj1. Hence, σ is more popular. All in all, it is shown that there exists no popular partition if (R, S) is a Yes-instance. This concludes the proof of the theorem. A.3 Fractional Hedonic Games Theorem 14. Checking whether there exists a popular partition in a symmetric FHG is NP-hard, even if all utilities are non-negative. Proof. The reduction is from X3C to deciding whether there exists a popular partition. Let (R, S) be an instance of X3C. We transform it into an FHG (N, ) defined by the graph G = (N, E) that is given as follows: N = {cr, lr j : r R, j [6]} {ys, zs j : s S, j [2]} and E = ER EC E6 ES where ER = {{cr, lr j}: r R, j [6]}, EC = {{lr 6, ys}: s S, r s}, E6 = {{lr 6, lt 6}: r = t, r, t s for s S}, ES = {{ys, zs j}, {zs 1, zs 2}: s S, j [2]}. The edge set EC connects the gadgets for the ground set and the subsets for the X3C instance. The weights are 1, except v(e) = 1 2 for e EC and v(e) = 1 4 for e E6. A schematic of the reduction for a certain set s = {i, j, k} S is depicted in Figure 6. We show that there exists a popular partition of (N, ) if and only if (R, S) is a Yesinstance of X3C. Assume (R, S) is a Yes-instance of X3C. Then, there exists S S such that S is a partition of R. Consider the partition π = {{cr, lr 1, lr 2, lr 3}: r R} {{lr j}: r R, j = 4, 5} {{ys, li 6, lj 6, lk 6}: s = {i, j, k} S } {{zs 1, zs 2}: s S } {{ys, zs 1, zs 2}: s S \ S }. We claim that π is popular. Assume for contradiction that π is more popular than π and let π be with ϕ(π , π) maximal. We will prove that ϕ(π, π ) 0, deriving a contradiction. We introduce some notation for the proof. Let V r = {cr, lr j : j [6]}, where r R, and W s = {ys, zs 1, zs 2}, where s S. Also denote V R = r RV r, W S = s SW s and A6 = {lr 6 : r R} and Y c = {s S : a A6 with a π (ys)}. To derive a contradiction, we prove several claims. 1. Let r R such that, for all s S with r s, it holds that ys / π (lr 6). Then, ϕV r(π, π ) 1. Brandt & Bullinger s = {i, j, k} Figure 6: Reduction for existence problem of popular partitions in FHGs. The schematic displays the part of the network corresponding to one specific set s = {i, j, k}. 2. There exist no r R, s, s S with s = s and {ys, ys } π (lr 6). 3. For all s S, it holds that π (ys) W s = {ys} or π (ys) W s. 4. For all r R, ϕV r(π, π ) 0. 5. It holds that ϕW S(π , π) |R| 3|Y c|. The first claim says that we need sufficient external influence for V r to be locally popular. The second and third claim give insight on the structure of potential more popular partitions. The forth claim shows that we locally do best for every V r. The final claim calculates the tradeoff between forming a coalition W s and joining the agents in V r. In order to complete the proof from the claims, we apply Claims 1 and 4 to obtain ϕV R(π, π ) max{0, |R| 3|Y c|} |R| 3|Y c|. Combining this inequality with the one of Claim 5 yields ϕ(π, π ) 0. The first claim is a straightforward case distinction considering π (cr). Observe that by construction of her neighboring agents, lr 6 N(π, π ) or lr 6 π (cr). This property makes lr 6 play an equivalent role compared to the agents lr 5 and lr 4 in the analysis. We proceed with the second claim. Therefore, assume for contradiction that r R, s, s S with s = s and {ys, ys } π (lr 6). We denote C = π (lr 6) for this part. We claim that we can change π while strictly increasing ϕ(π , π). This is done by forming a partition π that consists of coalitions W t whenever yt C. The agents outside W S in C form a coalition of their own. Other coalitions are not changed. Let t S with yt C. If π(yt) = W t, then W t N(π, π ). This is immediate for the zt j. In addition, by assumption on C, at least 3 agents are present, and the utility is estimated as vyt(π ) max{ 7 2 7 } = 1 If π(yt) = W t, then zt 1, zt 2 / N(π , π) and yt / N(π , π) ( i : zt i N(π, π )). Finding and Recognizing Popular Coalition Structures Define Y = |{t S : yt C}|. These first two insights yield, that ϕ{W s:s Y }(π , π) 3|Y | + ϕ{W s:s Y }(π , π). There is an increase of at least 6 by the assumption that {ys, ys } C. The only agents that can decrease (π , π) compared to (π , π) are in A6. Note that if a A6 C has at most one neighbor in Y , then for some p (the number of neighbors in A6), va(π ) = 4 = va(π). Define the improving agents in A6 via I = C A6 N(π , π) and the non-worsened agents as I = C A6 \(I N(π, π )). If |I| 2, then ϕC A6(π , π) ϕC A6(π , π) 4 (the agents in I each counted twice for being worse instead of better off). If |I| 3, we know that |Y | 3 (otherwise, three agents in I are incident to the same two yt, but then in the instance of X3C, we had two identical 3-elementary sets). This means for any a A6 C that has exactly two neighbors in Y that for some p, va(π ) 1+ p 4. Hence, a / N(π , π). Agents in I need therefore three neighbors in Y and agents in I two. Since every agent in Y has at most three neighbors, this accumulates to |Y | |I| + 2 3|I |. Consequently, for M = C (A6 W S), ϕ(π , π) = ϕN\M(π , π) + ϕC A6(π , π) + ϕW S C(π , π) ϕN\M(π , π) + ϕC A6(π , π) 2|I| |I | + ϕW S C(π , π) + 3|Y | > ϕ(π , π). In both cases, we contradict the maximality of ϕ(π , π). The third claim is proven similarly, but we have to refine some calculation of the previous claim, since we do not get the same lower bounds for the denominators of the utilities. Assume for contradiction that s S with π (ys) A6 = and π (ys) W s = . We set C = π (ys). First, we argue that we may assume that A6 C N(π , π) = . Otherwise, by the previous claim, if lr 6 A6 C N(π , π), then cr C. Consequently, lr j N(π, π ) for j [3] and cr N(π, π ). The latter is due to vcr(π ) 6 4 = vcr(π). Also, there exists j {4, 5} : lr j / C or lr 6 / N(π , π). Indeed, if the first is wrong, then for some p, vlr 6(π ) 1+ 1 4 = vlr 6(π). Hence resetting the coalition within V r to π yields a coalition contradicting the maximality of ϕ(π , π). Now, we consider two cases. First assume that π(ys) = W s. We claim that rearranging π by means of removing agents of W s from π (ys) improves ϕ(π , π). Indeed, zs j / N(π , π), but they will be after the rearrangement, and ys N(π , π) afterwards. Also, for all a A6 C, va(π ) 4 and these agents are already worse off in the original π . If π(ys) = W s, the same holds for agents in A6 C. Since W s N(π, π ), the same rearrangement improves ϕ(π , π). Brandt & Bullinger We proceed with the next claim and fix r R. We may assume that for some s, ys π (lr 6) (since the other case is already covered in the first claim). In addition, if cr / π (lr 6), then lr 6 / N(π , π) (by the previous claims). In this case, the coalition π restricted to V r \ {lr 6} is popular and the claim is true. Denote C = π (lr 6) and assume therefore cr C. We also know that {lr 1, lr 2, lr 3} N(π , π) = and |{lr 1, lr 2, lr 3} N(π, π )| 2. Consequently, if {lr 4, lr 5} C = , we are done. If {lr 4, lr 5} C = , {lr 1, lr 2, lr 3} N(π, π ). Hence, in the final case, |N(π , π)| 3 while |N(π, π )| 3 and the claim is true. For the fifth claim, we consider the coalitions in π for different ys: If W s = π(ys), then W s N(π , π) = (by Claim 3) and if s Y c, then W s N(π, π ). This gives |N(π, π ) W S| 3|{s Y c : π(ys) = W s}|. If W s = π (ys) and s Y c, then W s N(π , π) = (again using Claim 3). Consequently, |N(π , π) W S| 3|{s / Y c : π(ys) = W s}|. Combining the inequalities yields |N(π , π) W S| |N(π, π ) W S| 3(|{s / Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}|) = 3(|{s / Y c : π(ys) = W s}| + |{s Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}| |{s Y c : π(ys) = W s}|) = 3|S | 3|Y c| = |R| 3|Y c|. This proves the final claim and we have proved that Yes-instances of X3C map to popular partitions of the FHG. For the reverse implication, assume that π is a popular partition. We exhibit the coalitions of the agents in A6. 1. For all r R, there exists a unique s S with ys π(lr 6). For this s holds that r s. 2. For all r R, |A6 π(lr 6)| = 3. If the claims are true, S = {s S : A6 π(ys) = } covers R due to existence and is a partition due to uniqueness and the fact, that uniqueness and the second claim imply that the coalition of the unique ys must contain precisely li 6 for i s. We start with the first claim. Existence is clear because otherwise the subpartition of π on V r (possibly restricted to V r) is popular on V r, contradicting Proposition 11. For uniqueness, assume for contradiction that there is r R and s = s S with {ys, ys } π(lr 6). We obtain a more popular coalition π as follows: remove the agents in W s from their partitions in π and let them form a coalition. Then W s {ys } N(π , π) and N(π, π ) {lr 6 : r s}. Hence, π is more popular. For the second claim, we know due to uniqueness in the first claim that |A6 π(lr 6)| 3. Assume for contradiction that |A6 π(lr 6)| < 3 and let ys π(lr 6). Then, the same coalition π as in the proof of the previous claim is more popular. This time, W s N(π , π) and N(π, π ) {lr 6 : r s}, hence by assumption |N(π, π )| 2. Finding and Recognizing Popular Coalition Structures i j k x y z s = {i, j, k} t = {x, y, z} V Figure 7: Schematic of the reduction for the verification problem of popular partitions on bipartite FHGs. The bipartition is indicated by the shapes of the agents. The partition π under consideration is marked in gray. Theorem 15. Checking whether a given partition in a symmetric FHG is popular is co NPcomplete, even if all utilities are non-negative and the underlying graph is bipartite. Proof. First of all, the verification problem is in co NP, because a more popular partition serves as a polynomial-time certificate for a No-instance. For hardness, we reduce again from X3C. Given an instance (R, S) of X3C, we assume without loss of generality that |R| 6. We define an FHG (N, ) given by the underlying graph G = (N, E) depicted in Figure 7 and defined as: N = R {s1, s2, s3 : s S} {b1, b2, b3}, E = {{s3, r}: r R s} {{s1, s3}, {s2, s3}: s S} {{sj, bj}: s S, j [2]} {{b1, b3}, {b2, b3}}. The symmetric weights v are given as v(i, s3) = 1 v(s1, s3) = v(s2, s3) = 1 for s S, v(sj, bj) = 1 4 for s S, j [2], and v(b1, b3) = v(b2, b3) = α for 3(|R| 3) 4|R| < α < 3|R| 4(|R|+3). One can choose α with a size bounded polynomially in the input size. For the reduction, only the above bounds matter. We introduce the same notation as in the proof for ASHGs. Denote V s = {s1, s2, s3} for s S, B = {b1, b2, b3}, and V = s SV s. G is bipartite with bipartition (R {s1, s2 : s S} {b3}, {s3 : s S} {b1, b2}) and all weights on present edges are positive. The verification problem is asked for the partition π = {V s : s S} {{r}: r R} {B}. We claim that (R, S) is a Yes-instance of X3C if and only if π is not popular for the FHG given by G. Brandt & Bullinger If (R, S) is a Yes-instance, there exists a subset S S that partitions R. In particular |R| = 3|S |. Consider the partition given by π = {V s : s S \ S } {{s3, i, j, k}: {i, j, k} = s S } {{bj, sj : s S }: j [2]} {{b3}}. Then, for j [2], vbj(π ) = 1 4 |S | |S |+1 = |R| 4(|R|+3) > α 3 = vbj(π). Since all agents in R have clearly improved their utility, R {b1, b2} N(π , π) (and in fact equality holds here). Moreover, the utilities of agents in V s for s S \ S have not changed. Consequently, N(π, π ) s S V s {b3}. Hence, π is more popular than π. Conversely, assume that there exists a more popular partition π and fix one that maximizes ϕ(π , π). We have to prove that there exists a subset S S that yields a partition of R. First, we make the observation that if bj N(π , π) for j [2], then b3 N(π, π ). Hence, ϕB(π , π) 1. Second, we claim that for all s S, N(π , π) V s = . Clearly, s3 / N(π , π) (by construction, since she receives a top coalition with respect to the given utilities). Assume for j [2], sj N(π , π). Then, π (sj) = {sj, s3, bj}. Note that both neighbors of sj are needed to improve utility, but no other agent may be present since for |π (sj)| 4 follows 3 = vsj(π). In addition, s3 j, b3 N(π, π ). We form a new coalition π from π by having the coalitions V s and B and all other coalitions remain the same. The exact same case distinction for b3 j as in the case of ASHGs yields a contradiction to the maximality condition on π . The remainder of the proof follows a similar strategy as the one for ASHGs, but some arguments are more tedious. To make this more formal, we introduce the sets RI = R N(π , π) of agents in R that form a coalition with a neighbor in π and SC = {s S : π (s3) R = }. The latter is the set of critical sets in S whose corresponding agents s3 form a coalition with agents in R. We split it into SC,1 = {s S : |π (s3) R| = 1} and SC,2 = SC \ SC,1. We have the following facts: For s SC, s3 N(π, π ). For s SC,1, s1 N(π, π ) s2 N(π, π ). For s SC,2, s1 N(π, π ) s2 N(π, π ). Consequently, |N(π, π ) V | 2|SC,1| + 3|SC,2|. In addition, |N(π , π) R| = |RI| |SC,1| + 3|SC,2|. If SC,1 = , then ϕ(π, π ) = ϕB(π, π ) + ϕV (π, π ) + ϕR(π, π ) 1 + 2|SC,1| + 3|SC,2| (|SC,1| + 3|SC,2|) = |SC,1| 1 0 and π is not more popular. We conclude that SC,1 = or equivalently SC = SC,2. A similar calculation excludes the case |RI| < 3|SC,2| which means |RI| = 3|SC,2|. We claim that in fact |R| = 3|SC| = 3|SC,2|. Before we prove this, we show the same two auxiliary claims as for ASHGs. 1. If B π (b3) then b1 / N(π , π) b2 / N(π , π). 2. For j [2], if bj N(π , π), then bj π (b3) |{s S : sj π (bj)} π (bj)| |R| Finding and Recognizing Popular Coalition Structures For the first claim, assume that B π (b3) and b1, b2 N(π , π). Denote pj = |{s S : sj π (b3)}|. We know that pj 1, since otherwise bj / N(π , π). The function x 7 3(x 3) 4x is monotonically increasing for x > 0. Thus, by the lower bound on α, we know that α > 3 8 (using |R| 6). Let j [2] with pj = min{pj, p3 j}. Then |π (b3)| 3 + 2pj. We compute vbj(π) vbj(π ) = α 4 3+2pj = pj 3(3+2pj)(2α 3 4) > 0. Hence, bj / N(π , π), a contradiction. For the second claim, let j [2] with bj N(π , π) and assume bj / π (b3). Similarly as before, let p = |{s S : sj π (bj)}|. Note that vbj(π) = α Therefore, vbj(π) < vbj(π ) 1 4 p p+1 only if p > |R| 3 1 and since p is an integer, this implies 3 . The remainder of the proof is identical to the one for ASHGs (Theorem 9). Lemma 4. The class of symmetric FHGs with non-negative utility functions satisfies property PP. Proof. Let (R, S) be an instance of X3C. We construct the following game. Let k = min{k N: 2k |R|} define the smallest power of 2 that is larger than the cardinality of R. We define a symmetric FHG with non-negative utility functions on vertex set N = {ys 1, ys 2 : s S} {y1, y2} Sk j=0 Nj, where Nj = S2j i=1 Ai j consists of 2j sets of agents Ai j. We define the sets of agents as Ai k = {ai k, bi k, ci k} for i [2k], and Ai j = {ai j, bi j, ci j, αi j, βi j, γi j, δi j} for j [0, k 1], i [2j]. We order the set R in an arbitrary but fixed way, say R = {r1, . . . , r|R|} and for a better understanding of the proof and the preferences, we label the agents bi k = ri for i [|R|]. If we view the set of agents N as k + 1 levels of agents, then the ground set R of the instance of X3C is identified with some specific agents in the top level k. We are ready to define the preferences. v(ys 1, ys 2) = 21 10(k + 1) for all s S, v(ys 2, bi k) = 3 2(k + 1) if there exists s S with ri s, v(y1, y2) = 1, v(y2, bi k) = 2k+2(k + 1), i [|R| + 1, 2k], v(bi k, bi k ) = 0, i, i [|R| + 1, 2k], v(bi k, bi k ) = 2 3(k + 1), i, i [|R|], v(ai k, bi k) = v(ai k, ci k) = v(bi k, ci k) = k + 1, i [2k], For j [0, k 1], i [2k], Brandt & Bullinger v(ai j, bi j) = v(ai j, ci j) = j + 1, v(bi j, ci j) = j + 1.5, v(bi j, c2i 1 j+1 ) = v(bi j, c2i j+1) = j + 1.5, v(αi j, βi j) = j + 1, v(βi j, γi j) = j v(βi j, ai j) = j + 1.75, v(γi j, ai j) = j + 1.25, v(γi j, δi j) = j + 2, v(δi j, α2i 1 j+1 ) = v(δi j, α2i j+1) = j + 1.6, and v(g, h) = 0 for all g, h N such that the utility is not defined, yet. Let π = {{ai j, bi j, ci j}: j [0, k], i [2j]} {{αi j, βi j}, {γi j, δi j}: j [0, k 1], i [2j]} {{y1, y2}} {{ys 1, ys 2}: s S} and x = c1 0. Now consider a partition π = π . We will prove the following claim by induction over j = k, . . . , 0. For every i [2j] holds: 1. If {bi j, ai j} π(ci j) = , then ϕT i j (π , π) 1 and ϕT i j (π , π) 3 or {bi k : i [2k]} T i j N(π, π ). 2. If αi j / N(π, π ) and there exists an agent z T i j with π(z) = π (z). Then ϕT i j (π , π) 1. We will start by arguing, how the first part of the lemma follows from the induction claim. First, note that y1 / N(π, π ) and if y2 N(π, π ), then y1 N(π , π). Similarly, for all s S, ys 1 / N(π, π ) and if ys 2 N(π, π ), then ys 1 N(π , π). We can therefore focus on T 1 0 and have ϕ(π , π) ϕT 1 0 (π , π). Define ρ = {C T 1 0 : C π} and ρ = {C T 1 0 : C π }, which are the partitions π and π restricted to agents in T 1 0 . If ρ = ρ , then π = π can only happen if some agent outside T 1 0 forms a coalition with a former coalition of π in T 1 0 . Note that the only agents in T 1 0 that can improve by that are the agents of the type bi k. In every case, this will lead to ϕT 1 0 (π , π) 1. As we have argued above, this implies ϕ(π , π) 1. If ρ = ρ , we use the claim for the case j = 0 and observe that αi 0 / N(π, π ). Hence, ϕ(π , π) 1 also holds in this case. It needs still to be shown that if π(x) π (x) = {x}, then ϕ(π , π) 3 or (R, S) is a Yes-instance. Assume therefore that π(x) π (x) = {x}. By the first part of the induction claim, we conclude that ϕT 1 0 (π , π) 3 or {bi k : i [2k]} N(π, π ). Since we are done in the former case, we assume that {bi k : i [2k]} N(π, π ). This can only happen if, for every i 1, . . . , |R|, there exists an si S with ysi 2 π(bi k). Indeed, if this is not the case, then the utility of bi k is bounded by 2(k+1)+ 2λ 3 (k+1) 3+λ = 2 3(k + 1) = vbi k(π ), where λ = |{bj k : j [|R|]} (π(bi k) \ {bi k})|. Note that the equality is true for every λ 0. Hence, bi k / N(π, π ). Define S = {s S : π(ys 2) {bi k : i [|R|]} = }. Now fix s S and define C = π(ys 2). We deal first with the case that ys 1 C and let ri R with bi k C. We claim that ai k, ci k C. Otherwise, for some λ 0, vbi k(π) 3 2 (k+1)+(k+1)+ 2λ 3 (k+1) 4+λ < 2 3(k + 1) = vbi k(π ), and bi k / N(π, π ), which is a contradiction. Hence, ai k, ci k C. If ys 2 N(π , π), we are Finding and Recognizing Popular Coalition Structures done, because then ϕ(π , π) ϕ{y1,y2}(π , π)+ϕ{ys 1,ys 2}(π , π)+P s S\{s} +ϕ{ys 1 ,ys 2 }(π , π)+ ϕT 1 0 (π , π) 0 + 2 + 0 + 1 = 3. Now, if C {bj k : j [|R|]} = {bi k}, then vys 2(π) 21 10 (k+1)+ 3 2 (k+1) 5 < 21 20(k + 1) = vys 2(π ), but we already excluded that. Thus, there is i = i with bi k C. It is easy to see that bi k N(π , π), which is contradicting our assumption that {bi k : i [2k]} N(π, π ). This concludes the case that ys 1 C and we assume henceforth that, for all s S , ys 1 / C. Let I = s {ri R: bi k C} the set of members of s whose corresponding agents are in the coalition C. If |I| 2, then vys 2(π) 3 = k+1 < 21 20(k+1) = vys 2(π ). However, it is already excluded that ys 2 N(π , π). Hence, |I| = 3. In other words, π(ys 2) = {ys 2, bi k, bj k, bw k } with s = {i, j, w}. We conclude that S is a 3-partition of R by sets in S. We will now proceed with the proof of the induction claim. For the base case j = k, fix i [2k] and assume that Ai k / π. We observe that if Ai k N(π, π ) = , then clearly ϕAi k(π , π) 1. If Ai k N(π, π ) = , then {ai k, ci k} N(π , π) and ϕAi k(π , π) 1. If in addition {bi k, ai k} π(ci k) = , then bi k N(π , π) N(π, π ) and the first part of the claim follows. For the induction step, let j {k 1, . . . , 0} and fix i [2j]. Assume first that there exists an agent z T i j with π(z) = π (z) but no such agent in Ai j. The premise of the first claim is vacuous and this part is therefore true. Since z T 2i 1 j+1 z T 2i j+1, we can apply induction for the second claim since the premise of the second claim for T 2i 1 j+1 or T 2i j+1 is true. Assume therefore that there exists an agent z Ai j with π(z) = π (z). We make the following observations. If αi j N(π, π ), then βi j N(π , π). If βi j N(π, π ), then αi j N(π , π). If γi j N(π, π ), then δi j N(π , π). If δi j N(π, π ), then γi j N(π , π). Now, we consider the case that π(ai j) = π (ai j). We consider first the subcase that bi j N(π, π ). Then ci j N(π , π). If π(bi j) {c2i 1 j+1 , c2i j+1}, then ϕAi j(π, π ) 1 (with the above observations), while by induction ϕT 2i 1 j+1 T 2i j+1(π , π) 2 and ϕT 2i 1 j+1 T 2i j+1(π , π) 4 {bi k : i [2k]} (T 2i 1 j+1 T 2i j+1) N(π, π ) and we are done. Otherwise, ci j π(bi j) and π(bi j) {c2i 1 j+1 , c2i j+1} = . Then ϕAi j(π , π) 1 or ai j N(π, π ). We only need to consider the second case. Assume for contradiction that ai j π(bi j). Then, π(bi j) {βi j, γi j} = (otherwise, ai j N(π , π)). Then, vbi j(π) 3j+4 3 = vbi j(π ), contradicting our assumption on bi j (note that we used that π(bi j) {c2i 1 j+1 , c2i j+1}). Therefore, ai j / π(bi j) and therefore π(ai j) = {ai j, βi j, γi j}. Hence, ϕAi j(π , π) 1 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1}. But then ϕAi j(π , π) 1 and ϕT 2i 1 j+1 T 2i j+1(π , π) 2 and we are done. Brandt & Bullinger We can even assume that bi j N(π , π), since otherwise ai j π(bi j) and ai j, ci j N(π , π) and it follows ϕAi j(π , π) 1. If ci j N(π, π ), then ai j, bi j N(π , π) and therefore ϕAi j(π , π) 1 and we are done. Since π(ci j) = π (ci j), we can assume ci j N(π , π) Next, consider the case that ai j N(π, π ) and, by the previous cases, ci j, bi j N(π , π). If π(ai j) = {ai j, βi j, γi j}, then ϕAi j(π , π) 3 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1}. In the latter case, ϕAi j(π , π) 1 and ϕT 2i 1 j+1 T 2i j+1(π , π) 2 by induction and we are done. Otherwise, βi j π(ai j) N(π , π) or γi j π(ai j) N(π , π). In the former case, αi j N(π , π) and in total ϕAi j(π , π) 3. In the latter case, again, ϕAi j(π , π) 3 or π(δi j) = {δi j, α2i 1 j+1 , α2i j+1} and the case is similar as before. Note that ai j is not indifferent between π(ai j) and π (ai j), because π(ai j) = π (ai j). It remains that ai j, bi j, ci j N(π , π), in which case ϕAi j(π , π) 3. We may therefore assume that π(ai j) = π (ai j). Only for the remaining cases, we need that αi j / N(π, π ). If π(αi j) = π (αi j), then αi j, βi j N(π , π) and consequently ϕAi j(π , π) 2. If π(γi j) = π (γi j), then ϕAi j(π , π) 2 or ϕAi j(π, π ) 0 π(δi j) {α2i 1 j+1 , α2i j+1} = and the claim follows by induction. For the second part of the lemma, assume that S is a 3-partition of R through sets in S. Define π ={{bv k, bw k , bx k, ys 2}, {ys 1}: {rv, rw, rx} = s S } {{ys 1, ys 2}: s S \ S } {{b|R|+1 k , . . . , b2k k , y2}, {y1}} {{δi k 1, a2i 1 k , a2i k }: i [2k 1]} {{bi j, c2i 1 j+1 , c2i j+1}, {ai j, βi j, γi j}: j [k 1], i [2j]} {{δi j, α2i 1 j+1 , α2i j+1}: j [k 2], i [2j]} {{α1 0}, {c1 0}}. It is easily checked that ϕ(π , π ) = 1 and that c1 0 forms a singleton coalition with c1 0 N(π , π ). Theorem 16. Checking whether there exists a strongly popular partition in a symmetric FHG is co NP-hard, even if all utilities are non-negative. Proof. The reduction is from X3C. Given an instance (R, S) of X3C, we consider the symmetric, non-negative FHG of Lemma 4 on agent set N with utility function v together with the partition π and the special agent x N. We define a symmetric, non-negative FHG on agent set N = N {z} where the utilities are given by v (y, w) = v(y, w) if y, w N, v (z, x) = vx(π )/2, and v (z, y) = 0 for y N \{x}. Note that by Lemma 4, this reduction is in polynomial time. Finding and Recognizing Popular Coalition Structures Consider the partition σ = π {{z}} and let a partition σ = σ of N be given. Define π = (σ\σ(z)) {σ(z)\{z}}. Note that every agent y N \{x} can only improve her utility if z leaves her coalition. In addition, the utility v(x, z) is designed so that x still receives her unique top-ranked coalition in σ (apply Proposition 10). Hence, ϕN(σ , σ) ϕ(π , π). We consider the popularity margin between σ and σ by a case distinction. If π = π , then ϕ(σ , σ) 1 + ϕ(π , π) 0 and ϕ(σ , σ) > 0 if (R, S) is a No-instance. On the other hand, if π = π , then σ(z) = {z} (since σ = σ ). As vy(π ) > 0 for all y N, we know that |σ(z) \ {z}| 2 and y N(σ , σ) for all y σ(z) \ {z} (by design of the utilities, this holds in particular for agent x). Hence, ϕ(σ , σ) = ϕσ(z)(σ , σ) 1 + |σ(z) \ {z}| > 0 It follows that σ is popular and it is a strongly popular partition if (R, S) is a Noinstance. If (R, S) is a Yes-instance, then σ is the only candidate that might be strongly popular. Consider the partition π from Lemma 4 and define σ = (π \ {{x}}) {{x, z}}. Then, x N(π , π ) N(σ , σ ), whereas z N(σ , σ ). Therefore, ϕ(σ , σ) = 1 + ϕ(π , π ) = 0. Hence, π is not strongly popular and there exists no strongly popular partition. Theorem 17. Verifying whether a given partition in a symmetric FHG is strongly popular is co NP-complete, even if all utilities are non-negative. Proof. In the proof of Theorem 10, the partition σ is strongly popular if, and only if, (R, S) is a No-instance of X3C. Theorem 18. Computing a mixed popular partition in a symmetric FHG is NP-hard, even if all utilities are non-negative. Proof. We give a Turing reduction from X3C. Given an instance (R, S) of X3C, we consider the symmetric FHG of Lemma 4 on agent set N with utility function v together with the partition π and the special agent x N. We define a symmetric, non-negative FHG on agent set N = N {z1, z2} where the utilities are given by v (y, w) = v(y, w) if y, w N, v (z1, z2) = vx(π )/2, v (z1, x) = v (z2, x) = vx(π )/3 > 0, and v (zi, y) = 0 for i [2], y N \ {x}. Note that by Lemma 4, this reduction is in polynomial time. Consider the partition σ = π {{z1, z2}} and let σ = σ be given. Define π = (σ \ (σ(z1) σ(z2))) {σ(z1) \ {z1, z2}, σ(z2) \ {z1, z2}}, that is, the partition of agent set N where z1 and z2 leave their coalitions. Assume that (R, S) is a No-instance. We will prove that ϕ(σ , σ) > 0, and therefore that σ is strongly popular. We may assume that σ(z1) = {z1, z2} or x σ(zi) for some i, because otherwise it is a Pareto improvement if z1 and z2 leave their coalitions and form a coalition of their own. Note that as in the proof of Theorem 16, it holds that ϕN(σ , σ) ϕ(π , π). Now, for i [2] holds that zi N(σ , σ) unless σ(zi) {{z1, z2, x}, {z1, z2}}. If σ(zi) = {z1, z2}, then ϕ(σ , σ) = ϕ(π , π) 1, because π = π . On the other hand, σ(zi) = {z1, z2, x}, then π(x) π (x) = {x} and it follows that ϕ(σ , σ) 2 + ϕ(π , π) 1 (where the last inequality uses Lemma 4). It remains the case that z1, z2 N(σ , σ) and we obtain ϕ(σ , σ) 2 + ϕ(π , π) 2. Together, the partition σ is strongly popular and therefore, the unique mixed popular partition consists of σ with probability 1. Now assume that (R, S) is a Yes-instance. Consider the partition π from Lemma 4 and define σ = (π \ {{x}}) {{x, z1, z2}}. Then, x N(π , π ) N(σ , σ ), whereas Brandt & Bullinger z1, z2 N(σ , σ ). Therefore, ϕ(σ , σ) = 2 + ϕ(π , π ) = 1. Hence, the pure mixed partition {σ } is not mixed popular. We can solve X3C by computing a partition σ in the support of a mixed popular partition and checking its probability in case that σ = σ . Theorem 19. Checking whether there exists a popular partition in a symmetric FHG is co NP-hard, even if all utilities are non-negative. Proof. We provide a reduction from X3C. Given an instance (R, S) of X3C, we consider the symmetric FHG with non-negative utility functions of Lemma 4 on agent set N with utility function v together with the partition π and the special agent x N. Set α = vx(π ). For i [2], let Ni = {yi : y N} be two copies of N. Accordingly, let π i be their respective copies of π . We define a symmetric ASHG on agent set N = N1 N2 Z where Z = {zj k : k [2], j [3]}. Define Zj = {zj 1, zj 2}. Utilities are as follows. v (yi, wi) = v(y, w) if y, w Ni for i [2], v (zj k, x1) = 2α/5, v (zj k, x2) = α/3 for k [2], j [3], v (zj 1, zj 2) = α/2 for j [3], and v (u, y) = 0 for every pair of agents u, y N such that their utility is not yet defined. By Lemma 4, this reduction is in polynomial time. First assume that (R, S) is a No-instance. We claim that σ = π 1 π 2 {Zj : j [3]} is popular. To prove this, let σ = σ be an arbitrary partition and define πi = {σ(y) Ni : y Ni} be the coalitions restricted to Ni. Let k [2] and j [3]. The first key insight is that if there exists y σ(zj k) \ (Zj {x1, x2}), then zj k N(σ , σ). Assume that such an agent y exists. Observe that the only agents that provide positive utility to zj k are zj 3 k, x1, and x2. The maximum utility that under these circumstances can be obtained for zj k is if σ(zj k) = {zj k, zj 3 k, x1, y} and even in this case vzj k(σ) = 4 = vzi k(σ ). We will use this insight to show that we can assume for every k [2], j [3] that σ(zj k) Zj {x1, x2}. Fix again k [2], j [3] and assume otherwise. Then, σ(zj k) (Zj {x1, x2}) N(σ , σ). This follows for agents in Zj from what we have just shown before, and for agents xi by the design of their utilities and the fact that they received a top-ranked coalition in π i and by Proposition 10 in σ . We modify σ by leaving the coalition with the agents in Zj, that is, we define σ = (σ \ σ(zj k)) {σ(zj k) \ Zj, σ(zj k) Zj}. Then, N(σ , σ ) N(σ , σ) and N(σ, σ ) N(σ , σ ), which implies that ϕ(σ , σ) ϕ(σ , σ ) and it suffices to consider σ and show a non-negative popularity margin for that partition. We are ready to compute the popularity margin. Therefore, define I = {i [2]: σ(xi) Z = }. Note that for i [2], ϕNi(σ , σ) ϕ(π i , πi). Furthermore, if i I, then πi(xi) Ni = {xi} and |Z σ(xi)| 2. It follows that ϕ(σ , σ) = ϕN1(σ , σ) + ϕN2(σ , σ) + ϕZ(σ , σ) P i I ϕNi(π i , πi) + P i/ I ϕNi(π i , πi) + ϕZ(σ , σ) 3|I| |{z Z : σ(z) {x1, x2} = }| = 3|I| 2|I| 0. Hence, σ is popular. Finding and Recognizing Popular Coalition Structures Conversely, assume that (R, S) is a Yes-instance and assume for contradiction that σ is popular and define πi = {σ(y) Ni : y Ni} as above. The overall proof strategy is as follows. First, we show that for k [2] and j [3], σ(zj k) {Zj, Zj {x1}, Zj {x2}}. Then we show, that for i [2], there exists j [3] with Zj {xi} σ. Finally, we perform a cyclic exchange of such coalitions. Let k [2] and j [3] and define C = σ(zj k). The first crucial step is to show that C {x1, x2} Zj. To see this, assume for contradiction that there exists an agent y C \ ({x1, x2} Zj). We may assume that vy(σ) > 0, since otherwise leaving the coalition with y yields a Pareto-improvement. Recall, that we have shown in the first part of the proof that, under these circumstances, vzj k(Zj) > vzj k(σ). The same holds for zj 3 k in both the case that zj 3 k C and zj 3 k / C. Define σ = (σ\{σ(zj 1), σ(zj 2)}) {σ(zj 1)\{zj 1}, σ(zj 2)\{zj 2}, Zj}. Then {zj 1, zj 2, y} N(σ , σ), while N(σ, σ ) {x1, x2}. Hence, σ is more popular, which is a contradiction. It follows that C {x1, x2} Zj. Next, we claim that zj 3 k σ(zj k). Assume otherwise. If one of zj k and zj 3 k is in a singleton coalition, it is a Pareto improvement to form σ(zj k) σ(zj 3 k). Otherwise, there exists i [2] with σ(zj k) = {xi, zj k} and if σ(zj 3 k) = {zj 3 k, x3 i}. Hence, if zj 3 k leaves her coalition and joins σ(zj k), we obtain a more popular partition. Define I = {i [2]: Z σ(xi) = } and let i I. We claim that there exists j [3] with σ(xi) = {xi} Zj. Let k [2], j [3] with zj k σ(xi). We already know that then Zj σ(xi) Zj {x1, x2}. Furthermore, by the pigeon hole principle, for some j [3] \ {j} holds Zj σ. Assume for contradiction that x3 i σ(xi). Then, σ = (σ \ {σ(xi), Zj }) {Zj {x1}, Zj {x2}} is more popular. Indeed, N(σ , σ) = {x1, x2, zj 1 , zj 2 }, while N(σ, σ ) = Zj. The remainder of the proof is identical to the proof for ASHGs, namely we show that I = {1, 2} and find a more popular partition even in this case. All in all, it is shown that there exists no popular partition if (R, S) is a Yes-instance. This concludes the proof of the theorem. Abraham, D. J., Leravi, A., Manlove, D. F., & O Malley, G. (2008). The stable roommates problem with globally ranked pairs. Internet Mathematics, 5(4), 493 515. Abraham, D. K., Irving, R. W., Kavitha, T., & Mehlhorn, K. (2007). Popular matchings. SIAM Journal on Computing, 37(4), 1030 1034. Aziz, H., Brandl, F., Brandt, F., & Brill, M. (2018). On the tradeoff between efficiency and strategyproofness. Games and Economic Behavior, 110, 1 18. Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., & Peters, D. (2019). Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2), 1 29. Aziz, H., Brandt, F., & Harrenstein, P. (2013a). Pareto optimality in coalition formation. Games and Economic Behavior, 82, 562 581. Aziz, H., Brandt, F., & Seedig, H. G. (2013b). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316 334. Brandt & Bullinger Aziz, H., Brandt, F., & Stursberg, P. (2013c). On popular random assignments. In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), Vol. 8146 of Lecture Notes in Computer Science (LNCS), pp. 183 194. Springer-Verlag. Aziz, H., & Savani, R. (2016). Hedonic games. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.), Handbook of Computational Social Choice, chap. 15. Cambridge University Press. Ballester, C. (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 30. Bir o, P., Irving, R. W., & Manlove, D. F. (2010). Popular matchings in the marriage and roommates problems. In Proceedings of the 7th Italian Conference on Algorithms and Complexity (CIAC), pp. 97 108. Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201 230. Brandl, F., & Brandt, F. (2020). Arrovian aggregation of convex preferences. Econometrica, 88(2), 799 844. Brandl, F., Brandt, F., & Hofbauer, J. (2017). Random assignment with optional participation. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 326 334. Brandl, F., Brandt, F., & Seedig, H. G. (2016). Consistent probabilistic social choice. Econometrica, 84(5), 1839 1880. Brandl, F., Brandt, F., & Stricker, C. (2022). An analytical and experimental comparison of maximal lottery schemes. Social Choice and Welfare, 58(1), 5 38. Brandl, F., & Kavitha, T. (2018). Two problems in max-size popular matchings. Algorithmica, 81(7), 2738 2764. Brandt, F., Hofbauer, J., & Suderland, M. (2017). Majority graphs of assignment problems and properties of popular random assignments. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 335 343. Bullinger, M. (2020). Pareto-optimality in cardinal hedonic games. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 213 221. Cseh, A. (2017). Popular matchings. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 6. AI Access. Cseh, A., Huang, C.-C., & Kavitha, T. (2015). Popular matchings with two-sided preferences and one-sided ties. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Vol. 9134 of Lecture Notes in Computer Science (LNCS), pp. 367 379. Springer-Verlag. Cseh, A., & Kavitha, T. (2018). Popular matchings in complete graphs. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Finding and Recognizing Popular Coalition Structures Cseh, A., & Peters, J. (2022). Three-dimensional popular matching with cyclic preferences. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Forthcoming. Dr eze, J. H., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48(4), 987 1003. Edmonds, J. (1965). Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B, 69, 125 130. Faenza, Y., Kavitha, T., Power, V., & Zhang, X. (2019). Popular matchings and limits to tractability. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2790 2809. Fishburn, P. C. (1984). Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4), 683 692. G ardenfors, P. (1975). Match making: Assignments based on bilateral preferences. Behavioral Science, 20(3), 166 173. Gr otschel, M., Lov asz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169 197. Gupta, S., Misra, P., Saurabh, S., & Zehavi, M. (2019). Popular matching in roommates setting is np-hard. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2810 2822. Huang, C.-C., & Kavitha, T. (2011). Popular matchings in the stable marriage problem. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), Vol. 6755 of Lecture Notes in Computer Science (LNCS), pp. 666 677. Springer-Verlag. Huang, C.-C., & Kavitha, T. (2017). Popularity, mixed matchings, and self-duality. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2294 2310. Huang, C.-C., & Kavitha, T. (2021). Popularity, mixed matchings, and self-duality. Mathematics of Operations Research, 46(2), 405 427. Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. E., & Thatcher, J. W. (Eds.), Complexity of Computer Computations, pp. 85 103. Plenum Press. Kavitha, T. (2014). A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1), 52 71. Kavitha, T., Mestre, J., & Nasre, M. (2011). Popular mixed matchings. Theoretical Computer Science, 412(24), 2679 2690. Kavitha, T., & Nasre, M. (2009). Optimal popular matchings. Discrete Applied Mathematics, 157, 3181 3186. Khachiyan, L. (1979). A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20, 191 194. Brandt & Bullinger Kir aly, T., & M esz aros-Karkus, Z. (2017). Finding strongly popular b-matchings in bipartite graphs. Electronic Notes in Discrete Mathematics, 61, 735 741. Lam, C.-K., & Plaxton, C. G. (2019). On the existence of three-dimensional stable matchings with cyclic preferences. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), Vol. 11801 of Lecture Notes in Computer Science (LNCS), pp. 329 342. Springer-Verlag. Mahdian, M. (2006). Random popular matchings. In Proceedings of the 7th ACM Conference on Electronic Commerce (ACM-EC), pp. 238 242. Manlove, D. F. (2013). Algorithmics of Matching Under Preferences. World Scientific Publishing Company. Mc Cutchen, R. M. (2008). The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In Proceedings of the 8th Latin American Conference on Theoretical Informatics (LATIN), Vol. 4957 of Lecture Notes in Computer Science (LNCS), pp. 593 604. Padberg, M. W., & Wolsey, L. A. (1984). Fractional covers for forests and matchings. Mathematical Programming, 29, 1 14. von Neumann, J. (1928). Zur Theorie der Gesellschaftspiele. Mathematische Annalen, 100(1), 295 320. von Neumann, J., & Morgenstern, O. (1947). Theory of Games and Economic Behavior (2nd edition). Princeton University Press.