{"id":"be20af03-f120-4d86-b33e-034f317596da","arxiv_id":"2608.06872","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every ε>0 there exists an election in which every approximately dominating committee has size at least about 1/(32π ε^2), matching the known upper bound up to a constant factor.","lead":"This paper constructs elections in which every small committee of winners fails to approximately dominate some losing candidate, proving a lower bound of about 1/ε^2 on committee size. The construction uses Boolean functions as election gadgets and matches the known O(1/ε^2) upper bound up to a constant factor, settling the asymptotic question.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the Section 4 comparison identity checks out and the parity 'WLOG' gap is patchable.","rationale":"I followed both proofs from the construction to the reparameterization. The first proof's correlation computation for majority is standard and correctly derives E[Maj_L x_i]=C(k−1,(k−1)/2)/2^{k−1}; the second proof's streamlined version is cleaner and the comparison formula is exact. The choice of j outside the union of supports and A containing all loser coordinates uses N>(k+1)^2 correctly. The conversion from δ_k ~ 1/(4√(2πk)) to the ε-lower bound 1/(32πε²) is arithmetic: setting k ≈ 1/(32πε²) makes δ_k ~ ε, and choosing k slightly below the threshold makes the inequality strict. The parity reductions are hand-waved but valid by padding; for odd k in Section 4, applying the even-k result with K=k+1 gives margin δ_{k+1} ~ δ_k, and for even k in Section 3 the analogous K=k+1 argument works. No circularity, no hidden parameter, and no contradiction with the upper bound. The paper's central theorem is sound; the verdict should remain ACCEPT.","tokens_in":7482,"tokens_out":18915,"duration_ms":160750,"concrete_test":"Brute-force verify the Section 4 construction for k=2, N=5: list all candidates (A,j), form the 2|Ω|=64 voters, compute every pairwise margin, then enumerate all size-2 committees S and check that for each S the constructed loser (A,j) with A containing the two ℓ_i and j outside both B_i achieves margin 1/2+ρ_2/8 = 1/2+1/16 against every member. If any margin deviates from the claimed formula, the central identity is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the central claim that for every k there is an election in which every size-k committee fails to approximately dominate. The load-bearing step is the Section 4 comparison formula: 1/n |(A,j)≻(B,ℓ)| = 1/2 + ρ_k/8 (1[ℓ∈A] − 1[j∈B]). I re-derived it from the decision tree: the expression (x_j−x_ℓ)/2 + ((x_j+x_ℓ)/2)(Maj_A−Maj_B)/2 is exactly +1, −1, or 0 according to whether (A,j) is preferred, dispreferred, or tied by both voters in a household; averaging gives the formula. The subsequent simplification only uses E[x_j]=0, E[x_ℓ]=0, E[Maj_A x_j]=E[Maj_B x_ℓ]=ρ_k, and independence when the relevant coordinate is outside the junta's support; all are correct. The conclusion then follows by choosing A to contain all ℓ_i and j outside every B_i, which is possible because N>(k+1)^2. The only genuine gap is the 'assume WLOG k is even' phrase in Section 4 (and analogously 'k odd' in Section 3): for odd k, the even-k theorem applied to K=k+1 and padding any size-k committee to size K gives the same asymptotic δ_k. This is a presentation issue, not a correctness issue. I find no load-bearing concern.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses the asymptotic size of (1/2−ε)-dominating sets in elections. Prior work by the authors gave an upper bound of (1+o(1)) π/(8ε^2) and lower bounds of Ω(1/ε log(1/ε)) and Ω(1/ε), with a later average-case lower bound of 1/(2ε). The paper constructs, for every k, an election in which every committee of k candidates has a losing candidate who beats all k winners by margin 1/2+δ_k with δ_k ∼ 1/(4√(2πk)). This yields a lower bound of (1+o(1)) 1/(32π ε^2) on the size of approximate dominating sets, matching the upper bound up to a constant. Two proofs are given: a Boolean-function construction using majority correlation, and a streamlined direct construction where voters are defined by a three-check decision tree. The central comparison identity in Section 4 gives pairwise margins exactly in terms of E[Maj_A x_ℓ].","tokens_in":7683,"tokens_out":16359,"duration_ms":133680,"significance":"The result resolves the central open problem stated as Conjecture 3.14 of the authors' survey. The construction is explicit and has no fitted parameters; the lower-bound instance is a concrete election whose behavior is exactly governed by a simple correlation identity. The proofs are self-contained and readily checkable, relying only on standard facts about Rademacher variables and the majority function. If correct, the paper closes the constant-factor gap between upper and lower bounds and demonstrates an elegant use of Boolean function analysis in election construction.","major_comments":[],"minor_comments":[{"comment":"The phrase 'Assume without loss of generality that k is even' is not justified as written, because for odd k the majority function over k+1 coordinates has ties. The odd-k case can be recovered by applying the even-k construction with K=k+1 and padding any size-k committee to size K, but this argument is not stated. Please add an explicit sentence, and similarly in Section 3 for the 'WLOG k is odd' claim.","section":"Section 4"},{"comment":"The derivation of the comparison formula says that the algebraic expression 'traces the paths' and evaluates to 1, −1, or 0. This is correct but terse; a brief verification of the cases x_j≠x_ℓ and x_j=x_ℓ would make the proof easier to check.","section":"Section 4"},{"comment":"The credit line crediting the proof to GPT-5.6 Sol Ultra in the abstract is unconventional. Consider confining this attribution to the 'Statement on AI use' section, unless the journal's policy explicitly encourages abstract-level disclosure.","section":"Abstract and Section 1"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically sound. The only genuine gap I found is the parity justification in Section 4, which is minor and easily fixed by the padding argument. I have no concerns about circularity or hidden assumptions. The AI-use statement is transparent; the editor may wish to confirm that the abstract's credit line is acceptable under the journal's policy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper settles the committee-size question for approximate majority domination: for every ε, there is an election where every (1/2−ε)-dominating set has size Ω(1/ε^2), matching the O(1/ε^2) upper bound from the authors' earlier work. That is the headline, and it is a real result, not a marginal one. It also resolves the open conjecture from their survey, and the construction—building elections directly from Boolean functions and majority correlation—is a genuine novelty in this area.\n\nWhat the paper does well: both proofs are self-contained and surprisingly clean. The second proof is the more streamlined one, and I re-derived the central comparison identity from the decision tree. It checks out. The expectation calculations use only independence of Rademacher coordinates, linearity, and the standard majority correlation with a single coordinate. No fitted parameters, no hidden appeals to the theorem being proved. The lower bound is explicit and asymptotic, with the constant stated. The paper also does a good job contextualizing prior work: the old Alon et al. bound, the linear bound from their own SODA paper, and the independent 1/(2ε) bound from Lin et al. are all cited and used correctly.\n\nThe soft spots are minor. The 'without loss of generality k is even' in Section 4 is too glib; for odd k, the construction needs a small adjustment (use k+1 and pad the committee, or fall back on the first proof which handles odd k directly). This is a presentation gap, not a correctness gap—the theorem statement covers all k, and the fix is obvious. The first proof similarly handwaves the even-k tie-breaking in majority, but again it is patchable. Both issues should be cleaned up in revision, but neither threatens the result.\n\nOn the AI-generation disclosure: the authors state that GPT-5.6 Sol Ultra generated the original proofs and that they subsequently wrote the exposition and take full responsibility. That is an honest and appropriately cautious way to handle it, and it does not affect the mathematical assessment. The citation pattern is healthy—self-citations to their own upper bound and survey are appropriate since those are the results being matched and the conjecture being resolved.\n\nWho is this for? Anyone working in computational social choice or on majority domination in elections. It is a tight result on a natural problem, with proofs short enough to teach. I would send it to a serious referee. My own verdict is accept with minor revisions.","headline":"Clean, self-contained lower bound matching the known upper bound for approximate majority domination; the quadratic gap is closed and the paper deserves a serious referee.","tokens_in":8311,"tokens_out":1149,"would_cite":true,"duration_ms":11391,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every ε>0, some elections force every (1/2−ε)-dominating committee to have size Ω(1/ε²), matching the known upper bound up to a constant.","keywords":["approximately dominating sets","committee selection","Condorcet paradox","majority function","Boolean function analysis","lower bound","social choice theory","elections"],"falsifier":"Build the Section 4 election for a small even k, say k=2 with N=10, and compute for every pair of candidates the exact fraction of the 2^N voters preferring one to the other. If any pairwise margin deviates from ρ_k/8 times the indicator expression, the construction fails. Alternatively, enumerate all committees of k candidates and check that each has a loser preferred to every winner by the claimed margin; if some committee escapes, the lower bound is false.","tokens_in":7234,"feed_emoji":"🗳️","tokens_out":6573,"duration_ms":54939,"temperature":0.7,"pith_summary":"This paper proves that the quadratic bound on the size of approximately dominating sets in elections is tight. It constructs, for every k, an election with the property that any committee of k winners has a losing candidate who beats every winner by a margin of about 1/(4√(2πk)). Reparameterizing, any committee that dominates all losers at threshold 1/2−ε must have at least (1+o(1))/(32πε²) winners. The result resolves the open problem left by the authors' earlier upper bound and shows the O(1/ε²) guarantee cannot be improved in the worst case.","feed_headline":"Committee sizes must grow like 1/ε² in the worst case","feed_subtitle":"New construction matches the known upper bound up to a constant, settling the size of approximately dominating sets.","key_machinery":"Candidates are pairs (A,j), where A is a set of k+1 coordinates of the Boolean hypercube {±1}^N and j is a designated coordinate in A. For each point x, two voters order candidates by three checks: prefer x_j=1 over x_j=−1; if tied, prefer x_j = Maj_A(x); if still tied, follow a fixed order or its reverse. The load-bearing identity is $$1/n |(A,j)≻(B,ℓ)| = 1/2 + (ρ_k/8)(1[ℓ∈A] - 1[j∈B]),$$ with ρ_k=E[Maj_A(x)x_j]∼√(2/(πk)). This identity turns domination into correlation: a loser (A,j) chosen with A containing all ℓ_i and j outside all B_i beats every winner by ρ_k/8, because each ℓ_i is a variable of Maj_A while no B_i sees j.","core_discovery":"The central claim is Theorem 2: for every ε>0 there is an election in which every (1/2−ε)-dominating set has size at least (1+o(1)) 1/(32πε²). Equivalently, for every k there is an election in which, for every committee S of k candidates, some candidate outside S is preferred to every member of S by at least 1/2 + (1+o(1))/(4√(2πk)) of the voters. Since earlier work gave an upper bound of (1+o(1))π/(8ε²), the committee-size problem is now determined up to a constant factor. The paper also notes this makes the support-size bound for approximate maximal lotteries optimal up to a constant.","pith_inferences":["The construction suggests a general reduction: to force large committees in any election-like setting, it suffices to design a balanced Boolean function with prescribed correlations to a family of coordinate sets, so the same approach may yield lower bounds for other committee-selection or tournament problems.","The use of majority functions as the source of correlation is likely not optimal for the constant factor; choosing a different balanced function with higher total influence could improve the leading constant beyond 1/(32π), though the quadratic order in 1/ε would remain.","If the same construction is run with the threshold relaxed to 1/2−ε for ε depending on k, it shows the hardness is not an artifact of the proof: the quadratic lower bound is realized by an explicit, efficiently describable election rather than by a random construction."],"forward_implications":["The worst-case size of a (1/2−ε)-dominating set is now known up to a constant: it is Θ(1/ε²).","Approximate maximal lotteries, which are stronger objects, also require worst-case support Ω(1/ε²), so the previous support-size upper bound is tight up to a constant factor.","The lower bound holds even for elections with a particular, explicit structure: 2^N voters indexed by the Boolean hypercube, and candidates indexed by (k+1)-coordinate sets with a designated coordinate.","The open problem highlighted in the authors' survey, Conjecture 3.14, is resolved in the sense that the optimal asymptotic dependence on ε is now settled."],"supporting_citations":[{"why":"Supplies the set-system-to-election reduction (Lemma 1) and the template construction whose parameters the new proof modifies.","marker":"Alon et al. (2006)"},{"why":"Establishes the O(1/ε²) upper bound and poses the tightness question; the paper's lower bound matches it up to a constant.","marker":"Charikar, Ramakrishnan, and Wang, 2026a"},{"why":"Provides an independent constant-factor upper bound that the new lower bound must match and does match.","marker":"Bourneuf, Charbit, and Thomassé, 2025"},{"why":"Gives the previous best lower bound of 1/(2ε) from random elections, which the new construction improves to 1/ε².","marker":"Lin, Qin, Wang, and Xia, 2026"},{"why":"Provides the majority-function correlation identity and the optimality of majority used to set the margin ρ_k.","marker":"O’Donnell, 2021"}],"fun_headline_variants":["Election committee size: tight bound found","Worst-case elections force committee size Θ(1/ε²)","Committee size lower bound matches upper","Approximate dominating sets: constant-factor optimal size","GPT-5.6 construction settles committee size bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the comparison formula for the constructed election holds exactly as stated; if the three-check voter construction produced pairwise margins that differed from 1/2 + (ρ_k/8)(1[ℓ∈A] − 1[j∈B]) by even a constant factor, the Ω(1/ε²) lower bound would no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Election committee size: tight bound found","Worst-case elections force committee size Θ(1/ε²)","Committee size lower bound matches upper","Approximate dominating sets: constant-factor optimal size","GPT-5.6 construction settles committee size bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00135,"raw_usage":{"total_tokens":5422,"prompt_tokens":826,"completion_tokens":4596,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":442,"completion_tokens_details":{"reasoning_tokens":4524}},"tokens_in":442,"tokens_out":4596,"duration_ms":31361,"temperature":1.0,"reasoning_tokens":4524,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:29:35.115325+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the Section 4 election for a small even k, say k=2 with N=10, and compute for every pair of candidates the exact fraction of the 2^N voters preferring one to the other. If any pairwise margin deviates from ρ_k/8 times the indicator expression, the construction fails. Alternatively, enumerate all committees of k candidates and check that each has a loser preferred to every winner by the claimed margin; if some committee escapes, the lower bound is false.","supporting_citations":[{"cited_title":"Kierstead, Alexandr V","cited_arxiv_id":null,"evidence_quote":"Supplies the set-system-to-election reduction (Lemma 1) and the template construction whose parameters the new proof modifies."}],"review_version":2}