Pith. sign in

REVIEW 5 major objections 5 minor 14 references

A few good choices

T0 review · 5 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read Any election admits a $(t,\alpha)$-undominated committee of $O(t/\alpha)$ candidates, and five candidates always form a Condorcet-winning set.

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

arxiv 2506.22133 v2 pith:YB62SIQY submitted 2025-06-27 cs.GT math.CO

classification cs.GTmath.CO MSC 91B1291B1491B26
keywords CondorcetwinningsetundominatedcommitteeordinalpreferencesLindahlequilibriumselectionsocialchoicequantilecomparisonmajorityvoting
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 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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

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.

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 (5)
  1. [Section 3, Theorem 1 and its proof] 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.
  2. [Definition 3.2(2)] 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.
  3. [Appendix B.4, proof of δ(t) ≤ 4.75] 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.
  4. [Appendix B.4, proof of δ(t) → 1] 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.
  5. [Proposition 4.1(3) and Claim 4.1] 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.
minor comments (5)
  1. [Definition 3.2(3)] 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.
  2. [Algorithm 1] 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'.
  3. [Definition 4.1] 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'.
  4. [Proof of Theorem 2] 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.
  5. [Appendix C, Figures 4 and 5] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims are derived from self-contained existence proofs, and the Nguyen–Song self-citation is not load-bearing.

full rationale

The paper's central machinery, LEO and s-SLEO, is attributed to Nguyen and Song (2024), but the existence theorems are reproven in the appendices using Kakutani's fixed-point theorem and the Maximum Theorem (Appendix A for Theorem 4; Appendix B.2 for Theorem 5). Thus the self-citation is not the argument's foundation. Theorem 1 is derived within the paper from Claim 3.1, Lemma 3.1, and a probabilistic sampling argument with no fitted parameters. Theorem 2's constant δ(t) is defined by explicit optimization formulas s1 and s2, and the bound δ(t) ≤ 4.75 is supported by stated inequalities and numerical plots in Appendix B.4; those checks may be a rigor concern, but they are not circular because they do not assume the theorem's conclusion. Theorem 3's lower bound is an independent explicit construction adapted from prior work and proved in Appendix B.1. No step defines a target quantity in terms of itself, no fitted input is renamed as a prediction, and no load-bearing uniqueness claim is imported solely from the authors' prior work. The proof chain is self-contained against external benchmarks, so the honest finding is no circularity.

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

No new physical or ontological entities are introduced. The only novel constructs are mathematical definitions ((t, alpha)-undominated sets, SLEO) and proof parameters beta, gamma, tau, epsilon, none of which are fitted to empirical data.

free parameters (4)
  • beta (Theorem 1 undominance ratio optimizer) = beta*(k) approximates 1 - k^{-1/(k-1)}; for k=5, beta* near 0.331
    Chosen to minimize beta + (1-beta)^k; not a physical or empirical parameter.
  • gamma (SLEO scaling factor) = At least 1, optimized numerically in delta(t)
    Controls the scale of the scaled LEO and appears in the Chernoff tail bound.
  • tau (budget reduction factor in Algorithm 1) = At least 1, chosen above 3.47 for the 4.75 bound
    Controls the geometric reduction of the budget across iterations; constrained by tau * omega(gamma, t) < 1.
  • epsilon (income smoothing/perturbation) = Arbitrarily small, goes to 0
    Introduced to make the income distribution continuous; the limit epsilon -> 0 is taken in the proofs.
assumptions (5)
  • standard math Kakutani's fixed point theorem
    Used to establish existence of LEO and SLEO in Appendices A and B.2.
  • standard math Berge Maximum theorem
    Used to show the producer's best-response correspondence is upper hemi-continuous in prices.
  • standard math Chernoff bound for sums of negatively correlated Bernoulli variables
    Used in Claim 4.1 to bound the probability a voter has fewer than t good candidates; relies on negative correlation from dependent rounding.
  • standard math Dependent rounding theorem of Gandhi et al. (2006)
    Proposition 4.1 asserts existence of a rounding with preserved marginals, size near B, and negative correlations.
  • domain assumption Voters have strict total preferences over candidates with an added least-preferred outside option
    The entire model is defined on strict preference orders; the paper does not handle indifferences.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A few good choices." pith.science (2026). https://pith.science/paper/YB62SIQY

@misc{pith2026250622133,
  author       = {Pith},
  title        = {Pith review of: A few good choices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YB62SIQY}},
  note         = {Machine review of arXiv:2506.22133}
}
abstract

A Condorcet winning set addresses the Condorcet paradox by selecting a few candidates--rather than a single winner--such that no unselected alternative is preferred to all of them by a majority of voters. This idea extends to $\alpha$-undominated sets, which ensure the same property for any $\alpha$-fraction of voters and are guaranteed to exist in constant size for any $\alpha$. However, the requirement that an outsider be preferred to every member of the set can be overly restrictive and difficult to justify in many applications. Motivated by this, we introduce a more flexible notion: $(t, \alpha)$-undominated sets. Here, each voter compares an outsider to their $t$-th most preferred member of the set, and the set is undominated if no outsider is preferred by more than an $\alpha$-fraction of voters. This framework subsumes prior definitions, recovering Condorcet winning sets when $(t = 1, \alpha = 1/2)$ and $\alpha$-undominated sets when $t = 1$, and introduces a new, tunable notion of collective acceptability for $t > 1$. We establish three main results: 1. We prove that a $(t, \alpha)$-undominated set of size $O(t/\alpha)$ exists for all values of $t$ and $\alpha$. 2. We show that as $t$ becomes large, the minimum size of such a set approaches $t/\alpha$, which is asymptotically optimal. 3. In the special case $t = 1$, we improve the bound on the size of an $\alpha$-undominated set given by Charikar, Lassota, Ramakrishnan, Vetta, and Wang (STOC 2025). As a consequence, we show that a Condorcet winning set of five candidates exists, improving their bound of six.

Figures

Figures reproduced from arXiv: 2506.22133 by the authors.

Figure 1
Figure 1. Threshold Income distribution It is straightforward to construct I β,ϵ for any β, ε ∈ (0, 1). Consider the distribution I β,0 , which assigns probability β to 1 and 1 − β to 0. While this distribution satisfies the last two properties, it is not continuous. However, a slight perturbation by ε ensures continuity (see [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Voters v ∈ V in 3 categories based on a fixed a ∈ A \ C: (1) uncovered by C, (2) covered by C and a ≻v C, or (3) covered by C and ∃c ∈ C such that c ≻v a. Note that there are at most βn 1−ε voters in category (2) by Lemma 3.1. Now we are ready to prove Theorem 1. Proof of Theorem 1. Let (x, y, p) be a LEO with B = 1 and I = I β,ϵ. From Claim 3.1, we regard y as a lottery for selecting a single candidate. We sample k… view at source ↗
Figure 3
Figure 3. Voters v ∈ V in 3 categories based on a fixed c ∈ A \ C: (1) not t￾covered by C, (2) t-covered by C and c ≻t v C, or (3) t-covered by C and C ≻t v c. Note that there are at most ω(γ, t) · |V | voters in category (1) by Claim 4.2 and at most γt B(1−ϵ) · |V | voters in category (2) by Claim 4.3. P v∈V pv,a′ ≥ P v∈V pv,c. Therefore, if P v∈V pv,c > γt|V | · 1 B · E[I], we will have R ≥ B · X v∈V pv,c > γt · |V | · E[I]… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Plots for s1(α, t), s2(α, t), and t/α when α ∈ [0.1, 1] and t ≤ 8. When α is small, s1(α, t) < s2(α, t). This is not illustrated in the figure, but in [PITH_FULL_IMAGE:figures/full_fig_p028_4.png]
Figure 5
Figure 5. Figure 5: Plots for αs1(α, t)/t and αs2(α, t)/t. When t ≥ 2 and α ≥ 0.045, αs2(α, t)/t ≤ 4.75. αs2(α, t)/t is sawtooth-wave-shaped because s2(α, t) is integral [PITH_FULL_IMAGE:figures/full_fig_p029_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

  1. [3]

    https://arxiv.org/pdf/2411.03390 Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang. 2025b. Approximately Dominating Sets in Elections. arXiv preprint arXiv:2504.20372 (2025). Jean Antoine Nicolas de Caritat Mis et al

  2. [8]

    Paradox of nontransitive dice and elusive principle of indifference.Scientific American 223, 6 (1970),

  3. [1941]

    Duke Math

    A Generalization of Brouwer’s Fixed Point Theorem. Duke Math. J. 8, 3 (1941), 457–459. Gilbert Laffond, Jean-Francois Laslier, and Michel Le Breton

  4. [1953]

    Econometrica: Journal of the Econometric Society (1953), 608–610

    A theorem on the construction of voting paradoxes. Econometrica: Journal of the Econometric Society (1953), 608–610. Michael Mitzenmacher and Eli Upfal

  5. [1970]

    Econometrica 38, 1 (1970), 66–72

    Lindahl’s Solution and the Core of an Economy with Public Goods. Econometrica 38, 1 (1970), 66–72. Rajiv Gandhi, Samir Khuller, Parthasarathy Srinivasan, and Aravind Srinivasan

  6. [1973]

    Econometrica: Journal of the Econometric Society (1973), 1027–1041

    Aggregation of preferences with variable electorate. Econometrica: Journal of the Econometric Society (1973), 1027–1041

  7. [1981]

    Journal of Economic Theory 25, 2 (1981), 255–268

    Majority committees. Journal of Economic Theory 25, 2 (1981), 255–268. Duncan K Foley

  8. [1993]

    Games and Economic Behavior 5, 1 (1993), 182–201

    The bipartisan set of a tournament game. Games and Economic Behavior 5, 1 (1993), 182–201. David C McGarvey

Show all 14 references
  1. [2006]

    Dependent rounding and its applications to approximation algorithms. J. ACM 53, 3 (2006), 324–360. Martin Gardner

  2. [2015]

    Peter C Fishburn

    Condorcet winning sets.Social Choice and Welfare 44, 3 (2015), 493–517. Peter C Fishburn

  3. [2017]

    Trends in computational social choice (2017), 3–26

    Rolling the dice: Recent results in probabilistic social choice. Trends in computational social choice (2017), 3–26. Felix Brandt, Vincent Conitzer, Ulle Endriss, J´ erˆ ome Lang, and Ariel D Procaccia

  4. [2020]

    In STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Chicago, Illinois, USA)

    Approximately Stable Committee Selection. In STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Chicago, Illinois, USA). Association for Computing Machinery, New York, NY, USA, 463–472. https: //dl.acm.org/doi/abs/10.1145/3357713.3384238 Shi...

  5. [2024]

    Manuscript (2024)

    Approximate core of Participatory Budgeting. Manuscript (2024). John H Smith

  6. [2025]

    arXiv preprint arXiv:2504.02992 (2025)

    A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number. arXiv preprint arXiv:2504.02992 (2025). Felix Brandt

Pith tools

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