Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games

1 Introduction

We consider the task of partitioning a set of agents, say humans or machines, into disjoint coalitions. Agents have preferences regarding the coalition they are part of and a reasonable partition should reflect these preferences. This task is commonly studied in the framework of coalition formation and is an intriguing object of study at the intersection of economics and computer science. The typical economic setting is the formation of teams, such as working groups or political parties, but applications also consider reaching international agreements, establishing research collaboration, or forming customs unions [Ray, 2007]. Partitioning problems are also studied in other fields, such as clustering in machine learning and community detection in social science [Cohen-Addad et al., 2022; Newman, 2004].

The output of a coalition formation scenario is usually measured by means of solution concepts, that capture the ideas of stability and optimality. While stability conceptualizes the prospect of agents staying in their own coalition rather than performing deviations to join other coalitions, optimality aims at global guarantees, for instance, with respect to notions of welfare. We consider the notion of popularity, a solution concept due to Gärdenfors [1975] that incorporates both ideas [Brandt and Bullinger, 2022]. 1 Informally speaking, an outcome is popular if no other outcome wins a vote against this outcome. In social choice theory, this corresponds to the well-established notion of weak Condorcet winners [Condorcet, 1785], but popularity can be defined in any context where agents have preferences over outcomes. Popularity hence captures the idea of a status quo that cannot be defeated in a head-to-head election. For instance, students engaged in a popular research collaboration would not be able to propose a different outcome preferred by a majority.

1 In his original work, Gärdenfors [1975] calls popular outcomes "majority assignments."

Gärdenfors [1975] was the first to consider popularity in a coalitional setting. He considered bipartite matching instances and showed that stable matchings-in the sense of Gale and Shapley [1962]-are popular if the agents' preferences are strict. Interestingly, relaxing either assumption (bipartiteness or strict preferences) may lead to instances in which popular outcomes do not exist, and the corresponding decision problems become NP-complete [Biró et al., 2010; Faenza et al., 2019; Gupta et al., 2021]. Notably, membership in NP is not trivial for this problem because one has to certify that a matching does not lose a vote against any other matching, of which there are exponentially many. This task can, however, be performed by transforming the verification of popular matchings to a maximum weight matching problem [Biró et al., 2010] or a linear program that can simultaneously handle weak and incomplete preferences as well as nonbipartite instances [Kavitha et al., 2011; Brandt and Bullinger, 2022].

When allowing coalitions to be of size greater than 2, we reach the typical domain of coalition formation. We consider the prominent classes of additively separable and fractional hedonic games [Bogomolnaia and Jackson, 2002; Aziz et al., 2019]. Specifically, we study the following decision problems.

ASHG-EXISTS-POPULAR (FHG-EXISTS-POPULAR)

Input: Additively separable hedonic game (fractional hedonic game)

Question: Does the given game admit a popular par-

tition?

For these, we prove two sweeping hardness results. These complete the characterization of the complexity hierarchy of popularity in coalitional scenarios, as detailed in Figure 1.

Theorem 1. ASHG-EXISTS-POPULAR is Σp2 -complete.

Theorem2. FHG-EXISTS-POPULAR is Σp2 -complete, even if valuations are nonnegative.

Our results highlight the significant computational hardness presented by popularity in coalition formation. While NP-hard problems can often be addressed in practice using SAT or ILP solvers, Σp2 -completeness indicates a higher level of complexity that surpasses these typical approaches.

Notably, the definition of popularity, i.e., the existence of an outcome such that for all other outcomes, a vote is not lost, suggests membership in the complexity class Σp2 . Still, we are the first to prove a corresponding completeness result. By contrast, previous work only establishes hardness for the first level of the polynomial hierarchy [Aziz et al., 2013; Brandt and Bullinger, 2022; Cseh and Peters, 2022] or considers the simpler to analyze verification problem [Kerkmann et al., 2020].

Note that the nonnegativity assumption in Theorem 2 is a strong additional restriction, which is not possible for Theorem 1. Indeed, additively separable hedonic games define agents' utilities for coalitions based on the sum of valuations of its members. Hence, forming the grand coalition containing all agents is optimal for all agents if valuations are nonnegative. By contrast, the sum of valuations is divided by the size of the coalition in fractional hedonic games, which leads to nontrivial preferences, even for nonnegative valuations.

2 RelatedWork

Coalition formation in the framework of hedonic games was first considered by Drèze and Greenberg [1980] and further conceptualized by Bogomolnaia and Jackson [2002], Banerjee et al. [2001], and Cechlárová and Romero-Medina [2001]. The book chapters by Aziz and Savani [2016] and Bullinger et al. [2024] provide an introduction to hedonic games.

In a general model of hedonic games, agents have to rank an exponentially large set of possible coalitions. Since this causes computational issues, a wide range of succinct preference representations has been proposed in the literature. Often, this is based on restricting attention to important meta-information about a coalition such as its size [Bogomolnaia and Jackson, 2002] or its best or worst member [Cechlárová and Romero-Medina, 2001]. Another way is to aggregate cardinal valuation functions of single agents to a utility for a coalition. We consider models that follow this latter approach, namely additively separable hedonic games (ASHGs) and fractional hedonic games (FHGs) [Bogomolnaia and Jackson, 2002; Aziz et al., 2019].

Similar to the landscape of game classes, there exists a variety of solution concepts for hedonic games. We focus our discussion on the large body of research on ASHGs and FHGs. Much of this literature concerns stability, i.e., the absence of beneficial deviations to join other or form new coalitions. A common theme is that stability is usually only satisfiable for restricted domains of games, and various computational hardness results have been observed. Interestingly, there is a difference in complexity dependent on whether single agents or groups of agents perform a deviation. Whether a single agent can perform a deviation can usually be checked in polynomial time and we obtain NP-completeness results [Sung and Dimitrov, 2010; Aziz et al., 2013; Brandl et al., 2015; Brandt et al., 2023; Brandt et al., 2024]. By contrast, whether a group deviation exists is itself NP-complete to check and hence the existence of group stability, e.g., whether there exist partitions in the core, becomes Σp2 -complete [Woeginger, 2013; Peters, 2017; Aziz et al., 2019]. Prior to our complexity results on popularity, these were the only problems known to be Σp2 -complete for hedonic games.

It is possible to achieve more positive results regarding the existence of stable outcomes by considering restricted domains [Bogomolnaia and Jackson, 2002; Dimitrov et al., 2006], weakened solution concepts [Fanelli et al., 2021], stability under randomized deviations [Fioravanti et al., 2023], or in random games [Bullinger and Kraiczy, 2024]. For instance, symmetric utilities lead to the existence of singledeviation stability in ASHGs [Bogomolnaia and Jackson, 2002], but the same is not true in FHGs [Brandt et al., 2023], and even in ASHGs, computation is still PLS-hard [Gairing and Savani, 2019].

Popularity, our main solution concept, has received less attention. Most related to our work is the paper by Brandt and Bullinger [2022] who prove NP-hardness and coNP-hardness of the existence problem for ASHGs and FHGs. In addition, they show coNP-completeness of the verification of popular partitions, a problem that was also considered by Aziz et al. [2013] for ASHGs. 2 Our results improve upon these results by showing Σp2 -completeness of the existence problem, which settles the precise complexity of popularity in ASHGs and FHGs.

Popularity has also been considered in further classes of hedonic games. Brandt and Bullinger [2022] and Cseh and Peters [2022] study it for games with coalitions bounded in size by three, and Kerkmann et al. [2020] consider a preference model based on the distinction of friends, enemies, and neutrals. Moreover, Kerkmann and Rothe [2020] consider popularity for a nonhedonic class of coalition formation games aimed at modeling altruism. All of these papers show coNP-completeness of the verification problem. However, while Brandt and Bullinger [2022] and Cseh and Peters [2022] at least show NP-hardness, the complexity of the existence problem remains unresolved in all of these models.

2 Aziz et al. [2013] also consider the existence problem of popularity for ASHGs, but their proof was pointed out to be incomplete by Brandt and Bullinger [2022].

3 Preliminaries

In this section, we provide the preliminaries for our work. We start with defining hedonic games, then define important solution concepts, and finally discuss the computational aspects of these solution concepts.

3.1 Succinct Classes of Cardinal Hedonic Games

Let N be a set of agents. A coalition is a nonempty subset of N. A coalition of size one is called a singleton coalition. Denote by Ni = {S ⊆ N : i ∈ S} the set of all coalitions agent i belongs to. A coalition structure, or a partition, is a partition π of N into coalitions. For an agent i ∈ N, we denote by π(i) the coalition i belongs to in π.

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 order ≿i over Ni. In hedonic games, agents are only concerned with the members of their own coalition which is also reflected in their preference order. Therefore, we can naturally define an associated preference order over partitions by π ≿i π′ if and only if π(i) ≿i π′ (i). For coalitions S, S′ ∈ Ni, we say that agent i weakly prefers S over S′ if S ≿i S′ . Moreover, we say that i prefers S over S′ if S ≻i S′ . We use the same terminology for preferences over partitions.

In this paper, we assume agents rank coalitions (and by extension, partitions) by underlying utility functions u = (ui : Ni → R)i∈N. These induce a hedonic game (N,≿) where, for every agent i ∈ N and two coalitions S, S′ ∈ Ni, we define S ≿i S′ if and only if ui(S) ≥ ui(S′ ). Hence, i prefers S over S′ if and only if ui(S) > ui(S′ ). We say that ui(S) is i's utility for coalition S and extend this to utilities for partitions by setting ui(π) = ui(π(i)). A hedonic game together with its utility-based representation is called a cardinal hedonic game and is specified by the pair (N, u).

Hedonic games as introduced so far need every agent to specify a preference order or cardinal values for an exponentially large set of coalitions. By contrast, we focus on succinctly representable sub-classes of cardinal hedonic games, where the utilities are induced by the aggregation of values that each agent assigns to other members of her coalition. These games are specified by a pair (N, v), where v = (vi : N → R)i∈N is a vector of valuation functions. The quantity vi(j) denotes the value agent i assigns to agent j.

Following Bogomolnaia and Jackson [2002], an additively separable hedonic game (ASHG) given by the pair (N, v) is the cardinal hedonic game (N, u) where

Hence, the utility ui(S) of agent i for coalition S ∈ Ni is defined as the sum of the values agent i assigns to the other members of her coalition.

Following Aziz et al. [2019], a fractional hedonic game (FHG) given by the pair (N, v) is the cardinal hedonic game

(N, u) where

Hence, the utility ui(S) of agent i for coalition S ∈ Ni is defined as the sum of the values agent i assigns to the other members of her coalition divided by the coalition size. This quantity can be interpreted as the average value that i assigns to the members of her coalition if we include a value of 0 for herself.

3.2 Popular Partitions

We now move towards defining popularity, our main solution concept, for a given hedonic game (N,≿). Let π and π′ be two partitions of N. We denote the set of agents who prefer π over π′ by N(π, π′ ), i.e., N(π, π′ ) = {i ∈ N : π ≻i π′ }. For any subset of agents M ⊆ N, we define the popularity margin on M with respect to the ordered pair (π, π′ ) to be ϕM(π, π′ ) = |N(π, π′ ) ∩M| - |N(π′ , π) ∩M|. Note that in this definition, agents who are indifferent between the two partitions do not contribute to any of the two terms. When M is a singleton containing a single agent a, we use the abbreviated notation ϕa(π, π′ ) = ϕ{a}(π, π′ ). The definition of popularity margins is useful as sometimes it is convenient to consider restricted subsets of agents separately. Further, considering the entire set of agents, we define the popularity margin of the ordered pair (π, π′ ) as ϕ(π, π′ ) = ϕN(π, π′ ). Note that the popularity margin is antisymmetric, i.e., ϕ(π, π′ ) = -ϕ(π′ , π). We say that π is more popular than π′ if ϕ(π, π′ ) > 0. Moreover, π is called popular if there exists no partition π′ that is more popular than π, i.e., for any partition π′ it holds that ϕ(π, π′ ) ≥ 0.

Another useful concept in the context of popularity is Pareto optimality. We say that π′ is a Pareto improvement from π if all agents weakly prefer π′ over π, and at least one agent strictly prefers π′ over π. If there exists no Pareto improvement from π, we say π is Pareto-optimal. Clearly, popular partitions are Pareto-optimal. Indeed, every Pareto improvement is a more popular partition. By contrast, Paretooptimal partitions need not be popular. In addition, a useful observation is that it suffices to restrict attention to Paretooptimal partitions when considering popularity [Brandt and Bullinger, 2022].

Proposition 1 (Brandt and Bullinger [2022], Proposition 4). A partition π is popular if and only if for all Pareto-optimal partitions π′ it holds that ϕ(π, π′ ) ≥ 0.

As a consequence, whenever we postulate a more popular partition than a given partition, we may assume without loss of generality that this partition is Pareto-optimal.

3.3 Complexity Theory

We assume familiarity of the reader with basic notions of complexity theory such as polynomial-time reductions or the classes P (deterministic polynomial time) and NP (nondeterministic polynomial time). Here, we focus on the complexity class Σp2 in the second level of the polynomial hierarchy, which captures the problems considered in this paper. We refer to the textbooks by Papadimitriou [1994] and Arora and Barak [2009] for an introduction to complexity and a deeper coverage of Σp2 .

The class Σp2 contains all problems Q for which there exists a polynomial-time Turing machine M and a polynomial q such that x is a Yes-instance of Q if and only if there exists a y ∈ {0, 1}q(|x|) such that for all z ∈ {0, 1}q(|x|) it holds that M(x, y, z) = TRUE. Informally speaking, this captures problems in which the solutions y of an instance x are challenged by any possible adversary z. The class is thus described by the concatenation of an existential and a universal quantifier. It therefore contains NP, which is defined by just an existential quantifier (because we can ignore the universal quantifier), and coNP, which is defined by just a universal quantifier (because we can ignore the existential quantifier). As with other complexity classes, a problem Q is said to be Σp2 -hard if for every problem in Σp2 , there exists a polynomial-time reduction from this problem to Q. A problem is said to be Σp2 -complete if it is Σp2 -hard and contained in Σp2 .

As a first example, we define the problem 2-QUANTIFIED 3-DNF-SAT, which is a canonical SAT problem for Σp2 . It is the source problem of our reductions in Theorems 1 and 2.

2-QUANTIFIED 3-DNF-SAT

Input: Two sets X = {x1, . . . , xn} and Y = {y1, . . . , yn} of Boolean variables and a Boolean formula ψ(X , Y) over X ∪Y in disjunctive normal form, where each of the conjunctive clauses consists of exactly three distinct literals.

Question: Does there exist a truth assignment τX to x1, . . . , xn such that for all truth assignments τY to y1, . . . , yn it holds that ψ(τX , τY) = TRUE?

• 2-QUANTIFIED 3-DNF-SAT is exactly in the spirit of Σp2 . Yes-instances are described by the existence of a certificate (the truth assignment to x1, . . . , xn) such that the output of the formula is TRUE regardless of the truth assignment to y1, . . . , yn. Even more, 2-QUANTIFIED 3-DNF-SAT was shown to be Σp2 -complete by Stockmeyer [1977].

As a second example, we argue that ASHG-EXISTSPOPULAR and FHG-EXISTS-POPULAR are contained in Σp2 , as remarked by Brandt and Bullinger [2022]: One can consider a polynomial-time Turing machine with three inputs that are a hedonic game (say, an ASHG or FHG) and two partitions π and π′ and it outputs TRUE if and only if ϕ(π, π′ ) ≥ 0 in the given hedonic game. This Turing machine attests membership in Σp2 of the existence problem of popularity. In our proofs, we will therefore only consider hardness.

4 Popularity in ASHGs

In this section, we discuss the proof of Theorem 1. We start by describing our reduction from 2-QUANTIFIED 3DNF-SAT. Then, in the subsequent two sections, we give an overview of the proof that satisfiability of the source instance implies the existence of a popular partition and vice versa. We focus on the key arguments and an illustration while the detailed proof is available in the full version of our paper [Bullinger and Gilboa, 2024].

4.1 Setup of the Reduction

We now describe the construction of the reduction. First, we introduce the following No-instance of ASHG-EXISTSPOPULAR, on which the reduction relies; it resembles the No-instance described by ? [?]Example 4]ABS11c. Suppose we have five agents, consisting of three top agents t1, t2, and t3, and two bottom agents b1 and b2. For each i ∈ {1, 2, 3}, ti assigns value 1 to b1 and value 2 to b2. Moreover, b1 assigns value 1 to each top agent and b2 assigns value 2 to each top agent. All other values are set to -∞ (representing some sufficiently large negative value, e.g., -7 suffices here) between the agents. This instance is depicted in Figure 2.

One may verify that there exists no popular partition in this instance: It is easy to see that it is more popular to dissolve any coalition of size at least three into singletons. Hence, the interesting case is a partition of the type {{t1, b1}, {t2, b2}, {t3}}, which, however, is less popular than {{t1, b2}, {t3, b1}, {t2}}.

In our reduction, we construct a game which has a similar structure to this No-instance (with some additional agents). However, each top agent ti is replaced by a set of multiple agents who, intuitively, together function in a similar way as the single agent ti. Hence, familiarity with the above Noinstance is helpful to understand the reduction as well: when a satisfying assignment to the 2-QUANTIFIED 3-DNF-SAT instance does not exist, the reduced game simulates a behaviour similar to that of this No-instance.

We proceed by describing our reduction. Suppose that we are given an arbitrary instance (X, Y, ψ) of 2-QUANTIFIED 3-DNF-SAT. Denote by C the set of clauses in ψ and let m = |C|; without loss of generality, we may assume that m ≥ 2. We construct the following ASHG consisting of 12n+4m+1 agents, depicted in Figure 3.

• For every variable x ∈ X:
• We create two X-agents ax and a¬x, where the former represents the variable and the latter its negation. We will use α to denote any literal over X, meaning aα can correspond to a variable or its negation; accordingly, a¬α will simply correspond to the negated literal, e.g., if α = ¬x, then a¬α = ax. If ax and a¬x originate in the same variable, they are called complementary agents.
• We create a corresponding Xt-agent and a corresponding Xf -agent, denoted xt and xf , respectively. The subscripts of these agents indicate "true" and "false" and these agents are used to deduct the satisfying truth assignments from popular partitions (and vice versa).

• For every variable y ∈ Y:
• We create two Y -agents ay and a¬y, where the former represents the variable and the latter its negation. We will use β to denote any literal over Y, meaning aβ can correspond to a variable or its negation; a¬β will refer to the agent corresponding to the negated literal. If aβ and a¬β originate in the same variable, they are called complementary agents.
• We create a Y ′ -agent a′y corresponding to ay, and a Y ′ -agent a′¬y corresponding to a¬y (we emphasize that, in contrast to the X-agents, which have corresponding agents as a pair, ay and a¬y each have separate Y ′ -agents).
• For every clause c ∈ C, we create a C-agent ac. For a literal α over X (or β over Y) occurring in c, we refer to the X-agent aα (or Y -agent aβ) as corresponding to clause c.
• We create m- 1 agents, called C ′ -agents.
• We create 2n +m agents, called T1 agents and another 2n + m agents, called T2 agents.
• We create a single agent denoted b1, and a single agent denoted b2.

For each agent type, the set of all agents from that type is denoted by the name of the type (e.g., T1 is the set of all T1agents). We use the terms real agents to refer to the X-, Y -, and C-agents, and structure agents to refer to all other agents. In addition, we speak of left-side agents to refer to b1, b2, and the T1- and T2-agents, and right-side agents to refer to the other agents (this terminology is based on the visualization in Figure 3). We denote by L and R the sets of all left-side and right-side agents, respectively.

We refer to Figure 3 for an overview of the valuation functions and to the full version of our paper for a detailed description. Valuations missing from the figure (as well as some of the depicted ones) correspond to a large negative constant which we indicate by a value of -∞. For the reduction to work, one can, for instance, set ∞= 6(12n+4m+1). This completes the description of the reduction.

When the input 2-QUANTIFIED 3-DNF-SAT instance is a No-instance, the reduced ASHG mimics the No-instance in Figure 2, where b1 and b2 are still single agents, but t1 and t2 are replaced by the sets T1 and T2, and the real agents correspond to the agent t3. The real agents also encode the source instance of 2-QUANTIFIED 3-DNF-SAT, as they are representatives of the literals and clauses. The right-side structure agents provide options for "good" coalitions for the real agents.

In essence, a popular partition can only exist if all rightside agents are in good coalition which will allow for a partition corresponding to the partition {{t1, b1}, {t2, b2}, {t3}} to be popular. The good coalitions for the real agents are:

• coalitions of the type {ax, xt} and {a¬x, xf} or {a¬x, xt} and {ax, xf } for the X-agents,
• coalitions {aβ, a′β } for the Y -agents, and
• coalition C ∪C ′ for the C-agents.

The crucial part is to determine the exact coalitions of the X-agents. Whether we form {ax, xt} or {a¬x, xt} corresponds to a truth assignment to the X variables.

To prove Theorem 1, we will show that the logical formula is satisfiable if and only if there exists a popular partition in the constructed ASHG. If we have a truth assignment, we can define a partition as described above and prove that it is popular. Conversely, a popular partition has to be a structure similar to the partition described above and we can use it to extract a truth assignment. The two directions of the proof will be sketched in Sections 4.2 and 4.3.

4.2 Satisfiability Implies Popular Partition

Throughout this section, we assume that (X, Y, ψ) is a Yesinstance of 2-QUANTIFIED 3-DNF-SAT. Hence, there is a truth assignment τX to the variables in X such that for all truth assignments τY to the variables in Y it holds that ψ(τX , τY) = TRUE. Consider the following partition of the agents, denoted by π∗ .

• For each x ∈ X, if x is assigned TRUE by τX then {{ax, xt}, {a¬x, xf }} ⊆ π∗ , and if x is assigned FALSE by τX then {{a¬x, xt}, {ax, xf }} ⊆ π∗ .
• Each Y -agent aβ forms a coalition with her corresponding Y ′ -agent a′β .
• The coalition C ∪C ′ is formed.
• Coalitions T1 ∪ {b1} and T2 ∪ {b2} are formed.

Our goal is to show that π∗ is a popular partition. We formally prove this statement in the full version of our paper. Here, we focus on outlining key steps. Assume towards contradiction that there exists a partition π that is more popular than π∗ . We wish to use π to extract a truth assignment τ ′Y to the variables in Y such that ψ(τX , τ ′Y ) = FALSE. For this, we will determine various structural insights about the partition π and finally use the coalition π(b1) to find both the assignment τ ′Y as well as a proof that it can be used to evaluate ψ as false.

For determining the structure of π, it is good to first consider the popularity margin for certain groups of agents. By using that π∗ is a very good partition for the Y ′ -, Xf -, Xt-, and C ′ -agents, we obtain the following facts

• For each aβ ∈ Y , it holds that ϕ{aβ,a′β }(π∗ , π) ≥ 0.
• For each x ∈ X, it holds that ϕ{ax,a¬x,xt,xf}(π∗ , π) ≥ 0.
• If for every ac ∈ C we have that ϕac (π, π∗ ) > 0, then ϕC∪C′ (π∗ , π) = -1. Otherwise, ϕC∪C′ (π∗ , π) ≥ 0.

Together, the worst-case popularity margin of the right-side agents is thus ϕR(π∗ , π) ≥ -1.

As a next step, we consider coalitions of left-side agents and show that

1. Agents in T1 and T2 cannot be in the same coalition.
2. The coalition of b1 contains a right-side agent.
3. The coalition of b2 does not contain a right-side agent.

Item 1 holds because these agents only gain positive value from b1 and b2, whereas valuations between agents in T1 and T2 are -∞. This insight can then be leveraged to show that at least one agent of {b1, b2} has to contain a right-side agent. Otherwise, it is easy to deduce that the left-side agents have a popularity margin of ϕL(π∗ , π) ≥ 0, and furthermore no C-agent can gain positive utility in π, and therefore also ϕR(π∗ , π) ≥ 0. Together, these two facts imply that π was not more popular. Items 2 and 3 follow with little effort from this conclusion.

We can now show that ϕT1∪T2∪{b2}(π∗ , π) ≥ 0. Together with our other insights about the popularity margins, π can only be more popular than π∗ if ϕb1 (π∗ , π) ≤ 0.

Next, it is easy to see that each agent in T1 or T2 that forms a coalition with a right-side agent would have to be in the coalition with b1. However, by carefully analyzing π(b1), it can then be shown that it cannot contain agents in T1 and T2.

To summarize our knowledge about left-side agents, we know that b1 forms a coalition with right-side agents only, whereas all other left-side agents form coalitions with other left-side agents.

The next step is to analyze the exact coalition of b1 in π. It can be shown that π(b1) can only contain real agents (recall that ϕb1 (π∗ , π) ≤ 0) and that it has to contain exactly n Xagents corresponding to the agents forming coalitions with the Xt-agents in π∗ , all C-agents, and either aβ or a¬β for every Y variable.

We can now extract a truth assignment τ ′Y to Y from the Y -agents contained in π(b1). The only way that π is more popular than π∗ is when all C-agents prefer π over π∗ which, due to the valuations by the C-agents of the agents corresponding to their respective literals, can only happen if τX and τ ′Y evaluate every clause to FALSE. This implies that ψ(τX , τ ′Y ) = FALSE, a contradiction. We thus conclude this part of the proof.

4.3 Popular Partition Implies Satisfiability

Throughout this section, we assume that there is a popular partition π∗ in the reduced ASHG. We will prove that this implies that the source instance is a Yes-instance to 2QUANTIFIED 3-DNF-SAT. The detailed proof of this statement can be found in the full version of our paper. In this section, we give an overview of the proof.

Our main goal is to show that π∗ has a structure similar to that of the popular partition defined in Section 4.2 (up to symmetries), which will enable us to extract a satisfying truth assignment to the variables in X by looking at the coalitions of the Xt-agents.

As a first step, we show that left-side and right-side agents cannot form a joint coalition. Suppose a coalition S ∈ π∗ contains both a left-side and a right-side agent. The only agents who may have a nonnegative utility in such a coalition are b1, b2, and real agents, and thus S must contain some combination of agents b1 and b2. If both b1 and b2 are in S, then the partition obtained from π∗ by extracting b1 and b2 from S, and forming the coalitions {b1} ∪ T1 and {b2} ∪ T2, can be shown to be more popular. So, only one of b1 and b2 may reside in S. Denote bj ∈ S, and bi /∈ S, where i, j ∈ {1, 2}. Hence, it is easy to see that we must have either π∗ (bi) = {bi} ∪ T1 or π∗ (bi) = {bi} ∪ T2. Without loss of generality, assume π∗ (bi) = {bi} ∪ T1. Now, intuitively, we can think of T1, T2, and S \ {bj} as the agents t1, t2, and t3 from the No-instance discussed in Section 4.1, respectively. A deviation analogous to that discussed in the context of this No-instance shows that this partition is not popular.

Having established that the left and right side are separated, the only possibility for π∗ to be popular is if agents form coalitions with their corresponding agents, who give them positive utility. Specifically, the following must hold.

1. For the left side, we have that {b1}∪T1 ∈ π∗ and {b2}∪ T2 ∈ π∗ , or {b2} ∪ T1 ∈ π∗ and {b1} ∪ T2 ∈ π∗ .
2. We have that C ∪C ′ ∈ π∗ .
3. For each aβ ∈ Y , we have that {aβ, a′β } ∈ π∗ .
4. For each x ∈ X, we have that {ax, xt} ∈ π∗ and {a¬x, xf } ∈ π∗ , or {ax, xf } ∈ π∗ and {a¬x, xt} ∈ π∗ .

This allows us to define the following truth assignment τX to the X variables. For each x ∈ X, x is assigned TRUE if and only if π∗ (ax) = {ax, xt} (by Item 4, this is a valid assignment). We claim that τX is a satisfying assignment to the 2-QUANTIFIED 3-DNF-SAT instance, i.e., that ψ(τX , τY) = TRUE for all truth assignments τY to the Y variables.

Assume otherwise, namely that there exists a truth assignment τ ′Y to the Y variables such that ψ(τX , τ ′Y ) = FALSE. We will now find a partition that is more popular than π∗ . Recalling Item 1, let us assume without loss of generality that {{b1} ∪ T1, {b2} ∪ T2} ⊆ π∗ . Consider the partition π obtained from π∗ as follows.

• Extract all aα ∈ X such that {aα, xt} ∈ π∗ , for some xt ∈ Xt, all aβ ∈ Y such that the literal represented by aβ is assigned TRUE by τ ′Y , and all C-agents and agent b1. With them, form a new coalition S.
• Extract b2 from her coalition, and set π(b2) = {b2}∪T1.

Note that the new coalition S consists of 2n +m+ 1 agents. Moreover, by definition of τX , if τX assigns TRUE to x, then S contains ax and if τX assigns FALSE to x, then S contains a¬x. In addition, for y ∈ Y, S contains ay if τ ′Y assigns TRUE to y and S contains a¬y if τ ′Y assigns FALSE to y.

We compute the popularity margin between π and π∗ . Let c ∈ C. Since ψ(τX , τ ′Y ) = FALSE, we have that c has at most two literals in S assigned TRUE by τX and τ ′Y . Hence, since the X- and Y -agents in S correspond to the literals assigned TRUE by τX and τ ′Y , there are at most two X- or Y -agents in S to whom ac assigns value -2 (to the other X- or Y - agents she assigns 0). Therefore, all C-agents prefer π over π∗ . Thus, it is simple to check that ϕR(π∗ , π) = -1 (which stems from the fact that |C ′ | - |C| = -1). Furthermore, we have ϕL(π∗ , π) = 0 (T1-agents prefer π, T2-agents prefer π∗ , and b1 and b2 are indifferent between the partitions). Altogether, we conclude that ϕ(π∗ , π) = -1, in contradiction to π∗ being a popular partition. Hence, (X, Y, ψ) is a Yes-instance of 2-QUANTIFIED 3-DNF-SAT.

5 Popularity in Nonnegative FHGs

In this section, we discuss the reduction of Theorem 2. Due to space constraints, we only describe the proof using the illustration of Figure 4. The detailed proof is available in the full version of our paper [Bullinger and Gilboa, 2024].

The reduction for ASHGs in Theorem 1 used one blownup No-instance, where the whole combinatorics of the source problem had replaced the role of a single agent. For FHGs, the combinatorics of the source instance is still encoded similarly. Literals are still represented by X- and Y -agents and once again, they have good options to form coalitions together with their corresponding structure agents by forming coalitions {ax, xt} and {a¬x, xf , xf ′} or {a¬x, xt} and {ax, xf , xf ′} for the X-agents, and coalitions {aβ, a′β , a′′ β } for the Y -agents. As in the proof for ASHGs, the coalitions of the Xt-agents in popular partitions correspond to satisfying truth assignments for the variables in X.

However, the combinatorics of the source instance is not embedded in a single No-instance, but multiple No-instances are used as gadgets. The gadgets are FHGs induced by a star graph, which are known to not admit popular partitions [Brandt and Bullinger, 2022] (see the left part of Figure 4).

This implies that popular partitions have to contain coalitions of some agent in the gadgets with another agent outside the gadgets. We have one star gadget for every clause and the only agent that is linked to the gadget by a positive valuation is its corresponding clause agent. We will see that the only possibility to achieve popularity is to use this single connection by forming coalitions of the type {ac, ℓ6c }.

To prove Theorem 2, we will show that the logical formula is satisfiable if and only if there exists a popular partition in the constructed FHG. Every truth assignment lets us define a popular partition along these ideas, while we can show that every popular partition has such a structure and lets us extract a truth assignment.

6 Conclusion

We considered the complexity of deciding whether popular partitions exist in typical classes of hedonic games. By showing that this problem is Σp2 -complete, we pinpoint its precise complexity for ASHGs and FHGs with nonnegative valuation functions. Hence, allowing coalitions of size at least three can raise the complexity of popularity from completeness for the first to the second level of the polynomial hierarchy.

Our work is an important step in understanding popularity in coalition formation. However, there are still various dimensions along which a deeper understanding would be welcome. Firstly, our methods might aid in resolving the exact complexity of popularity in other classes of coalition formation games for which popularity was considered before [Kerkmann et al., 2020; Kerkmann and Rothe, 2020; Brandt and Bullinger, 2022; Cseh and Peters, 2022]. Secondly, it would be interesting to consider popularity in other classes of hedonic games, such as modified fractional hedonic games [Olsen, 2012] and anonymous hedonic games [Bogomolnaia and Jackson, 2002].

Finally, popularity has the closely related concepts of strong popularity, where a partition has to strictly win the vote in a pairwise comparison against every other partition, and mixed popularity, which considers probability distributions of partitions that are popular in expectation. In the domain of matching, strong popularity and mixed popularity were first considered by Gärdenfors [1975] and Kavitha et al. [2011], respectively, and studied by Brandt and Bullinger [2022] in ASHGs and FHGs. In these classes, Brandt and Bullinger [2022] show that deciding whether a strongly popular partition exists is coNP-hard 3 while computing a mixed popular partition is NP-hard. The exact complexity of both problems remains open. Notably, Σp2 seems not to be the right complexity class for these problems because mixed popular partitions always exist and strongly popular partitions are unique whenever they exist. Resolving their complexity could lead to an intriguing complexity picture of concepts of popularity in hedonic games.

3 This aligns with known complexity results for strong popularity in other classes of coalition formation games [Kerkmann et al., 2020; Kerkmann and Rothe, 2020].

Acknowledgments

Martin Bullinger was supported by the AI Programme of The Alan Turing Institute. Matan Gilboa was supported by an Oxford-Reuben Foundation Graduate Scholarship. We would like to thank Edith Elkind for many fruitful discussions.