Complexity of Strong Popularity in Hedonic Games
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Complexity of Strong Popularity in Hedonic Games".
Jane: Here's the gist of the paper. In this paper, determining whether an additively separable hedonic game admits a strongly popular partition is complete for PCW, a complexity class lying between PNP and SP2 The paper proves that determining the existence of strongly popular partitions in additively separable hedonic games (ASHGs) is complete for PCW, which sits above PNP and below SP2 The authors resolve an open question regarding the precise complexity of this problem by showing that PCW is the correct class to capture strong popularity in ASHGs.
Tom: Defining Strong Popularity and Complexity Classes Strong popularity is defined as a partition being strictly better than any other partition in a majority vote among the agents In the context of ASHGs, this problem is denoted as Ashg-Strong-Popularity and was shown to be coNP-hard in
BB22: .
Jane: The paper introduces PCW (Polynomial Condorcet Winner) as a class that sits between PNP and SP2.
Tom: The Reduction from Ckt-Condorcet The proof establishes the PCW-hardness by reducing the problem of Ckt-Condorcet to Ashg-Strong-Popularity.
Title and authors: Jane: The paper starts by framing this as a problem in hedonic games, which are all about how agents choose coalitions or groups based on their preferences Ray07 and community detection New04. It sets up the scenario where agents have a preference order over all possible partitions of the set >
Tom: And then they introduce the core concept: strong popularity. The authors define it as a partition being strictly better than any other partition in a majority vote among all the agents >
Lu: They are looking at additively separable hedonic games, or ASHGs, where agents have additive valuations that determine their preferences and utility in a coalition is some aggregation of values they assign to the members of that coalition <ref:2607.27277#pg2>
Meng: So the naive question a listener might ask is how do you even represent all those possible partitions when there are, like, exponential number of them?
Jane: That’s the hurdle. The paper addresses this by focusing on cardinal hedonic games where agents assign individual values to each other agent >
Tom: And they tackle that representation problem by constructing a reduction from Ckt-Condorcet to ASHG, which is how they prove the complexity <ref:2607.27277#pg1>
Lalam: So, the main point here is that if you can solve this one type of game, you can solve all of them because of that reduction >
The paper's summary: Jane: Okay, so what’s the actual result they are claiming about finding these strongly popular partitions in ASHGs? They establish PCW-completeness for this problem <ref:2607.27277#pg1>
Tom: They’re proving that it’s complete for PCW, which is this complexity class sitting between PNP and SP2 GGKN25 This means determining if a strongly popular partition exists is as hard as any problem in PCW >
Lu: The key result they establish is that the existence of a Condorcet string implies the existence of a strongly popular partition <ref:2607.27277#pg3> This gives us a path to check for strong popularity >
Meng: That sounds like it’s giving us a constructive way to find the solution if one exists, which is helpful for AI design, but what does that string actually look like?
Jane: The paper shows that if a strongly popular partition exists, then there must be a Condorcet string for the instance >
Tom: And they characterize this structure by showing that all assignment gadgets and gate gadgets must have a popularity margin of exactly zero with respect to the partition and the string <ref:2607.27277#pg3>
The paper's improvements: Jane: They also touch on what makes strong popularity different from other stability notions like Nash or individual stability
BBS15, BBT24: It highlights that the unambiguity property required for strong popularity necessitates a less standard approach than those weaker concepts >
Lu: They explain that this uniqueness—that no two strongly popular partitions can coexist—is what separates it from weak popularity, which is why the complexity is higher <ref:2607.27277#pg3>
Tom: So, the improvement they offer is really showing that this specific uniqueness requirement forces a certain structural property on the solution >
Meng: If we think about deployment, does this mean that when we build a system to find this partition, we don't just need an approximation, but something exact?
Lalam: Yeah. The authors state they characterize the structure of the optimal partition pi* through numerous lemmas >
Conclusion: Jane: So to wrap up on this paper, determining if an additively separable hedonic game admits a strongly popular partition is complete for PCW <ref:2607.27277#pg1> which sits between PNP and SP2 GGKN25
Tom: The main implication is that we have the first natural complete problem for PCW, and this sets a benchmark for how hard it is to find strong popularity in these games >
Lu: It confirms that strong popularity isn't just another instance of weak stability problems; it requires a different class of tools because of that unambiguity requirement <ref:2607.27277#pg3>
Meng: For practical AI, this suggests that if you’re looking for the absolute best partition in a game, you might need to use an exact method instead of just aiming for a good approximation >
Lalam: And they suggest that this approach might extend to fractional and modified-fractional hedonic games because of how structure is characterized through those popular partitions <ref:2607.27277#pg3>
Matan Gilboa
University of Oxford
cs.GT, cs.CC
Submitted: 2026-07-29
Updated: 2026-11-08
Comments: This version includes additional results: Theorems 1.2 and 1.3. A preliminary version of Theorem 1.1 in this paper appeared as part of earlier versions of arXiv:2510.19084, when the two works formed a single manuscript
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 99/100
The gist: In this paper, determining whether an additively separable hedonic game admits a strongly popular partition is complete for PCW…
Key concepts
- Strong Popularity
- This is a very strict condition where one partition in a majority vote must be strictly better than every other possible partition. It requires an unambiguous winner, meaning no other outcome can tie or beat it, which makes the problem computationally harder.
- PCW (Polynomial Condorcet Winner)
- PCW is the complexity class that captures the difficulty of finding a strongly popular partition in additively separable hedonic games. It sits between PNP and SP2, meaning it represents a specific level of computational complexity for this type of preference game.
- Condorcet String
- A Condorcet string is a specific sequence derived from the game structure that must be satisfied if a strongly popular partition exists. The existence of such a string provides the necessary structural information to verify strong popularity efficiently.
Terminology
Summary
In this paper, determining whether an additively separable hedonic game admits a strongly popular partition is complete for PCW, a complexity class lying between PNP and SP2
The paper proves that determining the existence of strongly popular partitions in additively separable hedonic games (ASHGs) is complete for PCW, which sits above PNP and below SP2 The authors resolve an open question regarding the precise complexity of this problem by showing that PCW is the correct class to capture strong popularity in ASHGs.
Defining Strong Popularity and Complexity Classes
Strong popularity is defined as a partition being strictly better than any other partition in a majority vote among the agents In the context of ASHGs, this problem is denoted as Ashg-Strong-Popularity and was shown to be coNP-hard in [BB22]. The paper introduces PCW (Polynomial Condorcet Winner) as a class that sits between PNP and SP2. p. 2
The Reduction from Ckt-Condorcet
The proof establishes the PCW-hardness by reducing the problem of Ckt-Condorcet to Ashg-Strong-Popularity. This reduction involves constructing an ASHG where agents are defined based on Boolean circuits, and valuations are set up such that a Condorcet string exists if and only if a strongly popular partition exists in the constructed game. p. 7 The construction details the creation of various agent types, including X-agents, A-agents, G-agents, L-agents, W-agents, Z-agents, and V-voters. p. 5
Proof of PCW Completeness
The proof sketch demonstrates that the existence of a Condorcet string implies the existence of a strongly popular partition. The core of the proof involves showing that if a Condorcet string exists, then all gadgets comply with the string, leading to the conclusion that every component has a popularity margin of at least 0 with respect to (π∗, π), which contradicts strong popularity unless x′ = x∗. p. 2 Conversely, if a strongly popular partition exists, it implies the existence of a Condorcet string. p. 8
Characterization via Condorcet String
The paper shows that if a strongly popular partition exists, then there must exist a Condorcet string x∗ for the instance C. This is established by showing that properties derived from strong popularity, such as the structure of the partition π∗, force all gadgets to comply with xstar The final step involves showing that if another string x' exists such that sgn(Ci(x∗) − Ci(x')) <= 0, a contradiction arises regarding the number of V-agents who prefer π over πstar.
Implications for Other Stability Notions
The study highlights a difference between strong popularity and other stability notions like Nash, individual, and contractual stability. While existence problems for these notions are typically complete for NP or SP2 in various cardinal hedonic games, the unambiguity property required for strong popularity necessitates a less standard approach. p. 1 The authors speculate that this uniqueness may extend to fractional and modified-fractional hedonic games. p. 2
Conclusion on Unambiguity
The paper concludes by characterizing the structure of πstar through numerous lemmas, showing that all assignment gadgets and gate gadgets must have a popularity margin of exactly 0 with respect to (π∗, π) This confirms that strong popularity is a distinct complexity class from those associated with weaker stability concepts. The result settles the open problem regarding the precise complexity of determining existence in ASHGs. p. 0
Final Result Summary
It is PCW-complete to determine whether a given additively separable hedonic game admits a strongly popular partition This result establishes that strong popularity is captured by PCW, which sits above PNP and below SP2. The paper provides the first natural complete problem for PCW and the first completeness result for strong popularity in hedonic games. p. 2 The work suggests that the unambiguity property requires a less standard approach. p. 2
References
[ABB+19] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. p. 1 ACM Transactions on Economics and Computation, 7(2):1–29, 2019
[ABH13] Haris Aziz, Felix Brandt, and Paul Harrenstein. Pareto optimality in coalition formation. p. 4 Games and Economic Behavior, 82:562–581, 2013
[ABS13] Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively separable hedonic games. p. 1 Artificial Intelligence, 195:316–334
[AS16] Haris Aziz and Rahul Savani. Hedonic games. p. 0 In Felix Brandt, Vincent Conitzer, Ulle Endriss, J. Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 15. p. 1 Cambridge University Press, 2016
[BB22] Felix Brandt and Martin Bullinger. Finding and recognizing popular coalition structures. p. 0 Journal of Artificial Intelligence Research, 74:569–626, 2022
[BBS15] Florian Brandl, Felix Brandt, and Martin Strobel. Fractional hedonic games: Individual and group stability. p. 3 In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1219–1227, 2015
[BBT24] Felix Brandt, Martin Bullinger, and Leo Tappe. Stability based on single-agent deviations in additively separable hedonic games. p. 3 Artificial Intelligence, 334, 2024
[BER24] Martin Bullinger, Edith Elkind, and Jörg Rothe. Cooperative game theory. p. 1 In Jörg Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chapter 3, pages 139–229
[BG25] Martin Bullinger and Matan Gilboa. Settling the complexity of popularity in additively separable and fractional hedonic games. p. 2 In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25, pages 3771–3779, 8 2025
[BIM10] Péter Biró, Robert W. Irving, and David F. Manlove. Popular matchings in the marriage and roommates problems. p. 2 In Proceedings of the 7th Italian Conference on Algorithms and Complexity (CIAC), pages 97–108, 2010
[BJ02] Anna Bogomolnaia and Matthew O Jackson. The stability of hedonic coalition structures. p. 1 Games and Economic Behavior, 38(2):201–230, 2002
[BKS01] Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez. Core in a simple coalition formation game. p. 1 Social Choice and Welfare, 18:135–153, 2001
[Cai07] Jin-Yi Cai. Sp2 <= ZPPNP. p. 2 Journal of Computer and System Sciences, 73(1):25–35, 2007
[CALMP22] V. Cohen-Addad, S. Lattanzi, A. Maggiori, and N. Parotsidis. Online and consistent correlation clustering. p. 1 In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 4157–4179, 2022
[CCRS23] Jiehua Chen, Gergely Csáji, Sanjukta Roy, and Sofia Simola. Hedonic games with friends, enemies, and neutrals: Resolving open questions and fine-grained complexity. p. 3 In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 251–259, 2023
[CRM01] Katarína Cechlárová and Antonio Romero-Medina. Stability in coalition formation games. p. 1 International Journal of Game Theory, 29:487–494, 2001
[DBHS06] Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao Chin Sung. Simple priorities and core stability in hedonic games. p. 1 Social Choice and Welfare, 26(2):421–433, 2006
[DC85] Marquis De Condorcet. Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York
[DG80] Jacques H. Drèze and Joseph Greenberg. Hedonic coalitions: Optimality and stability. p. 1 Econometrica, 48(4):987–1003, 1980
[Gär75] Peter Gärdenfors. Match making: assignments based on bilateral preferences. p. 2 Behavioral Science, 20(3):166–173, 1975
[GGKN25] Matan Gilboa, Paul W Goldberg, Elias Koutsoupias, and Noam Nisan. Complexity of unambiguous problems in SP2. p. 3 arXiv preprint arXiv:2510. p. 019084, 2025
[GMSZ21] Sushmita Gupta, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Popular matching in roommates setting is np-hard. p. 1 ACM Transactions on Computation Theory, 13(2):9:1–9:20, 2021
[HB76] Juris Hartmanis and Leonard Berman. On isomorphisms and density of NP and other complete sets. p. 5 In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, pages 30–40, 1976
[New04] Mark E. J. Newman. Detecting community structure in networks. p. 1 The European Physical Journal B - Condensed Matter and Complex Systems, 38(2):321–330, 2004
[OBI+17] Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai, and Makoto Yokoo. Core stability in hedonic games among friends and enemies: Impact of neutrals. p. 3 In IJCAI, pages 359–365, 2017
[Ols12] Martin Olsen. On defining and computing communities. In Proceedings of the 18th Computing: The Australasian Theory Symposium (CATS), volume 128 of Conferences in Research and Practice in Information Technology (CRPIT), pages 97–102, 2012
[Ray07] Debraj Ray. A Game-Theoretic Perspective on Coalition Formation. p. 1 Oxford University Press, 2007
[SD10] Shao C. Sung and Dinko Dimitrov. Computational complexity in additive hedonic games. p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Strong popularity determination for additively separable hedonic games (ASHGs) can be solved in Polynomial Condorcet Winner (PCW), which sits between PNP and SP2 complexity classes. This allows AI systems to efficiently decide if a given game admits a strongly popular partition by reducing the problem to checking membership in PCW.
-
The existence of a Condorcet string implies the existence of a strongly popular partition, meaning an AI system can verify strong popularity by checking if there exists a string x such that all agents outside the coalition defined by x are indifferent between partitions, as shown in Lemma 5.19:
x' = x star.
-
The reduction from Ckt-Condorcet to ASHG demonstrates that the problem of finding a strongly popular partition for cardinal hedonic games is PCW-complete, enabling the creation of AI tools that can solve complex combinatorial preference problems by mapping them to Boolean circuits.
-
AI systems can leverage the structural properties derived in Lemma 6.13, which shows
all gates in Cl pi star-comply with x star,
to efficiently verify if a partition is strongly popular by checking compliance against a derived string x star for every circuit in the game. -
The analysis of strong popularity implies that
the unambiguity property requires a less standard approach,
suggesting AI systems can be designed to handle problems where uniqueness of solutions is crucial, potentially extending this approach to fractional and modified-fractional hedonic games.
Sources
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments