pith. machine review for the scientific record. sign in

arxiv: 2605.06194 · v1 · submitted 2026-05-07 · 💻 cs.GT

Recognition: unknown

Core Existence in Approval-Based Committee Elections with up to Five Voter Types

Dominik Peters, Matthias Greger, Patrick Becker

Authors on Pith no claims yet

Pith reviewed 2026-05-08 04:29 UTC · model grok-4.3

classification 💻 cs.GT
keywords approval votingcommittee electionscore stabilityproportional representationfractional committee roundingaffine monoidsweighted voters
0
0 comments X

The pith

Approval-based committee elections with at most five voters always have a core committee.

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

The paper shows that a core committee, which is stable in the sense of proportional representation, always exists when there are at most five voters in an approval-based committee election. This is achieved by proving that any fractional committee can be rounded to an integral committee such that no voter's utility drops below the floor of its fractional value. Such a result matters because the core is a strong fairness notion that ensures no group of voters can all be made better off by choosing a different committee. The argument uses affine monoid methods and extends to weighted voters with five or fewer distinct approval sets, with efficient computability in these cases.

Core claim

We prove that for any approval-based committee election with at most five voters, there always exists a committee belonging to the core. The proof demonstrates that every fractional committee admits a deterministic rounding to an integral committee preserving each voter's utility up to the floor of the fractional utility, using affine monoid methods. This extends to the weighted voter setting, establishing core existence for instances with up to five distinct approval sets, and allows polynomial-time computation of such a committee.

What carries the argument

Affine monoid methods enabling the deterministic rounding of every fractional committee to an integral one while preserving voter utilities up to floors.

If this is right

  • Core non-emptiness holds for all approval-based committee elections with n ≤ 5.
  • Core committees can be computed in polynomial time for these cases.
  • The result carries over to weighted voters with at most five distinct approval sets.
  • The rounding technique does not extend directly to n=6 or to models with additive valuations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar techniques could potentially be adapted for other stability concepts in voting theory with small numbers of participants.
  • Instances with more voters but few distinct approval types might inherit the guarantee.
  • The breakdown at n=6 highlights a potential threshold where core existence becomes harder to guarantee via rounding.

Load-bearing premise

That affine monoid methods always allow rounding every fractional committee to an integral committee preserving each voter's utility up to floors for all instances with at most five voters.

What would settle it

An approval-based committee election instance with five voters and a fractional committee for which no integral rounding exists that keeps all voters' utilities at or above their floor values would disprove the claim.

read the original abstract

In an approval-based committee election, the task is to select a committee of up to $k$ candidates from a set of $m$ candidates based on the preferences of $n$ voters, each of whom approves a subset of the candidates. A central open question is whether there always exists a committee in the core, a stability notion capturing proportional representation. We prove core non-emptiness for all approval-based committee elections with at most five voters. The proof is based on affine monoid methods and shows that, for $n\le5$, every fractional committee admits a deterministic rounding to an integral committee that preserves each voter's utility up to floors. We extend our argument to the weighted voter setting, which implies core existence for instances with up to five distinct approval sets. In all these cases, a core committee can be computed in polynomial time. We show that our technique cannot be extended as-is: our rounding method breaks down for $n=6$, and for $n=3$ when applied to more general models with additive valuations or non-unit candidate costs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves core non-emptiness for approval-based committee elections with n ≤ 5 voters. It establishes that every fractional committee admits a deterministic rounding to an integral committee preserving each voter's utility up to the floor, via an affine-monoid construction that enumerates generators and exhibits an integral point in the target polytope. The argument extends to the weighted case with five distinct approval sets and yields a polynomial-time algorithm; a counterexample monoid is provided showing the method fails for n = 6 and for certain generalizations to additive valuations or non-unit costs.

Significance. If the rounding result holds, the paper resolves a central open question on core stability for small voter counts in a key model of proportional representation. The algebraic approach supplies an explicit, constructive proof together with a sharp negative result for n = 6, and the polynomial-time computability is a concrete algorithmic contribution.

minor comments (2)
  1. [rounding construction] The description of the monoid generators for the n = 5 case would benefit from an explicit tabular listing or small diagram that cross-references the coordinates of the target polytope.
  2. [introduction] A short paragraph comparing the affine-monoid technique with prior rounding methods in the literature (e.g., those based on dependent rounding or flow-based arguments) would help situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading and positive assessment of the manuscript. The referee's summary accurately reflects our main results on core non-emptiness for approval-based committee elections with at most five voters (or five distinct approval sets), the affine-monoid rounding technique, the polynomial-time algorithm, and the negative results for n=6 and certain generalizations. We are pleased that the referee views this as resolving a central open question with a constructive proof.

Circularity Check

0 steps flagged

Direct algebraic existence proof via monoid rounding; no circularity

full rationale

The derivation establishes core non-emptiness for n≤5 by exhibiting an explicit affine-monoid rounding procedure: for every fractional committee the construction enumerates the relevant monoid generators in low dimension, verifies that an integral point always lies inside the target polytope defined by the floor-utility constraints, and thereby produces a deterministic integral committee. The same finite case analysis is extended to the weighted setting with five distinct approval vectors. Because the argument proceeds by direct enumeration and polytope membership rather than by fitting parameters, renaming known results, or invoking a self-citation chain whose validity depends on the target theorem, the proof is self-contained and does not reduce to its own inputs. The explicit counter-example monoid for n=6 further confirms that the method is not tautological.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on algebraic properties of affine monoids that enable utility-preserving rounding; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption Affine monoids admit integral points that preserve floor-bounded linear inequalities corresponding to voter utilities.
    Invoked to guarantee the existence of the rounding for every fractional committee when n≤5.

pith-pipeline@v0.9.0 · 5484 in / 1280 out tokens · 35546 ms · 2026-05-08T04:29:51.954185+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

59 extracted references · 6 canonical work pages

  1. [1]

    Osborne and Ariel Rubinstein , keywords =

    Martin J. Osborne and Ariel Rubinstein , keywords =. A Course in Game Theory , year =

  2. [2]

    Justified Representation in Approval-Based Committee Voting , volume =

    Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh , journal =. Justified Representation in Approval-Based Committee Voting , volume =. 2017 , doi =

    2017

  3. [3]

    Multi-Winner Voting with Approval Preferences , year =

    Martin Lackner and Piotr Skowron , keywords =. Multi-Winner Voting with Approval Preferences , year =

  4. [4]

    Proportionality and the Limits of Welfarism , year =

    Dominik Peters and Piotr Skowron , booktitle =. Proportionality and the Limits of Welfarism , year =. 1911.11747 , archivePrefix=

    work page arXiv 1911

  5. [5]

    Computing

    Christian Kroer and Dominik Peters , booktitle =. Computing. 2025 , doi =. 2503.16414 , archivePrefix=

    work page arXiv 2025

  6. [6]

    Proportional Decisions in Perpetual Voting , year =

    Martin Lackner and Jan Maly , booktitle = proc #. Proportional Decisions in Perpetual Voting , year =

  7. [7]

    Committees and Equilibria: Multiwinner Approval Voting Through the Lens of Budgeting Games , year =

    Adrian Haret and Sophie Klumper and Jan Maly and Guido Sch. Committees and Equilibria: Multiwinner Approval Voting Through the Lens of Budgeting Games , year =. Proceedings of the 25th ACM Conference on Economics and Computation (EC) , note =

  8. [8]

    Structure in Dichotomous Preferences , year =

    Edith Elkind and Martin Lackner , booktitle = proc #. Structure in Dichotomous Preferences , year =

  9. [9]

    Proportional Participatory Budgeting with Additive Utilities , year =

    Dominik Peters and Grzegorz Pierczy\'nski and Piotr Skowron , booktitle = proc #. Proportional Participatory Budgeting with Additive Utilities , year =

  10. [10]

    Foley , journal =

    Duncan K. Foley , journal =. Lindahl's Solution and the Core of an Economy with Public Goods , volume =. 1970 , doi =

    1970

  11. [11]

    The Core of the Participatory Budgeting Problem , year =

    Brandon Fain and Ashish Goel and Kamesh Munagala , booktitle = proc #. The Core of the Participatory Budgeting Problem , year =

  12. [12]

    Maximum Flow Is Fair: A Network Flow Approach to Committee Voting , year =

    Mashbat Suzuki and Jeremy Vollen , booktitle =. Maximum Flow Is Fair: A Network Flow Approach to Committee Voting , year =

  13. [13]

    Vaish , booktitle =

    Rupert Freeman and Nisarg Shah and R. Vaish , booktitle =. Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation , year =. doi:10.1145/3391403.3399537 , eprint=

    work page doi:10.1145/3391403.3399537

  14. [14]

    Preferences Single-Peaked on a Circle , volume =

    Dominik Peters and Martin Lackner , journal =. Preferences Single-Peaked on a Circle , volume =. 2020 , doi =

    2020

  15. [15]

    Theory of Linear and Integer Programming , year =

    Alexander Schrijver , publisher =. Theory of Linear and Integer Programming , year =

  16. [16]

    Haris Aziz and B. E. Lee and Nimrod Talmon , booktitle = proc #. Proportionally Representative Participatory Budgeting: Axioms and Algorithms , year =

  17. [17]

    The (Computational) Social Choice Take on Indivisible Participatory Budgeting , year =

    Simon Rey and Felicia Schmidt and Jan Maly , eprint =. The (Computational) Social Choice Take on Indivisible Participatory Budgeting , year =

  18. [18]

    Proportionality in Approval-Based Participatory Budgeting , year =

    Markus Brill and Stefan Forster and Martin Lackner and Jan Maly and Jannik Peters , booktitle = proc #. Proportionality in Approval-Based Participatory Budgeting , year =

  19. [19]

    2026 , eprint=

    Computing Thiele Rules on Interval Elections and Their Generalizations , author=. 2026 , eprint=

    2026

  20. [20]

    Proceedings of the 18th International Conference on Web and Internet Economics (WINE) , pages=

    Auditing for Core Stability in Participatory Budgeting , author=. Proceedings of the 18th International Conference on Web and Internet Economics (WINE) , pages=. 2022 , organization=

    2022

  21. [21]

    Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI) , pages=

    Market-Based Explanations of Collective Decisions , author=. Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI) , pages=. 2021 , doi=

    2021

  22. [22]

    doi:10.1007/b105283 , year=

    Polytopes, Rings, and K-Theory , author=. doi:10.1007/b105283 , year=

    work page doi:10.1007/b105283

  23. [23]

    Formalizing the Theory of Approval-Based Committee Voting in Lean 4 , author=

  24. [24]

    Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , pages =

    Fain, Brandon and Munagala, Kamesh and Shah, Nisarg , title =. Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , pages =. 2018 , doi =. 1805.03164 , archivePrefix=

    work page arXiv 2018

  25. [25]

    2026 , eprint=

    Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences , author=. 2026 , eprint=

    2026

  26. [26]

    2018 , eprint=

    Thresholds Quantifying Proportionality Criteria for Election Methods , author=. 2018 , eprint=

    2018

  27. [27]

    2025 , eprint=

    Justified Representation: From Hare to Droop , author=. 2025 , eprint=

    2025

  28. [28]

    2018 , eprint=

    Proportional Representation in Approval-Based Committee Voting and Beyond , author=. 2018 , eprint=

    2018

  29. [29]

    Naval Research Logistics Quarterly , volume=

    An inductive method for constructing mimmal balanced collections of finite sets , author=. Naval Research Logistics Quarterly , volume=. 1965 , doi=

    1965

  30. [30]

    SIAM Journal on Applied Mathematics , volume=

    Some theorems on the core of an n -person game without side-payments , author=. SIAM Journal on Applied Mathematics , volume=. 1970 , doi=

    1970

  31. [31]

    Discrete Applied Mathematics , volume=

    Minimal balanced collections and their application to core stability and other topics of game theory , author=. Discrete Applied Mathematics , volume=. 2023 , doi=

    2023

  32. [32]

    2004 , issn =

    A necessary and sufficient condition for non-emptiness of the core of a non-transferable utility game , journal =. 2004 , issn =. doi:10.1016/S0022-0531(03)00261-8 , author =

    work page doi:10.1016/s0022-0531(03)00261-8 2004

  33. [33]

    Proceedings of the 18th International Conference on Web and Internet Economics (WINE) , pages=

    Core-Stable Committees under Restricted Domains , author=. Proceedings of the 18th International Conference on Web and Internet Economics (WINE) , pages=. 2022 , doi =

    2022

  34. [34]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages=

    Approximately Stable Committee Selection , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages=. 2020 , doi =

    2020

  35. [35]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Approximate Core for Committee Selection via Multilinear Extension and Market Clearing , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , doi =

    2022

  36. [36]

    ACM Transactions on Economics and Computation (TEAC) , articleno =

    Cheng, Yu and Jiang, Zhihao and Munagala, Kamesh and Wang, Kangning , title =. ACM Transactions on Economics and Computation (TEAC) , articleno =. 2020 , publisher =

    2020

  37. [37]

    2025 , booktitle =

    Peters, Dominik , title =. 2025 , booktitle =

    2025

  38. [38]

    Three Little-Known and Yet Still Significant Contributions of

    Zhao, Jingang , journal=. Three Little-Known and Yet Still Significant Contributions of. 2018 , doi=

    2018

  39. [39]

    1955 , institution=

    Markets as Cooperative Games , author=. 1955 , institution=

    1955

  40. [40]

    Vestnik Leningrad

    The theory of the core in an n-person game , author=. Vestnik Leningrad. Univ , volume=

  41. [41]

    , title =

    Shapley, Lloyd S. , title =. Naval Research Logistics Quarterly , volume =

  42. [42]

    Ein Satz über Untermengen einer endlichen Menge , volume =

    Sperner, Emanuel , journal =. Ein Satz über Untermengen einer endlichen Menge , volume =

  43. [43]

    Transactions of the American Mathematical Society , volume=

    The Core of a Cooperative Game without Side Payments , author=. Transactions of the American Mathematical Society , volume=. 1961 , doi=

    1961

  44. [44]

    The Core in Participatory Budgeting Can Be Empty , volume =

    Jan Maly , journal =. The Core in Participatory Budgeting Can Be Empty , volume =. 2025 , doi =

    2025

  45. [45]

    2026 , eprint=

    Ordinal Lindahl Equilibrium for Voting , author=. 2026 , eprint=

    2026

  46. [46]

    2026 , publisher=

    Approximate Core of Participatory Budgeting via Lindahl Equilibrium , author=. 2026 , publisher=

    2026

  47. [47]

    2025 , eprint=

    Computation of Approximately Stable Committees in Approval-Based Elections , author=. 2025 , eprint=

    2025

  48. [48]

    Richard Dedekind , journal=

  49. [49]

    Universitatis Iagellonicae Acta Mathematica , volume =

    Winfried Bruns and Robert Koch , title =. Universitatis Iagellonicae Acta Mathematica , volume =. 2001 , pages =

    2001

  50. [50]

    The Range of the Determinant Function on the Set of n n (0,1) -Matrices , volume =

    Craigen, Rob , year =. The Range of the Determinant Function on the Set of n n (0,1) -Matrices , volume =. Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC) , url =

  51. [51]

    atzungen f\

    Hartmut Ehlich , year =. Determinantenabsch\"atzungen f\"ur bin\"are. Mathematische Zeitschrift , url =

  52. [52]

    Mathematical Programming , volume=

    Markus Brill and Paul G\"olz and Dominik Peters and Ulrike Schmidt-Kraepelin and Kai Wilker , title=. Mathematical Programming , volume=. 2024 , pages=

    2024

  53. [53]

    Proceedings of the 24th ACM Conference on Economics and Computation (EC) , pages =

    Markus Brill and Jannik Peters , title =. Proceedings of the 24th ACM Conference on Economics and Computation (EC) , pages =. 2023 , doi =

    2023

  54. [54]

    On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting , booktitle =

    Berker, Ratip and Tewolde, Emanuel and Conitzer, Vincent and Guo, Mingyu and Heule, Marijn and Xia, Lirong , year =. On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting , booktitle =

  55. [55]

    Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI) , author=

    Voting in Divisible Settings: A Survey , volume=. Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI) , author=. 2026 , pages=

    2026

  56. [56]

    2025 , eprint=

    A Linear Theory of Multi-Winner Voting , author=. 2025 , eprint=

    2025

  57. [57]

    Thiele , title =

    Thorvald N. Thiele , title =. Oversigt over det Kongelige Danske Videnskabernes Selskabs Fordhandlinger , year =

  58. [58]

    Winfried Bruns and Bogdan Ichim and Christof S\"oger and Ulrich von der Ohe , title =

  59. [59]

    H. W. Lenstra , journal =. Integer Programming with a Fixed Number of Variables , volume =