Pith. sign in

REVIEW 5 minor 51 references

Candidate Resignation Monotonicity in Approval-Based Committee Elections

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

Pith's one-line read This paper proves that no approval-based committee rule can satisfy both resignation monotonicity and justified representation, and constructs a maximum-flow rule that recovers the stronger PJR+ guarantee after resignations.

desk verdict A clean, well-proved theory paper that introduces a natural new axiom, proves a strong incompatibility, and offers a new rule (MPR) that is likely to become a reference point. read the letter →

arxiv 2608.06156 v1 pith:YH7FWUUL submitted 2026-08-06 cs.GT

classification cs.GT MSC 91B1291B1405C2168Q17
keywords approval-basedcommitteeelectionsresignationmonotonicityjustifiedrepresentationmaximumflowproportionalityaxiomsstrategiccandidacyMonroeruleNP-hardness
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

Approval-based committee elections pick a fixed-size set of winners, and when an elected member resigns, the natural demand is that everyone else who won keeps their seat when the election is re-run. The paper formalizes this as resignation monotonicity and proves a stark incompatibility: no rule can be resignation monotone and satisfy justified representation (JR), the weakest standard proportionality axiom. The escape is to lower the demand from "the rule itself must keep all survivors" to "some proportional committee containing all survivors exists after resignations." The paper constructs the Maximum Payment Rule (MPR), which maximizes the value of a maximum flow in the approval network, and proves it satisfies this relaxed property for the stronger axiom PJR+. If the paper is right, committees can be made resilient to resignations, but only by abandoning strict resignation monotonicity or by allowing fractional committees.

What carries the argument

The load-bearing object is the network representation of an election: a flow network with source $s$, a node per voter with capacity $k/n$ from $s$, infinite-capacity edges from voters to candidates they approve, and capacity-1 edges from candidates to sink $t$. A committee $W$ is scored by $\phi(W)$, the value of a maximum flow through the subnetwork restricted to $W$; fractional versions of the same network characterize GRP committees. The arguments run on flow augmentation: when winners resign, deleting their flow and augmenting along paths can only weakly increase flow to surviving winners, and if a replacement committee's total flow fell below the original, some replacement candidate has flow less than 1, which yields an improving swap that contradicts local payment-maximality and hence forces PJR+. The same network gives MPR its algorithmic profile: it is NP-hard to compute in general, polynomial-time on voter-interval and candidate-interval domains via the Monroe connection, and FPT in the number of voters.

What would settle it

To falsify the central impossibility, exhibit any approval-based committee rule that outputs a committee satisfying JR on every instance and, whenever an elected candidate resigns, always outputs a committee containing every other previous winner. To test the MPR recovery guarantee, enumerate small instances, compute an MPR committee $W$, delete each $T\subseteq W$, and check whether any committee $(W\setminus T)\cup T'$ with $|T'|=|T|$ satisfies PJR+ in the resigned instance; a counterexample would disprove Theorem 5.2.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.4: there is no resignation monotone ABC rule satisfying JR. The proof adapts a robust-decremental impossibility for PJR+ from the dynamic-candidate-set literature and forces any JR committee through an adaptive sequence of resignations that ends in a two-pair obstruction where a single replacement cannot cover all uncovered voter pairs whose common candidate has resigned. On the positive side, the paper shows that fractional committees escape the impossibility: the rule outputting all GRP committees is resignation monotone, because GRP committees are exactly those extending a maximum flow, and after deleting resigned candidates one can augment the flow without decreasing any remaining candidate's flow. For integral committees, the paper proposes MPR, which selects committees $W$ maximizing the maximum flow value $\phi(W)$ in the network representation, and proves MPR is PJR+-resignation monotone: after any resignation $T$, some committee $(W\setminus T)\cup T'$ satisfies PJR+. MPR is the unique homogeneous rule that coincides with Monroe when $k$ divides $n$, induces the largest remainder method on party-list instances, and satisfies perfect representation, so it fails EJR+.

Load-bearing premise

The paper fixes the election model so that a resignation only removes the resigned candidates from the candidate set and from every ballot, keeps the committee size $k$ and the voter set unchanged, and requires all non-resigning winners to stay winners; if instead vacant seats may go unfilled or voters update their approvals after a resignation, the impossibility and the MPR recovery guarantee need not hold.

Editorial extensions

If this is right

  • Any rule that offers even the weakest proportional guarantee (JR) will sometimes drop a surviving winner after a resignation, so a strict "never remove winners" policy forces Approval Voting or another non-proportional rule.
  • MPR guarantees that after any resignation, a PJR+ committee extending all surviving winners exists, and such a replacement committee can be computed in polynomial time once the original committee is known.
  • In fractional committee voting, proportionality and resignation monotonicity are compatible: the GRP rule is resignation monotone, so the incompatibility is an artifact of integrality.
  • On party-list instances MPR reduces to the largest remainder apportionment method, so it inherits the usual quota properties of Hamilton's method while also satisfying PJR+.
  • Resignation monotone rules that are independent of losers are immune to a losing candidate introducing new weak candidates to get elected, while PAV is vulnerable to this manipulation.

Reading between the lines

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

  • Since PJR+ is stronger than JR, the impossibility for JR suggests that no integral rule can satisfy both strict resignation monotonicity and any proportional axiom, so MPR's relaxed guarantee is essentially the best an integral rule can offer.
  • The Monroe characterization suggests a recipe: any homogeneous extension of a proportional apportionment method built from a flow-maximization network could inherit similar resignation recovery properties; testing this on other apportionment methods is a natural next step.
  • In practice, a rule like MPR would need to publish the flow certificate for the original committee, because finding replacement candidates is much easier with it than without it, as the comparison between MPR and MCAR indicates.
  • The strategic candidacy result suggests a new design criterion: if a rule is resignation monotone and independent of losers, it automatically resists candidate-controlled ballot stuffing, which may be a useful robustness check beyond the usual candidate-monotonicity axioms.
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

0 major / 5 minor

Summary. The paper introduces resignation monotonicity for approval-based committee elections: after a subset T of the winning candidates resigns, re-running the rule on the reduced instance must keep all non-resigning winners in some output committee. Section 3 shows that among Thiele and sequential Thiele rules only AV is resignation monotone (Theorem 3.1), and proves the central impossibility that no rule can satisfy both resignation monotonicity and justified representation (Theorem 3.4). Section 4 shows that in the fractional committee world the maximum-flow-based GRP rule is resignation monotone (Theorem 4.2). Section 5 introduces the Maximum Payment Rule (MPR), proves it satisfies the relaxed PJR+-resignation monotonicity (Theorem 5.2), establishes NP-hardness in general with tractable structured and bounded-resignation cases, and characterizes MPR as the unique homogeneous extension of Monroe when k divides n (Theorem 5.8). Section 6 introduces a second rule, MCAR, also PJR+-resignation monotone, with a greedy algorithm for voter-interval instances. Section 7 connects resignation monotonicity to strategic candidacy, showing that resignation monotone rules that are independent of losers are candidacy strategyproof while PAV is manipulable. The appendix contains full proofs and experiments measuring how often PAV and MES fail resignation monotonicity.

Significance. If the results hold, the paper settles a natural open question: JR is incompatible with retaining all surviving winners after resignations, and this is tight because the weaker PJR+ can be recovered by the newly designed MPR and MCAR. The fractional result (Theorem 4.2) and the characterization of MPR as the homogeneous Monroe extension (Theorem 5.8) are elegant and give the rules independent interest beyond the resignation setting. The proofs are thorough: Theorem 3.4's adaptive adversarial case analysis and the flow-augmentation arguments in Theorems 4.2 and 5.2 are careful and internally consistent, and the computational hardness/tractability statements are standard but complete. The experimental appendix provides useful quantitative context for how often common rules fail in practice. Overall this is a strong contribution to computational social choice.

minor comments (5)
  1. [Abstract / Section 7] The metadata abstract states that all resignation monotone rules are immune to strategic candidacy, while Proposition 7.1 requires the additional independence-of-losers condition; the full-text abstract correctly includes the qualifier. Please reconcile the two abstracts.
  2. [Theorem 5.2] In the case val(f') ≥ val(f), the sentence that W' is payment-maximizing for E and therefore also for E−T skips the needed argument that φ_{E−T}(W'') ≤ φ_{E−T}(W') for every committee W''; adding the one-line subnetwork argument would improve verifiability.
  3. [Theorem 5.5] The assertion that the proof of Theorem 5.2 goes through with a 1-locally payment-maximizing replacement is terse; a brief explanation that the contradiction in Theorem 5.2 uses only a single swap (replacing one c' ∈ T') would help the reader follow the reduction.
  4. [Proposition 7.3] For the MES case, the 'first time' argument should explicitly note that if a weak candidate c' ∈ T with N(c') ⊆ N(c) is taken before c, then c and c' have equal effective prices, so there exists a tie-breaking in which c is taken first; this is implicit in the current wording.
  5. [Appendix A] The experimental plots do not report confidence intervals or standard errors for the estimated probabilities; given the parameter sweep, a brief statement about Monte Carlo uncertainty would be useful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the impossibility and recovery results are derived from stated assumptions with self-contained proofs.

full rationale

The paper's central derivation chain is self-contained. Theorem 3.4 is proved by a detailed K12 case analysis in Appendix B.2, explicitly extending—rather than merely importing—the Dong and J. Peters (2025) PJR+ impossibility to JR; the cited prior work is not co-authored by the present authors and the proof is reproduced. Theorem 5.2 establishes PJR+-resignation monotonicity of MPR through a max-flow augmenting-path argument, and Lemma 5.1 derives PJR+ from payment-maximality without assuming the conclusion. The fractional result (Theorem 4.2) uses the Suzuki and Vollen (2024) max-flow characterization of GRP as an external lemma, and the recovery is proven via flow augmentation and capacity accounting. The NP-hardness and tractability results reduce from X3C and use Lenstra's fixed-dimension ILP algorithm, both standard external benchmarks. The only self-citations (e.g., D. Peters and Skowron 2020 for MES and EJR+) are used for standard definitions and background, not as load-bearing support for the new theorems. The fixed-preference, fixed-quota model after resignations is explicitly stated in Section 3 and is a scope condition, not a circular assumption. No step quotes an equation or prior result that reduces, by construction, to the claim being derived.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

No fitted parameters appear in this theory paper. The axioms are standard mathematical results or explicit modeling assumptions. MPR and MCAR are new constructs whose properties are established by internal proofs, with no external falsifiable handles.

assumptions (6)
  • standard math Max-flow min-cut theorem
    Used in Lemma 4.1 (from Suzuki and Vollen 2024), Lemma 6.6, and the proofs of Theorems 5.2 and 5.3.
  • standard math Hall's marriage theorem
    Used in the generalized Hall condition of Lemma 6.6 to characterize affordable sets.
  • standard math X3C is NP-complete
    Used in the reduction for MPR-Threshold NP-hardness (Theorem 5.3).
  • standard math Lenstra's fixed-dimension integer programming algorithm
    Used in Theorem 5.12 to show FPT parameterized by number of voters.
  • domain assumption Fixed committee size and static approval sets under resignations
    Section 3 models a resignation by deleting candidates from the candidate set and from approval ballots, keeping k and N fixed; all results are relative to this model.
  • domain assumption Subset candidacy model: new candidates' supporters are subsets of the manipulator's supporters (S3)
    Section 7 defines subset candidacy strategyproofness under this restriction; the results on immunity depend on it.
invented entities (2)
  • Maximum Payment Rule (MPR)
    purpose: Integral maximum-flow-based voting rule that is PJR+-resignation monotone and the unique homogeneous extension of the Monroe rule.
    Introduced in Section 5.1; its properties are established by internal proofs, with no external falsifiable handle.
  • Maximum-Cardinality Affordable Rule (MCAR)
    purpose: Alternative PJR+-resignation monotone rule based on maximum-cardinality affordable sets.
    Introduced in Section 6; properties proven in-paper with no external evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Candidate Resignation Monotonicity in Approval-Based Committee Elections." pith.science (2026). https://pith.science/paper/YH7FWUUL

@misc{pith2026260806156,
  author       = {Pith},
  title        = {Pith review of: Candidate Resignation Monotonicity in Approval-Based Committee Elections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YH7FWUUL}},
  note         = {Machine review of arXiv:2608.06156}
}
read the original abstract

Approval-based committee (ABC) elections select a fixed-size committee of candidates based on voters' approval preferences. We study a setting where elected members may resign and formalize resignation monotonicity: when we re-run the voting rule after resignations, a resignation monotone rule must still elect all remaining previously winning candidates. We show that many prominent ABC rules fail this property, and by connecting our notion to prior work on ABC elections with dynamic candidate sets, we show that the justified representation (JR) axiom is incompatible with resignation monotonicity. It turns out that fractional committee voting does not suffer from this issue: rules based on using maximum flows in the network representation of an election instance can satisfy both representation axioms and resignation monotonicity. We design an integral version of maximum flow, the Maximum Payment Rule (MPR), and show that it satisfies a relaxed form of resignation monotonicity that only requires there to be some way of replacing the resigning candidates in a way that guarantees the PJR+ axiom. MPR is NP-hard to compute in general, but becomes tractable in structured domains. Finally, we study a strategic setting where a losing candidate may introduce new weak candidates to the election to try to become a winner. We show that all resignation monotone rules as well as many sequential rules are immune, but that the PAV rule can be manipulated in this way.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 48 canonical work pages

  1. [1]

    Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages=

    Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting , author=. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages=. 2019 , doi=

  2. [2]

    Control and Bribery in Voting , booktitle=

    Faliszewski, Piotr and Rothe, Jörg , year=. Control and Bribery in Voting , booktitle=

  3. [3]

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

    Multiwinner Voting with Possibly Unavailable Candidates , author=. Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI) , pages=. 2023 , doi=

  4. [4]

    2026 , booktitle =

    Reconfiguring Proportional Committees , author=. 2026 , booktitle =. 2504.15157 , archivePrefix =

  5. [5]

    2025 , eprint=

    Preference Restrictions in Computational Social Choice: A Survey , author=. 2025 , eprint=

  6. [6]

    Operations Research , volume=

    A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs , author=. Operations Research , volume=. 1986 , doi=

  7. [7]

    and Kilgour, D

    Brams, Steven J. and Kilgour, D. Marc , title =. Mathematical and Computational Modeling , chapter =. doi:10.1002/9781118853887.ch11 , year =

  8. [8]

    Mathematical Programming , volume =

    Approval-Based Apportionment , author =. Mathematical Programming , volume =. 2024 , doi =

Show all 51 references
  1. [9]

    Ofversigt af Kongliga Vetenskaps-Akademiens F\

    E. Phragm. Sur une m. \"Ofversigt af Kongliga Vetenskaps-Akademiens F\"orhandlingar , Number = 3, Pages =. 1894 , url_hidden =

  2. [10]

    Proceedings of the 42nd International Conference on Machine Learning (ICML) , year =

    Maintaining Proportional Committees with Dynamic Candidate Sets , author =. Proceedings of the 42nd International Conference on Machine Learning (ICML) , year =

  3. [11]

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

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

  4. [12]

    2020 , booktitle =

    Peters, Dominik and Skowron, Piotr , title =. 2020 , booktitle =. doi:10.1145/3391403.3399465 , eprint =

  5. [13]

    Social Choice and Welfare , year =

    Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh , title =. Social Choice and Welfare , year =

  6. [14]

    On the Complexity of Extended and Proportional Justified Representation , booktitle =

    Haris Aziz and Edith Elkind and Shenwei Huang and Martin Lackner and Luis S. On the Complexity of Extended and Proportional Justified Representation , booktitle =. 2018 , pages =

  7. [15]

    Thiele , journal =

    Thorvald N. Thiele , journal =. Om Flerfoldsvalg , year =

  8. [16]

    2023 , publisher=

    Multi-Winner Voting with Approval Preferences , author=. 2023 , publisher=. doi:10.1007/978-3-031-09016-5 , series=

  9. [17]

    Proportional Participatory Budgeting with Additive Utilities , volume =

    Peters, Dominik and Pierczy\'. Proportional Participatory Budgeting with Additive Utilities , volume =. Advances in Neural Information Processing Systems (NeurIPS) , pages =. 2021 , eprint =

  10. [18]

    Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI) , pages =

    Dominik Peters , title =. Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI) , pages =. 2025 , doi =

  11. [19]

    2023 , volume =

    Martin Lackner and Peter Regner and Benjamin Krenn , doi =. 2023 , volume =

  12. [20]

    and Johnson, David S

    Garey, Michael R. and Johnson, David S. , title =. 1979 , publisher =

  13. [21]

    Jackson and Michel Le Breton , journal =

    Bhaskar Dutta and Matthew O. Jackson and Michel Le Breton , journal =. Strategic Candidacy and Voting Procedures , volume =. 2001 , doi =

  14. [22]

    Jackson and Michel

    Bhaskar Dutta and Matthew O. Jackson and Michel. Voting by Successive Elimination and Strategic Candidacy , journal =. 2002 , doi =

  15. [23]

    2021 , doi =

    Skowron, Piotr , title =. 2021 , doi =

  16. [24]

    Proceedings of the 3rd ACM Conference on Advances in Financial Technologies (AFT) , pages =

    Cevallos, Alfonso and Stewart, Alistair , title =. Proceedings of the 3rd ACM Conference on Advances in Financial Technologies (AFT) , pages =. 2021 , doi =

  17. [25]

    Social Choice and Welfare , year =

    Elkind, Edith and Faliszewski, Piotr and Skowron, Piotr and Slinko, Arkadii , title =. Social Choice and Welfare , year =

  18. [26]

    Monotonicity Axioms in Approval-Based Multi-Winner Voting Rules , year =

    S\'. Monotonicity Axioms in Approval-Based Multi-Winner Voting Rules , year =. Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =

  19. [27]

    Proportional Justified Representation , year =

    S\'. Proportional Justified Representation , year =. Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI) , pages =

  20. [28]

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

    Bullinger, Martin and Dong, Chris and Lederer, Patrick and Mehler, Clara , title =. Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , pages=. 2024 , doi =

  21. [29]

    Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) , year =

    Online Approval Committee Elections , author =. Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) , year =. doi:10.24963/ijcai.2022/36 , pages =

  22. [30]

    Multi-Winner Reconfiguration , url =

    Chen, Jiehua and Hatschka, Christian and Simola, Sofia , booktitle =. Multi-Winner Reconfiguration , url =. 2024 , doi =

  23. [31]

    2021 , doi =

    Consistent Approval-Based Multi-Winner Rules , journal =. 2021 , doi =

  24. [32]

    Brill, Markus and Freeman, Rupert and Janson, Svante and Lackner, Martin , booktitle =. Phragm. 2017 , doi =

  25. [33]

    Brill, Markus and Freeman, Rupert and Janson, Svante and Lackner, Martin , journal =. Phragm. 2024 , doi =

  26. [34]

    2015 , booktitle =

    Elkind, Edith and Lackner, Martin , title =. 2015 , booktitle =

  27. [35]

    Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , year =

    Markus Brill and Jannik Peters , title =. Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , year =

  28. [36]

    and Trick, Michael A

    Bartholdi, John and Tovey, Craig A. and Trick, Michael A. , title =. Mathematical and Computer Modelling , volume =. 1992 , doi =

  29. [37]

    Journal of Artificial Intelligence Research , volume =

    Elkind, Edith and Faliszewski, Piotr and Slinko, Arkadii , title =. Journal of Artificial Intelligence Research , volume =. 2011 , doi =

  30. [38]

    The Complexity of Cloning Candidates in Multiwinner Elections , booktitle =

    Neveling, Marc and Rothe, J. The Complexity of Cloning Candidates in Multiwinner Elections , booktitle =. 2020 , url =

  31. [39]

    Journal of Economic Theory , volume =

    Florian Brandl and Dominik Peters , title =. Journal of Economic Theory , volume =. 2022 , doi =

  32. [40]

    Journal of Economic Theory , volume =

    Felix Brandt and Paul Harrenstein , title =. Journal of Economic Theory , volume =. 2011 , doi =

  33. [41]

    2023 , booktitle =

    Dong, Chris and Lederer, Patrick , title =. 2023 , booktitle =

  34. [42]

    Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) , pages =

    How to Sample Approval Elections? , author =. Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) , pages =. 2022 , doi =

  35. [43]

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

    Suzuki, Mashbat and Vollen, Jeremy , title =. Proceedings of the 25th ACM Conference on Economics and Computation (EC) , pages =. 2024 , doi =

  36. [44]

    Proceedings of the 19th Conference on Web and Internet Economics (WINE) , year =

    Aziz, Haris and Lu, Xinhang and Suzuki, Mashbat and Vollen, Jeremy and Walsh, Toby , title =. Proceedings of the 19th Conference on Web and Internet Economics (WINE) , year =

  37. [45]

    2026 , eprint =

    Beyond Lower Quota: Avoiding Overrepresentation in Multi-Winner Voting , author =. 2026 , eprint =

  38. [46]

    , title =

    Monroe, Burt L. , title =. American Political Science Review , volume =. 1995 , month = dec, doi =

  39. [47]

    Journal of Artificial Intelligence Research , volume =

    Betzler, Nadja and Slinko, Arkadii and Uhlmann, Johannes , title =. Journal of Artificial Intelligence Research , volume =

  40. [48]

    Proceedings of the 26th European Conference on Artificial Intelligence (ECAI) , series =

    Chen, Jiehua and Hatschka, Christian and Simola, Sofia , title =. Proceedings of the 26th European Conference on Artificial Intelligence (ECAI) , series =. 2023 , doi =

  41. [49]

    , title =

    Lenstra, Hendrik W. , title =. Mathematics of Operations Research , volume =. 1983 , doi =

  42. [50]

    2026 , eprint =

    An Axiomatic Analysis of Proportionality Notions in Approval-Based Multiwinner Voting , author =. 2026 , eprint =

  43. [51]

    Multiwinner Approval Rules as Apportionment Methods , journal =

    Markus Brill and Jean. Multiwinner Approval Rules as Apportionment Methods , journal =. 2018 , doi =

Pith tools

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