Pith. sign in

REVIEW 3 major objections 4 minor 31 references

Complexity of Strong Popularity in Additively Separable Hedonic Games

T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Determining whether an additively separable hedonic game admits a strongly popular partition is exactly PCW-complete.

desk verdict Strong popularity in ASHGs is very likely PCW-complete, and the first natural complete problem for PCW is a nice result, but the proof as written has two fixable gaps — a false X-majority count and an unhandled duplicate-encoding issue in containment — so I'd want revision before trusting it. read the letter →

arxiv 2607.27277 v1 pith:HE3QEHSY submitted 2026-07-29 cs.GT cs.CC

Matan Gilboa This is my paper · ORCID
classification cs.GTcs.CC MSC 68Q1591A1291B1468Q17
keywords strongpopularityhedonicgamesadditivelyseparablePCWcomputationalcomplexityCondorcetwinnerunambiguousproblemscoalitionformationCkt-Condorcet
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the existence problem for strongly popular partitions in additively separable hedonic games is complete for the complexity class PCW, a class introduced in 2025 that sits strictly between P^NP and S_2^P. Strong popularity means a partition that beats every other partition in a strict majority vote among agents; such partitions are unique when they exist. The result settles an open problem from 2022 and gives the first natural complete problem for PCW. It shows that the unambiguity of strong popularity — there is at most one witness — is what differentiates its complexity from weak popularity, which is Sigma_2^P-complete.

What carries the argument

The reduction's central object is the one-way replica: for an agent p, a replica set R that values p and each other at 10, mimics p's valuations of others, and is valued 0 by any agent who non-negatively values p. This turns a single agent into a weighted voting block without changing preferences. The gadgets — assignment gadgets for input bits, gate gadgets for Copy/Not/And gates, and voter agents whose exponentially weighted valuations encode circuit outputs — enforce that any strongly popular partition must correspond to a valid partial assignment and that voters alone determine the majority.

What would settle it

Construct an ASHG with a strongly popular partition, encode the same partition in two ways as bit-strings, and run the Ckt-Condorcet winner check: if the two encodings produce a tie instead of a strict win, the claimed containment cannot hold as stated; alternatively, exhibit a Ckt-Condorcet instance where a Condorcet string exists but the constructed partition fails strong popularity, or vice versa.

Watch

Extended reading notes

Core claim

The paper establishes Theorem 1.1: Ashg-Strong-Popularity is PCW-complete. The membership direction is argued by encoding each agent's additive utility as a Boolean circuit, reducing the problem to Ckt-Condorcet. The hardness direction constructs an ASHG from an arbitrary Ckt-Condorcet instance, using assignment, gate, and And-gadgets with one-way replicas that serve as weight multipliers, so that a partition is strongly popular if and only if the corresponding string is a Condorcet winner.

Load-bearing premise

The containment in PCW is asserted to be 'straightforward' but the paper never specifies how a partition of n agents is encoded as a bit-string candidate for Ckt-Condorcet; because two distinct encodings of the same partition yield identical utility vectors, the strict-majority condition in the definition of PCW would fail (ties) without a canonical or label-validity encoding.

Editorial extensions

If this is right

  • If correct, strong popularity in ASHGs is neither NP-complete nor Sigma_2^P-complete (unless collapse), but PCW-complete, placing it in a newly charted region between P^NP and S_2^P.
  • It provides the first natural complete problem for PCW, giving the class a concrete anchor for future reductions.
  • The result likely extends to fractional and modified fractional hedonic games, as the paper suspects, since those are also cardinal and the containment holds for any cardinal hedonic game.
  • The uniqueness of strong popularity (at most one witness) is the feature that forces this classification; this suggests other unambiguous problems in Sigma_2^P may find natural homes in PCW or related classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the missing encoding is supplied (e.g., canonical representatives of partitions), the containment completes; this is likely a fixable gap rather than a fatal flaw.
  • The reduction's replica mechanism might be reusable to show PCW-completeness for other unambiguous coalition-formation problems, such as strong popularity in fractional hedonic games, giving a template for transferring Condorcet-like majority conditions to cardinal games.
  • The connection between unambiguity and majority-vote stability suggests that other unique-witness solution concepts (e.g., unique core outcomes under strict preferences) could be classified via PCW or sibling classes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the problem Ashg-Strong-Popularity: given an additively separable hedonic game, does there exist a strongly popular partition? It claims Theorem 1.1: this problem is PCW-complete, where PCW is the class of problems reducible to Ckt-Condorcet. The proof consists of a reduction from Ckt-Condorcet to ASHGs using X-, A-, G-, W/Z/L-agents and one-way replicas; Section 5 proves that a Condorcet string yields a strongly popular partition, and Section 6 proves the converse. The paper also asserts, in one sentence, that membership in PCW is straightforward.

Significance. If established, the result resolves the open problem of Brandt and Bullinger and gives the first natural complete problem for PCW, showing that the existence of a strongly popular partition in ASHGs is neither simply NP-complete nor Sigma_2^P-complete. The reduction is elaborate, with structural lemmas argued separately in both directions; it is not circular and appears to use no fitted parameters beyond the fixed gadget valuations. However, two load-bearing gaps—the erroneous X-majority count and the missing canonical encoding for the membership direction—currently prevent the completeness claim from being accepted.

major comments (3)
  1. [Section 4 (X-agent count)] The claim that the number of non-X agents is at most 9mn + 3n + Σ(10|C_i|+1) is false. The construction actually contains 3n(m+1) A/L_a agents, 6Σ|C_i| gate/replica agents, 8·(#And-gates) W/Z/L agents, and m voters. For m=n=1 with one Copy gate and 100 And gates, |X| = 1+9+3+(10·101+1)=1024, while non-X = 6+6·101+8·100+1=1413, so |X| < |N|/2. Lemmas 5.3, 5.4, 6.2 and 6.3 all rely on |X|>|N|/2 to force X⊆MC and L∩MC=∅; without that inequality both directions of the proof fail for such instances. This is repairable by enlarging the X-agent count to non-X+1, but the counting error must be corrected and all affected lemmas re-verified.
  2. [Section 4, after Definition 1 (PCW membership)] The assertion that containment of Ashg-Strong-Popularity in PCW is 'straightforward' is insufficient and is load-bearing. In Ckt-Condorcet, candidates are bit strings; if the same partition has two distinct encodings y and y', then for every voter circuit Ci(y)=Ci(y'), so a candidate encoding of that partition ties with its duplicate and cannot be a Condorcet string. The reduction must therefore fix an injective/canonical encoding of partitions, or otherwise ensure that non-canonical strings cannot be Condorcet winners, and the voter circuits must be able to compute utilities from that encoding (including rejecting invalid strings). No such encoding is given. Since Theorem 1.1 is a completeness statement, this missing construction leaves the PCW-membership direction unproved.
  3. [Section 5 / Section 6 (consequences of the X-count error)] Even if the X-count is repaired, the proofs of Lemmas 5.3, 5.4, 6.2 and 6.3 must be revisited: they currently derive X⊆MC and L∩MC=∅ solely from the majority inequality. After enlarging X, one must check that the enlarged X-agents do not disturb the gadget arguments elsewhere, e.g., Lemma 5.2 and Lemma 6.9(1) still hold with the new value of |X|. This is likely straightforward, but it is not merely a typographical fix in the current text.
minor comments (4)
  1. [Section 4 (And-gadget)] In the definition of the And-gadget, the agents w_i and z_i are said to assign value 1 to 'g^0_0', but no agent g^0_0 exists. This is presumably a typo for one of the input gate agents; please clarify.
  2. [Throughout] Several lemmas are referred to as 'Theorem 5.3', 'Theorem 5.7', etc., although they are lemmas. Please correct the cross-references.
  3. [Section 4 / Section 5] There are minor typos: 'since are m voter agents' should be 'since there are m voter agents'; 'fo the output gates' should be 'for the output gates'; 'inπall agents' is missing spaces.
  4. [Section 1] 'unambiguity may have affect' should be 'may have an effect'. Also, the phrase 'custom unions' should likely be 'customs unions'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PCW-completeness proof is a direct reduction from Ckt-Condorcet and does not reduce to its own inputs.

full rationale

The derivation chain is self-contained in the relevant sense. The paper reduces the defining PCW problem Ckt-Condorcet to Ashg-Strong-Popularity via an explicit ASHG construction, and proves both directions by comparing popularity margins within the constructed gadgets. No parameter is fitted to the target answer, no prediction is renamed as a fit, and no uniqueness or completeness claim is imported as a black box from the author's prior work. The definition of PCW is cited to [GGKN25], but that citation supplies only the formal definition of the class and its position between P^NP and S_2^P; it does not supply the equivalence proved here. The acknowledgement that a preliminary version of these results appeared in earlier versions of [GGKN25] is a provenance note, not a circularity: the present hardness proof still reduces from the independently meaningful Ckt-Condorcet problem. The reader-flagged encoding issue (representing partitions as bit-string candidates for the containment direction) is a potential correctness or formality gap, not a circularity, because it concerns whether the containment simulation is written down, not whether the claimed result is assumed in its own proof. Overall, the central claim has independent content and is not forced by definition, by self-citation, or by construction.

Assumptions & free parameters 5 free parameters · 4 assumptions · 3 invented entities

The central claim rests on standard circuit/gadget definitions plus the new class PCW from prior work. The constants 10, 2^(n+1), powers of two, and -infinity are construction choices, not fitted parameters; they are chosen to force gadget behavior. One-way replicas and alternative agents are invented combinatorial gadgets with no independent evidence outside the proof.

free parameters (5)
  • replica mutual value = 10
    Definition 2: mutual valuation among origin and one-way replicas; chosen to exceed all other positive values involving replicated agents so replicas always prefer to stay with their origin.
  • voter dominance value = 2^(n+1)
    Voter valuation for other voters and x1; chosen to dominate the sum of all output-bit values, used in Lemmas 5.5 and 5.16.
  • output-bit weights = 2^1,...,2^n
    Voter values for output gate representatives; chosen so that C_j(x*) > C_j(x') iff the voter prefers the partition realizing x*.
  • large negative valuation = -infinity (|N| times max positive)
    Used throughout the gadget design so that any coalition containing an agent to whom an agent assigns -infinity yields negative utility; underpins all structural forcing lemmas.
  • X-agent count = 1+9mn+3n+sum_i(10|C_i|+1)
    Section 4: chosen to guarantee |X|>|N|/2, so X-agents form an absolute majority and force the main-coalition structural lemmas.
assumptions (4)
  • standard math Boolean circuits can be assumed to consist only of AND, NOT, and input-copy gates in topological order, with fan-out allowed.
    Section 4 setup; standard functional completeness, needed for the gadget construction.
  • domain assumption ASHG preferences are induced by additive valuations and agents only care about their own coalition; strongly popular partitions are Pareto-optimal.
    Section 3 definitions; the basis of the reduction's structural lemmas.
  • domain assumption PCW is a well-defined complexity class with the properties stated in [GGKN25], including that P^NP ⊆ PCW ⊆ S_2^P.
    Section 3, Definition 1; the target class comes from prior work by the same author.
  • standard math Circuit outputs can be shifted by a constant to be non-negative without changing the Ckt-Condorcet problem.
    Section 4; allows voter valuations to be powers of two.
invented entities (3)
  • One-way replicas
    purpose: Amplify the popularity weight of selected agents by copying their valuations and creating a strong mutual bond (value 10).
    Internal construction tool; no falsifiable handle outside the proof.
  • L-agents (alternative agents)
    purpose: Provide a 'false' coalition for the representative not realizing the gadget's truth value, enabling the compliance definitions.
    Internal gadget design; no independent evidence.
  • W/Z-agents for And-gadgets
    purpose: Punish non-compliant And-gate configurations and support the correct output for each combination of inputs.
    Internal gadget design; no independent evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of Strong Popularity in Additively Separable Hedonic Games." pith.science (2026). https://pith.science/paper/HE3QEHSY

@misc{pith2026260727277,
  author       = {Pith},
  title        = {Pith review of: Complexity of Strong Popularity in Additively Separable Hedonic Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HE3QEHSY}},
  note         = {Machine review of arXiv:2607.27277}
}
abstract

In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partition in a majority vote among the agents. We focus on the fundamental class of additively separable hedonic games (ASHGs), where agents have additive valuations that induce their preferences. We prove that determining the existence of strongly popular partitions in ASHGs is complete for PCW, a recently introduced complexity class which lies in between $P^{NP}$ and $S_2^P$ (Gilboa et al., 2025). This settles an open problem by Brandt and Bullinger (2022) and Bullinger and Gilboa (2025).

Figures

Figures reproduced from arXiv: 2607.27277 by the authors.

Figure 1
Figure 1. Assignment gadget of bit xi . Dots represent single agents; circles represent sets of m replicas. a 0 i a 1 i g 0 i g 1 gˆ i 0 i gˆ 1 i ℓ g i ˆℓ g i [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 3
Figure 3. Not-gadget of gate Gi = ¬Gj . g 0 j g 0 k g 1 j g 1 k g 0 i g 1 i gˆ 0 i gˆ 1 i ℓ g i ˆℓ g i wi zi ℓ w i ℓ z i ˆℓ w i ˆℓ z i wˆi zˆi 2 3 2 2 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 6
Figure 6. High-level illustration of the reduction used in the proof of Theorem 1.1, for [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 1 canonical work pages

  1. [1]

    2007 , publisher=

    Cai, Jin-Yi , journal=. 2007 , publisher=

    2007

  2. [2]

    On isomorphisms and density of

    Hartmanis, Juris and Berman, Leonard , booktitle=. On isomorphisms and density of

  3. [3]

    International Colloquium on Automata, Languages, and Programming , pages=

    On the difference between one and many: preliminary version , author=. International Colloquium on Automata, Languages, and Programming , pages=. 1977 , organization=

    1977

  4. [4]

    Manuscript, Leeds , year=

    A reduction from satisfiability to Hamiltonian circuits that preserves the number of solutions , author=. Manuscript, Leeds , year=

  5. [5]

    Behavioral Science , volume=

    Match making: assignments based on bilateral preferences , author=. Behavioral Science , volume=. 1975 , publisher=

    1975

  6. [6]

    Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,

    Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games , author =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence,. 2025 , month =. doi:10.24963/ijcai.2025/419 , url =

    work page doi:10.24963/ijcai.2025/419 2025

  7. [7]

    On defining and computing communities , volume =

    Martin Olsen , booktitle =. On defining and computing communities , volume =

  8. [8]

    Finding and Recognizing Popular Coalition Structures , volume =

    Brandt, Felix and Bullinger, Martin , journal =. Finding and Recognizing Popular Coalition Structures , volume =

Show all 31 references
  1. [9]

    The Stability of Hedonic Coalition Structures , volume =

    Bogomolnaia, Anna and Jackson, Matthew O , journal =. The Stability of Hedonic Coalition Structures , volume =. 2002 , publisher=

    2002

  2. [10]

    Essai sur l'application de l'analyse

    De Condorcet, Marquis , note =. Essai sur l'application de l'analyse

  3. [11]

    Complexity of Unambiguous Problems in

    Gilboa, Matan and Goldberg, Paul W and Koutsoupias, Elias and Nisan, Noam , journal=. Complexity of Unambiguous Problems in

  4. [12]

    A Game-Theoretic Perspective on Coalition Formation , year =

    Debraj Ray , publisher =. A Game-Theoretic Perspective on Coalition Formation , year =

  5. [13]

    Mark E. J. Newman , journal =. Detecting community structure in networks , volume =

  6. [14]

    Cohen-Addad and S

    V. Cohen-Addad and S. Lattanzi and A. Maggiori and N. Parotsidis , booktitle = proc #. Online and consistent correlation clustering , year =

  7. [15]

    Jacques H. Dr. Hedonic Coalitions: Optimality and Stability , volume =. Econometrica , number =

  8. [16]

    Core in a simple coalition formation game , volume =

    Suryapratim Banerjee and Hideo Konishi and Tayfun S. Core in a simple coalition formation game , volume =. Social Choice and Welfare , keywords =

  9. [17]

    Stability in Coalition Formation games , volume =

    Katar. Stability in Coalition Formation games , volume =. International Journal of Game Theory , pages =

  10. [18]

    Fractional Hedonic Games , volume =

    Haris Aziz and Florian Brandl and Felix Brandt and Paul Harrenstein and Martin Olsen and Dominik Peters , journal =. Fractional Hedonic Games , volume =

  11. [19]

    Hedonic Games , year =

    Haris Aziz and Rahul Savani , booktitle =. Hedonic Games , year =

  12. [20]

    Cooperative Game Theory , year =

    Bullinger, Martin and Elkind, Edith and Rothe, J. Cooperative Game Theory , year =. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division , chapter =

  13. [21]

    Sung and Dinko Dimitrov , journal =

    Shao C. Sung and Dinko Dimitrov , journal =. Computational Complexity in Additive Hedonic Games , volume =

  14. [22]

    Stability Based on Single-Agent Deviations in Additively Separable Hedonic Games , volume =

    Felix Brandt and Martin Bullinger and Leo Tappe , journal =. Stability Based on Single-Agent Deviations in Additively Separable Hedonic Games , volume =

  15. [23]

    Fractional Hedonic Games:

    Florian Brandl and Felix Brandt and Martin Strobel , booktitle = proc #. Fractional Hedonic Games:

  16. [24]

    Computing Desirable Partitions in Additively Separable Hedonic Games , volume =

    Haris Aziz and Felix Brandt and Hans Georg Seedig , journal =. Computing Desirable Partitions in Additively Separable Hedonic Games , volume =

  17. [25]

    Woeginger , journal =

    Gerhard J. Woeginger , journal =. A hardness result for core stability in additive hedonic games , volume =

  18. [26]

    Games and Economic Behavior , volume=

    Pareto optimality in coalition formation , author=. Games and Economic Behavior , volume=. 2013 , publisher=

    2013

  19. [27]

    Popular Matchings in the Marriage and Roommates Problems , year =

    P\'. Popular Matchings in the Marriage and Roommates Problems , year =. Proceedings of the 7th Italian Conference on Algorithms and Complexity (CIAC) , pages =

  20. [28]

    Popular Matching In Roommates Setting is NP-hard , volume =

    Gupta, Sushmita and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav , journal =. Popular Matching In Roommates Setting is NP-hard , volume =

  21. [29]

    Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems , pages=

    Hedonic games with friends, enemies, and neutrals: Resolving open questions and fine-grained complexity , author=. Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems , pages=

    2023

  22. [30]

    , author=

    Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals. , author=. IJCAI , pages=

  23. [31]

    Social Choice and Welfare , volume=

    Simple priorities and core stability in hedonic games , author=. Social Choice and Welfare , volume=. 2006 , publisher=

    2006

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.