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

2024/11/08 by Martin Bullinger, Bullinger, Martin, Matan Gilboa +1 · 3 citations
Economics, Econometrics and Finance · Physics and Astronomy · Social Sciences · #Computer Science and Game Theory (cs.GT) #Evolutionary Game Theory and Cooperation #FOS: Computer and information sciences #Opinion Dynamics and Social Influence #Sports Analytics and Performance

paper · pdf · doi:10.48550/arxiv.2411.05713

openalex publication_date 2024/11/08 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28

Abstract

We study coalition formation in the framework of hedonic games. There, a set of agents needs to be partitioned into disjoint coalitions, where agents have a preference order over coalitions. A partition is called popular if it does not lose a majority vote among the agents against any other partition. Unfortunately, hedonic games need not admit popular partitions and prior work suggests significant computational hardness. We confirm this impression by proving that deciding about the existence of popular partitions in additively separable and fractional hedonic games is Σ₂^p-complete. This settles the complexity of these problems and is the first work that proves completeness of popularity for the second level of the polynomial hierarchy.

Cited by

• Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
• Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
• Complexity of Strong Popularity in Additively Separable Hedonic Games

Related

• Complexity of Strong Popularity in Additively Separable Hedonic Games
• Simple Causes of Complexity in Hedonic Games
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
• Computing stable outcomes in symmetric additively-separable hedonic\n games
• Reaching Individually Stable Coalition Structures