{"id":"67040615-c696-4feb-b17c-10b985d0ddb8","arxiv_id":"2501.18304","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Core-stable committees always exist for approval-based elections with up to 8 seats or up to 15 candidates, proved via Proportional Approval Voting and computer-verified linear programming certificates.","lead":"Approval-based committee elections pick k winners from candidates approved by voters, and the 'core' is a demanding stability standard whose non-emptiness has been open since 2016. This paper proves core-stable committees always exist when k is at most 8, or when at most 15 candidates run, using computer-checked linear programming certificates.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Completeness of Algorithm 2's history enumeration is the load-bearing unverified step; the Farkas certificates prove infeasibility but not exhaustiveness.","rationale":"The reader's weakest assumption correctly identifies the same load-bearing concern: the exhaustiveness of the computer enumeration behind Theorem 5.3 and the k=8 classification. I agree with that identification. The paper does much better than is typical: it ships reproducible code and exact Farkas certificates, so the infeasibility of the checked LP systems is verifiable without trusting a solver. What is not machine-checked is the completeness of Algorithm 2: the Farkas witnesses only certify the systems that Algorithm 2 happened to solve. The symmetry reduction in Footnote 6 is argued informally, and the correctness of its implementation is not independently certified. If that reduction is wrong or the implementation skips a feasible continuation, Theorem 5.3 could fail even though all stored certificates are valid. I did not find a concrete error, and the amount of independent support in the form of code and certificates is substantial, so I do not lower the reader's ACCEPT verdict. The proposed independent reimplementation is a concrete way to close the remaining gap and would raise confidence from high to very high. For Theorem 4.1, the analogous finite check behind inequality (3) is tiny and can be audited by a simple script, so it is not the main risk; the principal risk is the global history enumeration for m≤15.","tokens_in":16612,"tokens_out":21633,"duration_ms":209203,"concrete_test":"Independently re-implement the history search for m=15, k=9..13 without reusing the repository's symmetry code, for example by brute-force enumerating all (W_t,T_t) pairs for a smaller case such as m=10,k=6 as a smoke test and by using canonical labeling (nauty/bliss) for m=15, then compare the resulting set of canonical histories and their |T|-sums against Table 1 and the 114,373 Farkas witnesses. If the independent enumerator finds exactly the same histories and every history satisfies |T1|+...+|Tr|≤k, the completeness concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central existence theorems for k=8 and m≤15 depend on finite computer enumerations whose soundness is certified, but whose completeness is not. In Theorem 5.3, Algorithm 2 must generate every relevant canonical history; the 114,373 Farkas witnesses in the repository are certificates that the particular LP systems Algorithm 2 chose to solve are infeasible. They do not prove that the search visited every relevant continuation, nor that the symmetry reduction of Footnote 6 has no gaps. If a non-canonical history is not equivalent to a canonical one, or if the canonicalization code drops a feasible continuation because it miscomputes equivalence classes, the enumeration could miss a history with |T1|+...+|Tr|>k, and Proposition 5.2 would no longer imply core existence. The same type of reliance appears in Lemma 4.4, where the claim that only |T|=4, |W∩T|=2 objections are possible for k=8 rests on iterating through all T-patterns and solving an LP for each. I found no internal contradiction and the code and exact certificates are real supporting evidence, but the completeness step is the least secure link in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16869,"tokens_out":17275,"duration_ms":198777,"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":[{"comment":"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.","section":"§5.1, Theorem 5.3 and Algorithm 2"},{"comment":"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.","section":"§4.2, Lemma 4.4"},{"comment":"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.","section":"§4.1, inequality (3)"}],"minor_comments":[{"comment":"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'}.","section":"§4.2, proof of Theorem 4.5"},{"comment":"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.","section":"§5.1, before Theorem 5.3"},{"comment":"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.","section":"§5.1, Definition 5.1"},{"comment":"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.","section":"§4.3 and §6, figures"}],"recommendation":"major_revision","confidential_remarks":"This is a strong paper and I expect the results to be correct. My recommendation is driven by the absence of a formal completeness proof for the two finite enumerations, not by any identified mathematical contradiction. The paper would be considerably strengthened by shipping a machine-checked completeness certificate for Algorithm 2 and for the T-pattern enumeration in Lemma 4.4; the existing Farkas certificates are excellent but address infeasibility, not exhaustiveness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the first real progress on core non-emptiness for approval-based committee elections since Cheng et al.'s k=3 result, and it is credible. The paper proves that every local PAV committee is in the core for k≤7, that some global PAV committee is in the core for k=8, and that a core-stable committee exists for m≤15, all independent of the number of voters. It also introduces the recursive PAV rule and an LP-based certified proof framework with Farkas witnesses. Those are genuine contributions, not incremental tweaks.\n\nThe proof structure is careful. The analytic part (Lemma 3.1, Proposition 5.2, Theorem 4.5) is clear, and the inequality (3) check is a finite brute force over triples, which is fine. The k=8 classification in Lemma 4.4 is an LP enumeration with exact rational certificates, and the m≤15 result in Theorem 5.3 rests on Algorithm 2's enumeration of canonical histories plus 114,373 Farkas witnesses. The code and certificates are shipped, and the verification script is simple enough that an independent group could check it without trusting a solver. That is real evidence.\n\nThe soft spot, as the stress-test says, is completeness of the enumeration. The Farkas certificates prove infeasibility for the specific LPs the code generates; they do not prove that Algorithm 2 visits every relevant history, nor that the symmetry reduction of Footnote 6 is gap-free. If a non-canonical history is missed or the canonicalization drops a feasible continuation, the m≤15 theorem falls. The paper does not give a closed-form argument for this. I don't think it is a fatal flaw: the enumeration code is public, and the symmetry reduction is standard and described in enough detail to reimplement. But a referee should explicitly ask for either a formal proof of the canonicalization or, better, an independent reimplementation of Algorithm 2 for at least one of the harder cases (say m=15, k=12). The Droop quota section is honest about where things break (PAV fails Droop core even for k=6), and the m=16 failure is disclosed with an explicit history.\n\nWho is this for: anyone working on proportional representation, committee voting, or computational social choice with computer-assisted proofs. It deserves a serious referee, not a desk reject. I would not accept the proof as settled until the completeness issue is either tightened or independently verified, but I would encourage engaging with it at full depth.","headline":"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.","tokens_in":17376,"tokens_out":1185,"would_cite":true,"duration_ms":86259,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["approval-based committee elections","core stability","proportional approval voting","proportional representation","justified representation","computational social choice","linear programming","Farkas certificates"],"falsifier":"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.","tokens_in":16404,"feed_emoji":"🗳️","tokens_out":12663,"duration_ms":109840,"temperature":0.7,"pith_summary":"In an approval-based committee election, a committee is in the core if no set $T$ of up to $k$ candidates wins support from at least $|T|/k$ of the voters who prefer $T$ to the committee. Since the notion was proposed in 2016, it has been open whether a core committee always exists. This paper establishes that it does whenever the committee has at most eight seats, regardless of the number of candidates or voters, and also whenever there are at most fifteen candidates, for any committee size. The proof works by showing that local optima of the 130-year-old Proportional Approval Voting rule are core-stable up to $k = 7$, that some global PAV optimum is core-stable at $k = 8$, and that a recursive PAV rule terminates with a core-stable committee when $m \\le 15$. The computer-assisted arguments come with exact Farkas certificates, so the conclusions do not depend on trusting a solver.","feed_headline":"Up to 8 seats, a core-stable committee always exists","feed_subtitle":"The proof covers any number of voters, and shows PAV itself finds a core-stable committee for small k.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduced core stability for approval-based committee elections and posed the non-emptiness question that this paper answers for small parameters.","marker":"Aziz et al. (2017)"},{"why":"Defined the Proportional Approval Voting rule whose score and local optima are the objects analyzed throughout.","marker":"Thiele (1895)"},{"why":"Supplies the theorem that local PAV committees admit no disjoint deviations, used in Lemma 3.1 and therefore in the $k \\le 7$ proof.","marker":"Brill et al. (2022)"},{"why":"Provides the EJR+ axiom satisfied by local PAV committees, used to rule out deviations containing a single unelected candidate.","marker":"Brill and Peters (2023)"},{"why":"Proved the previous best existence result for $k = 3$ and conjectured general non-emptiness, the baseline this paper improves.","marker":"Cheng et al. (2020)"},{"why":"Documents known core failures of welfarist rules and the $(2,1)$-approximate core result that motivates examining PAV variants.","marker":"Peters and Skowron (2020)"},{"why":"Provides the local-search and $\\varepsilon$-local-swap-stable techniques used to compute core-stable committees efficiently for $k \\le 7$.","marker":"Aziz et al. (2018)"}],"fun_headline_variants":["Core-stable committees exist for up to 8 seats","Small elections always have a core-stable committee","Core existence proven for few seats or few candidates","Open problem resolved for small committees","PAV always yields a core committee for small k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Core-stable committees exist for up to 8 seats","Small elections always have a core-stable committee","Core existence proven for few seats or few candidates","Open problem resolved for small committees","PAV always yields a core committee for small k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001859,"raw_usage":{"total_tokens":7328,"prompt_tokens":1002,"completion_tokens":6326,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":6255}},"tokens_in":618,"tokens_out":6326,"duration_ms":56813,"temperature":1.0,"reasoning_tokens":6255,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:57:36.126576+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}