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

摘要

Hedonic games are a central model of coalition formation, yet most of their general subclasses are marked by negative results: stable outcomes often fail to exist, and deciding their existence is typically computationally hard. The most notable exception is the class of hedonic games with the common ranking property (HGCRP), a nontrivial subclass that guarantees both the existence and tractability of stable partitions. The common ranking property implies the top-coalition property, which in turn implies the weak top-coalition property, forming a natural hierarchy of increasingly general domains. In this paper, we extend the frontier of strong existence and tractability results beyond the HGCRP to hedonic games with the top-coalition property (HGTCP) and hedonic games with the weak top-coalition property (HGWTCP). We show that every HGWTCP instance admits a strong individually stable (SIS) partition that can be computed in polynomial time, and prove that our polynomial-time algorithm generates a partition that is both SIS and Pareto optimal (PO) if preferences are strict. These results show that strong stability and tractability results persist well beyond the common ranking framework. We further show that a contractually Nash stable (CNS) partition may fail to exist even in HGTCP, revealing a sharp contrast with HGCRP, where the existence of partitions that are both CNS and PO is guaranteed. Taken together, these results provide a comprehensive characterization of stability and efficiency in top-coalition-based hedonic games, mapping how stability guarantees evolve from HGCRP to HGWTCP.