{"id":"55166f81-d00a-4d86-bda1-7f6155f27b39","arxiv_id":"2607.27277","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Determining whether an additively separable hedonic game admits a strongly popular partition is PCW-complete.","lead":"This paper shows that checking whether a group of agents can be split into coalitions so that the split beats every other split in a majority vote is exactly as hard as a newly defined complexity class, PCW. It resolves an open question and provides the first natural problem known to capture this class.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"X-agent count in the reduction can fail to exceed half of N, breaking the X-majority lemmas (Section 4, Lemmas 5.3/6.2).","rationale":"The reader's concern about the missing canonical encoding for PCW membership is real but belongs to the easy direction and is a straightforward omitted detail: an injective partition encoding with enough bits and a default utility for invalid strings fixes it. I found a more concrete problem in the hard reduction. The paper's domination argument is built on |X|>|N|/2, and the stated X count does not guarantee this for all Ckt-Condorcet inputs. The arithmetic is simple: the bound ignores the 8 extra W/Z/L agents per And-gate relative to the 10-per-gate X coefficient, and the RHS shrinks when And-gates are numerous. Since this inequality is used in both directions (Lemma 5.3/5.4 for Condorcet-to-partition; Lemma 6.2/6.3 for partition-to-Condorcet), the proof as written is incomplete for such instances. However, the fix is easy — set |X| = non-X+1 — so the central claim is likely correct and the appropriate verdict remains conditional, consistent with the reader's assessment. Credit where due: the reduction's gadget analysis is detailed, the uniqueness/unambiguity motivation is coherent, and the paper transparently acknowledges a repaired error.","tokens_in":24684,"tokens_out":21249,"duration_ms":176732,"concrete_test":"Take a Ckt-Condorcet instance with m=1, n=1, one Copy gate and 100 And gates. Instantiate the Section 4 construction and count agents: X = 1024, non-X = 1413. Verify that |X|>|N|/2 fails. Then check whether Lemmas 5.3 and 6.2 remain provable without the X-majority inequality; if not, the reduction proof does not cover this input. An independent count of the gadget sizes from the bullet list settles the arithmetic.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4 the paper sets the number of X-agents to 1+9mn+3n+Σ(10|C_i|+1) and claims the number of non-X agents is at most that bound, so |X|>|N|/2. But the construction actually contains 3n(m+1) A-agents, 6Σ|C_i| gate/core/replica agents, 8·(#And-gates) additional W/Z/L agents, and m voters. For m=1, n=1, one Copy gate and 100 And gates, non-X=1413 while X=1024, 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 it, the proof of both directions does not go through for such instances. The flaw is quantitative and repairable by enlarging X to non-X+1, but as written the claimed property is false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24986,"tokens_out":7503,"duration_ms":75865,"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":[{"comment":"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.","section":"Section 4 (X-agent count)"},{"comment":"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.","section":"Section 4, after Definition 1 (PCW membership)"},{"comment":"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.","section":"Section 5 / Section 6 (consequences of the X-count error)"}],"minor_comments":[{"comment":"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.","section":"Section 4 (And-gadget)"},{"comment":"Several lemmas are referred to as 'Theorem 5.3', 'Theorem 5.7', etc., although they are lemmas. Please correct the cross-references.","section":"Throughout"},{"comment":"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.","section":"Section 4 / Section 5"},{"comment":"'unambiguity may have affect' should be 'may have an effect'. Also, the phrase 'custom unions' should likely be 'customs unions'.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real result in search of a proof that is fully written down. The paper settles an open problem by giving the first completeness result for strong popularity in ASHGs, and the first natural complete problem for the class PCW. I think the main theorem is probably true, but the manuscript as it stands has two gaps that are both repairable and both need repair.\n\nWhat's genuinely new: the hardness direction. The construction with one-way replicas and voter agents is clever, and the gadget analysis is detailed. The author is also honest about a previous error getting fixed. That's good faith and good work.\n\nWhere it falls short. First, the X-agent count. The paper claims non-X agents are at most 9mn+3n+Σ(10|C_i|+1), so |X|>|N|/2. That count is wrong. Each And-gate contributes 14 agents — six gate/replica agents plus eight W/Z/L agents and their replicas — not 10. With m=1, n=1, one Copy gate and 100 And gates, X=1024 while non-X=1413, so |X|<|N|/2. Lemmas 5.3, 5.4, 6.2 and 6.3 all lean on the majority property. This is fixable by padding X with dummy agents, but not present. Second, containment in PCW is called 'straightforward' but doesn't handle the fact that two distinct bit strings can encode the same partition. Condorcet requires strict majority; duplicate encodings tie. You need a canonical encoding or a validity check in the circuits. That's also fixable, but it's real work. I also noticed a typo in the And-gate valuation block ('g0_0' appears where a W- or Z-agent is presumably meant) — minor, but it makes checking the table harder.\n\nFor a reader: this is for people who care about complexity of coalition formation or about giving PCW traction. If the gaps get fixed, it's a solid paper. As written, I'd want a careful referee to check the repaired counting and the containment direction before accepting. My recommendation: send it to review, but expect major revision.","headline":"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.","tokens_in":25411,"tokens_out":9307,"would_cite":false,"duration_ms":79057,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","91A12","91B14","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Determining whether an additively separable hedonic game admits a strongly popular partition is exactly PCW-complete.","keywords":["strong popularity","hedonic games","additively separable hedonic games","PCW computational complexity","Condorcet winner","unambiguous problems","coalition formation","Ckt-Condorcet"],"falsifier":"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.","tokens_in":24572,"feed_emoji":"🗳️","tokens_out":3328,"duration_ms":31634,"temperature":0.7,"pith_summary":"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.","feed_headline":"Strong popularity in hedonic games is PCW-complete","feed_subtitle":"The existence of a majority-winning partition is exactly PCW-complete, settling a long-open question.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Majority-winning partitions in ASHGs are PCW-complete","ASHG strong popularity: PCW-complete","Strong popularity in ASHGs is PCW-complete","Existence of strong popularity in ASHGs is PCW-complete"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Majority-winning partitions in ASHGs are PCW-complete","ASHG strong popularity: PCW-complete","Strong popularity in ASHGs is PCW-complete","Existence of strong popularity in ASHGs is PCW-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000373,"raw_usage":{"total_tokens":1763,"prompt_tokens":614,"completion_tokens":1149,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":358,"completion_tokens_details":{"reasoning_tokens":1079}},"tokens_in":358,"tokens_out":1149,"duration_ms":10046,"temperature":1.0,"reasoning_tokens":1079,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T10:36:34.152326+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}