Pessimal Elections for Approximately Dominating Sets

Kangning Wang; Moses Charikar; Prasanna Ramakrishnan

Pessimal Elections for Approximately Dominating Sets

T0 review · 0 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every ε>0, some elections force every (1/2−ε)-dominating committee to have size Ω(1/ε²), matching the known upper bound up to a constant.

desk verdict 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. read the letter →

arxiv 2608.06872 v1 pith:TUFYBIBP submitted 2026-08-07 cs.GT cs.DMmath.CO

Moses Charikar , Prasanna Ramakrishnan , Kangning Wang This is my paper · ORCID

classification cs.GTcs.DMmath.CO MSC 91B1291B14

keywords approximatelydominatingsetscommitteeselectionCondorcetparadoxmajorityfunctionBooleananalysislowerboundsocialchoicetheoryelections

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

On 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.

Who 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.

Referee Report

0 major / 3 minor

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_ℓ].

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.

minor comments (3)

[Section 4] 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 4] 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.
[Abstract and Section 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower-bound construction is explicit and self-contained.

full rationale

The central claim is a lower bound proved by an explicit election construction. The load-bearing Section 4 comparison formula is derived algebraically from the decision-tree definition of voter preferences, not assumed; its simplification uses only E[x_j]=E[x_l]=0, independence of a majority junta from outside coordinates, and the standard correlation E[Maj_A(x)x_j] ~ sqrt(2/(pi k)), which the paper sketches from the central binomial coefficient. None of the cited prior work is used to assert the target result: the authors' earlier papers are invoked only for the matching upper bound and for the open-problem framing, while Lemma 1 is attributed to Alon et al. with a proof included for completeness. The only questionable textual passage is the repeated 'without loss of generality' parity assumption in Sections 3 and 4, which glosses over odd/even k, but this is a patchable presentation gap rather than a circular step, since the even construction can be applied to k+1 and the asymptotics are unchanged. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

There are no fitted parameters, no empirical data, and no invented physical or mathematical entities. The construction uses only standard combinatorial objects (Boolean hypercube, majority functions, strict preference orders) and standard analytic estimates. The two proofs are self-contained apart from textbook results in probability and combinatorics.

assumptions (4)

standard math Stirling's approximation for central binomial coefficients
Used to estimate binom(k,k/2)/2^k ~ sqrt(2/(πk)), which sets the size of δ_k in both proofs.
standard math Independence of coordinates under the uniform measure on the Boolean hypercube
The voter construction uses uniform independent ±1 coordinates so that E[x_i x_j] = 0 and E[Maj_A x_j] has the stated closed form.
standard math Existence of a coordinate j outside the union of the winners' coordinate sets
The paper requires N > (k+1)^2 while the union of k sets of size k+1 has size at most k(k+1), so a free coordinate exists by the pigeonhole principle.
domain assumption The election model with strict linear preference orders
The result is framed in the standard social choice model; the construction produces strict orders via the three-check decision tree.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Pessimal Elections for Approximately Dominating Sets." pith.science (2026). https://pith.science/paper/TUFYBIBP

@misc{pith2026260806872,
  author       = {Pith},
  title        = {Pith review of: Pessimal Elections for Approximately Dominating Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TUFYBIBP}},
  note         = {Machine review of arXiv:2608.06872}
}

abstract

Condorcet's paradox is a foundational result in social choice theory, showing that no matter which candidate wins an election, a majority of voters may prefer some losing candidate. Worse still, even if the election can choose a committee of $k$ winners, some loser may beat every winner in a majority vote. Recent work showed that this obstruction can be sidestepped by relaxing the majority threshold. For all $\varepsilon > 0$, any election can select a committee of $O(1/\varepsilon^2)$ winners such that no loser is preferred to every winner by $\frac12 + \varepsilon$ fraction of voters. We present a simple construction, found by GPT-5.6 Sol Ultra, which proves that this result is tight up to a constant factor.

Figures

Figures reproduced from arXiv: 2608.06872 by the authors.

**Figure 1.** For a fixed x ∈ Ω, the first two checks sort each candidate (A, j) into one of four blocks. The block labeled (s, t) contains the candidates satisfying (xj , MajA(x)) = (s, t). Each branch is labeled by the value of the test at its parent, and the blocks are ordered from less to more preferred. they land in the same block.4 Since these three cases correspond directly to the voters vx and ux sharing the preference (A… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

[1]

Kierstead, Alexandr V

Noga Alon, Graham Brightwell, Hal A. Kierstead, Alexandr V. Kostochka, and Peter Winkler. Dominating sets in k -majority tournaments. Journal of Combinatorial Theory, Series B, 96 0 (3): 0 374--387, 2006

work page 2006
[2]

A dense neighborhood lemma: Applications of partial concept classes to domination and chromatic number

Romain Bourneuf, Pierre Charbit, and St \' e phan Thomass \' e . A dense neighborhood lemma: Applications of partial concept classes to domination and chromatic number. In Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 1--37. IEEE , 2025. doi:10.1109/FOCS63196.2025.00007. URL https://doi.org/10.1109/FOCS631...

arXiv 2025
[3]

Rolling the dice: Recent results in probabilistic social choice

Felix Brandt. Rolling the dice: Recent results in probabilistic social choice. In Trends in computational social choice, pages 3--26. AI Access, Lulu, 2017

work page 2017
[4]

Six candidates suffice to win a voter majority

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. Six candidates suffice to win a voter majority. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages 1590--1601. ACM , 2025. doi:10.1145/3717823.3718235. URL https://doi.org/10.1145/3717823.3718235

arXiv 2025
[5]

Approximately dominating sets in elections

Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang. Approximately dominating sets in elections. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1747--1760. SIAM , 2026 a . doi:10.1137/1.9781611978971.62. URL https://doi.org/10.1137/1.9781611978971.62

work page doi:10.1137/1.9781611978971.62 2026
[6]

A game theory toolkit for voting rules

Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang. A game theory toolkit for voting rules. ACM SIGecom Exchanges, 24 0 (1): 0 77--98, June 2026 b

work page 2026
[7]

Choosing collectively optimal sets of alternatives based on the Condorcet criterion

Edith Elkind, J \'e r \^o me Lang, and Abdallah Saffidine. Choosing collectively optimal sets of alternatives based on the Condorcet criterion. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI). Citeseer, 2011

work page 2011
[8]

Condorcet winning sets

Edith Elkind, J \'e r \^o me Lang, and Abdallah Saffidine. Condorcet winning sets. Social Choice and Welfare, 44 0 (3): 0 493--517, 2015

work page 2015

Show all 14 references

[9]

On a problem in graph theory

Paul Erd o s. On a problem in graph theory. The Mathematical Gazette, 47 0 (361): 0 220--223, 1963

1963
[10]

Approximately stable committee selection

Zhihao Jiang, Kamesh Munagala, and Kangning Wang. Approximately stable committee selection. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 463--472, New York, 2020. ACM

2020
[11]

Winning in the limit: Average-case committee selection with many candidates

Yifan Lin, Shenyu Qin, Kangning Wang, and Lirong Xia. Winning in the limit: Average-case committee selection with many candidates. In Proceedings of the 27th ACM Conference on Economics and Computation (EC) , 2026

2026
[12]

McGarvey

David C. McGarvey. A theorem on the construction of voting paradoxes. Econometrica: Journal of the Econometric Society, pages 608--610, 1953

1953
[13]

Analysis of boolean functions

Ryan O'Donnell. Analysis of boolean functions. CoRR, abs/2105.10386, 2021. URL https://arxiv.org/abs/2105.10386

2021 arXiv
[14]

A few good choices

Haoyu Song, Th \` a nh Nguyen, and Young - San Lin. A few good choices. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4861--4874. SIAM , 2026. doi:10.1137/1.9781611978971.175. URL https://doi.org/10.1137/1.9781611978971.175

2026 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Kierstead, Alexandr V

Noga Alon, Graham Brightwell, Hal A. Kierstead, Alexandr V. Kostochka, and Peter Winkler. Dominating sets in k -majority tournaments. Journal of Combinatorial Theory, Series B, 96 0 (3): 0 374--387, 2006

work page 2006

[2] [2]

A dense neighborhood lemma: Applications of partial concept classes to domination and chromatic number

Romain Bourneuf, Pierre Charbit, and St \' e phan Thomass \' e . A dense neighborhood lemma: Applications of partial concept classes to domination and chromatic number. In Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 1--37. IEEE , 2025. doi:10.1109/FOCS63196.2025.00007. URL https://doi.org/10.1109/FOCS631...

arXiv 2025

[3] [3]

Rolling the dice: Recent results in probabilistic social choice

Felix Brandt. Rolling the dice: Recent results in probabilistic social choice. In Trends in computational social choice, pages 3--26. AI Access, Lulu, 2017

work page 2017

[4] [4]

Six candidates suffice to win a voter majority

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. Six candidates suffice to win a voter majority. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages 1590--1601. ACM , 2025. doi:10.1145/3717823.3718235. URL https://doi.org/10.1145/3717823.3718235

arXiv 2025

[5] [5]

Approximately dominating sets in elections

Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang. Approximately dominating sets in elections. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1747--1760. SIAM , 2026 a . doi:10.1137/1.9781611978971.62. URL https://doi.org/10.1137/1.9781611978971.62

work page doi:10.1137/1.9781611978971.62 2026

[6] [6]

A game theory toolkit for voting rules

Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang. A game theory toolkit for voting rules. ACM SIGecom Exchanges, 24 0 (1): 0 77--98, June 2026 b

work page 2026

[7] [7]

Choosing collectively optimal sets of alternatives based on the Condorcet criterion

Edith Elkind, J \'e r \^o me Lang, and Abdallah Saffidine. Choosing collectively optimal sets of alternatives based on the Condorcet criterion. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI). Citeseer, 2011

work page 2011

[8] [8]

Condorcet winning sets

Edith Elkind, J \'e r \^o me Lang, and Abdallah Saffidine. Condorcet winning sets. Social Choice and Welfare, 44 0 (3): 0 493--517, 2015

work page 2015