Beyond the Common Ranking Property: Stable and Efficient Outcomes in Hedonic Games with Top-Coalition Properties

1 Introduction

Coalition formation [Shenoy, 1979] is a central theme in multi-agent systems, where autonomous agents must decide how to group themselves to pursue individual and collective goals. Hedonic games [Aziz and Savani, 2016], first introduced by Dr`eze and Greenberg [Dr`eze and Greenberg, 1980] and later developed by Banerjee, Konishi, and S¨onmez [Banerjee et al., 2001], as well as Bogomolnaia and Jackson [Bogomolnaia and Jackson, 2002], provide one of the most fundamental and well-studied frameworks for this purpose: each agent's preferences depend solely on the members of its coalition. Hedonic games have since been widely investigated in economics, artificial intelligence, and algorithmic game theory, and form the basis of applications ranging from team formation [Alcalde and Revilla, 2004] and task allocation [Saad et al., 2011; Jang et al., 2018] to matching markets [Gale and Shapley, 1962; Irving, 1985; Manlove, 2013] and social choice [Brandt et al., 2016].

Recurring challenges in the study of hedonic games arise from the fact that many important subclasses are characterized by negative results. Core stability and Nash-type stability often fail to exist [Fanelli et al., 2025], and determining their existence is typically computationally intractable [Peters and Elkind, 2015]. These difficulties were recognized early on: Bogomolnaia and Jackson [Bogomolnaia and Jackson, 2002] introduced structural restrictions on utilities, such as additive separability and anonymity, and proposed weaker stability notions-individual stability, which restricts deviations compared to Nash stability, and contractual individual stability, which restricts them even further. Neither additive separability nor anonymity alone guarantees the nonemptiness of the core, even when further strengthened by structural assumptions such as single-peakedness or the intermediate preference property-conditions known to ensure stability in congestion-free environments (see [Greenberg and Weber, 1986; Greenberg and Weber, 1993])-since cyclical coalitional deviations may still arise [Banerjee et al., 2001].

To overcome this limitation, Farrell and Scotchmer [Farrell and Scotchmer, 1988] introduced hedonic games with the common ranking property (HGCRP), which require a linear ordering over all coalitions that coincides with each agent's preference over coalitions containing them. They proved that every instance of HGCRP admits a core-stable (CS) partition, computable via a simple greedy algorithm. Building on this, Banerjee, Konishi, and S¨onmez [Banerjee et al., 2001] introduced hedonic games with the top-coalition property (HGTCP) and hedonic games with the weak topcoalition property (HGWTCP), which successively relax HGCRP yet still guarantee the nonemptiness of the core. They also showed that HGWTCP is a particularly compelling domain, since it subsumes several economically motivated game forms, including Becker's marriage game [Becker,

1973], transferable utility games with proportional sharing, B´enassy's uniform reallocation economy [B´enassy, 1982], Shapley and Scarf's housing market [Shapley and Scarf, 1974], and Moulin and Shenker's average cost sharing problem [Moulin and Shenker, 1994].

Subsequent research strengthened these positive results by exploring richer stability and efficiency notions. Dimitrov [Dimitrov, 2006] introduced the concept of semistrict core stability, a refinement of core stability that lies between the core and the strict core, and proved that in HGTCP the semistrict core is always nonempty and, moreover, coincides with the core in HGCRP. Caskurlu and Kızılkaya [Caskurlu and Kizilkaya, 2024] established that every HGCRP instance admits a partition that is simultaneously CS, individually stable (IS), and Pareto optimal (PO). They further showed that a CS and IS partition can be computed in polynomial time, although finding a PO partition is NP-hard. Building on these results, Caskurlu and Eser [Caskurlu and Eser, 2025] proved that every HGCRP instance has a partition that is both strongly individually stable (SIS) and Pareto optimal, and that SIS outcomes can be found efficiently. They also demonstrated the existence of partitions that are contractually Nash stable (CNS) and PO, and analyzed a comprehensive family of stability and optimality notions, showing that beyond these two positive results no further extensions are possible for HGCRP. Since the common ranking property implies the top-coalition and weak top-coalition properties, the nonexistence results for HGCRP directly carry over to HGTCP and HGWTCP, leaving open the question of whether stability or efficiency guarantees for HGCRP can be achieved in the broader domains of HGTCP and HGWTCP.

Our Contributions. In this paper, we address this open question by extending the frontier of strong stability and efficiency guarantees beyond HGCRP to the broader domains of HGTCP and HGWTCP. We prove that every HGWTCP instance admits an SIS partition, and that such a partition can be found in polynomial time. We also show that, in the case of strict preferences, an SIS and PO partition can be found in polynomial time. We further demonstrate that a CNS partition may fail to exist even in HGTCP, in sharp contrast to HGCRP, where the existence of partitions that are both CNS and PO is guaranteed. Collectively, these results offer a comprehensive view of stability and efficiency in topcoalition-based hedonic games, tracing the evolution of guarantees from HGCRP to HGWTCP.

1.1 RelatedWork

HGCRP instances are closely related to several other models of cooperative and noncooperative interaction. In particular, it can be viewed as the cooperative analogue of resource selection games (RSGs), a restricted subclass of singleton congestion games [Ieong et al., 2005]. In RSGs, agents are partitioned into groups that jointly use the same resource and receive identical utilities [Feldman and Tennenholtz, 2010]. The existence and computation of equilibria in such games-under varying coordination and behavioral assumptions-have been extensively studied, [Anshelevich et al., 2013a; Caskurlu et al., 2021; Caskurlu et al., 2022; Caskurlu et al., 2020]. This connection highlights the close relationship between cooperative stability in HGCRP and equilibrium analysis in congestion-type environments.

Another line of closely related work explores subclasses of HGCRP that impose additional structure on coalition utilities. Caskurlu, Kızılkaya, and Ozen [Caskurlu et al., 2024] introduced the class of hedonic expertise games (HEGs), which model coalition formation among agents with complementary skills. HEGs resemble coalitional skill games [Bachrach et al., 2013; Tran-Thanh et al., 2013] in that each agent is endowed with a set of skills, and for each skill the coalition's utility depends on the highest level achieved by any agent in the group. HEGs are characterized by joint utility functions that are both monotone and submodular, and include a coalition-size parameter κ to ensure nontrivial outcomes-since without such a bound, monotonicity would make the grand coalition universally optimal. The authors also examined monotone HGCRP, a related subclass where the joint utility function is monotone but not necessarily submodular, and provided an extensive analysis of the existence and nonexistence of stable and efficient partitions. Their results show that HEGs and monotone HGCRP share the same existence guarantees for standard stability notions, while differing in computational complexity. Caskurlu and Eser [Caskurlu and Eser, 2025] further introduced and studied submodular HGCRP, a natural subclass that subsumes HEGs where the joint utility function satisfies submodularity-a property capturing diminishing returns and frequently arising in coalition formation on graphs, such as in social or networked settings. This framework also generalizes several graph-based games, including certain forms of cut games [Anshelevich et al., 2013b].

Because each agent's preference relation in a hedonic game is defined over all possible coalitions that include it, representing a general hedonic game requires space exponential in the number of agents. Consequently, a rich literature has explored compact representations that encode preferences concisely while preserving expressiveness. Examples include additively separable hedonic games [Bogomolnaia and Jackson, 2002], where each player assigns values to others and ranks coalitions by their sum (or average, in fractional variants [Aziz et al., 2019]); anonymous hedonic games [Banerjee et al., 2001], where preferences depend only on coalition size; and Boolean or hedonic coalition net representations [Aziz et al., 2016; Elkind and Wooldridge, 2009], which use logical formulas or weighted clauses to encode coalitional satisfaction. Other representations capture additional structural restrictions, such as W-preferences [Cechl´arov´a and Hajdukov´a, 2004] and B-preferences [Hajdukova, 2006; Cechl´arov´a and Hajdukov´a, 2003; Aziz et al., 2012]. Another widely used compact representation is the individually rational coalition list (IRCL) [Ballester, 2004], which records only those coalitions that each player weakly prefers to being alone, omitting any coalition that could never appear in a stable outcome.

In this paper, we adopt the IRCL format, following the most relevant literature, since it explicitly enumerates only the coalitions that are individually rational for each agent. This representation is particularly suitable for our setting because all stability notions studied here from the perspective of computational complexity guarantee that no coalition containing a dissatisfied member can occur in an outcome. Moreover, when the number of individually rational coalitions is polynomial in the number of agents, the IRCL format provides a compact and complete encoding of the information relevant to stability analysis. Accordingly, all our algorithmic and complexity results assume that the input is presented in IRCL form.

2 The Model and Definitions

A hedonic game G = (N, (≿i)i∈N) is defined by a finite set of agents N = {1, . . . , n} and, for each agent i ∈ N, a preference relation ≿i over Si(N) = {S ⊆ N : i ∈ S}, the set of all coalitions containing agent i. For any coalitions S, T ⊆ N with i ∈ S ∩ T , we write S ≻i T if S ≿i T and not T ≿i S. A partition (coalition structure) π = {S1, S2, . . . , SK} of N is a collection of disjoint, nonempty coalitions whose union is N. For each agent i, we denote by π(i) the coalition of i in π. The outcome of a hedonic game is represented by such a partition.

2.1 Stability Concepts

Stability concepts in hedonic games differ in how they restrict agents' ability to deviate from a given partition. We distinguish between concepts based on individual deviations and those based on group deviations. The stability concepts we use in this paper are defined below.

Individual-Deviation-Based Stability In these concepts, agents may deviate one by one. Let π be a partition, and consider an arbitrary move by agent i from π(i) to another coalition C ∈ π ∪ {∅}. We then have:

• Nash stability (NS) if no such profitable move exists, i.e., π(i) ≿i C ∪ {i}.
• Individual stability (IS) if no such profitable move exists without making an agent j ∈ C worse off, i.e., C ∪ {i} ≻i π(i) implies C ≻j C ∪ {i} for some j ∈ C.
• Contractual Nash stability (CNS) if no such profitable move exists without making an agent j ∈ π(i) worse off, i.e., C ∪ {i} ≻i π(i) implies π(i) ≻j π(i) \ {i} for some j ∈ π(i).

While some definitions of CNS in the literature implicitly include IS by requiring consent from both the target and departing coalitions, we follow the standard decomposition [Bogomolnaia and Jackson, 2002] where CNS strictly focuses on the consent of the departing coalition.

Group-Deviation-Based Stability

• A coalition C is said to block π if C ≻i π(i) for all agents i ∈ C. A partition π is core stable (CS) if no coalition blocks π.
• A coalition C is said to weakly block π if C ≿i π(i) for all agents i ∈ C and C ≻j π(j) for an agent j ∈ C. A partition π is strict core stable (SCS) if no coalition weakly blocks π.
• A partition π′ is reachable from partition π by movements of agents S ⊆ N if ∀i, j ∈ N \S : π(i) = π(j) ⇔ π′ (i) = π′ (j). We write π S-→ π′ to denote this reachability relation.
• A subset of agents S ⊆ N is said to strongly individually block π if π S-→ π′ and π′ (i) ≻i π(i) for every i ∈ S, and π′ (j) ≿j π(j) for every j ∈ π′ (i) receiving deviators. A partition π is strongly individually stable (SIS) if no subset of agents strongly individually blocks π.
• A partition π is Pareto optimal (PO) if there is no other partition π′ such that π′ (i) ≿i π(i) for every i ∈ N, with strict preference for at least one agent.
• A partition π is perfect if all agents are in one of their most preferred coalitions.

The relations between these stability concepts are summarized in Figure 1.

2.2 Common Ranking and Top-Coalition Properties

A hedonic game satisfies the common ranking property if there exists a ranking ≿ on 2N \ {∅} such that for any player i ∈ N, and any coalitions S, T ∈ Si(N) containing i, we have S ≿i T ⇐⇒ S ≿ T . Thus, all agents share a common ranking over coalitions that include them. A game satisfying this property is called a hedonic game with the common ranking property (HGCRP).

The top-coalition property relaxes the common ranking property by requiring that within every nonempty subset of agents V ⊆ N, there exists a nonempty top coalition S ⊆ V such that, for every i ∈ S and T ⊆ V with i ∈ T, we have S ≿i T. Hence, within any population V , some coalition S is most preferred by all its members among all coalitions in V . A game satisfying this condition is called a hedonic game with the top-coalition property (HGTCP).

The weak top-coalition property (HGWTCP) further relaxes this condition. A coalition S ⊆ V is a weak topcoalition of V if there exists an ordered partition S = (S1 , . . . , S ℓ ) of S satisfying the Weak Top-Layering Condition: for every k ∈ [1, ℓ] and every i ∈ S k , any coalition T ⊆ V with T ≻i S must contain an agent from ⋃j<k Sj . Intuitively, agents in S1 most-prefer S within V , while those in later layers require the "cooperation" of preceding agents to form any strictly better alternative.

Cardinality tuple and maximality For any such S, we define its cardinality tuple as the length-n vector Λ(S) =

(|S1 |, . . . , |S ℓ |, 0, . . . , 0). Among all such partitions of S, there is a unique S ⋆ that lexicographically maximizes this tuple; we define the cardinality tuple of S as Λ(S) = Λ(S ⋆ ).

To illustrate, let N = {1, . . . , 5}, V = {1, . . . , 4}, and S = {1, 2, 3}. Suppose S is agent 1's most-preferred coalition in V , while for agents 2 and 3 it is their second choice, behind {1, 2} and {1, 3} respectively. Here, S is a weak topcoalition with maximal ordered partition S ⋆ = ({1}, {2, 3}) and Λ(S) = (1, 2, 0, 0, 0). Agent 1 anchors the first layer; agents 2 and 3, despite having better alternatives, cannot form them without agent 1, and thus safely form the second layer. Note that S = ({1}, {2}, {3}) also satisfies the weak toplayering condition, but its tuple (1, 1, 1, 0, 0) is lexicographically smaller than Λ(S).

Hierarchy of Properties The common ranking property strictly implies the top-coalition property, which strictly implies the weak top-coalition property [Banerjee et al., 2001].

Game Representation Because preference profiles in hedonic games require exponential space in the number of agents, compact representations are often employed. In this paper, we adopt the individually rational coalition list (IRCL) representation [Ballester, 2004], storing for each agent i only coalitions S ≿i {i}.

IRCL input convention (chained order) We assume each IRCLi is a preference-ordered chain (Si,1, . . . , Si,mi ). We denote the maximum list length by m = maxi mi and the total input size by M = ∑i mi. This linearization provides a successor map nexti(Si,t) = Si,t+1 and starting pointer head(i) = Si,1. An unordered list can be converted via stable sorting in O(M logm) time. This convention is without loss of generality and facilitates our algorithms.

3 Existence and Computation of Stable Partitions

In this section, we investigate the existence and computation of stable partitions in HGTCP and HGWTCP. We begin by summarizing nonexistence results that follow from earlier work on HGCRP, which delineate the limits of achievable stability and efficiency guarantees in more general domains. We then present a constructive result showing that SIS partitions are guaranteed to exist and can be found in polynomial time for HGWTCP. Next, we show that when preferences are strict, our algorithm computes a partition that is both SIS and Pareto optimal. Finally, we present a nonexistence result for CNS partitions, highlighting a structural separation between HGCRP and its generalizations.

3.1 Implied Nonexistence Results from the Literature

We begin by recalling the most comprehensive characterization of stability and efficiency in HGCRP due to Caskurlu and Eser [Caskurlu and Eser, 2025]. They showed that a partition that is both CNS and Pareto optimal can be computed in polynomial time, that every HGCRP instance admits a partition that is both SIS and Pareto optimal, and that no stronger combination of stability and efficiency notions can be guaranteed. Since the common ranking property implies both the top-coalition property and the weak top-coalition property, the corresponding impossibility results in [Caskurlu and Eser, 2025] apply directly to HGTCP and HGWTCP. We present these results below as Theorem 1.

Theorem 1. The following statements are true:

1. An HGTCP (and thus HGWTCP) instance may not admit an SCS partition.
2. An HGTCP (and thus HGWTCP) instance may not admit a partition that is simultaneously CNS and IS.
3. An HGTCP (and thus HGWTCP) instance may not admit a partition that is simultaneously CNS and CS.

3.2 ComputingWeak Top-Coalitions

We first present a verification routine (Algorithm 1) that, given a candidate coalition S ⊆ N, either returns its maximal ordered partition (thereby certifying that S is a weak top-coalition of the current ground set V , initially V = N) or certifies failure. We then wrap this routine in a finder that returns some weak top-coalition of the current ground set.

Algorithm 1 VERIFYWEAKTOP(S)

1: A ← ∅ {Assigned agents} 2: R←S {Remaining agents} 3: S ← [ ]; k ← 0 4: while R ̸= ∅ do 5: k ← k +1; Sk ← ∅ 6: for each i ∈ R do 7: ok ← true 8: for each T ∈ IRCLi such that T ≻i S do 9: if T ∩ A = ∅ then 10: ok ← false; break 11: end if 12: end for 13: if ok then 14: Sk ← Sk ∪ {i} 15: end if 16: end for 17: if Sk = ∅ then 18: return ∅ 19: end if 20: Append Sk to S; A←A∪Sk ; R←R \ Sk 21: end while 22: return S

Proof of Correctness. Success case. Suppose S is a weak top-coalition. We will show that the algorithm returns its maximal ordered partition by induction on k, the position within the ordered partition.

Base case (k = 1): By construction, we define

Thus, S1 consists of all agents for whom S is a mostpreferred coalition in N. It follows that S1 has the maximal cardinality among all feasible first sets.

Inductive step: Assume that for some k ≥ 1, the sets S1 , . . . , S k defined by the algorithm are maximal. Consider the construction of Sk+1 . At this stage, we have A = ⋃kj=1 Sj and R = S \ A. The algorithm assigns

Thus, Sk+1 contains exactly those agents in R who cannot be strictly improved relative to S without involving agents already assigned to earlier layers. This set is maximal and has the largest possible cardinality given the prior choices S1 , . . . , S k .

By induction, the algorithm constructs an ordered partition (S1 , S2 , . . . , S ℓ ) with the cardinalities of the earlier sets maximized lexicographically. Thus, the algorithm correctly outputs the maximal ordered partition of S when it is a weak top-coalition of N.

Failure case. Suppose S is not a weak top-coalition of N. Apply Algorithm 1 to S and let k ≥ 1 be the first iteration at which no agent is eligible for the next layer. Let

so the algorithm would define

By definition of k, we have Sk = ∅. Hence, for every i ∈ R, there exists T ∈ IRCLi with i ∈ T ⊆ N, T ≻i S, and T ∩ A = ∅, which is precisely the negation of the weak top-layering condition at level k. Therefore the while-loop terminates and the algorithm returns ∅.

Proof of Complexity. Each round ℓ inspects at most |S| agents. For each agent i ∈ R, the algorithm performs at most mi ≤ m comparisons. Each comparison involves a set intersection with A, which takes O(|S|) time. Therefore, each layer takes O(m|S|2 ) time. There are at most |S| layers, so the total runtime is O(|S| · m|S|2 ) = O(m|S|3 ).

Having established a verifier for a given coalition, we now use it as a subroutine to recover a weak top-coalition of the current ground set V ⊆ N. Any weak top-coalition is most preferred by at least one of its members and therefore appears in some IRCLi; it thus suffices to scan the union of these lists and invoke VERIFYWEAKTOP on each candidate, returning at the first success. The resulting procedure is given next.

Implementation note (implicit scan). For each agent i, we traverse IRCLi from its head along nexti while coalitions remain tied with the head under ≿i. These are exactly i's mostpreferred coalitions in V . We invoke VERIFYWEAKTOP on each such coalition and return at the first success.

Algorithm 2 FINDWEAKTOP(V )

1: for each i ∈ V do 2: S ← head(i) 3: while S ̸= ⊥ and S ∼i head(i) do 4: S ⋆ ← VERIFYWEAKTOP(S) 5: if S ⋆ ̸= ∅ then 6: return (S, S ⋆ ) 7: end if 8: S ← nexti(S) 9: end while

10: end for

Proof of Correctness. By the weak top-coalition property, there exists a weak top-coalition S⋆ of V with ordered partition (S1 , . . . ). For every i ∈ S 1 , S⋆ is (weakly) mostpreferred for i within V . Hence, while scanning i's chain from head(i) through its top indifference class, the algorithm visits S⋆ and calls VERIFYWEAKTOP (unless it had already found a weak top-coalition earlier). By Lemma 1, this call returns the maximal ordered partition of S⋆ , and the algorithm returns.

Proof of Complexity. For each agent i ∈ V , the inner whileloop advances across at most ti coalitions (those tied with head(i)). Therefore the total number of verifier calls is at most t = ∑i∈V ti. Each call to VERIFYWEAKTOP runs in O(m|V |3 ) time by Lemma 1. Hence the overall time is O(tm|V |3 ).

3.3 Existence and Computation of Strong Individually Stable Partitions

The main result of this subsection, stated as Theorem 2, shows that every HGWTCP instance admits an SIS partition, and that such a partition can be computed in polynomial time. The procedure, presented as Algorithm 3, generalizes the greedy construction of [Caskurlu and Eser, 2025] that yields an SIS partition for HGCRP.

Algorithm 3 Greedy Construction of an SIS Partition for HGWTCP

• 1: Initialize π ← ∅, R←N.
• 2: while R ̸= ∅ do
• 3: S, S ⋆ ← FINDWEAKTOP(R)
• 4: π ← π ∪ {S}.
• 5: R←R \ S.
• 6: end while
• 7: return π

Theorem 2. Every HGWTCP instance admits a strongly individually stable partition. Moreover, such a partition can be computed in polynomial time by Algorithm 3.

Proof of Correctness. Let π be the partition returned by Algorithm 3 for an HGWTCP instance G = (N, (≿i)i∈N). Let Ri ⊆ N denote the set of agents that remain unassigned at the beginning of the i-th iteration, and let Si ⊆ Ri be the weak top-coalition selected in that iteration. We show, by induction on i, that no agent in Si can be part of a strongly individually blocking coalition.

Base case (i = 1). Since R1 = N, the first coalition S1 is a weak top-coalition of the entire player set. Let (S1 , . . . , S ℓ ) denote its maximal ordered partition as guaranteed by the weak top-coalition property. We prove by an inner induction on k that no agent in Sk can be in a blocking coalition.

For k = 1, all agents in S1 are in one of their most preferred coalitions and thus have no incentive to deviate. Assume the claim holds for all Sj with j < k. For any agent a ∈ Sk , forming a coalition that a strictly prefers to π(a) requires cooperation from at least one agent in ⋃j<k Sj by the weak top-coalition property.

By the induction hypothesis, such agents will not cooperate, implying that no member of Sk can join a strongly individually blocking coalition. Thus, no agent in S1 can be part of a strongly individually blocking coalition.

Inductive case. Assume that for all q < i, no agent in Sq can be part of a strongly individually blocking coalition. Consider the i-th iteration, when the algorithm selects a weak topcoalition Si with ordered partition (S1 , . . . , S ℓ ). We again use an inner induction on k.

For k = 1, all agents in S1 belong to one of their most preferred coalitions among those consisting entirely of unassigned agents. Since previously fixed agents (from earlier iterations) never join blocking deviations by the outer induction hypothesis, these agents have no profitable deviation available.

Assume that no agent in Sj participates in a blocking coalition for j < k. Consider any agent a ∈ S k . By the weak top-layering condition, a cannot form a coalition in Sa(Ri) that she strictly prefers to π(a) without the cooperation of at least one agent in ⋃j<k Sj . Crucially, moving to a successive layer Sk′ with k′ > k cannot assist agent a in forming a strictly preferred coalition within Ri, as any such coalition T ≻a Si is by definition blocked by the lack of cooperation from agents in preceding layers. By the inner induction hypothesis, such agents do not cooperate. Therefore, a cannot participate in a strongly individually blocking deviation.

Since the claim holds for all i and all k, no agent in any coalition Si can join a strongly individually blocking coalition. Thus, the final partition π produced by Algorithm 3 is strongly individually stable.

Proof of Complexity. To establish polynomial-time complexity, we analyze each component of Algorithm 3.

Within each iteration, the algorithm finds a weak topcoalition from the remaining agents R ⊆ N by calling FINDWEAKTOP(R). The time complexity of this procedure is O(tm|R|3 ) by Lemma 2. Trivially, we have ti ≤ mi ≤ m, t ≤ nm and |R| ≤ n, which translates to a time complexity of O(m2n4 ) per iteration.

Since the main loop executes at most n times, the overall time complexity of Algorithm 3 is O(m2n5 ), which is polynomial in both the number of agents and the maximum preference list size.

3.4 Strong Individual Stability and Pareto Optimality under Strict Preferences

We now show that, under strict preferences, the greedy construction of Algorithm 3 yields not only a strongly individually stable partition but also a Pareto optimal one.

Theorem 3. Let G = (N, (≻i)i∈N) be an HGWTCP instance with strict preferences. Then Algorithm 3 computes, in polynomial time, a partition that is both strongly individually stable (SIS) and Pareto optimal (PO).

Proof. Let π be the partition produced by Algorithm 3, and let S1, S2, . . . , SK denote the sequence of weak topcoalitions selected in successive iterations of the algorithm.

We prove by induction on the iterations i that any partition π′ that Pareto dominates π must coincide with π on all coalitions S1, . . . , Si chosen so far.

In the first iteration (i = 1), S1 is a weak top-coalition of N. Let (S1 , . . . , S ℓ ) denote its maximal ordered partition. Since preferences are strict, every agent j ∈ S1 is assigned to her unique most preferred coalition. Hence, any partition π′ satisfying π′ (j) ⪰j π(j) for all j ∈ S 1 must contain S1 as a coalition.

Assume now that for some i ≥ 1, every Pareto-dominating partition coincides with π on S1, . . . , Si. Consider iteration i+1, where Algorithm 3 selects Si+1 as a weak top-coalition of the remaining agents. Let (S1 , . . . , S ℓ ) denote its maximal ordered partition. By strictness of preferences, each agent in S1 is again assigned to her unique most preferred coalition among the unassigned agents. Therefore, any partition that Pareto dominates π and agrees with it on earlier coalitions must also contain Si+1.

By induction, any Pareto-dominating partition must coincide with π on all coalitions selected by the algorithm. Hence, no partition can strictly Pareto improve upon π, and π is Pareto optimal.

Strong individual stability follows from Theorem 2.

3.5 Nonexistence of Contractually Nash Stable Partitions

Theorem 4. Not every HGTCP (and thus HGWTCP) instance admits a CNS partition, even when preferences are strict.

Proof. Consider an HGTCP instance G = (N, (≻i)i∈N) with N = {1, 2, 3, 4, 5}. Every agent i follows a strict preference ordering ≻i over coalitions containing i, defined by a common hierarchy over coalition sizes:

Within each size class, agents rank coalitions lexicographically by their members, with the following agent-specific exceptions for coalitions of size 3:

• ≻1: {1, 4, 5} ≻1 {1, 2, 3} ≻1 {1, 3, 5} ≻1 {1, 2, 4}

• ≻3: {1, 2, 3} ≻3 {3, 4, 5} ≻3 {2, 3, 5} ≻3 {1, 3, 4}
• ≻4: {2, 3, 4} ≻4 {1, 4, 5} ≻4 {1, 3, 4} ≻4 {2, 4, 5}

where all other size-3 coalitions containing the agent follow in lexicographical order. Since preferences are size-based and every agent i ranks all size-2 coalitions containing i at the very top, G satisfies the top-coalition property: for any V ⊆ N, if |V | ≥ 2, the lexicographically lowest size-2 coalition in V is a top-coalition; if |V | = 1, the singleton itself is the top-coalition.

Now we show that G does not possess a CNS partition. Let π be a partition. We perform a case analysis on the integer partitions of 5:

• [5] (Grand Coalition): Any agent i ∈ N strictly prefers being alone (size 1) over the grand coalition (size 5). Since the remaining agents j ∈ N \ {i} also strictly prefer their size-4 coalition over the size-5 one, i can leave contractually.
• [4|1]: Let S be the coalition of size 4. Any agent i ∈ S strictly prefers being alone (size 1) over S (size 4). Since agents in S \ {i} prefer their new size-3 coalition over S, i can leave contractually.
• [3|1|1], [2|1|1|1], [1|1|1|1|1]: Any agent i in a singleton coalition can contractually move to join another singleton, as both i and the target agent strictly prefer a size-2 coalition.
• [2|2|1]: The agent in the singleton can contractually join either size-2 coalition to form a strictly preferred size-3 coalition, which the target agents also prefer over their current size-2 coalition.
• [3|2]: We exhaustively show that no partition of this structure is CNS:

where →i corresponds to the movement of agent i.

Thus, G is a hedonic game with top-coalition property which does not admit a CNS partition.

4 Conclusion and Future Research Directions

In this paper, we provided a comprehensive characterization of stability and efficiency in top-coalition-based hedonic games, generalizing the known frontier for the common ranking property in two critical ways. First, we proved that the fundamental existence and tractability guarantees of HGCRP carry over to the much broader domain of HGWTCP: every instance admits a strongly individually stable (SIS) partition computable in polynomial time, and in the case of strict preferences, this partition is additionally guaranteed to be Pareto optimal. Second, we established a sharp structural boundary by showing that contractually Nash stable (CNS) partitions, which always exist in HGCRP, may fail to exist even in the more restricted HGTCP subclass. Collectively, these results delineate the exact extent to which the strong properties of common rankings persist as the underlying preference structure is relaxed, offering a complete map of the stability landscape across the top-coalition hierarchy. Our findings naturally suggest several directions for future research.

Parameterized complexity of Pareto optimality It is known that finding a Pareto optimal partition is NP-hard even for HGCRP, yet our results show that when preferences are strict, a partition that is both SIS and Pareto optimal can be computed in polynomial time even for HGWTCP. This sharp contrast indicates that the computational hardness of Pareto optimality stems from the presence of indifferences rather than from the structural richness of the preference domain. A promising direction is therefore a parameterized complexity analysis of Pareto optimality in HGCRP, HGTCP, and HGWTCP, where the parameter captures the extent of indifference in agents' preferences. Natural parameters include the maximum size of an indifference class in an agent's coalition list, the total number of tied coalitions across all agents, or the number of agents with non-strict preferences. Such an analysis could lead to fixed-parameter tractable algorithms that interpolate smoothly between the strict and general preference settings.

Compactly representable subclasses with real-world structure Another important direction is the identification of compactly representable subclasses of HGTCP and HGWTCP that arise from real-world applications and admit efficient algorithms for stable outcome computation. Hedonic expertise games (HEGs) [Caskurlu et al., 2024] constitute one such example within HGCRP, but the enlargement of the stability-guaranteeing domain to HGWTCP opens the door to many additional models. As shown in [Banerjee et al., 2001], HGWTCP subsumes several economically motivated game forms that fall outside HGCRP. Developing new coalition formation models that fit within HGTCP or HGWTCP, together with concise representations and tailored algorithms, would further bridge the gap between theoretical guarantees and practical applicability.

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant No. 2110707.