Pith. sign in

REVIEW 1 major objections 1 minor 1 cited by

In Candidate Interval and Voter Interval domains, Pareto optimal committees satisfy monotonicity and can be reconfigured one candidate at a time without auxiliaries.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-29 00:15 UTC pith:47W4SFJE

load-bearing objection The paper gives a clean characterization of Pareto optimality via Single Dominance Only on Candidate Interval and Voter Interval domains plus polynomial algorithms for monotonicity, reconfiguration, and counting, but the general-domain claims stay open and the key equivalence needs checking. the 1 major comments →

arxiv 2605.30490 v1 pith:47W4SFJE submitted 2026-05-28 cs.GT

Pareto Optimality in Approval-Based Multiwinner Voting

Joshua Sch\"unke (Hasso Plattner Institute , University of Potsdam) This is my paper
classification cs.GT
keywords Pareto optimalityapproval votingmultiwinner votingcommittee monotonicityreconfigurationinterval domainsproportionality
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper studies the structure of Pareto optimal committees in approval-based multiwinner voting. It restricts attention to Candidate Interval and Voter Interval domains and introduces the Single Dominance Only property as a characterization of Pareto optimality. This property is then used to prove that Pareto optimal committees are committee-monotonic. The same property supports a reconfiguration result: any Pareto optimal committee can be transformed into any other by successive single-candidate swaps that preserve Pareto optimality at every step and use no auxiliary candidates. The work also gives polynomial-time algorithms for finding an EJR+-satisfying Pareto optimal committee and for counting all Pareto optimal committees under Voter Interval preferences, while outlining why the same claims remain open in the unrestricted setting.

Core claim

In the Candidate Interval and Voter Interval domains, the Single Dominance Only property provides a simple characterization of Pareto optimality. Using this property, the paper shows that Pareto optimal committees satisfy committee monotonicity and that any two Pareto optimal committees can be reconfigured into each other by replacing candidates from the symmetric difference one by one while preserving Pareto optimality throughout and without introducing auxiliary candidates.

What carries the argument

The Single Dominance Only property, which characterizes Pareto optimality by ensuring that no candidate outside the committee strictly dominates a candidate inside it under the interval structure.

Load-bearing premise

The voting instances are restricted to Candidate Interval or Voter Interval domains.

What would settle it

A concrete Candidate Interval or Voter Interval instance containing two Pareto optimal committees that cannot be transformed into each other by single-candidate Pareto-preserving swaps would falsify the reconfiguration claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Pareto optimal committees satisfy committee monotonicity in these domains.
  • Any Pareto optimal committee can be reconfigured to any other Pareto optimal committee by single-candidate swaps without auxiliary candidates.
  • A polynomial-time algorithm finds a committee that satisfies both EJR+ and Pareto optimality.
  • The number of Pareto optimal committees can be counted in polynomial time for Voter Interval instances.

Where Pith is reading between the lines

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

  • The reconfiguration result implies that the Pareto optimality graph is connected with diameter bounded by the symmetric difference size in these domains.
  • The same structural property may allow efficient local search or enumeration algorithms for other efficiency-related axioms.
  • The explicit counter-example distance in the unrestricted domain suggests that any general proof would require a different technique or additional auxiliary candidates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The paper studies the structure of Pareto optimal (PO) committees in approval-based multiwinner voting. For Candidate Interval and Voter Interval domains it introduces the Single Dominance Only property as a characterization of PO, derives committee monotonicity and reconfiguration of any PO committee to any other PO committee without auxiliary candidates, adapts a polynomial-time algorithm to find a PO committee satisfying EJR+, gives a polynomial-time counting algorithm for PO committees under Voter Interval, and outlines challenges plus an example for the unrestricted domain.

Significance. If the claimed characterization and derived results hold, the work supplies concrete structural and algorithmic tools for restricted domains that arise in applications. The polynomial algorithms for EJR+ with PO and for counting PO committees, together with the explicit discussion of the reconfiguration graph, constitute reusable contributions to computational social choice.

major comments (1)
  1. [section introducing Single Dominance Only] The section introducing the Single Dominance Only property: the claim that this property is equivalent to Pareto optimality (necessary and sufficient) is load-bearing for the subsequent committee-monotonicity and reconfiguration-without-auxiliaries theorems. The proof must be inspected to confirm both directions hold for all instances satisfying the interval restrictions, including degenerate cases where multiple candidates share identical approval sets or where the interval structure collapses at the boundary.
minor comments (1)
  1. [section on counting Pareto optimal committees] The counting algorithm for Voter Interval is supported only by a proof idea; a complete, self-contained proof would strengthen the result without altering its scope.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our contributions on the structure of Pareto optimal committees in approval-based multiwinner voting and for the detailed comment. We address the concern regarding the Single Dominance Only characterization below.

read point-by-point responses

  1. Referee: [section introducing Single Dominance Only] The section introducing the Single Dominance Only property: the claim that this property is equivalent to Pareto optimality (necessary and sufficient) is load-bearing for the subsequent committee-monotonicity and reconfiguration-without-auxiliaries theorems. The proof must be inspected to confirm both directions hold for all instances satisfying the interval restrictions, including degenerate cases where multiple candidates share identical approval sets or where the interval structure collapses at the boundary.

    Authors: We appreciate the referee's emphasis on verifying both directions of the equivalence in all cases, including degeneracies. The proof of the characterization (Theorem 3.1) relies on the interval representation of approvals and proceeds by contradiction for necessity and by direct construction for sufficiency. When multiple candidates share identical approval sets, they occupy the same position in the interval ordering and are interchangeable; the single-dominance condition applies uniformly without violation. Boundary collapses (degenerate intervals of length zero) are subsumed by the general interval definition used in the domain restrictions, and the logical steps remain valid as no step assumes positive length or distinct sets. We have re-examined the proof and confirm it holds without additional assumptions. If a concrete counterexample is identified, we will address it directly. revision: no

Circularity Check

0 steps flagged

No circularity; new characterization derived from definitions in restricted domains

full rationale

The paper defines Pareto optimality in the standard way for approval-based multiwinner voting and introduces Single Dominance Only as a proposed equivalent property specifically for Candidate Interval and Voter Interval domains. It then proves monotonicity and reconfiguration results from that characterization. This is a direct axiomatic derivation from the domain restrictions and the definition of Pareto optimality, with no self-referential equations, fitted parameters renamed as predictions, or load-bearing self-citations. The unrestricted-domain challenges are explicitly left open. All steps are self-contained against the paper's own definitions and proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard mathematical definitions of Pareto optimality, committee monotonicity, and interval domains; the Single Dominance Only property is introduced as a derived characterization rather than an independent axiom or entity.

axioms (2)
  • standard math Standard definitions of approval profiles, committees, and Pareto dominance in social choice theory
    Invoked throughout to define the objects of study.
  • domain assumption Interval domain restrictions (Candidate Interval, Voter Interval) admit linear orderings of candidates or voters
    Central to all positive results; the paper notes these do not hold in the general case.

pith-pipeline@v0.9.1-grok · 5784 in / 1379 out tokens · 26824 ms · 2026-06-29T00:15:52.303790+00:00 · methodology

0 comments
read the original abstract

In approval-based multiwinner voting, Pareto optimality is used as an axiom capturing efficiency of committees. We study the structure of the space of Pareto optimal committees in restricted domains and in general by investigating the monotonicity and reconfigurability of such committees. For the Candidate Interval and Voter Interval domains, we propose the Single Dominance Only property, which provides a simple characterization of Pareto optimality, and show that Pareto optimal committees satisfy committee monotonicity using this property. Further, we show that, for the above domains, any Pareto optimal committee can be reconfigured into any other Pareto optimal target committee without using auxiliary candidates, meaning that the candidates in the starting but not the target committee can be replaced by candidates in the target but not the starting committee one by one while preserving Pareto optimality at every step. In addition, we adapt a polynomial-time algorithm for finding a committee satisfying EJR+, a proportionality axiom, such that it also satisfies Pareto optimality, for the above domains. We further describe a polynomial-time algorithm for counting the number of Pareto optimal committees for voting instances satisfying Voter Interval, and give a proof idea for its correctness. For the unrestricted domain, we explain the challenges of proving committee monotonicity and reconfigurability. We provide an example in which the distance of two committees in the Pareto optimality reconfiguration graph exceeds the distance proven for the above domains, and outline an approach toward showing the connectedness of the graph.

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Fractional Pareto-Optimality in Multiwinner Voting

    cs.GT 2026-06 unverdicted novelty 6.0

    Defines fractional Pareto-optimality (fPO) in multiwinner voting via a weighted welfare characterization that enables poly-time verification, committee monotonicity, and shows PAV violates it.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages · cited by 1 Pith paper

  1. [1]

    Computing and testing pareto optimal committees

    Haris Aziz and J \'e r \^o me Monnot. Computing and testing pareto optimal committees. Autonomous Agents and Multi-Agent Systems, 2020. doi:10.1007/s10458-020-09445-y

    work page doi:10.1007/s10458-020-09445-y 2020

  2. [2]

    Computational aspects of multi-winner approval voting

    Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. International Foundation for Autonomous Agents and Multiagent Systems, 2015

    2015

  3. [3]

    Justified representation in approval-based committee voting

    Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 2017. doi:10.1007/s00355-016-1019-3

    work page doi:10.1007/s00355-016-1019-3 2017

  4. [4]

    Brams and Peter C

    Steven J. Brams and Peter C. Fishburn. Approval voting. American Political Science Review, 1978. doi:10.2307/1955105

    work page doi:10.2307/1955105 1978

  5. [5]

    Robust and verifiable proportionality axioms for multiwinner voting

    Markus Brill and Jannik Peters. Robust and verifiable proportionality axioms for multiwinner voting. Proceedings of the 24th ACM Conference on Economics and Computation, 2023. doi:10.1145/3580507.3597785

    work page doi:10.1145/3580507.3597785 2023

  6. [6]

    Reconfiguring proportional committees

    Chris Dong, Fabian Frank, Jannik Peters, and Warut Suksompong. Reconfiguring proportional committees. CoRR, 2025. doi:10.48550/ARXIV.2504.15157

    work page doi:10.48550/arxiv.2504.15157 2025

  7. [7]

    Structure in dichotomous preferences

    Edith Elkind and Martin Lackner. Structure in dichotomous preferences. Proceedings of the 24th International Conference on Artificial Intelligence, 2015

    2015

  8. [8]

    Multi-Winner Voting with Approval Preferences

    Martin Lackner and Piotr Skowron. Multi-Winner Voting with Approval Preferences. 2023. doi:10.1007/978-3-031-09016-5

    work page doi:10.1007/978-3-031-09016-5 2023

  9. [9]

    Ngatchou, A

    P. Ngatchou, A. Zarei, and A. El-Sharkawi. Pareto multi objective optimization. Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems, 2005. doi:10.1109/ISAP.2005.1599245

    work page doi:10.1109/isap.2005.1599245 2005

  10. [10]

    28 Sang-il Oum and Paul D

    Naomi Nishimura. Introduction to reconfiguration. Algorithms, 2018. doi:10.3390/a11040052

    work page doi:10.3390/a11040052 2018

  11. [11]

    Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections

    Dominik Peters. Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections. Proceedings of the AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/aaai.v32i1.11460

    work page doi:10.1609/aaai.v32i1.11460 2018

  12. [12]

    Facets of proportionality

    Jannik Peters. Facets of proportionality. Phd thesis, Technische Universit\"at Berlin, 2025

    2025