{"id":"ddf1ab2b-95a0-41a6-908e-efd2497f1e1a","arxiv_id":"2506.22133","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Every election admits a (t, alpha)-undominated committee of size O(t/alpha), the bound is asymptotically optimal, and for t=1 this gives a Condorcet winning committee of size 5.","lead":"This paper defines a tunable notion of undominated voting committees and proves that for any parameters t and alpha a committee of size O(t/alpha) always exists. The new bounds improve the known Condorcet winning committee size from 6 to 5 candidates.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's 4.75 bound and δ(t)→1 rest on unverified numerical 'verifications' in Appendix B.4, and the δ(t)→1 proof is only pointwise in α; without a certificate or a uniform argument the asymptotic claims are unsupported.","rationale":"The reader's weakest assumption identifies exactly the non-rigorous numerical verification behind the constant 4.75 in Theorem 2, and I agree that this is the most load-bearing concern. The main results of Section 4—the existence of a (t,α)-undominated set of size δ(t)t/α and the asymptotic optimality δ(t)→1—both route through the proof of Theorem 2. In Appendix B.4 the authors write 'we can verify' for the α>0.045 regime and cite Figure 5; no code, interval arithmetic, or analytical derivation is supplied. The second regime, α≤0.045, depends on an inequality bounding a logarithm by 0.025 times the main term, again asserted without proof. Because δ(t) is the maximum over all α∈(0,1] and all integral t≥2, this is not a decorative gap: a failure at any parameter point would invalidate the stated bound. I also note a related logical gap in the convergence proof: the argument fixes α and produces a T(α), then concludes δ(t)→1. Since δ(t) is a supremum over α, uniform convergence is required, and the proof as written does not supply it. This is consistent with the reader's observation that the convergence is only shown pointwise in α. Other issues in the manuscript, such as the misstated threshold distribution property in Definition 3.2 and the apparent superscript error in Theorem 1, are real but clearly fixable typographical/inferential slips; they do not change the central concern. The correct fix for the main concern is to replace the informal 'verifications' with a rigorous computational certificate or analytic bound, and to give a uniform argument for δ(t)→1. Under that standard, the reader's CONDITIONAL verdict is the right one, and no change to the verdict is needed.","tokens_in":24883,"tokens_out":15264,"duration_ms":159856,"concrete_test":"Run a standalone interval-arithmetic verifier (e.g., Mathematica or Python with mpmath) over the domains in Appendix B.4: (1) for all t≥2 and α∈(0.045,1], check α·s2(α,t)/t≤4.75; (2) for all t≥2, α∈(0,0.045], γ≥1, τ≥3.47 with τω(γ,t)<1, check the log-bound inequality and the resulting s1 ratio; (3) for adversarial sequences α_t=1/t^c, c>0, compute the min-ratio and check it tends to 1 uniformly. If (1)–(2) pass with rigorous error bounds, the 4.75 constant is supported; if (3) fails for some sequence, δ(t)→1 as stated is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing issue is in the proof of Theorem 2 (Appendix B.4). The bound δ(t)≤4.75 is justified by statements like 'we can verify that whenever α>0.045, s2(α,t)≤4.75·t/α for all t≥2, as shown in Figure 5' and by an asserted log-inequality over α≤0.045, γ≥1, τ≥3.47. No rigorous proof or machine-checkable certificate is provided; a plot and a bare assertion are not verifiable evidence for an infinite parameter domain. Since δ(t) is defined as a maximum over α∈(0,1] and over all integral t≥2, one missed corner case breaks Theorem 2. In addition, the proof of δ(t)→1 fixes α and then chooses T(α); because δ(t) is a sup over α, this does not establish uniform convergence. These are correctness risks, not just presentation issues.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces (t, α)-undominated committees, where an outside candidate is rejected if at least a 1−α fraction of voters prefer at least t members of the committee to that candidate. The authors prove that such a committee of size O(t/α) always exists (Theorem 2), that the size bound is asymptotically tight as t→∞ with constant δ(t)→1, and that the t=1 case improves the known undominance ratio, yielding a 5-member Condorcet winning set (Theorem 1 and Corollary 3.1). The proofs use a Lindahl equilibrium with ordinal preferences (LEO) and a scaled variant (SLEO), combined with dependent rounding and an iterative budget-reduction algorithm. The lower bound (Theorem 3) is adapted from a construction of Charikar et al.","tokens_in":25046,"tokens_out":27470,"duration_ms":280638,"significance":"If the technical gaps identified below are repaired, the paper makes a solid contribution: it proposes a flexible and well-motivated generalization of Condorcet winning sets, gives existence and asymptotic tightness results with a promising market-equilibrium technique, and improves the best known bound for Condorcet winning committees from 6 to 5. The LEO existence theorem is reproved in Appendix A, so the reliance on Nguyen and Song (2024) is not circular. However, the paper currently contains a misstated theorem, an inconsistent definition, and an unverified numerical proof for the crucial constant 4.75 and the δ(t)→1 claim. No machine-checkable certificate or shipped code is provided for the numerical assertions.","major_comments":[{"comment":"The statement of Theorem 1 says a (β + (1−β)k)-undominated committee of size k exists, and the final line of the proof repeats the expression (1−β)k. The derivation, however, bounds the uncovered voters by (1−β)^k, and Table 1 numerically matches the exponential form (e.g., for k=2 the minimum of β+(1−β)^2 is 0.75, as listed). The linear form is load-bearing: with β+(1−β)k, the minimum over β∈[0,1] is 1 for k≥2, so Corollary 3.1 (a 5-member Condorcet winning set) would not follow. Please correct the statement and proof to use (1−β)^k throughout.","section":"Section 3, Theorem 1 and its proof"},{"comment":"Definition 3.2(2) states F(1−β)=1−ε and then claims this means Pr[X ≥ 1−ε] = β. This implication is false as written; the intended condition is F(1−ε)=1−β, which gives Pr[X ≥ 1−ε]=β when the CDF is continuous. The proof of Theorem 1 relies on the latter property ('when a voter's realized income is at least 1−ε ... this occurs with probability at least β'). The definition must be repaired, since as written it is internally inconsistent with the construction described in Figure 1.","section":"Definition 3.2(2)"},{"comment":"The proof of the omitted part of Theorem 2 consists of two 'we can verify' statements: one for α > 0.045 supported only by Figure 5, and one for α ≤ 0.045 asserting a log-inequality over the unbounded domain α∈(0,0.045], τ≥3.47, γ≥1, t≥2. No analytic proof, code, or machine-checkable certificate is provided. Since δ(t) is a maximum over α∈(0,1] and over all integral t≥2, a plot and a bare assertion are insufficient evidence for an infinite family of cases. This is a load-bearing step in the main theorem, so it must be replaced by a rigorous proof or a verifiable computational certificate.","section":"Appendix B.4, proof of δ(t) ≤ 4.75"},{"comment":"The asymptotic claim is proved by fixing α, choosing γ0 = 1+η/2 and B_t = ⌈(1+η)t/α⌉, and then finding T(α) such that ω(γ0,t) is small enough for t≥T. This establishes pointwise convergence of s2(α,t)/(t/α) to 1 for each fixed α. However, δ(t) is a supremum over α∈(0,1]; pointwise convergence does not imply sup_α of the ratio converges to 1 unless the convergence is uniform in α. A uniform argument is needed (for instance, via s1 with a suitable choice of τ depending on t), and the current proof does not supply one.","section":"Appendix B.4, proof of δ(t) → 1"},{"comment":"Proposition 4.1(3) states only the all-zero negative-correlation inequality: Pr[∧_{k∈W} ỹ_k = 0] ≤ Π_{k∈W}(1−y_k). The proof of Claim 4.1 applies a Chernoff bound to the sum Z = Σ_{a∈A+} ỹ_a, citing 'negative correlation' from this condition. As stated, the displayed inequality is insufficient for the usual Chernoff bound on the lower tail of Z; one also needs the complementary all-one inequality or an explicit statement that the distribution is negatively associated. Please state the full negative-correlation property (which is available in the cited dependent-rounding theorem) and show how the Chernoff bound follows.","section":"Proposition 4.1(3) and Claim 4.1"}],"minor_comments":[{"comment":"The equivalence 'E[X] ≤ β, that is, ∫_0^1 F(x)dx ≤ β' is incorrect: for X∈[0,1], E[X] = 1−∫_0^1 F(x)dx, so E[X]≤β is equivalent to ∫_0^1 F(x)dx ≥ 1−β. This should be corrected to avoid confusion in the construction of the threshold distribution.","section":"Definition 3.2(3)"},{"comment":"The pseudocode uses 't ← 0' as the loop variable, which conflicts with the input parameter t. The loop variable should be a different symbol, e.g., 'i ← 0'.","section":"Algorithm 1"},{"comment":"The phrase 'Given 1 ≤ t ≤ n' refers to the number of voters n, but t is the number of committee members used in the comparison and should be bounded by |C|, not n. Please rephrase, e.g., 'Given an integer t ≥ 1'.","section":"Definition 4.1"},{"comment":"The proof says 'there exists a committee C_ε of size δ(t)·t/α', but δ(t)·t/α need not be an integer. The intended statement is 'of size at most δ(t)·t/α', which is consistent with the floor in the theorem statement.","section":"Proof of Theorem 2"},{"comment":"The figures display values only for t ≤ 8, while the surrounding text makes claims for all integral t ≥ 2. Please clarify whether the plots are illustrative only and how the claimed uniform behavior for larger t is established.","section":"Appendix C, Figures 4 and 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal and the core ideas are promising. The main obstacles are the unverified numerical claims in Appendix B.4 and the pointwise-to-uniform gap in the δ(t)→1 proof; these affect the central theorem and should be fixed before publication. The typos in Theorem 1 and Definition 3.2 are easy to correct and do not indicate a deeper flaw. The self-citation of Nguyen and Song (2024) is not circular because the needed LEO existence theorem is reproved in Appendix A."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things matter about this paper. First, it genuinely improves the best-known bound for Condorcet winning sets from 6 to 5, and it introduces a (t, α)-undominated set generalization that is new and nicely interpolates between existing notions. Second, as written, the paper has two small typos and one real gap: the 4.75 constant in Theorem 2 is justified by “we can verify” and plots, not by a proof or certificate.\n\nThe good parts are substantial. The LEO-based proof for Theorem 1 is clean; the threshold distribution trick works, and the expectation argument for the uncovered voters plus price bound is sound. The lower bound construction in Theorem 3 is a natural adaptation of Charikar et al. and appears correct. The iterative algorithm for small α is a good idea, and the dependent rounding step is standard. The fixed-point existence proofs in Appendices A and B.2 are self-contained and rest on Kakutani; there’s no circularity, and the self-citation to Nguyen and Song is not a problem because the needed theorem is reproven.\n\nNow the soft spots. Definition 3.2(2) as printed, F(1−β)=1−ε, cannot be right if the intended interpretation is Pr[X≥1−ε]=β. The correct condition is F(1−ε)=1−β. Similarly, Theorem 1 states a (β+(1−β)k)-undominated committee, but the proof and Table 1 use (β+(1−β)^k). For k=2 the printed version gives 1 at best, not 0.75. Both are easy fixes, but they are load-bearing for reading the paper.\n\nMore serious: Appendix B.4. The claim δ(t)≤4.75 rests on two “we can verify” statements: one over α>0.045 shown by Figure 5, and a log-inequality over α≤0.045 with τ≥3.47. A plot and an assertion do not cover an infinite domain. This needs either an analytical proof or a machine-checkable certificate. And the proof of δ(t)→1 fixes α and chooses T(α); because δ(t) is a sup over α, that only establishes pointwise convergence, not the claimed uniform statement. The stress-test note is right on both counts.\n\nThese are fixable, but they are correctness risks, not style nits. The paper is worth a serious referee: the new framework and the 5-candidate result are real contributions to computational social choice. Send it to review with the expectation of a careful revision. I’d cite the 5-candidate bound once the typos are fixed and the constant is rigorous.","headline":"Real new results—5-candidate Condorcet winning set and the (t,α)-undominated framework—but the 4.75 constant and δ(t)→1 are not yet supported, and a few typos need fixing.","tokens_in":25615,"tokens_out":4325,"would_cite":true,"duration_ms":43277,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","91B26"],"pacs":[],"model":"deepseek-v4-flash","headline":"Any election admits a $(t,\\alpha)$-undominated committee of $O(t/\\alpha)$ candidates, and five candidates always form a Condorcet-winning set.","keywords":["Condorcet winning set","undominated committee","ordinal preferences","Lindahl equilibrium","committee selection","social choice","quantile comparison","majority voting"],"falsifier":"Run a rigorous interval-arithmetic evaluation of the expressions $s_1(\\alpha,t)$ and $s_2(\\alpha,t)$ from the proof of Theorem 2 on a dense grid with $\\alpha\\le 0.045$, $\\tau\\ge 3.47$, and $t\\ge 2$; any point where the required committee size exceeds $4.75\\cdot t/\\alpha$ would refute the claimed constant. Independently, an explicit election in which every five-candidate set is beaten by some outsider in pairwise majority would refute the claim that five candidates always suffice.","tokens_in":24604,"feed_emoji":"🗳️","tokens_out":15206,"duration_ms":147779,"temperature":0.7,"pith_summary":"This paper proves that majority rule, which famously fails to produce a single winner, can always be rescued by a small committee once voters compare an outsider against several committee members rather than just the best one. The authors define a $(t,\\alpha)$-undominated committee: a set of at least $t$ candidates such that, for every alternative outside the set, no more than an $\\alpha$-fraction of voters rank that alternative above all but $t-1$ members of the set. Their central results are that such a committee of size $O(t/\\alpha)$ always exists, that this size is asymptotically tight (approaching $t/\\alpha$ as $t$ grows), and that the special case $t=1$, $\\alpha=1/2$ yields a five-candidate set that no outside alternative beats by a pairwise majority, improving the previous best of six. The significance is practical as well as mathematical: the $t$ parameter turns committee membership into a quantile comparison, so a rejected alternative must lose to the committee's top tier, not just to its single best member.","feed_headline":"Five candidates suffice to win any voter majority","feed_subtitle":"The new bound of five beats the previous six and scales to quantile-style committee comparisons.","key_machinery":"The machinery is a market equilibrium adapted to ordinal preferences. In a Lindahl equilibrium with ordinal preferences (LEO), each voter draws a random income from a continuous distribution, faces personalized candidate prices, and demands her favorite affordable candidate, while a revenue-maximizing producer commits to a common allocation of total budget $B$; market clearing lets each voter's demand lottery sit inside that allocation. For $t>1$, the paper scales the equilibrium (calling it s-SLEO) so that each voter's consumption spreads over roughly $\\gamma t$ candidates, which lets the proof control whether a voter has $t$ good committee members; a dependent-rounding procedure with negative correlation then converts the fractional allocation into a randomized committee of size $\\lceil B\\rceil$ or $\\lfloor B\\rfloor$, and an iterative algorithm re-runs the equilibrium on the voters left uncovered, with budgets shrinking geometrically. In the $t=1$ case, the crucial input is a threshold income distribution, a smoothed Bernoulli distribution that places mass $\\beta$ at the top income, which ensures that any candidate above a voter's price threshold carries price above $1-\\varepsilon$ and yields the bound $\\beta+(1-\\beta)k$.","core_discovery":"The paper's central claim is that undominated committees exist in constant size even when the comparison standard is raised from the committee's best member to its $t$-th best. Formally, for every $t\\ge 2$ and $\\alpha\\in(0,1]$ there is a $(t,\\alpha)$-undominated committee of at most $\\delta(t)\\cdot t/\\alpha$ candidates, with $1<\\delta(t)\\le 4.75$ and $\\delta(t)\\to 1$ as $t\\to\\infty$, and a lower-bound construction shows that at least $(t+1)/\\alpha-1$ candidates are sometimes necessary, so $t/\\alpha$ is asymptotically optimal. For $t=1$, the paper proves that for every integer $k$ and every $\\beta\\in[0,1]$ there is a committee of size $k$ that is $(\\beta+(1-\\beta)k)$-undominated; choosing $k=5$ and $\\beta\\approx 0.465$ gives a five-candidate Condorcet-winning committee, improving the previous universal bound of six. The authors interpret this as a quantile justification for exclusion: an outside alternative is rejected only if no more than an $\\alpha$-fraction of voters rank it above all but $t-1$ members of the committee.","pith_inferences":["Editorial inference: the same scaled-equilibrium machinery could be aimed at $\\alpha$-dominating sets, where an outside candidate must lose to a single committee member; the incomparability noted in the paper leaves room for a transfer of the income-spreading idea.","Editorial inference: replacing the plot-based verification behind $\\delta(t)\\le 4.75$ with certified interval arithmetic would either tighten the constant for small $t$ or reveal a gap in the current numerical check.","Editorial inference: the five-candidate corollary invites a targeted search over preference profiles for an election with no Condorcet-winning set of size four, which would be the next step toward closing the gap to the lower bound of three.","Editorial inference: real review or funding data could be audited with the $(t,\\alpha)$ test, where a rejected item is defensible only if fewer than an $\\alpha$-fraction of evaluators rank it above $t$ accepted items, giving a direct check of whether the $O(t/\\alpha)$ constants are practical."],"forward_implications":["Every election has a Condorcet-winning committee of five candidates: a five-candidate set that no outside alternative beats by pairwise majority, improving the previous universal bound of six; whether four can fail remains open because the known lower bound is three.","For any fixed $t$ and any $\\alpha$, a $(t,\\alpha)$-undominated committee of $O(t/\\alpha)$ candidates always exists, and this order is tight because some elections force any such committee to have size at least $(t+1)/\\alpha-1$.","As $t$ grows, the minimal committee size approaches $t/\\alpha$, making the guarantee asymptotically optimal for every $\\alpha$.","With committee size $2t-1$ and $\\alpha=1/2$, the condition becomes a median-style test: an outsider is excluded when a majority of voters prefer the committee's median member to it.","The $t=1$ theorem improves the known undominance ratio for every committee size $k$, not only at the Condorcet point."],"supporting_citations":[{"why":"Provides the previous bound of six for Condorcet-winning sets and the $\\alpha$-undominated bounds that Theorem 1 improves, plus the lower-bound election construction adapted in Theorem 3.","marker":"Charikar et al. (2025a)"},{"why":"Introduces LEO and proves its existence; the paper adapts this equilibrium for both the $t=1$ and $t\\ge 2$ constructions.","marker":"Nguyen and Song (2024)"},{"why":"Defines Condorcet winning sets and $\\alpha$-undominated sets, establishing the earlier logarithmic upper bound that this paper improves to a constant.","marker":"Elkind et al. (2015)"},{"why":"Supplies the dependent-rounding procedure with negative correlation used to turn the fractional SLEO allocation into a committee of the desired size.","marker":"Gandhi et al. (2006)"},{"why":"Provides the iterative committee-selection framework that the paper combines with SLEO to handle small $\\alpha$.","marker":"Jiang et al. (2020)"},{"why":"Fixed-point theorem used to prove existence of a LEO and, by the same argument, of an s-SLEO.","marker":"Kakutani (1941)"},{"why":"Source of the Chernoff bound used to control the probability that a voter ends up with fewer than $t$ good candidates in the rounded committee.","marker":"Mitzenmacher and Upfal (2017)"}],"fun_headline_variants":["Five candidates tame any majority: new bound","A five-member committee always beats the crowd","Undominated committees shrink to five: proof","From six to five: tighter Condorcet committee bound","Quantile voting: five picks can still win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the numerical inequality checks behind the constant $4.75$ in Appendix B.4 cover the full parameter range correctly, since if those plots hide a failed case the stated bound would be unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Five candidates tame any majority: new bound","A five-member committee always beats the crowd","Undominated committees shrink to five: proof","From six to five: tighter Condorcet committee bound","Quantile voting: five picks can still win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000564,"raw_usage":{"total_tokens":2781,"prompt_tokens":1155,"completion_tokens":1626,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":771,"completion_tokens_details":{"reasoning_tokens":1556}},"tokens_in":771,"tokens_out":1626,"duration_ms":12905,"temperature":1.0,"reasoning_tokens":1556,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:11:19.902858+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a rigorous interval-arithmetic evaluation of the expressions $s_1(\\alpha,t)$ and $s_2(\\alpha,t)$ from the proof of Theorem 2 on a dense grid with $\\alpha\\le 0.045$, $\\tau\\ge 3.47$, and $t\\ge 2$; any point where the required committee size exceeds $4.75\\cdot t/\\alpha$ would refute the claimed constant. Independently, an explicit election in which every five-candidate set is beaten by some outsider in pairwise majority would refute the claim that five candidates always suffice.","supporting_citations":[],"review_version":1}