{"id":"98b3bad0-9039-40c1-8e50-0423407e88a6","arxiv_id":"2412.10671","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In line metrics, a constant-size committee can achieve the same cost as the optimal single winner, bypassing the factor-3 barrier that applies to any single winner.","lead":"This paper asks whether electing a small committee instead of one winner can beat the classic factor-3 distortion bound in metric voting. It proves that on a line, two candidates suffice to match the optimal single winner under total cost, and four under max cost, with matching impossibility results in the plane.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 20's 1-distortion-1 claim rests on Lemma 13, whose proof uses an invalid WLOG and whose pseudocode swaps arguments; the ordering inference is load-bearing and unproven as written.","rationale":"The reader's weakest assumption correctly identifies Lemma 13 and the SplitLine/Determine inference as the linchpin of the positive results. I agree that this is the most load-bearing point in the paper: every upper bound, including the headline 2-committee result, runs through Theorem 10. However, I do not believe the lemma is false; my own analysis of the geometry suggests the inference can be repaired by treating the case c2 preferred to c1 separately, and the swapped-argument bug is a straightforward typo in the pseudocode rather than a conceptual flaw. The paper as written, though, does not contain that repair, so the proof of the central claim is incomplete as typeset. I found no counterexample to Lemma 13 or Theorem 20 in small line instances I considered manually, and the proof of Theorem 20 itself (the V1/V2/V3 comparison) is sound once the ordering is available. The reader's CONDITIONAL verdict is primarily driven by the invalid 2D Euclidean lower-bound constructions in Theorems 31 and 32, which I also view as genuinely flawed: in I0, voter vi is closer to c_{i+1} than to c_{i-2}, contradicting the asserted preference order. Those are separate, localized issues that do not affect the positive sum-cost upper bound. Since my read does not change the reader's overall CONDITIONAL recommendation, and the main positive claim appears likely true modulo the Section 3 proof repair, I set verdict_should_be to UNCHANGED rather than moving to reject.","tokens_in":22732,"tokens_out":34396,"duration_ms":294969,"concrete_test":"Implement Algorithms 1-4 exactly as specified but with the argument order in the Algorithm 3 call to Determine fixed to match the signature, and exhaustively enumerate all line-metric instances with m<=6 candidates and n<=6 voters on integer positions, breaking distance ties in all possible ways. Verify that C* is always a core, that S_C is the true left-to-right order of C*, and that S_V matches the true spatial voter order. If any counterexample is found, Theorem 20 collapses; if none is found after exhaustive search, the Section 3 inference is sound and the issue is only a proof gap, which can be closed by rewriting Lemma 13 without the invalid WLOG.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 20 depends on Lemma 19, which depends on Theorem 10: the algorithm must recover a core C*, its left-to-right order, and the voters' order. Theorem 10 is proved through Lemma 13, which justifies the Determine inference. Lemma 13's proof contains a false 'without loss of generality': it assumes c1 precedes c2 in voter vi's preference, but c1 and c2 are fixed as the left and right pivot candidates, so vi may legitimately prefer c2 to c1 when vi lies to the right of the pivot point. The second case is therefore not proved for the configuration in which Determine outputs R, and the 'prefix contains c1 and ck but not c2' argument silently depends on the unproved case. Separately, Algorithm 3 line 8 calls Determine with the roles of ck and cj swapped relative to the function signature, so the pseudocode as written does not implement the intended inference. If the missing case cannot be repaired, the recovered core/order may be wrong, and the median-voter selection in Lemma 19--and hence the central 2-committee result--is not established. The lemma appears to be true (the missing case can likely be handled by a separate argument), but the paper as written does not prove it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a bicriteria perspective on metric distortion: a voting rule selects a committee of k candidates and is evaluated by comparing the resulting social cost (sum or max over voters of distance to the nearest selected candidate) against the cost of the best single candidate. The main positive claim is that on the line metric, a 2-committee with the sum objective achieves 1-distortion 1, i.e., it always contains an optimal candidate; for the egalitarian objective, committees of size 4, 3, and 2 achieve distortions 1, 1.5, and 2, respectively, all tight. For general metrics, an (m-1)-committee achieves sum-cost distortion 1+2/(m-1), with a matching 2D Euclidean lower bound. The upper-bound arguments rely on an algorithm that recovers the order of a 'core' subset of candidates and the order of voters from ordinal preferences on a line.","tokens_in":22935,"tokens_out":8899,"duration_ms":75317,"significance":"If established, the results give the first bicriteria treatment of metric distortion and show that allowing a constant-sized committee can bypass the classical factor-3 barrier for single-winner distortion on the line. The proposed ordering-recovery algorithm is a technically interesting tool that could be useful beyond this paper. The paper also contains several concrete lower-bound constructions. However, the manuscript in its current form has load-bearing gaps in both the ordering-recovery proof and the Euclidean lower-bound constructions, so the advertised theorems are not yet established as written.","major_comments":[{"comment":"The proof of Case 2 uses an invalid 'without loss of generality' assumption: it assumes c1 precedes c2 in voter vi's ordinal preference, but c1 and c2 are fixed as the left and right pivot candidates, so if vi lies to the right of the pivot point, vi legitimately prefers c2 to c1. The missing case (c2≻i c1) is not analyzed, and it is exactly the configuration where Algorithm 2's 'else' branch would output R. Because the Determine inference is the engine behind the recovered ordering (Theorem 10), Lemma 19, and hence the central 2-committee result (Theorem 20), this gap is load-bearing and must be repaired.","section":"§3.1, Lemma 13, Case 2"},{"comment":"The pseudocode calls Determine(≻i, ck, cj, L, R, c1, c2), but the function signature in Algorithm 2 is Determine(≻i, cj, ck, L, R, c1, c2) with the convention that the second argument is the determined candidate and the third is the undetermined one, and ck≻i cj. As written, the arguments are swapped, so the procedure would treat the already-determined cj as the candidate to place and would not implement the intended inference. The correctness claim for SplitLine is therefore not backed by the provided code.","section":"§3, Algorithm 3, line 8"},{"comment":"The lower-bound family I0 uses candidates ci at (−ℓ, (2i−1)/(2m)) and voters vi at (0, (2i−1)/(2m)). With this uniform y-spacing, voter vi (for i≥2) is at distance sqrt(ℓ² + ((i−1)/m)²) from c1 and at distance sqrt(ℓ² + (1/m)²) from c_{i+1}; for i>2 the latter is strictly smaller, so c_{i+1} is preferred to c1, contradicting the claimed profile ci≻ci−1≻...≻c1≻ci+1≻...≻cm. Thus the instances do not realize the ordinal preferences that the indistinguishability argument requires. The same issue affects Theorem 32. The construction may be repairable with exponentially spaced y-coordinates, but as written the lower bounds are not valid.","section":"§5.1, Theorem 31 (and §5.2, Theorem 32)"},{"comment":"The symbols vl and vr are inconsistently defined as 'leftmost and rightmost candidates' in Lemma 23 and as 'leftmost and rightmost voters' in Theorem 26 and Figure 5; Lemma 24 then refers to 'candidates placed between vl and vr' when vl and vr are voters. This notational ambiguity makes the proofs of Lemma 24 and Theorem 26 hard to follow and should be clarified with distinct names for the extreme voters and the extreme candidates.","section":"§4.2, Lemmas 23–24 and Theorem 26"}],"minor_comments":[{"comment":"The condition 'c_j∈ Det' uses an undefined symbol Det; it should be C* (the current set of determined candidates).","section":"§3, Algorithm 3, line 7"},{"comment":"The function name 'SortCandiatesAndVoters' is misspelled; also the variable name in the comment 'SC' is not defined consistently.","section":"§3, Algorithm 1"},{"comment":"The proof says 'we consider the median voter v' and then uses 'v's closest candidate c' without explicitly handling ties among multiple median voters or multiple equidistant closest candidates; the argument goes through if ties are broken consistently, but this should be stated.","section":"§4.1, Lemma 19"},{"comment":"The sentence 'the distance to any other candidate ci remains the same as in I0' for the moved voter vj is false: moving vj from x=0 to x=ℓ changes the x-separation to every candidate ci (i≠j) from ℓ to 2ℓ. The relative order among those candidates is preserved, but the stated reason is incorrect.","section":"§5.1, Theorem 31 proof"},{"comment":"Several typos and minor formatting issues appear throughout (e.g., 'offer', 'prefernece', inconsistent use of 'ci' vs 'ck' in Algorithm 2 comments); a careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The central positive result (Theorem 20) is striking and, if repaired, would be a strong contribution. The Lemma 13 gap and the pseudocode swap are likely fixable with a dedicated case analysis and a corrected call; the 2D lower-bound coordinates also appear repairable by non-uniform y-spacing. None of these issues looks like an irreparable flaw, but the current manuscript does not support its headline claims as written. I would encourage the authors to fix the proof of Lemma 13, correct Algorithm 3, and revise the lower-bound constructions before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. The bicriteria framing—measuring a committee against the best single winner—is new and worth taking seriously, and the line-metric results are the real content: two candidates always contain an optimal single winner under sum cost, four do it under max cost. That is a surprising way around the factor-3 barrier, and I expect it to influence follow-up work.\n\nWhat's good: the model is clean, the upper-bound algorithms are simple and mostly self-contained, and the paper is honest about the baseline distinction from k-committee distortion. Theorem 20's argument—keep the middle of a three-candidate shortlist, one of the extremes is dominated—is neat. The general-metric m-1 bound is a straightforward frequency argument, but it is correct. The line lower bounds for max cost match the upper bounds and are standard adversary constructions.\n\nWhere it falls down. Two places. First, Lemma 13, which underpins the ordering recovery, has a real proof gap: the 'without loss of generality c1 precedes c2' is not WLOG—it is exactly the case that fails when the voter lies on the other side of the pivot—and the pseudocode in Algorithm 3 calls Determine with the arguments swapped. The lemma may be repairable, but as written the central 2-committee result does not have a complete proof. Second, the 2D lower bounds in Theorems 31 and 32 do not work as written. In I0, the equally spaced y-coordinates put c_{i-1} and c_{i+1} at equal distance from v_i, so the stated strict preference is not realized; and in I_j, moving voter v_j changes its distances to all other candidates, so the claim that all voters' ordinal preferences are unchanged is false. These constructions look repairable with some perturbation bookkeeping, but they are not valid in the current form.\n\nThere are also small typos, such as 'costm' where sum cost is meant in Theorem 22, but those are cosmetic.\n\nWho should read this: anyone working on metric distortion or committee selection. The bicriteria benchmark is a good idea, and the line results are likely true. The paper deserves a serious referee—this is not a desk reject—but the referee should ask for a corrected Lemma 13 and repaired lower bounds before acceptance.","headline":"Fresh bicriteria benchmark with clean line results, but the 2D lower bounds and the ordering lemma need repair before the paper is rigorous.","tokens_in":23509,"tokens_out":4611,"would_cite":true,"duration_ms":40546,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"On a one-dimensional line, a two-candidate committee picked from rankings alone always contains the optimal single candidate for total distance, giving a 1-distortion of 1.","keywords":["metric distortion","multiwinner voting","ordinal preferences","line metric","committee election","voting rule","approximation ratio","social choice"],"falsifier":"Enumerate all small line instances, say five candidates and four voters with distinct positions, and run the public algorithm; if any instance yields a determined set that is not consecutive on the true line, or a candidate placed on the wrong side of the pivot midpoint while every voter's ranking matches the distances, Lemma 13 fails and the 2-committee guarantee collapses. A cheaper check is to search for a voter v_i, a determined c_j, and an undetermined c_k with c_k ranked above c_j while both pivot candidates are closer to v_i than c_j, yet c_k and c_j lie on the same side of the pivot point in the true coordinates.","tokens_in":22511,"feed_emoji":"🗳️","tokens_out":8331,"duration_ms":73879,"temperature":0.7,"pith_summary":"The paper studies how much efficiency is lost when a voting rule sees only voters' rankings of candidates, not their true distances. It asks whether electing a small committee, and charging each voter only the distance to the nearest elected candidate, can beat the distortion-3 barrier that is unavoidable when exactly one winner is chosen. The main answer is yes on a line metric: with just two elected candidates, an algorithm can guarantee that the committee contains the single candidate minimizing total distance, giving a ratio of 1 to the optimal single candidate. The same ordering technique gives ratios 1, 3/2, and 2 for the maximum-distance objective with committees of sizes four, three, and two, all optimal. For general metrics, the paper shows m-1 candidates achieve total-distance ratio 1+2/(m-1), matching a lower bound, and that no deterministic rule can beat ratio 3 for maximum distance even with m-1 candidates in the plane.","feed_headline":"Two candidates always include the optimal single winner","feed_subtitle":"On a line, a ranking-only rule picks a pair whose total distance to voters equals the best single candidate.","key_machinery":"The engine is the sorting algorithm SplitLine plus SortCandidates and SortVoters. Starting from a pivot voter's two nearest candidates, whose midpoint defines a pivot point, the algorithm repeatedly calls Determine: for any undetermined candidate c_k that some voter ranks above a determined candidate c_j, it places c_k on the opposite side of the pivot point if both pivot candidates are closer to that voter than c_j, and otherwise on the side of the nearer pivot candidate. The invariant that the determined set stays consecutive on the line makes each such inference sound, and the process ends with a core set C* that every voter prefers to every candidate outside it. Sorting C* by the pivot voter's order and ordering voters lexicographically by their preferences over C* yields the voter order used to locate the median; the load-bearing inequality is $\\mathrm{cost}_s(c_2) \\le \\mathrm{cost}_s(c_3)+(|V_3|-|V_1|)\\,d(c_2,c_3)$, whose mirror for $c_1$ decides which of the two outer candidates can be discarded.","core_discovery":"The central claim is Theorem 20: there is a deterministic voting rule for the 2-committee sum-cost election on the line metric that always outputs a pair of candidates containing an optimal single candidate, so its 1-distortion is 1. The proof first recovers, from ordinal preferences alone, the left-to-right order of a core set of candidates and the order of voters with respect to that set; then it finds the median voter, takes that voter's closest candidate plus its immediate left and right neighbours, and shows one of these three is optimal by the median-voter property for sum costs. A counting argument on which side has more voters lets the rule drop one neighbour and still keep the optimal candidate. The paper also establishes matching upper and lower bounds for the max-cost objective on the line and for general and 2-D Euclidean metrics.","pith_inferences":["An extension left implicit by the paper is to tree metrics or metrics of bounded doubling dimension; the consecutive-interval structure used in the line proof fails there, so a different invariant would be needed.","The two-candidate shortlist could serve as a preprocessing step when distances are privately known: any mechanism that then chooses between the two candidates inherits the guarantee that one of them is optimal.","The recursive lower-bound construction suggests that on a line, choosing sub-exponentially many candidates may still force unbounded distortion against an optimal committee, which would connect to the literature on small winning sets.","A testable empirical extension is to run the ranking-only two-candidate rule on synthetic line elections with known positions and compare its cost with k-median on the true positions; the gap should be zero whenever the optimal candidate lies beside the median voter."],"forward_implications":["A two-candidate election on a line is never worse than the best single winner under total distance, even though each voter's distance is measured to the closer of the two.","Three candidates give a 3/2-approximation and four give the exact optimum under maximum distance, with matching lower bounds showing fewer candidates cannot do better.","The lower bounds imply that on the line the committee size, not the amount of preference detail, is what buys accuracy: in the plane, no number of candidates below m improves the max-cost ratio beyond 3.","The core-ordering routine gives a general way to recover geometric order from ordinal data, so it can be reused for other line-metric voting problems.","The bicriteria framework establishes a new benchmark for multiwinner voting: comparing a k-committee to the best single winner, rather than to the best k-committee."],"supporting_citations":[{"why":"Introduces metric distortion and the worst-case ratio that the paper's 1-distortion modifies.","marker":"[3]"},{"why":"Establishes the distortion-3 barrier for deterministic single-winner rules that this paper's committee results break.","marker":"[20]"},{"why":"Supplies the k-committee distortion framework and the lower bound that Theorem 29 extends.","marker":"[7]"},{"why":"Introduces distortion as the efficiency loss from ordinal to cardinal preferences, the conceptual starting point.","marker":"[29]"}],"fun_headline_variants":["On a line, two candidates always include the optimal single","Pair of candidates matches best single on line metrics","Two candidates suffice for optimal line-metric voting","Committee of two matches optimal single in line metric","Line metric: constant-size committee achieves optimal cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The ordering algorithm assumes that the voters' rankings really come from distances on a line, and that the geometric inference in Lemma 13, which decides an undetermined candidate's side of the pivot from whether both pivot candidates are closer to some voter, is valid whenever the determined set is consecutive.","fun_headline_variants_meta":{"raw":{"variants":["On a line, two candidates always include the optimal single","Pair of candidates matches best single on line metrics","Two candidates suffice for optimal line-metric voting","Committee of two matches optimal single in line metric","Line metric: constant-size committee achieves optimal cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000804,"raw_usage":{"total_tokens":3527,"prompt_tokens":933,"completion_tokens":2594,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":2521}},"tokens_in":549,"tokens_out":2594,"duration_ms":18158,"temperature":1.0,"reasoning_tokens":2521,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:48:02.971043+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all small line instances, say five candidates and four voters with distinct positions, and run the public algorithm; if any instance yields a determined set that is not consecutive on the true line, or a candidate placed on the wrong side of the pivot midpoint while every voter's ranking matches the distances, Lemma 13 fails and the 2-committee guarantee collapses. A cheaper check is to search for a voter v_i, a determined c_j, and an undetermined c_k with c_k ranked above c_j while both pivot candidates are closer to v_i than c_j, yet c_k and c_j lie on the same side of the pivot point in the true coordinates.","supporting_citations":[{"cited_title":"Anshelevich, O","cited_arxiv_id":null,"evidence_quote":"Introduces metric distortion and the worst-case ratio that the paper's 1-distortion modifies."},{"cited_title":"Gkatzelis, D","cited_arxiv_id":null,"evidence_quote":"Establishes the distortion-3 barrier for deterministic single-winner rules that this paper's committee results break."},{"cited_title":"Caragiannis, N","cited_arxiv_id":null,"evidence_quote":"Supplies the k-committee distortion framework and the lower bound that Theorem 29 extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces distortion as the efficiency loss from ordinal to cardinal preferences, the conceptual starting point."}],"review_version":1}