REVIEW 3 major objections 4 minor 1 cited by
The Core of Approval-Based Committee Elections with Few Seats
T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read This paper proves that core-stable committees always exist for approval-based elections with at most eight seats, and with at most fifteen candidates for any committee size.
desk verdict A real advance on a stubborn open problem, with a proof architecture that deserves serious referee time; the main soft spot is the unproven completeness of the computer enumeration, which is checkable but not closed-form. 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 Proportional Approval Voting (PAV) score, which evaluates a committee $W$ by the sum over voters of the harmonic utility $H(u_A(W))$, and whose local maxima are studied through single-swap score differences $\Delta_{P,x,y}$. The proof of Theorem 4.1 shows that a local optimum $W$ cannot admit a deviation $T$: summing the swaps that replace one member of $W \setminus T$ by one member of $T \setminus W$ yields inequality (2), and a per-ballot lower bound on $\delta_A$, verified by a finite exhaustive search over possible intersection sizes (inequality (3)), forces the opposing coalition to be smaller than $|T|/k$. The $k = 8$ analysis solves linear programs whose infeasibility is certified by Farkas witnesses to pin down the unique type of possible counterexample; the $m \le 15$ analysis enumerates canonical histories of the recursive rule and checks each extension with a linear program, with every rejected continuation backed by an exact integer Farkas certificate.
What would settle it
Run Algorithm 2 on $m = 15$ and $k = 10$ and look for a history with $|T_1| + \cdots + |T_r| > k$ whose defining inequalities are feasible; if found, Theorem 5.3 is false. Alternatively, solve system (4) for $k \le 8$: any rational profile $P$ and committee $W$ satisfying the local-PAV constraints together with the deviation constraint $\sum_{A: u_A(T) > u_A(W)} P(A) \ge |T|/k$ would be an explicit counterexample to Theorem 4.1 or Theorem 4.5. A cheaper check is to verify the 114,373 published Farkas witnesses with exact arithmetic and find even one that fails its inequalities, which would indicate the enumeration's rejection logic is unsound.
Extended reading notes
Core claim
The paper's central claim is that the core of an approval-based committee election is non-empty for all profiles when $k \le 8$ or $m \le 15$, with no restriction on the number $n$ of voters. On its own terms, the discovery is that Proportional Approval Voting (PAV), which maximizes the sum of harmonic utilities $\sum_A P(A) H(|A \cap W|)$, behaves much better than previously known: for $k \le 7$ every local PAV committee lies in the core, and for $k = 8$, although some local and even global PAV committees can fail the core, every such failure has the rigid structure of Lemma 4.4 and a tied global PAV committee in the core always exists. For the candidate-count result, a recursive rule that fixes each successful deviation $T$ as a requirement and removes the voters who supported it is shown, by exhaustive enumeration of canonical histories, to terminate within $k$ iterations whenever $m \le 15$. Together these theorems answer the open question affirmatively for every election with few seats or few candidates.
Load-bearing premise
Everything rests on the completeness of the computer enumerations: for $m \le 15$ every relevant canonical history must be found by Algorithm 2, and for $k \le 7$ the finite check of inequality (3) must cover every ballot-intersection pattern, with every rejected case backed by a valid Farkas certificate.
Editorial extensions
If this is right
- For real elections that fill at most eight seats, the core guarantee now holds for every possible approval profile, so PAV can be recommended as a core-stable rule in that range.
- The non-emptiness result is uniform in the number of voters because the linear programs describe fractional profiles directly, so no bound on $n$ is needed.
- For $k \le 7$, a core-stable committee is computable in polynomial time by reaching an $\varepsilon$-local-swap-stable PAV optimum through $O(k^2 \ln k)$ improving swaps.
- The recursive PAV method stops guaranteeing the core at $m = 16$ for $k = 10$ or $k = 11$, so the boundary of this particular proof technique is exactly at sixteen candidates.
- If the general non-emptiness conjecture holds, any counterexample must have $m \ge 16$ and $k \ge 9$, narrowing the search space left by this paper.
Reading between the lines
- One could push the same canonical-history machinery one parameter further: because the recursive rule fails at $m = 16$ only for $k = 10$ and $k = 11$, an ad hoc patch for those two cases would likely establish non-emptiness for all sixteen-candidate profiles.
- The Farkas-certificate style suggests a template for other representation axioms or quotas: any existential claim that holds uniformly in the number of voters can be cast as infeasibility of a rational linear system and verified exactly, not approximately.
- The rigidity of the $k = 8$ failure structure hints that a counterexample to the general conjecture, if one exists, will be highly structured, possibly with a unique PAV committee, which could guide a human-readable proof.
- For practice, the $k \le 7$ result makes the $\varepsilon$-tolerant local-search version of PAV attractive, but the paper's own laminar-proportionality example shows that core stability alone does not capture every intuitive fairness failure.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies non-emptiness of the core in approval-based committee elections. It proves three main results: (1) for k ≤ 7 every local PAV committee is core-stable, so the core is non-empty; (2) for k = 8 at least one global PAV committee is core-stable; and (3) for m ≤ 15 candidates a core-stable committee exists for every k ≤ m and any number of voters. The proofs reduce core existence to feasibility of linear programs, use exhaustive computer enumeration with symmetry reduction (Algorithm 2), and provide Farkas certificates in exact arithmetic for the infeasible cases. The paper also gives counterexamples showing that PAV can fail the core for k = 9, that the recursive-PAV method stops working for m = 16, and that the Droop-core analogue fails already for k = 6.
Significance. If the results are correct, they constitute a substantial advance on a question open since Aziz et al. (2016/2017), extending existence from k = 3 and m + n ≤ 14 to k ≤ 8 for all m and n and to m ≤ 15 for all k and n. The LP/Farkas-certificate approach is a notable methodological contribution: the repository allows independent verification of infeasibility certificates without trusting a solver, which is a real strength. The main caveat is that the completeness of the finite enumerations driving Theorems 4.5 and 5.3 is not formally certified in the manuscript, so the unconditional status of those results depends on closing that gap.
major comments (3)
- [§5.1, Theorem 5.3 and Algorithm 2] Theorem 5.3 is established by exhaustive enumeration of histories, but the manuscript never proves that the enumeration is complete. The Farkas witnesses certify infeasibility of the particular LP systems generated by Algorithm 2; they do not certify that every history has a canonical representative under the equivalence relation of Footnote 6, nor that the breadth-first search visits every canonical continuation. Without a completeness argument, or a machine-checked certificate of the enumeration itself, a missed canonical history would invalidate Theorem 5.3. Please add a formal proof that every history is equivalent to a canonical history produced by Algorithm 2, and ideally an independent verifier checking that the list of histories is closed under all canonical extensions.
- [§4.2, Lemma 4.4] The k = 8 classification, namely that a non-core local PAV committee has an objection T with |T| = 4 and |W ∩ T| = 2 and satisfies conditions (i)–(iii), is derived by iterating through all possible T and solving linear programs. The paper does not specify the finite set of T-patterns that were checked or prove that this set covers all cases; the provided dual certificates validate optimal values only for the LPs that were actually solved. Since Theorem 4.5 depends entirely on Lemma 4.4, please make the enumeration of T-patterns explicit, for example by listing the parameter ranges or by providing a script that verifies the classification exhaustively with exact arithmetic and without a solver.
- [§4.1, inequality (3)] The proof of Theorem 4.1 hinges on inequality (3), which is justified by a small exhaustive search over triples (a, b, c). Although the ranges are stated, the paper does not report the outcome of the check or provide the verification artifact for this specific inequality; it only points to the repository. Please add an exact verification, such as a script or a table of certificates, covering all k ≤ 7 and all relevant choices of |W ∩ T|, a, b, and c, and state in the text that this check is part of the proof.
minor comments (4)
- [§4.2, proof of Theorem 4.5] The statement that the only members of W approved by any voters are a, b, a', and b' is not literally correct, since a' and b' may lie outside W (for example, a' could be x); the subsequent conclusion still follows if the sentence is rephrased to refer to W ∩ {a', b'}.
- [§5.1, before Theorem 5.3] The note that existence for m = 15 implies existence for all m ≤ 15 deserves a short proof, for instance by adding unapproved dummy candidates and then replacing any dummy winners in a core committee by original candidates.
- [§5.1, Definition 5.1] The active-ballot set A_t is used in the displayed inequality before it is defined; please move its definition before the inequality for readability.
- [§4.3 and §6, figures] The two example diagrams with labels such as 'v1 v24 v7 v8 v14 v15' are hard to read; please specify the profiles by listing approval sets and voter multiplicities in the text or captions.
Circularity Check
No significant circularity: the core-existence theorems reduce to independent LP infeasibility and exhaustive history enumeration, not to their own conclusions.
full rationale
The paper's derivation is self-contained in the relevant sense. Theorem 4.1 proves that every local PAV committee is core-stable by assuming, toward a contradiction, a profile P and a local committee W with a successful deviation T; it then uses the local-optimality sum inequality (1) and the finite inequality (3) to derive s < |T|/k. Inequality (3) is verified by exhaustive search over finitely many triples (a, b, c) and does not assume the target result. Lemma 4.4 and Theorem 4.5 similarly derive the k = 8 structure from LP systems whose infeasibility is certified via Farkas witnesses; the certificates are exact and reproducible, and the LPs encode the negation of the theorem rather than its conclusion. Section 5's Proposition 5.2 is a valid reduction: a profile that defeated Algorithm 1 would produce a history with |T1| + ... + |Tr| > k, so proving all histories satisfy the bound is sufficient for core existence. The enumeration's completeness depends on the stated canonicalization argument and the generated Farkas certificates, which is an unverified-code and rigor risk rather than a circularity. The paper's own admission that recursive PAV stops working for m = 16 is a limitation, not a circular step. The citations to Brill et al. (2022) and Peters et al. (2021) share authors with the present paper, but they are used for auxiliary lemmas and an analogy, not as the load-bearing justification for the core-existence claims; the central deductions are supported by the paper's own LP and certificate pipeline. No fitted parameter is renamed as a prediction, and no known result is merely relabeled.
Assumptions & free parameters
assumptions (4)
- standard math Farkas' lemma and exact rational LP duality
- domain assumption Known proportionality properties of local PAV committees, specifically no disjoint deviations and EJR+ (Brill et al. 2022, Brill and Peters 2023)
- ad hoc to paper The finite exhaustive check over triples (a,b,c) in inequality (3) is complete and correctly implemented
- ad hoc to paper Symmetry reduction to canonical histories in Algorithm 2 preserves feasibility of the history LP
Cite this review
Pith. "Pith review of The Core of Approval-Based Committee Elections with Few Seats." pith.science (2026). https://pith.science/paper/TRPDKMTM
@misc{pith2026250118304,
author = {Pith},
title = {Pith review of: The Core of Approval-Based Committee Elections with Few Seats},
year = {2026},
howpublished = {\url{https://pith.science/paper/TRPDKMTM}},
note = {Machine review of arXiv:2501.18304}
}
abstract
In an approval-based committee election, the goal is to select a committee consisting of $k$ out of $m$ candidates, based on $n$ voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be "objected to" by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when $k \le 8$, for any number of candidates $m$ and any number of voters $n$, by showing that the Proportional Approval Voting (PAV) rule due to Thiele [1895] always satisfies the core when $k \le 7$ and always selects at least one committee in the core when $k = 8$. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are $m \le 15$ candidates, for any committee size $k \le m$ and any number of voters $n$. These results are obtained with the help of computer search using linear programs.
Forward citations
Cited by 1 Pith paper
-
Computation of Approximately Stable Committees in Approval-based Elections
A 3.65-approximately stable committee always exists in approval-based elections and can be computed using a Lindahl equilibrium and a strongly Rayleigh distribution.
Reference graph
Works this paper leans on
-
[2]
Justified Representation in Approval-Based Committee Voting
Justified representation in approval-based committee voting. arXiv:1407.8269v4 [cs.MA] https://arxiv.org/abs/1407.8269v4 [ → p. 2] Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh
-
[2016]
The lack of such a linear formulation can be formally established using the techniques of Xia (2025)
do not admit the same kind of linear formulations (because they would require multiplying variables corresponding to ballot frequencies with variables corresponding to ρ-values or to loads). The lack of such a linear formulation can be formally established using the techniques of Xia (2025). In part because computer search is difficult for these rules, to...
work page 2025
-
[2017]
Social Choice and Welfare 48, 2 (2017), 461–485
Justified representation in approval-based committee voting. Social Choice and Welfare 48, 2 (2017), 461–485. doi:10.1007/s00355-016-1019-3 [ → p. 2, 3, 10] Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis S´ anchez-Fern´ andez, and Piotr Skowron. 2018. On the complexity of extended and proportional justified representation. In Proceedings of...
arXiv 2017
-
[2022]
Mathematical Programming (2022)
Approval-based apportionment. Mathematical Programming (2022). doi:10.1007/ s10107-022-01852-1 [ → p. 2, 3, 5, 6] Markus Brill and Jannik Peters. 2023. Robust and verifiable proportionality axioms for multi- winner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (EC). 301. doi:10.1145/3580507.3597785 Full version arXiv:2302....
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.