{"id":"bc81a90d-b64d-4b65-9ec7-eaf8f81bb83c","arxiv_id":"2509.02519","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Maximizing how many voter pairs a committee connects is NP-hard in general but polynomial-time solvable on left-right interval preferences, with tight approximation trade-offs against classic representation goals.","lead":"This paper proposes two simple scores for how well an elected committee interconnects voters, PAIRS and CONS, to avoid parliaments that split the electorate into polarized blocks. It shows when maximizing these scores is easy or hard and proves unavoidable trade-offs with excellence, diversity, and proportional representation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's verdict is ACCEPT with high confidence; my review supports that. I examined the most vulnerable point, the polynomial-time claims on VCI. The transformation from VCI to CI after removing dominated candidates is the key step; the proof is valid modulo an omitted reflection case, and the DP's component-size state correctly captures the only information needed because, in a CI order, a new rightmost candidate can only attach to the component of the previous rightmost candidate. The trade-off proofs are standard worst-case constructions; I checked the score arithmetic, the EJR scaling arguments, and the monotonicity-based positive guarantees. The few typos and overstatements are minor and local, so the verdict should remain UNCHANGED.","tokens_in":25543,"tokens_out":39342,"duration_ms":372053,"concrete_test":"Exhaustively enumerate all small VCI profiles (e.g., m≤6 candidates, n≤5 voters, all k≤m) by sampling interval positions and radii, compute the maximum CONS by brute force over all size-k committees, and compare with the Appendix B dynamic program; a mismatch would reveal a hidden state-transition bug. As a secondary check, verify Proposition 4.3 on the same enumeration by testing CI membership after deleting dominated candidates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the NP-hardness reductions, the VCI-to-CI reduction (Proposition 4.3), the Appendix B dynamic program for CONS, and the trade-off propositions, I find no load-bearing flaw in the central claims. The only issues are presentation-level: the 'WLOG' in Proposition 4.3 omits the reflection argument for voters to the right of the middle candidate; Lemma 5.4 says α-MES returns exactly ⌊αk⌋ candidates whereas the proof only guarantees at most that many; and Proposition 5.9 contains an apparent typo ('y x^2−y chain voters' where all y x^2 chain candidates are intended). None of these affect the stated results: the domination argument still goes through, the EJR guarantee and the remaining-seat accounting are monotone, and the CONS lower bound in Proposition 5.9 is achieved by the committee that takes all chain candidates. The VCI restriction is real but explicitly identified, and the algorithms only claim polynomiality there.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two new objectives, PAIRS and CONS, for approval-based multiwinner committee selection, intended to quantify how well a committee interlaces the electorate and thereby reduce polarization. PAIRS counts voter pairs that share an approved committee member; CONS counts voter pairs connected by chains of such shared approvals. The authors prove that maximizing either objective is NP-complete in general (Theorems 4.1 and 4.2, by reductions from X3C), but that both can be maximized in polynomial time on the voter-candidate interval (VCI) domain. The VCI tractability rests on Proposition 4.3, which shows that a VCI profile without dominated candidates is in the candidate-interval domain, and on a dynamic program in Appendix B for CONS. The paper then studies compatibility with excellence (AV), diversity (CC), and proportionality (EJR). Its main trade-off results are: any rule satisfying α-PAIRS together with β-AV, β-CC, or β-EJR must have α+β≤1 (Propositions 5.2, 5.3, 5.6); any rule satisfying α²-CONS together with β-AV, β-CC, β-PAIRS, or β-EJR must have α+β≤1 (Propositions 5.7 and 5.8). A stepwise sharper bound is given for CONS versus AV (Proposition 5.9), and a positive result shows that in the VI domain with even k a committee can simultaneously guarantee 1/4-CONS and 1/2 of AV, CC, EJR, or PAIRS (Proposition 5.10).","tokens_in":25710,"tokens_out":32350,"duration_ms":302316,"significance":"If the proofs are correct, this is a solid and useful contribution to computational social choice. The two objectives are simple, interpretable, and directly motivated by a socially important concern, and the paper carefully delineates where they can be optimized efficiently and where they cannot. The VCI algorithms are nontrivial, especially the CONS dynamic program, which is specified in enough detail to be checked and reused. The trade-off results are tight in the worst case and the constructions are clean and convincing. A particular strength is that the load-bearing lemmas borrowed from prior work are re-proven in the appendix, and the hardness results are anchored to the standard X3C problem with no fitted parameters or circular dependencies. The VCI restriction is explicitly identified, and the paper is honest about the open problem of exact CONS trade-offs. Overall, the central claims appear sound and the presentation is generally careful, with only local issues that should be repaired before publication.","major_comments":[],"minor_comments":[{"comment":"The proof says 'we can then assume without loss of generality that xv < xi', but the reflection argument for the case xv > xi is not given. The proposition is true, and a short symmetric argument (showing ci is dominated by ch rather than cj) closes the gap, but the current text should be amended to include it.","section":"§4.2.1, Proposition 4.3"},{"comment":"The lemma states that α-MES 'returns a committee of size ⌊αk⌋', but the proof only establishes that it terminates after at most ⌊αk⌋ rounds and may return a smaller committee if no further candidate is affordable. Since EJR is monotone under adding candidates, the later use in Proposition 5.5 remains valid after topping up the committee, but the lemma statement should be corrected to 'at most ⌊αk⌋' or the topping-up step should be made explicit.","section":"Appendix C, Lemma 5.4"},{"comment":"There is a typo in the proof: 'select all y x^2−y chain voters' should read 'chain candidates'. In addition, the claim that 'it takes 2(x^2−1) chain candidates to connect two arm voters from different arms' appears to be off by two (the correct number is 2x^2), although the subsequent inequality remains valid because the proof only needs an upper bound below 2x^2.","section":"§5.2, Proposition 5.9"},{"comment":"The dynamic program is defined for committees of size at most b, and the final output committee may have size strictly smaller than k. Since CONS is monotone, the committee can be topped up to size k without decreasing the score; the text should state this explicitly when claiming that a feasible committee is output.","section":"Appendix B, Theorem 4.5"},{"comment":"The committee W' is written as {c1,c3,c4,c6,d1,d6}, but the profile only contains diagonal candidates d1 and d2. The intended committee is {c1,c3,c4,c6,d1,d2}, which indeed gives each voter exactly two approvals and six covered pairs.","section":"§3.3, Example 3.2"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is within scope and the technical content is sound. The issues I found are local and fixable: a missing reflection argument in Proposition 4.3, an imprecise statement of Lemma 5.4 about committee size, and a few typos in Example 3.2 and Proposition 5.9. I do not have concerns about novelty disclosure or citation practices; the self-contained appendix proofs strengthen the paper. A minor revision addressing the listed points is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid theory paper. It introduces two new objectives for polarization-aware committee selection—PAIRS (number of voter pairs who share an approved selected candidate) and CONS (number of pairs connected by a chain of selected candidates)—and gives a careful map of their computational complexity and their tension with excellence, diversity, and proportionality. The main theorems hold up; I read the appendix DP and the trade-off lower-bound constructions, and they are sound.\n\nWhat's genuinely new: explicitly modeling committee-induced interconnection. The closest prior work (Delemazure et al., Colley et al.) looks at most polarizing pairs or divisiveness of a single candidate, not at whether a committee as a whole connects the electorate. The PAIRS=CC-on-pairs observation is simple but useful, and the CONS objective is genuinely novel and behaves worse (non-submodular), which is itself interesting. The trade-off results are the meat: tight α+β≤1 for PAIRS with AV/CC/EJR, and the quadratic α²+β≤1 for CONS, with the stepwise improvement for AV in Proposition 5.9. These are clean, non-trivial theorems with detailed proofs.\n\nSoft spots, all presentational. Proposition 4.3's proof says \"WLOG x_v < x_i\" but if the voter is to the right of the middle candidate, you need a reflection argument; it works, but it's not there. Lemma 5.4 claims α-MES returns exactly ⌊αk⌋ candidates; the proof only gives at most. Padding with arbitrary candidates fixes that and doesn't hurt EJR, but the statement is wrong as written. Proposition 5.9 has a typo (voters vs candidates) and a stray \"−y\" in the max-CONS calculation; again, the intended bound is clear and correct. There's also a small unmentioned edge case: after deleting dominated candidates, the candidate set may have size below k; you need to say the final committee is padded. None of these are load-bearing.\n\nThe VCI-domain restriction is real and clearly flagged: off that domain the problems are NP-hard, so all the algorithmic and positive results are conditional on the interval structure. That's not a flaw, just a scope statement.\n\nWho's it for: anyone doing computational social choice or multiwinner voting. It's publishable at a strong theory venue. I'd send it to referees rather than desk-reject; the expectation should be minor revision, not major surgery. Engage with it; cite it if you work on multiwinner rules or polarization measures.","headline":"Solid theory paper: new PAIRS and CONS objectives for polarization-aware committees, clean NP-hardness/tractability results, tight trade-offs with AV/CC/EJR; only minor presentation gaps.","tokens_in":26223,"tokens_out":6131,"would_cite":true,"duration_ms":56696,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Committee polarization becomes measurable: PAIRS and CONS score how well a committee interlaces voters, with exact algorithmic and trade-off results.","keywords":["committee selection","multiwinner voting","approval-based preferences","polarization","voter-candidate interval domain","NP-hardness","approximation trade-offs","extended justified representation"],"falsifier":"Take a small VCI election, delete dominated candidates as in Proposition 4.3, and verify that the computed candidate order makes every voter's approval set contiguous; a single voter whose approvals are non-contiguous would show the VCI-to-CI reduction is not generally valid. Alternatively, brute-force all committees of a small random approval profile and look for a committee whose PAIRS and AV approximation ratios sum to more than 1, which would contradict Proposition 5.2.","tokens_in":25385,"feed_emoji":"🔗","tokens_out":11574,"duration_ms":102019,"temperature":0.7,"pith_summary":"The paper tries to make polarization a formal property of an elected committee rather than a mood of the electorate. It proposes two objectives: $\\mathrm{PAIRS}$ counts pairs of voters who approve a common selected candidate, and $\\mathrm{CONS}$ counts pairs who are connected by a chain of shared selected candidates; both are meant to reward committees that interlace the electorate instead of splitting it into opposing blocs. The main theoretical claim is that these objectives are worth taking seriously: maximizing either is NP-complete on arbitrary approval profiles, yet both can be maximized in polynomial time on one-dimensional voter-candidate interval (VCI) profiles, where voters and candidates are intervals on a line. The paper then shows that interlacing cannot be combined with standard objectives for free: a rule guaranteeing $\\alpha$-$\\mathrm{PAIRS}$ and $\\beta$-$\\mathrm{AV}$, $\\beta$-$\\mathrm{CC}$, or $\\beta$-EJR must satisfy $\\alpha+\\beta\\le 1$, while the corresponding bound for $\\mathrm{CONS}$ is $\\alpha^2+\\beta\\le 1$, with a subtler stepwise bound against $\\mathrm{AV}$. These bounds are matched by constructive algorithms in the relevant domains, so the paper maps the frontier of what simultaneous guarantees are possible.","feed_headline":"New committee scores measure, and reduce, parliamentary polarization","feed_subtitle":"PAIRS and CONS count connected voter pairs; maximizing them is NP-hard in general, polynomial on one-dimensional electorates.","key_machinery":"The machinery has four pieces. The first is the voter-candidate interval (VCI) domain, in which every voter and candidate is an interval on the real line and approval means the two intervals intersect; it is the most general one-dimensional approval domain and the setting where the efficient algorithms hold. The second is candidate dominance: a candidate whose supporting voter set is a proper subset of another's can be deleted without changing PAIRS or CONS, and Proposition 4.3 shows that after deleting all dominated candidates every VCI instance becomes a candidate-interval (CI) instance with a computable candidate order. The third is the submodularity fact stated as Proposition 3.1: for any submodular score, some subcommittee of size $\\ell$ inside a size-$k$ committee retains at least an $\\ell/k$ fraction of the score, which is what makes seat-splitting optimal for PAIRS, AV, and CC. The fourth is a chain-decomposition argument for CONS on interval profiles: an optimal CONS committee partitions into overlapping chains, and splitting each chain or paired odd chains near its middle preserves a quarter of the connected pairs, yielding the $1/4$-CONS guarantee.","core_discovery":"On the paper's own terms, the central discovery is a pair of tractability and trade-off results. Polarization is captured by connectivity scores rather than by winner-set properties: $\\mathrm{PAIRS}(\\cdot)$ is the Chamberlin–Courant score of the induced pair instance, and $\\mathrm{CONS}(\\cdot)$ counts pairs in the same connected component of the hypergraph induced by the committee. After deleting dominated candidates, every VCI election is actually a candidate-interval (CI) election, so the PAIRS maximizer can be inherited from known CC algorithms and CONS admits an $O(mnk)$-cell dynamic program tracking the component size of the rightmost selected candidate. In combination, no rule can beat the sum bound $\\alpha+\\beta\\le 1$ for $\\alpha$-PAIRS with $\\beta$-AV, $\\beta$-CC, or $\\beta$-EJR, and no rule can beat $\\alpha^2+\\beta\\le 1$ for $\\alpha^2$-CONS with any of those objectives. For CONS and AV, the actual frontier is even steeper at some parameters, given by a stepwise function; on voter-interval profiles, however, a quarter of the optimal CONS can always be combined with half of AV, CC, EJR, or PAIRS.","pith_inferences":["Editorial inference: the dominance reduction suggests a transfer principle: any preference domain where dominated candidates can be recognized and removed, and where the remaining approvals are contiguous in an order, inherits the polynomial algorithms; checking whether planar or 2D-Euclidean approval sets have an analogous reduction is a natural next test.","Editorial inference: the trade-off theorems are worst-case bounds; on realistic electorates with correlated approval sets the simultaneous frontier may be much better, and this is directly testable by brute-force enumeration on small empirical profiles.","Editorial inference: a path-length-weighted version of CONS would distinguish tight community ties from long chains of intermediaries; the paper itself notes that refined versions are needed when a universally approved candidate trivializes both scores."],"forward_implications":["On one-dimensional left-right electorates, a polarization-minimizing committee can be computed in polynomial time, making the two objectives practically usable for such profiles.","No voting rule can simultaneously guarantee more than an $\\alpha$-fraction of PAIRS and a $(1-\\alpha)$-fraction of AV, CC, or EJR in the worst case, so the simple seat-splitting construction is essentially optimal.","For CONS, combining objectives is harder: guaranteeing $\\beta$-AV, $\\beta$-CC, $\\beta$-EJR, or $\\beta$-PAIRS leaves at most a $(1-\\beta)^2$-fraction of CONS, reflecting the non-submodularity of connectivity.","On voter-interval profiles with even committee size, a single committee can achieve $1/4$-CONS together with $1/2$-AV, $1/2$-CC, $1/2$-EJR, or $1/2$-PAIRS.","The scaled method of equal shares, $\\alpha$-MES, provides $\\alpha$-EJR in polynomial time, a standalone proportionality guarantee that is used in the positive results."],"supporting_citations":[{"why":"Defines the voter-candidate interval (VCI) domain that the efficient algorithms operate on.","marker":"Godziszewski et al., 2021"},{"why":"Supplies the NP-complete EXACT COVER BY 3-SETS problem used in the reductions for PAIRS and CONS hardness.","marker":"Garey and Johnson, 1979"},{"why":"Provides the polynomial-time algorithm for Chamberlin–Courant maximization in the CI domain that the PAIRS algorithm invokes on the pair instance.","marker":"Betzler et al., 2013"},{"why":"Defines the CI domain, gives the polynomial-time candidate-ordering preprocessing, and supplies the CC-in-CI algorithm.","marker":"Elkind and Lackner, 2015"},{"why":"Its Lemma 4.7 contains the VCI-to-CI dominance observation that Proposition 4.3 formalizes.","marker":"Elkind et al. (2024, Lemma 4.7)"},{"why":"Defines extended justified representation (EJR), the proportionality standard whose approximate form is used in the trade-off results.","marker":"Aziz et al., 2017"},{"why":"Introduces the method of equal shares whose budget-scaling argument is adapted to prove the $\\alpha$-EJR guarantee of $\\alpha$-MES.","marker":"Peters and Skowron, 2020"},{"why":"Underlies the submodularity fact (Proposition 3.1) that makes proportional seat-splitting work for submodular objectives.","marker":"Nemhauser et al., 1978"}],"fun_headline_variants":["Interlacing scores measure and curb polarization","Connectivity scores for less polarizing committees","Tractable anti-polarization via one-dimensional voters","Balancing representation and anti-polarization scores"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polynomial-time results rest on the assumption that the election lies in the voter-candidate interval domain, meaning every voter and candidate can be placed as an interval on a line and approval means the intervals intersect, because outside such a one-dimensional representation both objectives are NP-hard and the efficient algorithms do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Interlacing scores measure and curb polarization","Connectivity scores for less polarizing committees","Tractable anti-polarization via one-dimensional voters","Balancing representation and anti-polarization scores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000289,"raw_usage":{"total_tokens":1689,"prompt_tokens":934,"completion_tokens":755,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":699}},"tokens_in":550,"tokens_out":755,"duration_ms":8142,"temperature":1.0,"reasoning_tokens":699,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:38:50.320202+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small VCI election, delete dominated candidates as in Proposition 4.3, and verify that the computed candidate order makes every voter's approval set contiguous; a single voter whose approvals are non-contiguous would show the VCI-to-CI reduction is not generally valid. Alternatively, brute-force all committees of a small random approval profile and look for a committee whose PAIRS and AV approximation ratios sum to more than 1, which would contradict Proposition 5.2.","supporting_citations":[{"cited_title":"On the computation of fully proportional representation","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time algorithm for Chamberlin–Courant maximization in the CI domain that the PAIRS algorithm invokes on the pair instance."},{"cited_title":"OWA -based extensions of the C hamberlin-- C ourant rule","cited_arxiv_id":null,"evidence_quote":"Defines the CI domain, gives the polynomial-time candidate-ordering preprocessing, and supplies the CC-in-CI algorithm."},{"cited_title":"The price of justified representation","cited_arxiv_id":null,"evidence_quote":"Its Lemma 4.7 contains the VCI-to-CI dominance observation that Proposition 4.3 formalizes."},{"cited_title":"Proportionality and the limits of welfarism","cited_arxiv_id":null,"evidence_quote":"Introduces the method of equal shares whose budget-scaling argument is adapted to prove the $\\alpha$-EJR guarantee of $\\alpha$-MES."},{"cited_title":"An analysis of approximations for maximizing submodular set functions— I","cited_arxiv_id":null,"evidence_quote":"Underlies the submodularity fact (Proposition 3.1) that makes proportional seat-splitting work for submodular objectives."}],"review_version":1}