{"id":"8c3ef9da-ce3e-4b58-917a-aeb4847ca34f","arxiv_id":"2504.15157","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Approval-based proportional committees are not always reconfigurable while preserving justified representation, but become connected when allowing a 2-approximation.","lead":"This paper studies whether proportional committees can be gradually changed into one another while staying proportional at every step. It shows that such paths may not exist for the basic proportionality axiom, that deciding existence is PSPACE-complete, and that approximate proportionality restores connectivity.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's weakest assumption targets external lemmas (Dong et al. 2025, Brill and Peters 2024) that support Theorem 3.9 and Theorem 4.5. These are important for the paper's broader contributions, but they are not load-bearing for the paper's strongest claim: the disconnectedness of JR committees and the PSPACE-completeness of JR-reconfiguration. I independently re-checked the proofs of Theorems 3.1 and 3.4 and found them internally consistent. The counting in Theorem 3.1 is correct: any other JR committee must contain at least k−1 candidates from C2, giving distance at least k−1. The reduction in Theorem 3.4 correctly forces every JR committee on a path to contain exactly one literal candidate per variable, all non-special dummy candidates, and no special dummy candidates; any deviation creates a 10-voter 1-cohesive group with no representative. The only substantive issue I found is a definitional ambiguity for α-JR and α-EJR: Section 2 defines α-cohesive as requiring α common candidates, whereas the proofs and Proposition 3.8 use the standard notion of α-large and 1-cohesive (resp. αℓ-large and ℓ-cohesive). This is a presentation flaw that should be fixed in a revision, but it does not undermine the central claim, and the approximate-connectivity results remain true under the intended definitions. Since the central claim is self-contained and sound, no change to the reader's conditional verdict is warranted.","tokens_in":34514,"tokens_out":51270,"duration_ms":403469,"concrete_test":"Brute-force the k=4 instance of Theorem 3.1 (n=64): enumerate all size-4 committees, test JR, and verify that committee W=C1 is (k−2)-isolated and that the counting lower bound matches the actual JR-set. This independently confirms the isolation bound without relying on any external lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that JR committees need not be connected and that JR-reconfiguration is PSPACE-complete (Theorems 3.1 and 3.4)—survives scrutiny. The isolation construction in Theorem 3.1 is self-contained: the counting argument for the distance lower bound is correct, and the existence of a second JR committee using C2 candidates covering all of N2 is valid because k candidates with distinct missing voters cover every N2 voter. The PSPACE-completeness reduction is also internally sound: non-special dummy candidates cannot be removed without creating an unrepresented 10-voter 1-cohesive group, literal swaps must be exchanged with the opposite literal to keep the 10 literal voters represented, and clause voters enforce the satisfying-assignment structure. The external lemmas flagged by the reader (Dong et al. 2025 Lemma 5.5; Brill and Peters 2024) underpin Theorem 3.9 and Theorem 4.5, but these are auxiliary positive results, not the central impossibility/intractability claim. The only notable presentation issue is the formal definition of α-JR/α-EJR in Section 2, which literally requires α-cohesive groups to share α common candidates; the proofs and Proposition 3.8 use the standard 'α-large and 1-cohesive' (resp. 'αℓ-large and ℓ-cohesive') interpretation. This ambiguity should be corrected, but it does not affect the α=1 central results and does not invalidate the approximate-connectivity theorems under the intended definitions.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies reconfiguration of approval-based multiwinner committees under proportionality constraints. Two committees are adjacent when they differ by one candidate, and a committee satisfies JR (resp. EJR) if every 1-cohesive (resp. ℓ-cohesive) voter group is 'represented' in the appropriate sense. The main results are: (i) for every k≥3 there is an instance with a JR committee that is (k−2)-isolated among JR committees, and this bound is tight; (ii) deciding connectivity of two JR committees in the JR graph is PSPACE-complete; (iii) any two JR committees can be connected through 2-JR committees, with the factor 2 tight; (iv) any two EJR committees can be connected through 4-EJR committees; (v) committees returned by MES, seq-Phragmén, PAV, CCAV, seq-CCAV, GJCR, and GreedyEJR all lie in the same connected component of the JR graph; and (vi) on voter-interval and candidate-interval domains the JR graph is connected, with shortest-path connectivity in the CI case and in the Pareto-dominated-free VI case. The proofs combine counting arguments, a reduction from SAT-Reconfiguration, monotonicity and affordability arguments, and domain-specific interval arguments.","tokens_in":34794,"tokens_out":24336,"duration_ms":216519,"significance":"If the results stand, the paper makes a substantial contribution to the young literature on multiwinner reconfiguration. It gives the first impossibility and PSPACE-hardness results for proportionality-preserving transitions, and it offsets these with a clean positive result (2-JR connectivity) whose constant is proved tight. The section on voting rules is valuable: it shows that the isolation phenomenon of Theorem 3.1 is not realized by any of the standard proportional rules, since their output committees are all mutually reachable through JR committees. The restricted-domain results are also natural and give a complete picture for JR on CI and VI instances. A particular strength is that the central constructions, especially the isolation instance and the PSPACE-completeness reduction, are self-contained and the counting arguments check out. The paper does rely on two nontrivial external lemmas (Dong et al.'s 4-EJR subcommittee lemma and Brill and Peters' affordability observations); these are cited but not re-proved, so the corresponding theorems inherit whatever risk attaches to those sources.","major_comments":[{"comment":"The definition of α-JR is inconsistent with the rest of the paper and with standard usage. The text says a committee satisfies α-JR if 'for every α-cohesive group of voters N′' there is a represented voter, and α-cohesive is defined to mean α-large and sharing at least α common candidates. Similarly, α-EJR is defined with respect to '(αℓ)-cohesive' groups. This is not the notion used in the proofs: Lemma 3.6 and Theorem 3.7 rely on groups that are 2-large and 1-cohesive, and Proposition 3.8 constructs a violating group of size 2r = α n/k that shares a single common candidate. Under the literal wording, that group is not α-cohesive for α>1, so the proof of Proposition 3.8 does not establish a violation. The same issue affects the statements of Theorems 3.7 and 3.9. Please replace the definitions with the standard ones: α-JR means that every group that is α-large and 1-cohesive has a represented voter, and α-EJR means that every group that is αℓ-large and ℓ-cohesive has a voter with at least ℓ approved committee candidates. The α=1 case is unchanged, but all approximate-connectivity claims depend on this correction.","section":"Section 2, definitions of α-JR and α-EJR"}],"minor_comments":[{"comment":"The sentence 'one can check that any subset of C2 that covers all voters in N2 indeed satisfies JR, and that such a subset of size k exists' should be replaced by an explicit argument. For example, take k candidates from C2 with pairwise distinct missing voters in N2; every N2 voter then approves k−1 of the chosen candidates, and every 1-cohesive group either contains such an N2 voter or is not a support set of a C2 candidate, so JR is satisfied.","section":"Proof of Theorem 3.1"},{"comment":"The string 'PSP ACE' appears with a spurious space in the abstract and in the body; it should read 'PSPACE'.","section":"Abstract and Section 1"},{"comment":"The final transition sequence re-uses the labels d1,...,ds for witness candidates and then labels the members of W4-EJR as d_{s+1},..., while the deletion process might itself introduce additional witness candidates that would naturally receive those same labels. Please make the labeling of process witnesses and target-subcommittee candidates disjoint, or state explicitly that the d_i in W^i are an arbitrary enumeration of the additions in each step.","section":"Proof of Theorem 3.9, final paragraph"},{"comment":"In the case analysis for the shared candidate c of v and v′, the possibility c=ey is not mentioned. If c=ey, then v′ approves ey∈W∗, so the group is represented; this case should be stated to make the argument complete.","section":"Proof of Theorem 5.1"},{"comment":"The paper would benefit from a sentence in the text of Section 4 reminding the reader that the affordability results of Brill and Peters are used not only for MES and GJCR but also for the seq-Phragmén and seq-CCAV arguments in Lemma 4.6, so that the dependence on external results is visible at the point of use.","section":"Section 4, Lemmas 4.6–4.8"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper is the first to ask what happens when you reconfigure between proportional committees while preserving proportionality along the way, and it answers the question for the main axioms with a satisfying mix of hardness, possibility, and rule-specific results. If the details check out, it will be a standard reference.\n\nThe new results are real. Theorem 3.1's construction of a JR committee isolated at distance k-2 is neat, and the upper bound in Proposition 3.3 shows it is tight. The PSPACE-completeness reduction from SAT-Reconfiguration is careful—the dummy candidates and literal-swap constraints are doing real work, and I did not find a hole. On the positive side, the fact that any two JR committees are connected via 2-JR committees, and that the factor 2 is tight, is a clean theorem. The EJR analogue with 4-EJR is heavier but the proof strategy (modified PAV score with telescoping) is coherent. The voting-rules part is also strong: it shows that PAV, MES, seq-Phragmén, and friends all land in the same JR-connected component, which nicely contrasts with the general disconnectedness. The restricted-domain results (CI and VI) round out the picture.\n\nThe soft spots are minor but should be fixed. In Theorem 3.1, the existence of a size-k C2 committee covering all N2 voters is asserted with 'one can check' instead of a proof; it's true, but needs a sentence. Theorem 3.9 has a typo in the integral bound—the harmonic difference should be bounded by ln(k)-ln(k-r), and the displayed inequality has the limit signs slightly off. More importantly, Section 2's formal definition of α-JR and α-EJR literally says an α-cohesive group must share α common candidates, but the proofs (and Proposition 3.8) use the standard 'α-large and 1-cohesive' interpretation. That ambiguity is confusing and should be corrected; it doesn't affect the α=1 results or the approximation theorems once the intended definition is clear.\n\nThe reliance on external lemmas—Dong et al. 2025 for 4-EJR subcommittees, Brill and Peters 2024 for affordability—is fine, they are published results, but I would ask the authors to state them precisely so readers can verify.\n\nOverall this is a well-executed paper that deserves serious refereeing. The central claims survive scrutiny. I'd take it to a seminar and I'd expect it to be accepted after minor revisions.","headline":"Opens a genuinely new subarea—reconfiguration under proportionality axioms—and the main structural results appear sound; worth a careful referee.","tokens_in":35311,"tokens_out":1854,"would_cite":true,"duration_ms":17420,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","68Q17","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"The set of committees satisfying justified representation is not always connected, and deciding whether two such committees are connected is PSPACE-complete.","keywords":["approval-based multiwinner voting","justified representation","extended justified representation","reconfiguration","committee connectivity","PSPACE-completeness","proportional voting rules","restricted preference domains"],"falsifier":"Exhaustively search all approval profiles with $k=4$ and up to, say, twelve voters for two JR committees with no path of $2$-JR committees between them; an example would refute Theorem 3.7. For the EJR statement, search for a profile with no $4$-EJR subcommittee of size $\\lfloor k/4\\rfloor$; this would contradict the external lemma on which Theorem 3.9 depends.","tokens_in":34313,"feed_emoji":"🗳️","tokens_out":9888,"duration_ms":82354,"temperature":0.7,"pith_summary":"This paper asks whether a proportional committee can be transformed into another by swapping one candidate at a time while every intermediate committee remains proportional. The central answer for the standard axiom of justified representation (JR) is negative: some instances have JR committees that cannot be joined by a path of JR committees, and deciding whether two given JR committees are connected is PSPACE-complete. The negative result is tight and is accompanied by a positive one: any two JR committees can be joined through committees that satisfy a 2-approximation of JR (with the factor 2 optimal), and any two EJR committees can be joined through 4-EJR committees. For seven established voting rules the selected committees all lie in the same connected component of the JR graph, so the obstruction concerns weakly proportional committees rather than the rules used in practice. On candidate-interval and voter-interval preference domains, the set of JR committees is always connected.","feed_headline":"Proportional committees are not always reconnectable","feed_subtitle":"Relaxing justification by a factor of two makes all committees connect; exact reconfiguration is PSPACE-complete.","key_machinery":"The central object is the graph whose vertices are size-$k$ committees and whose edges connect committees differing in one candidate; a reconfiguration path is legal when every vertex satisfies the chosen proportionality axiom. The positive constructions rely on two structural devices: 2-JR greedy subcommittees, built by repeatedly adding a candidate that covers at least $2n/k$ previously uncovered voters, which every JR committee can reach in at most $k/2$ swaps; and affordable subcommittees, those for which every candidate can be paid for by voters each spending at most $k/n$ total budget, which connect the outputs of the studied voting rules. The PSPACE-hardness proof encodes a SAT instance's assignments as committees so that a legal swap corresponds exactly to a satisfying bit flip.","core_discovery":"The paper establishes a sharp phase transition in the swap graph of committees. Exact JR and EJR proportionality do not guarantee connectivity: Theorem 3.1 constructs, for every $k \\ge 3$, a profile with a JR committee whose closest other JR committee is at distance $k-1$, and Corollary 3.2 transfers the isolation to EJR. Deciding connectivity among JR committees is PSPACE-complete (Theorem 3.4), by reduction from SAT-Reconfiguration. Yet Theorem 3.7 shows any two JR committees can be connected by at most $2k$ swaps using only $2$-JR committees, and Proposition 3.8 shows no $\\alpha < 2$ works. The analogous EJR result uses $4$-EJR (Theorem 3.9). In addition, Theorem 4.5 shows that the outputs of PAV, MES, sequential-Phragmén, GJCR, GreedyEJR, sequential-CCAV, and CCAV are mutually connected within JR, and Theorems 5.1 and 5.2 show full JR connectivity on the candidate-interval and voter-interval domains.","pith_inferences":["The PSPACE-completeness result suggests that any practical system that must preserve exact JR while updating a committee will need domain restrictions, approximation slack, or rule-specific structure; the paper's restricted-domain results identify where exact paths survive.","The 2-JR and 4-JR connectivity results imply a simple implementation recipe for platform-style updates: cap the number of swaps at $O(k)$ and accept bounded representation loss, and the transition can be found by local search rather than a global solver.","The contrast between isolated JR committees and the connected choice sets of standard rules points to a possible new axiom: a proportional committee is 'strong' only if it is not isolated in the JR graph, which would rank the weak committees produced by Theorem 3.1 as proportionally deficient.","A direct open extension suggested by the paper's constants is whether the EJR connectivity factor can be lowered from $4$ to $2$; the modified PAV-score technique used in Theorem 3.9 gives a concrete avenue for testing that."],"forward_implications":["Any two JR committees have a reconfiguration path of at most $2k$ swaps whose intermediate committees satisfy $2$-JR, and this approximation factor cannot be improved below $2$.","No polynomial-time algorithm can decide whether a JR-only path exists between two given JR committees unless PSPACE collapses to P.","The committees selected by PAV, MES, sequential-Phragmén, GJCR, GreedyEJR, sequential-CCAV, and CCAV are pairwise connected inside the set of JR committees for the same instance.","On candidate-interval and voter-interval domains every pair of JR committees is connected by a JR path, and on the candidate-interval domain the path can be chosen to have length exactly the symmetric difference of the two committees.","JR committees can be isolated up to distance $k-2$ from every other JR committee, so exact-JR constraints alone do not guarantee any nearby alternative committee."],"supporting_citations":[{"why":"Introduces the multiwinner reconfiguration model that this paper applies to proportional committees.","marker":"Chen et al. [2024]"},{"why":"Defines justified representation and extended justified representation, the proportionality axioms under study.","marker":"Aziz et al. [2017]"},{"why":"Introduces affordable subcommittees and Observation 1, on which Lemma 4.2 and the voting-rule connectivity proofs rely.","marker":"Brill and Peters [2024]"},{"why":"Supplies the Method of Equal Shares and the priceability viewpoint used in Section 4.","marker":"Peters and Skowron [2020]"},{"why":"Defines GJCR and its EJR+ violation machinery, used for the non-isolation results.","marker":"Brill and Peters [2023]"},{"why":"Provides the existence of a 4-EJR subcommittee of size $\\lfloor k/4\\rfloor$ on which Theorem 3.9 is built.","marker":"Dong et al. [2025, Lemma 5.5]"},{"why":"Proves SAT-Reconfiguration is PSPACE-hard, the source of the reduction in Theorem 3.4.","marker":"Gopalan et al. [2009]"},{"why":"Supplies the committee-counting argument adapted in Proposition 3.3 to bound the isolation radius.","marker":"Elkind et al. [2023, Theorem 3.5]"}],"fun_headline_variants":["Proportional committees can get stranded","Exact proportional fairness blocks committee swaps","Committee reconfiguration is PSPACE-hard","Relaxing proportionality by 2 reconnects all"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that two cited results borrowed from other papers are correct: that every profile has a small committee meeting 4-EJR, and that affordable subcommittees behave as claimed, because the corresponding theorems here are proved by appeal to them rather than from scratch.","fun_headline_variants_meta":{"raw":{"variants":["Proportional committees can get stranded","Exact proportional fairness blocks committee swaps","Committee reconfiguration is PSPACE-hard","Relaxing proportionality by 2 reconnects all"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00079,"raw_usage":{"total_tokens":3463,"prompt_tokens":909,"completion_tokens":2554,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":2500}},"tokens_in":525,"tokens_out":2554,"duration_ms":19461,"temperature":1.0,"reasoning_tokens":2500,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:36:14.364108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively search all approval profiles with $k=4$ and up to, say, twelve voters for two JR committees with no path of $2$-JR committees between them; an example would refute Theorem 3.7. For the EJR statement, search for a profile with no $4$-EJR subcommittee of size $\\lfloor k/4\\rfloor$; this would contradict the external lemma on which Theorem 3.9 depends.","supporting_citations":[{"cited_title":"Multi-winner reconfiguration","cited_arxiv_id":null,"evidence_quote":"Introduces the multiwinner reconfiguration model that this paper applies to proportional committees."},{"cited_title":"Justified representation in approval-based committee voting","cited_arxiv_id":null,"evidence_quote":"Defines justified representation and extended justified representation, the proportionality axioms under study."},{"cited_title":"Completing priceable committees: Utilitarian and representation guarantees for proportional multiwinner voting","cited_arxiv_id":null,"evidence_quote":"Introduces affordable subcommittees and Observation 1, on which Lemma 4.2 and the voting-rule connectivity proofs rely."},{"cited_title":"Proportionality and the limits of welfarism","cited_arxiv_id":null,"evidence_quote":"Supplies the Method of Equal Shares and the priceability viewpoint used in Section 4."},{"cited_title":"Robust and verifiable proportionality axioms for multiwinner voting","cited_arxiv_id":null,"evidence_quote":"Defines GJCR and its EJR+ violation machinery, used for the non-isolation results."},{"cited_title":"Selecting interlacing committees","cited_arxiv_id":null,"evidence_quote":"Provides the existence of a 4-EJR subcommittee of size $\\lfloor k/4\\rfloor$ on which Theorem 3.9 is built."},{"cited_title":"Kolaitis, Elitza Maneva, and Christos H","cited_arxiv_id":null,"evidence_quote":"Proves SAT-Reconfiguration is PSPACE-hard, the source of the reduction in Theorem 3.4."},{"cited_title":"Justifying groups in multiwinner approval voting","cited_arxiv_id":null,"evidence_quote":"Supplies the committee-counting argument adapted in Proposition 3.3 to bound the isolation radius."}],"review_version":1}