REVIEW 3 major objections 3 minor 17 references
Computation of Approximately Stable Committees in Approval-based Elections
T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Every approval-based election admits a 3.65-approximately stable committee, and such a committee can be computed algorithmically.
desk verdict Improved constant for approximate stability in approval committees, via Lindahl equilibrium and strong Rayleigh sampling; proof not inspectable in our copy, but the claim is coherent and deserves refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Lindahl equilibrium of the committee-selection market. In such an equilibrium each voter is assigned a personalized price for every candidate; facing these prices, the voter chooses a most-preferred committee of size $k$, and the choices clear the market in the sense that total demand equals supply. Aggregating these equilibrium choices yields a probability distribution over committees. The proof then shows this distribution is strongly Rayleigh—a negative-correlation condition saying that the selection of one candidate makes the selection of another candidate less likely. That property supplies the large-deviation bound used to argue that no deviating committee $T$ is preferred by more than $\lambda |T|/k$ of the voters with probability larger than the union-bound threshold. The constant $3.65$ emerges from optimizing the parameters in this bound.
What would settle it
For a fixed small instance, compute the Lindahl-equilibrium distribution and exhaustively test every committee in its support: if any support committee $S$ has a rival $T$ preferred by at least $3.65|T|/k$ of the voters, the claimed guarantee fails. Because the instance is finite, this search is a concrete computation that would settle the theorem.
Extended reading notes
Core claim
The paper establishes that in any approval-based committee election—voters with approval sets over candidates, fixed committee size $k$—there exists a committee $S$ such that for every alternative committee $T$ of size $t$, the number of voters who prefer $T$ to $S$ is less than $\lambda t/k$ times $|\mathcal{V}|$, with $\lambda = 3.65$. Equivalently, no rival slate can assemble a coalition larger than $3.65$ times its proportional share of the electorate. The proof reaches this through a Lindahl equilibrium of a voting market: voters face personalized prices for candidates, and the equilibrium demands over candidate sets define a probability distribution on committees. The paper proves that this distribution is strongly Rayleigh, and that a single sample from it is approximately stable with positive probability, so repeated sampling yields an algorithm for finding such a committee.
Load-bearing premise
The proof's load-bearing premise is that the committee distribution coming out of the Lindahl equilibrium is negatively correlated strongly enough to keep the probability of any rival committee rallying a large coalition below the needed threshold; if that probabilistic control gives way, the $3.65$ guarantee collapses.
Editorial extensions
If this is right
- Every approval profile has a committee that no rival of the same size can replace by attracting even $3.65$ times its proportional share of voters.
- The guarantee is algorithmic: sampling from the equilibrium distribution finds such a committee, so approximate stability is not merely an existence result.
- The constant $3.65$ is universal—it does not grow with the number of voters, candidates, or the committee size.
- A polynomial number of samples from the equilibrium distribution suffices, because a sample is approximately stable with positive probability and each failure can be checked against all challengers.
- For a challenger of size $t$, the allowed coalition threshold scales as $\lambda t/k$, so small challengers are automatically easy to resist and the hardest case is a rival committee comparable in size to $k$.
Reading between the lines
- The paper does not claim $3.65$ is optimal; because the constant comes from a parameter optimization, a tighter large-deviation argument could plausibly lower it, and finding the true optimal constant is a natural next problem.
- A testable engineering extension is to draw several candidates from the equilibrium distribution, check each by exhaustive or heuristic search for challengers, and return the best; the theorem guarantees that good committees are present in the distribution, giving such a procedure an anytime certificate.
- The market-equilibrium route implies that stable committees could be produced by generic equilibrium-finding algorithms, which connects proportional representation to computational economics in a way the paper only begins to exploit.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This manuscript (arXiv:2508.00130) studies approximately stable committees in approval-based elections. It defines λ-approximate stability by requiring that no alternative committee T is preferred by at least (λ|T|/k)|V| voters, and it claims that for every instance a 3.65-approximately stable committee exists and can be computed algorithmically. The proposed method is to find a Lindahl equilibrium and then sample from a strongly Rayleigh distribution associated with it.
Significance. If the proof were correct, the result would be a substantial existence-and-computation guarantee for a natural stability notion in committee selection, and the Lindahl-equilibrium/strongly-Rayleigh approach appears to be a novel and promising technique. A strength of the claim is that the approximation constant is explicit and algorithmic; however, no machine-checked proof or reproducible code is supplied, and the proof text cannot be inspected because of corruption. The significance can therefore not be fully assessed from the submitted version.
major comments (3)
- [Full text (after title page)] The supplied full text is almost entirely corrupted after the title page, so no lemma, theorem statement, or proof step is readable. The central existence theorem for λ=3.65 and the algorithmic claim are therefore unsupported in the version under review. The load-bearing step—that the Lindahl equilibrium induces a strongly Rayleigh distribution whose sampled committees satisfy the uniform deviation bound—cannot be verified.
- [Abstract] The abstract asserts that sampling from the strongly Rayleigh distribution yields the 3.65 factor, but no derivation is visible; in particular, there is no legible statement of the negative-correlation/strongly Rayleigh condition for the Lindahl equilibrium distribution, nor a proof that the probability of a large-coalition deviation is controlled by that condition. Please provide the complete proof with numbered lemmas and all constants traced.
- [Algorithmic claim] The claimed algorithmic computation is not substantiated: no running time bound, representation of the Lindahl equilibrium, or sampling procedure is legible. Even if the existence proof were sound, a clear statement of the algorithmic steps would be needed to support the assertion that the committee 'can be computed algorithmically.'
minor comments (3)
- [Submission quality] Please resubmit a clean, non-corrupted PDF; as submitted, the paper cannot be read after the first page.
- [Related work] The abstract would benefit from a comparison with the best previous approximation factor; the reference list is not readable in this version.
- [Typesetting] There are equation fragments in the corrupted text that appear to be part of the proof; ensure all displayed equations are typeset correctly in the final version.
Circularity Check
No significant circularity: the 3.65 bound is presented as a derived theorem, not an assumed or fitted constant.
full rationale
The only substantive claim visible is the abstract's statement that a 3.65-approximately stable committee always exists and can be computed algorithmically, via a Lindahl equilibrium and sampling from an associated strongly Rayleigh distribution. Nothing in the abstract defines Lindahl equilibrium or the Rayleigh distribution in terms of the 3.65 bound, nor does the constant appear among the assumptions. The construction is presented as an argument whose conclusion is the approximate-stability guarantee; no fitted parameter is renamed as a prediction, and no load-bearing self-citation is visible. The supplied full text is heavily corrupted, so no equation or lemma can be inspected to exhibit a specific reduction of the claimed theorem to its inputs. Under the rule that circularity must be demonstrated by quotation and explicit reduction, the absence of any reconstructable derivation step that equals its own input by construction means the correct finding is no significant circularity. Any concern that the strongly Rayleigh premise is unverified is a correctness or completeness risk, not circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption Voters have approval utilities: each voter prefers a committee that contains more of their approved candidates.
- standard math A Lindahl equilibrium exists in the approval voting setting and can be computed.
- standard math Strongly Rayleigh distributions can be sampled in polynomial time and satisfy negative correlation properties.
Cite this review
Pith. "Pith review of Computation of Approximately Stable Committees in Approval-based Elections." pith.science (2026). https://pith.science/paper/24MBRRNZ
@misc{pith2026250800130,
author = {Pith},
title = {Pith review of: Computation of Approximately Stable Committees in Approval-based Elections},
year = {2026},
howpublished = {\url{https://pith.science/paper/24MBRRNZ}},
note = {Machine review of arXiv:2508.00130}
}
abstract
Approval-based committee selection is a model of significant interest in social choice theory. In this model, we have a set of voters $\mathcal{V}$, a set of candidates $\mathcal{C}$, and each voter has a set $A_v \subset \mathcal{C}$ of approved candidates. For any committee size $K$, the goal is to choose $K$ candidates to represent the voters' preferences. We study a criterion known as \emph{approximate stability}, where a committee is $\lambda$-approximately-stable if there is no other committee $T$ preferred by at least $\frac{\lambda|T|}{k} |\mathcal{V}| $ voters. We prove that a $3.65$-approximately stable committee always exists and can be computed algorithmically in this setting. Our approach is based on finding a Lindahl equilibrium and sampling from a strongly Rayleigh distribution associated with it.
Reference graph
Works this paper leans on
-
[1]
" write newline "" before.all 'output.state := FUNCTION output.nonempty.mrnumber duplicate missing pop "" 'skip if duplicate empty 'pop " " swap * " " * write if FUNCTION fin.entry add.period write newline INTEGERS nameptr namesleft numnames FUNCTION format.language language empty "" " (" language * ")" * if FUNCTION format.names 's := #1 'nameptr := s nu...
-
[2]
Jos \'e A Adell and P Jodr \'a , The median of the P oisson distribution , Metrika 61 (2005), 337--346
work page 2005
-
[3]
Kenneth J Arrow, A difficulty in the concept of social welfare, Journal of political economy 58 (1950), 328--346
work page 1950
-
[4]
Liggett, Negative dependence and the geometry of polynomials, 2008
Julius Borcea, Petter Brändén, and Thomas M. Liggett, Negative dependence and the geometry of polynomials, 2008
work page 2008
-
[5]
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang, Six candidates suffice to win a voter majority, CoRR abs/2411.03390 (2024)
work page Pith review arXiv 2024
-
[6]
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu, Breaking the metric voting distortion barrier, J. ACM 71 (2024), 42:1--42:33
work page 2024
-
[7]
Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang, Group fairness in committee selection, Proceedings of the 2019 ACM Conference on Economics and Computation, EC ’19, ACM, June 2019
work page 2019
-
[8]
Duncan K. Foley, Lindahl's solution and the core of an economy with public goods, Econometrica 38 (1970), 66--72
work page 1970
Show all 17 references
-
[9]
Shayan Oveis Gharan, L ecture 5: Maximum entropy convex programs , January 2020, https://homes.cs.washington.edu/ shayan/courses/polynomials/poly-lecture-5.pdf
2020
-
[10]
463--472
Zhihao Jiang, Kamesh Munagala, and Kangning Wang, Approximately stable committee selection, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 463--472
2020
-
[11]
Christian Kroer and Dominik Peters, Computing lindahl equilibrium for public goods with and without funding caps, arXiv preprint arXiv:2503.16414 (2025)
2025 arXiv
-
[12]
Greg Leo, Available at SSRN 3057453 (2017)
2017
-
[13]
2229--2252
Kamesh Munagala, Yiheng Shen, Kangning Wang, and Zhiyi Wang, Approximate core for committee selection via multilinear extension and market clearing, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 2229--2252
2022
-
[14]
Th \`a nh Nguyen and Haoyu Song, Approximate core of participatory budgeting via lindahl equilibrium
-
[15]
Dominik Peters, The core of approval-based committee elections with few candidates, CoRR abs/2501.18304 (2025)
2025 arXiv
-
[16]
793--794
Dominik Peters and Piotr Skowron, Proportionality and the limits of welfarism, EC '20: The 21st ACM Conference on Economics and Computation, pp. 793--794
-
[17]
Henry Teicher, An inequality on P oisson probabilities , The Annals of Mathematical Statistics 26 (1955), 147--149
1955
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.