{"id":"a59ab181-3a5a-463f-8044-7c754959c050","arxiv_id":"2602.08871","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Constant-randomness voting can achieve metric distortion below 3, breaking the deterministic barrier with only a fixed-size uniform lottery.","lead":"An open question in voting theory asks whether a rule can beat the well-known \"3x\" efficiency limit without relying on unlimited randomness. This paper answers yes: it constructs a voting rule whose random choice is limited to drawing uniformly from a fixed, constant-size list of candidates, yet still guarantees a worst-case cost ratio strictly below 3.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'deterministically identified list' step is unsubstantiated: Section 1.1 asserts a polynomial-time test for distortion <3−ε without giving one, so the bounded-randomness rule is not constructively identified.","rationale":"The reader's CONDITIONAL verdict is appropriate. The mathematical core—Theorem 3.4's DKW-based sampling bound, Section 4's support-distortion bound, Theorem 5.1's case analysis, and the Section 7 mixing inequalities—is coherent. I checked the Appendix B algebra; the parameter choices do give distortions <3. The weakest point is the conversion of the existence results into a deterministic rule. The paper explicitly promises a deterministic polynomial-time algorithm in Section 1.1 but omits the decision procedure for 'distortion <3−ε'. This is not a fatal flaw in the existence theorem because the RepApx definitions provide a checkable certificate, but as written it leaves the bounded-randomness contribution incomplete. I also note the Lemma 6.3/Claim A.1 constraint typo (first term should be λ(1−θ)/θ, not λ/[θ(1−θ)]); this supports the CONDITIONAL verdict but is secondary to the identification gap. No change to the reader's verdict is needed.","tokens_in":32732,"tokens_out":31968,"duration_ms":332353,"concrete_test":"Replace the unspecified distortion test with an explicit check: for a fixed profile, compute a Maximal Lottery and a Stable k-Lottery; enumerate all multisets of sizes O(ε1^{-4}) and O(k^2 ε2^{-2}) in lexicographic order and test whether Definition 3.1 / Definition 3.2 holds (support containment plus the pairwise inequalities). Since these conditions are polynomial-time verifiable and the sampling theorems guarantee at least one success, the first successful multiset yields a deterministic constant-size list. If this procedure is implemented and succeeds, the enumeration concern is resolved; if it cannot be made to succeed, the deterministic-identification claim fails as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 1.1 claims we can enumerate multisets and stop when the induced distribution 'achieves a metric distortion of less than 3−ε', with polynomial running time because a good multiset of constant size exists. No test for this predicate is supplied. Exact distortion is a worst case over all preference-consistent metrics; verifying it requires solving a family of optimization problems over metric constraints, and the paper's Theorem 2.8 only recasts it as an integral inequality over all biased metrics, not as a finite decision procedure. The sampling theorems (3.3, 3.4) establish positive-probability existence, not an identifiable witness. Consequently, the proof as written does not show that a deterministic polynomial-time rule can find the constant-size list; it only shows such a list exists. This is load-bearing because the advertised property is 'selects uniformly from a deterministically identified list'. The gap is reparable: one can enumerate constant-size multisets and test the RepApx conditions in Definitions 3.1/3.2, which are finite and polynomial-time checkable, and by Theorems 3.3/3.4 at least one multiset will pass. But the manuscript never states this.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies metric distortion in single-winner voting and asks whether the known randomized improvement below the deterministic barrier of 3 can be achieved with only 'bounded randomness': a rule that selects a winner uniformly from a constant-size list of candidates. The main formal result, Theorem 7.6, constructs a mixture of an ε1^2-RepApx Maximal Lottery and an (ε2,k,1/2+β~)-RepApx Pruned Lottery, with explicit parameters, whose metric distortion is strictly below 3. Corollary 7.7 states that the resulting rule has support size at most a constant independent of n and m. The proof develops several structural results: deterministic distortion of every candidate in the Maximal-Lottery support (Theorem 4.1), distortion of approximate Maximal Lotteries (Theorem 5.1), existence of small-support approximate Stable Lotteries via a DKW-based sampling argument (Theorem 3.4), and distortion bounds for approximate Pruned Lotteries under regular profiles and under strongly consistent biased metrics (Lemmas 6.3, 6.4, 7.5). The biased-metric framework of [CR22, CRWW24] is used throughout.","tokens_in":33016,"tokens_out":23292,"duration_ms":241468,"significance":"If the result holds, it is a significant step: it shows that the 3-distortion barrier for deterministic rules can be broken using randomness of a very restricted, interpretable form — a uniform lottery over a constant-size list. The structural results on the support of Maximal Lotteries and on small-support approximate Maximal/Stable Lotteries are likely to be of independent interest. The paper contains detailed proofs, and the main inequalities are derived in the body or appendices. The main caveat is that the advertised algorithmic 'deterministically identified list' part is not fully justified as written; however, the gap is local and reparable within the paper's framework.","major_comments":[{"comment":"The paper claims a deterministic polynomial-time algorithm that enumerates multisets and 'stop[s] if the induced distribution achieves a metric distortion of less than 3−ε'. No finite decision procedure for this predicate is supplied. Theorem 2.8 characterizes distortion as an integral inequality over all biased metrics, which is not an algorithmic test, and Theorems 3.3–3.4 only establish existence of a good multiset with positive probability. Since the abstract and Section 1.1 promise a 'deterministically identified list', this gap is load-bearing for the advertised constructive claim. The gap is reparable: rather than testing exact distortion, enumerate constant-size multisets and test the RepApx conditions from Definitions 3.1 and 3.2, which are finite and polynomial-time checkable once an exact ML/Stable-Lottery support is computed; by Theorems 3.3 and 3.4 some multiset of the guara","section":"Section 1.1 (final paragraph) and Corollary 7.7"}],"minor_comments":[{"comment":"The constraint displayed as λ/(θ(1−θ)) should be λ(1−θ)/θ. The closed-form expression for λ(θ,k,ε) and the algebra in Claim A.1 (where f1(p*) = p* gives λ = p* · θ/(1−θ)) show that the intended first threshold is (λ/θ)(1−θ). As printed, the text is ambiguous and the sufficiency argument in Lemma 6.3 is incorrect under the literal reading. Please rewrite the formula unambiguously.","section":"Lemma 6.3 / Claim A.1"},{"comment":"The step from the expectation bound (4) to 'there is a positive probability ... for all candidates a' uses the inequality max_a avg_v d_{v,a} ≤ avg_v max_a d_{v,a}. This is true and standard, but it is not stated; adding one sentence would make the probabilistic inference transparent.","section":"Section 3.4, proof of Theorem 3.4"},{"comment":"The text refers to 'ε2-RegApx Maximal Lotteries'; the intended term is 'RepApx'.","section":"Section 5, first paragraph"},{"comment":"The sentence about committee selection says the result implies existence of a deterministic committee rule with distortion strictly less than 3 when candidates may occupy multiple seats. This is only a corollary of the existential support-size statement, not of the algorithmic enumeration claim, and it may be worth stating as such.","section":"Section 1.1, committee-selection implication"}],"recommendation":"major_revision","confidential_remarks":"The main proof chain appears sound under the intended readings. The most substantive issue is the missing verification step for the claimed constructive 'deterministically identified list' property; it is local and fixable. The paper's reliance on recent results by overlapping authors, especially CRW26's Theorem 3.3, is a normal external dependency and not, on inspection, a circularity. The theorem statements themselves are existential and likely defensible even without the algorithmic enumeration claim; the authors should align the abstract and introduction with what is formally proved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the mathematical core is real. They show that a constant-size uniform lottery over candidates can achieve metric distortion strictly below 3, which is a genuinely new result. The proof chain from Theorem 3.4 to Corollary 7.7 is detailed and I found no fatal error. The support-of-ML bound (Theorem 4.1) is a nice standalone contribution, and the RepApx Stable sampling theorem (Theorem 3.4) is a real generalization of the existing Maximal Lotteries approximation result. The paper is technically serious.\n\nThe soft spots, in proportion. First, the stress-test concern is correct. Section 1.1 says you can enumerate multisets and stop when the induced distribution \"achieves metric distortion less than 3−ε\", and claims polynomial time. But no test for that predicate is given, and exact distortion over all biased metrics is not obviously decidable in finite time. This is not fatal to the existence result—the sampling theorems give positive probability, so a good multiset exists. But the abstract's \"deterministically identified list\" claim is not fully justified as written. The fix is easy: enumerate multisets and check the RepApx conditions in Definitions 3.1/3.2, which are finite and polynomial-time checkable; Theorems 5.1, 6.4, and the mixing theorem then give the distortion bound. The authors should say this explicitly.\n\nSecond, Lemma 6.3 and Claim A.1 have a typo: the first sufficient case should use λ(1−θ)/θ, not λ/(θ(1−θ)). The claimed closed-form λ is consistent with the corrected bound, so it looks like a transcription error, but as written the lemma's stated constraint is wrong.\n\nThird, the proof leans on [CRW26], a future SODA paper by overlapping authors, for Theorem 3.3. That is normal in this area, but the authors should check compatibility with the final version of that paper.\n\nOverall, the central existence claim holds up: a constant-size uniformly random list suffices to get distortion below 3. The \"deterministically identified\" strengthening is reparable but needs a spelled-out verification procedure. This paper deserves a serious referee: the result is new, the proofs are careful, and the gap is fixable. I would send it to review, with instructions to fix Lemma 6.3 and to add the RepApx verification step for the enumeration claim.","headline":"A real answer to a natural question about constant-size uniform randomness breaking the distortion-3 barrier, but the advertised 'deterministically identified list' is missing a verification step; worth refereeing after a fix.","tokens_in":33539,"tokens_out":5195,"would_cite":true,"duration_ms":56432,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B14","91B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a voting rule which picks uniformly at random from a fixed list of constant size can achieve metric distortion strictly below 3, breaking the barrier known to separate deterministic rules from randomized ones.","keywords":["metric distortion","randomized voting rules","bounded randomness","Maximal Lotteries","Stable Lotteries","quasi-kernel","social choice","approximate equilibrium"],"falsifier":"Enumerate all constant-size lists up to the paper's implied bound for a small election (say 10 voters, 10 candidates on a line) and compute the worst-case distortion of each uniform lottery; the theorem is false if any list produced by the construction, or every list, has distortion at least 3 in some metric. One concrete violation suffices because the bound is uniform over all metrics.","tokens_in":32597,"feed_emoji":"🎲","tokens_out":11979,"duration_ms":102275,"temperature":0.7,"pith_summary":"The paper asks whether the gap between deterministic voting rules, whose metric distortion cannot be better than 3, and fully randomized rules, which can do strictly better but with arbitrary distributions, can be closed using only bounded randomness — a rule that first names a constant-size list of candidates and then picks the winner uniformly from that list. The main result is an affirmative answer: there exist absolute constants ε > 0 and k such that a rule of this form has metric distortion at most 3 − ε. The proof mixes two approximate lottery rules — an approximate Maximal Lottery and an approximate Pruned Lottery, each supported on a constant number of samples — and shows that on every biased metric, the canonical hard case for distortion, the mixture is strictly below 3. If correct, the result shows that the advantage of randomization over determinism in metric voting does not require elaborate distributions; a transparent roster of constant size already suffices.","feed_headline":"A constant-size lottery breaks the 3-distortion barrier","feed_subtitle":"A voting rule that draws from a small fixed list achieves distortion below 3 — matching unrestricted randomized rules.","key_machinery":"The argument runs on four objects. (1) Biased metrics: a family of hard metric spaces such that a distortion bound on them transfers to all metrics; analysis reduces to two curves, ℓ(D,t) and r(t). (2) RepApx (Representative Approximate) Maximal and Stable Lotteries: distributions supported inside an exact lottery's support and satisfying approximate equilibrium inequalities; a standard concentration inequality for empirical distributions shows a constant-size uniform sample is RepApx with positive probability. (3) Quasi-Kernel Pruning: a linear-time reduction of candidates to a small kernel that preserves near-optimal social cost. (4) The mixing theorem: a tuned convex combination of the tw","core_discovery":"The central claim is Theorem 7.6: for suitable constants μ, β̃, ε₁, ε₂, and k, the mixed rule — with probability μ an ε₁²-RepApx Maximal Lottery, otherwise an (ε₂, k, 1/2+β̃)-RepApx Pruned Lottery — has metric distortion strictly below 3. Corollary 7.7 adds the bounded-randomness form: the support is a constant-size multiset, and with μ rational the rule is a uniform lottery over a fixed list with repetitions. The proof splits biased metrics into two regimes — inconsistent ones, where the Approximate Maximal Lottery component beats 3 by a constant, and strongly consistent ones, where the Approximate Pruned Lottery component does the same. Two structural results carry the proof: support candi","pith_inferences":["An implication the paper leaves implicit: the enumeration-and-stop procedure presumes a test for the distortion property; if the RepApx conditions are used as the test, the rule becomes fully constructive and polynomial-time.","The constants are far from tight; the same framework may support a much smaller list, and the paper's conjecture that two options suffice is a concrete target.","The multi-winner connection could yield a practical deterministic committee rule with distortion below 3; this is testable by simulation on random metrics."],"forward_implications":["Any metric space: a uniform lottery over a constant-size list achieves distortion strictly below 3, so the optimal distortion constant for bounded randomness matches that of unrestricted randomized rules.","Transparency: because the rule is a fixed roster with uniform probabilities, it is easy to publish and audit, addressing a common objection to randomized voting.","Robustness: the support bound implies that every realized winner of the mixed rule has distortion at most 4+√17, so no single realization is catastrophic.","Multi-winner connection: for any sufficiently large committee size, the same technique yields a deterministic committee selection rule with distortion below 3 when seats can be repeated.","Open question: the paper conjectures that two options (N = 2) already suffice to break the barrier, an order of magnitude smaller than the current constants."],"fun_headline_variants":["Small fixed lottery achieves sub-3 metric distortion","Bounded randomness breaks the 3-distortion ceiling","Voting rule with tiny lottery beats 3-distortion limit","Constant-size lottery tops deterministic voting distortion","Uniform lottery from small list undercuts 3 barrier"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that a constant-size multiset with distortion below 3−ε can be found: existence follows from the sampling theorems, but the paper's enumeration-and-stop argument assumes a way to test the distortion property without specifying it.","fun_headline_variants_meta":{"raw":{"variants":["Small fixed lottery achieves sub-3 metric distortion","Bounded randomness breaks the 3-distortion ceiling","Voting rule with tiny lottery beats 3-distortion limit","Constant-size lottery tops deterministic voting distortion","Uniform lottery from small list undercuts 3 barrier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1138,"prompt_tokens":689,"completion_tokens":449,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":433,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":433,"tokens_out":449,"duration_ms":5195,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T06:07:06.778062+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all constant-size lists up to the paper's implied bound for a small election (say 10 voters, 10 candidates on a line) and compute the worst-case distortion of each uniform lottery; the theorem is false if any list produced by the construction, or every list, has distortion at least 3 in some metric. One concrete violation suffices because the bound is uniform over all metrics.","supporting_citations":[],"review_version":1}