{"id":"65c90a3b-5e7a-46de-900d-f7b95ce6e46d","arxiv_id":"2505.13630","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Deterministic tournament rules have metric distortion between 3.1128 and 3.9312, and deterministic k-tournament rules approach distortion 3 while randomized 3-tournament rules can beat 3.","lead":"This paper proves new limits and guarantees for voting rules that use pairwise or small-set comparisons between candidates under the metric distortion model. The results narrow the distortion gap for deterministic tournament rules and introduce rules using k-wise comparisons that approach or beat the previous barrier of 3.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.14's randomized k-tournament separation rests on Lemma 5.15, which is only sketched and delegated to CRWW24; the 'distortion below 3 for 3-tournament rules' claim is therefore not yet formally supported.","rationale":"The reader's weakest_assumption matches the only genuine gap I found. The deterministic core of the paper is detailed and largely self-contained: Lemma 4.2 gives a clear block-sliding proof, the blanketing argument in Lemma 4.8 is constructive, and the lower-bound profiles in Tables 1 and 2 appear to realize the claimed tournament matrix with the stated parameters. The randomized k-tournament result, by contrast, relies on Lemma 5.15, which is explicitly only sketched and delegated to another paper. This is a correctness risk rather than a stylistic concern, because Theorem 5.14's proof does not otherwise connect the θ-regular analysis to arbitrary profiles. I do not see an independent flaw in the deterministic theorems or in the stability-representation lemma; Observation 5.3 and Theorem 5.5 are consistent with the tie-breaking rule. The right outcome is to keep the paper conditional pending a complete proof of Lemma 5.15 or an exact citation of a theorem in CRWW24 that implies it. If that proof is supplied, the central deterministic contribution and the k-tournament upper bounds appear credible.","tokens_in":31824,"tokens_out":19260,"duration_ms":170802,"concrete_test":"Complete the formal proof of Lemma 5.15 by instantiating the (α,β)-consistency argument from CRWW24 for stable k-lotteries after quasi-kernel pruning. In particular, verify the two cases in the sketch: (i) for biased metrics that are not sufficiently consistent, the stable 1-lottery has distortion below 3 by a uniform constant and the quasi-kernel rule has bounded distortion; (ii) for sufficiently consistent metrics, the quasi-kernel rule has distortion below 3 by a uniform constant for all k≥2, with constants independent of k. Also identify the exact theorem or lemma in CRWW24 that supplies this implication. If either case requires k-dependent constants, then Theorem 5.14's 'for any k≥2' claim fails as stated and the abstract's k=3 separation is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised randomized k-tournament result, distortion strictly below 3 using only 3-wise preferences, is Theorem 5.14. Its proof has two parts: a direct analysis of stable k-lotteries on θ-regular profiles, using Lemma 5.6 and Lemma 5.16, and Lemma 5.15, which extends this analysis to arbitrary profiles by mixing with a stable 1-lottery after quasi-kernel pruning. Lemma 5.15 is not proved in this paper. It is stated as 'implicit in [CRWW24]' and followed by a proof sketch whose final sentence refers the reader to [CRWW24] for formal execution. The sketch appeals to the (α,β)-consistency framework and to two qualitative cases, but no specific statement in CRWW24 is cited that directly implies Lemma 5.15 as written: stable k-lotteries for all k≥2, with parameters θ, µ, and r<3 chosen uniformly in k. Since Theorem 5.14 is the sole support for the randomized claim in Theorem 1.2 and for the abstract's claim of breaking the 'longstanding barrier' with k=3, this gap is load-bearing. The deterministic results, Theorem 1.1, Theorem 4.9, and Theorem 4.10, do not depend on Lemma 5.15 and appear well-supported by the detailed block argument and the explicit lower-bound profiles.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies metric distortion in social choice, focusing on tournament rules (which observe pairwise aggregate preferences) and a new class of k-tournament rules (which observe aggregate preferences over k-tuples). The main claims are: (i) the optimal metric distortion of deterministic tournament rules lies between 3.1128 and 3.9312, established via a new deterministic rule called Unblanketed Set and a 5-candidate lower-bound instance (Theorems 1.1, 4.9, 4.10); (ii) a deterministic k-tournament rule, Simultaneous Lottery Veto, achieves distortion 3 + O((log k / k)^{1/4}) (Theorem 5.13); and (iii) a randomized k-tournament rule, Pruned Double Lotteries, achieves distortion strictly below 3, even for 3-tournament rules (Theorems 1.2 and 5.14). The proofs use the biased-metric integral framework of Charikar and Ramakrishnan and Charikar et al., a block-sliding argument for the deterministic upper bound, and stable k-lotteries from committee selection. The deterministic results are developed in detail; the randomized k-tournament result depends on a lemma that is only sketched and delegated to prior work.","tokens_in":32050,"tokens_out":9688,"duration_ms":83896,"significance":"If the deterministic bounds are correct, they resolve a long-standing question by showing that no deterministic tournament rule can achieve distortion 3, while also improving the upper bound from 2+sqrt(5) to 3.9312. This is a substantive contribution to the metric distortion literature. The introduction of k-tournament rules is a natural and potentially useful generalization, with motivation from RLHF and from the theory of k-wise comparison queries. The deterministic proofs are largely self-contained and include explicit constructions: the stability-representation lemma (Lemma 5.6), the existence and defensive properties of stable k-lotteries (Theorems 5.4 and 5.5), and the subtle block-shifting argument for Lemma 4.2 are all given in full. The randomized claim of distortion below 3 for 3-tournament rules would be a striking separation if fully supported, but as written its proof lacks a complete formal derivation of the key reduction, which tempers the significance of that part of the paper.","major_comments":[{"comment":"The proof of Theorem 5.14 for arbitrary preference profiles, and hence the randomized claim in Theorem 1.2 and in the abstract, rests entirely on Lemma 5.15. This lemma is stated as 'implicit in [CRWW24]' and is followed by a proof sketch whose final sentence refers the reader to [CRWW24] for formal execution. No specific statement in [CRWW24] is cited that directly implies Lemma 5.15 as written, namely that stable k-lotteries for all k >= 2 can be combined with quasi-kernel pruning and a stable 1-lottery to give distortion below 3 with parameters independent of k. The sketch's two-case discussion does not quantify the (alpha,beta)-consistency threshold or the resulting constants r, r', mu, and theta. This gap is load-bearing: the direct analysis in the proof of Theorem 5.14 (using Lemma 5.16 and the stability-representation lemma) only establishes the desired lambda < 1 bound for theta-regular profiles, and the step from theta-regular profiles to general profiles is exactly Lemma 5.15. Please provide a complete proof of Lemma 5.15 or a precise citation to a statement in [CRWW24] that covers the needed parameter range for all k >= 2.","section":"Section 5.4, Lemma 5.15 and Theorem 5.14"},{"comment":"The lower bound of Theorem 4.10 requires the listed preference profiles to realize the tournament margins and to satisfy the exact equalities used in the integral computations, e.g., 1 - plu(j*-1) = s_{j*-2 > j*-1} for j* = 1,2,3,4, and s_{2 > 0} = s_{3 > 0} = s_{4 > 0} = s_{2,3,4 > 0} = beta for j* = 0. The text says these conditions are 'indeed satisfied' and that the profiles are 'optimal,' but it does not show the algebra or provide checking code. Because Theorem 4.10 is a central contribution, the verification should be included, either as an exact arithmetic derivation or as a reproducible auxiliary file. Without this, the lower-bound claim is not fully checkable as written.","section":"Section 4.3, Tables 1 and 2"},{"comment":"The proof of Theorem 5.13 is concise but appears to rely on an implicit re-use of the quasi-kernel pruning property for sets J that may contain pruned candidates. In the chain of inequalities after applying Lemma 5.6, the argument uses that s_{i > J} <= theta for every candidate i in the quasi-kernel and every subset J disjoint from {i}, but it is not stated explicitly whether the partition J is restricted to the pruned set C-hat. Since the inequality 's_{i > J} <= theta' is only justified for pairs both inside the quasi-kernel, the proof should clarify how subsets containing non-quasi-kernel candidates are handled. This is likely fixable and does not undermine the asymptotic claim, but it should be made explicit.","section":"Section 5.3, Theorem 5.13"}],"minor_comments":[{"comment":"In the last paragraph of the proof, 'Thus, g_v(1) = 1 as claimed' should be 'g_v(t) = 1' to match the preceding sentence.","section":"Section 4.1, proof of Lemma 4.2"},{"comment":"The notation 'i*, k* in I' should read 'i*, k in I' to be consistent with the statement of the corollary.","section":"Section 4.1, proof of Corollary 4.5"},{"comment":"The parameter k is overloaded: in Theorem 5.14 the rule is called a (k+1)-tournament rule, while the abstract and Theorem 1.2 refer to a randomized 3-tournament rule. This is not an error, but the correspondence (set the stable-lottery size to 2 for a 3-tournament rule) should be stated explicitly to avoid confusion.","section":"Sections 5.4 and Abstract"},{"comment":"The matrix and tables give decimal values rounded to a few digits, while the derivation uses exact symbolic parameters beta and lambda. Please state the precision of the decimal approximations and confirm that the profile weights in Tables 1 and 2 sum to 1 within the stated precision.","section":"Section 4.3, Theorem 4.10"},{"comment":"The phrase 'which had been a longstanding barrier even for the larger class of ranked voting rules' could be misread as claiming that breaking distortion 3 for ranked voting rules is new. Since [CRWW24] already achieved distortion below 3 for randomized ranked voting rules, please rephrase to make clear that the barrier here is specifically for k-tournament rules.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"The deterministic results---Theorems 1.1, 4.9, and 4.10---appear substantial and well-supported modulo the profile verification issue. The headline randomized claim (Theorems 1.2 and 5.14) is currently not fully supported because Lemma 5.15 is only sketched and delegated to [CRWW24] without a precise citation. Since the authors of the present paper include authors of [CRWW24], the delegation should be straightforward to either justify with a precise theorem reference or replace with a complete proof. I do not view this as a fatal flaw, but it is a load-bearing gap that must be resolved before the randomized claim can be accepted. I also recommend that the authors supply machine-checkable verification for the lower-bound profiles in Section 4.3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: read this for the deterministic tournament results, which are strong and look right; treat the randomized k-tournament “below 3” claim as conditional until Lemma 5.15 is actually proved rather than delegated.\n\nWhat is genuinely new: the paper closes the deterministic tournament distortion gap from [3, 4.236] to [3.1128, 3.9312]. The lower bound uses an asymmetric 5-candidate instance with explicit preference profiles and rules out distortion 3; the upper bound comes from a new rule, Unblanketed Set. The biased-metric “block sliding” lemma (Lemma 4.2) is a clean and useful step, and it also recovers the known Ranked Pairs result for at most four candidates. The introduction of k-tournament rules is a good conceptual extension, and the deterministic Simultaneous Lottery Veto rule approaching distortion 3 as k grows is a solid contribution. The stability-representation lemma for stable k-lotteries is a genuinely useful standalone tool.\n\nThe soft spots are real but uneven. The big one is Theorem 5.14: the randomized k-tournament separation rests on Lemma 5.15, which is stated as “implicit in [CRWW24]” and given only as a proof sketch. The abstract headlines this result, so the gap is load-bearing. It may well be true, and the sketch is plausible, but the formal execution is not in this paper. A referee should demand either a complete proof or a precise pointer to a proved statement in CRWW24 that directly implies Lemma 5.15.\n\nThe lower-bound profiles in Tables 1 and 2 are asserted to realize the claimed tournament margins, but the algebra is not shown. That is minor-to-moderate: the explicit tables make independent verification possible, yet the exact constant 3.1128 depends on it. Also, Theorem 1.2’s wording makes the k-tournament results sound like exact characterizations; in the deterministic case it is really an upper bound approaching 3 from above, with the known lower bound 3. Not a mathematical flaw, but a cleaner restatement would help.\n\nThe deterministic sections stand on their own and are the main reason to take the paper seriously. The citation pattern is fine: the reliance on CRWW24 is explicit and mostly in the randomized part where the gap lives. There is no concealed circularity in the deterministic argument.\n\nWho this is for: people working on metric distortion, tournament solutions, or voting with limited information. The deterministic part deserves a serious referee. I would send it out, with the request to fix Lemma 5.15 and verify the tables before final acceptance.","headline":"The deterministic tournament bounds are the real result; the randomized k-tournament claim is conditional on an unproved lemma.","tokens_in":32686,"tokens_out":2895,"would_cite":true,"duration_ms":29573,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deterministic tournament rules cannot reach distortion 3; the optimal constant lies between 3.1128 and 3.9312, and moving from pairwise to k-wise preference data restores near-3 or sub-3 performance.","keywords":["metric distortion","tournament rules","k-tournament rules","social choice","stable lotteries","biased metric framework","Unblanketed Set","deterministic voting rules"],"falsifier":"Take the 5-candidate tournament matrix from Section 4.3 and solve the exact integral condition for the best possible deterministic tournament rule; if the optimum is below 3.1128, the lower bound is false, and if the preference profiles in the tables fail to reproduce the matrix exactly, the construction is invalid.","tokens_in":31555,"feed_emoji":"🗳️","tokens_out":8183,"duration_ms":78181,"temperature":0.7,"pith_summary":"This paper asks how much social cost a voting rule must sacrifice when it sees only aggregate pairwise preferences instead of full rankings, and what can be gained by seeing slightly more. It establishes that deterministic tournament rules—rules that use only the share of voters preferring each candidate to each other—cannot achieve the distortion 3 available to deterministic ranked rules or randomized tournament rules; the optimal constant lies between 3.1128 and 3.9312. It then introduces k-tournament rules, which receive the fraction of voters ranking each k-tuple in each order, and shows that deterministic such rules approach distortion 3 as k grows, while a randomized 3-tournament rule drops strictly below 3, a level previously out of reach for pairwise-only rules. A sympathetic reader should care because metric distortion measures worst-case welfare loss from coarse preference information, and pinning down the floor for each information class says exactly how much extra querying is worth.","feed_headline":"Tournament voting: no rule beats distortion 3.1128","feed_subtitle":"Adding k-wise preference data pushes deterministic rules back toward 3 and randomized rules below it.","key_machinery":"The engine is the biased metric framework, which reduces worst-case distortion to an integral inequality over \"stacked blocks\" representing voter distances; for tournaments, the paper extracts local graph conditions from this inequality. The new deterministic rule is built on blanketing, a strengthening of the classical covering condition, and the proof that an unblanketed candidate always exists uses a cycle argument. For k-tournaments, the central objects are stable k-lotteries—distributions over candidates that beat any other distribution with probability $1-\\frac{1}{k+1}$ in a voter's eyes—together with the stability-representation lemma, which bounds how much probability a stable lottery can place on a set $J$ when many voters rank an outside candidate $i$ above all of $J$.","core_discovery":"The paper's central claim is that the metric distortion of deterministic tournament rules is not 3 but a non-integral constant in the interval $[3.1128, 3.9312]$. The lower bound is established by a 5-candidate election with a deliberately asymmetric tournament graph and exponentially increasing vote margins, for which every candidate has worst-case distortion at least $3.1128$; the upper bound comes from the Unblanketed Set rule, which always selects a candidate not \"blanketed\" by another and guarantees distortion at most $1+2\\lambda\\approx 3.9312$, where $\\lambda$ solves $\\lambda^3-\\lambda^2-1=0$. The paper then defines k-tournament rules and proves that deterministic such rules can approach distortion 3 as k grows, while a randomized rule using 3-way preference data achieves distortion strictly below 3.","pith_inferences":["The paper's use of a half-integral biased metric for one candidate suggests that the conjecture that $(0,1,2,3)$-metrics are the only hard cases may be too restrictive; similar metrics might improve known lower bounds for randomized voting rules.","Because the k-tournament rules need only each voter's top and bottom choice within a k-set rather than a full ranking, the results suggest that RLHF-style preference elicitation can use cheaper top-and-bottom queries and still capture much of the benefit of k-wise data.","Closing the deterministic tournament gap likely requires avoiding the block-sliding obstruction the paper identifies: a multi-candidate version of its shifting argument would imply Ranked Pairs has distortion 3, which is known to be false, so new upper-bound rules probably need a different mechanism."],"forward_implications":["If Theorem 1.1 is right, every deterministic rule that sees only pairwise vote shares has worst-case distortion above 3.1128, so the Condorcet-style distortion-3 guarantee is unattainable in this class.","The Unblanketed Set rule, if its analysis holds, improves the best deterministic tournament upper bound from $2+\\sqrt{5}\\approx 4.236$ to about $3.93$.","If Simultaneous Lottery Veto's bound holds, collecting favorite and least-favorite preferences over k-tuples lets a deterministic rule approach distortion 3 without full rankings.","If Pruned Double Lotteries' bound holds, randomizing over stable lotteries after quasi-kernel pruning yields distortion below 3 with k=3, separating randomized tournament rules from randomized 3-tournament rules.","The stability-representation lemma, if correct, is a reusable bridge between committee-selection algorithms and voting rules."],"supporting_citations":[{"why":"Supplies the biased-metric integral condition used for all upper and lower bounds, and the implicit reduction behind Lemma 5.15 on which the randomized sub-3 claim rests.","marker":"[CRWW24]"},{"why":"Introduced the biased metric framework and the (0,1,2,3)-metrics that the lower-bound constructions build on.","marker":"[CR22]"},{"why":"Gave the prior best deterministic tournament upper bound of $2+\\sqrt{5}$ and the covering machinery that Unblanketed Set strengthens.","marker":"[MW19]"},{"why":"Established the distortion-3 lower bound for deterministic rules and for randomized tournament rules, defining the barrier this paper breaks for k-tournaments.","marker":"[GKM17]"},{"why":"Proved that deterministic ranked voting rules achieve distortion 3, the benchmark that deterministic tournament rules are shown here to miss.","marker":"[GHS20]"},{"why":"Set up the metric distortion model and proved Ranked Pairs achieves distortion 3 with at most 4 candidates, which the 5-candidate lower bound complements.","marker":"[ABE+18]"},{"why":"Provided Simultaneous Veto, the deterministic rule whose k-tournament analogue becomes Simultaneous Lottery Veto.","marker":"[KK23]"},{"why":"Defined stable lotteries, the committee-selection tool whose distributional properties drive the k-tournament rules.","marker":"[CJMW20]"},{"why":"Supplies the quasi-kernel existence theorem used by the pruning step in both k-tournament rules.","marker":"[CL74]"}],"fun_headline_variants":["Tournament voting distortion: not 3, but between 3.1128 and 3.9312","5-candidate election forces tournament distortion above 3.1128","k-wise preference data: deterministic rules approach 3, randomized beat 3","Unblanketed Set rule caps tournament distortion at 3.9312"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that randomized rules with three-way preference data beat distortion 3 depends on a lemma the paper borrows from an earlier work and proves only by sketch; if that lemma is wrong as stated, that particular separation result is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Tournament voting distortion: not 3, but between 3.1128 and 3.9312","5-candidate election forces tournament distortion above 3.1128","k-wise preference data: deterministic rules approach 3, randomized beat 3","Unblanketed Set rule caps tournament distortion at 3.9312"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00141,"raw_usage":{"total_tokens":5754,"prompt_tokens":1060,"completion_tokens":4694,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":676,"completion_tokens_details":{"reasoning_tokens":4607}},"tokens_in":676,"tokens_out":4694,"duration_ms":30268,"temperature":1.0,"reasoning_tokens":4607,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:12:34.159076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the 5-candidate tournament matrix from Section 4.3 and solve the exact integral condition for the best possible deterministic tournament rule; if the optimum is below 3.1128, the lower bound is false, and if the preference profiles in the tables fail to reproduce the matrix exactly, the construction is invalid.","supporting_citations":[],"review_version":1}