Pith. sign in

REVIEW 1 major objections 46 references

Fractional Pareto-Optimality in Multiwinner Voting

T0 review · 1 major / 0 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read Fractional Pareto-optimality equals weighted utilitarian welfare maximization for some weights.

desk verdict The paper defines fPO and characterizes it via weighted utilitarian welfare, which directly yields a poly-time check plus monotonicity and connectedness; the cloning motivation is secondary and not load-bearing for the results. read the letter →

arxiv 2606.11160 v1 pith:4Y2HA4PJ submitted 2026-06-09 cs.GT

Patrick Becker , Niclas Boehmer , Fabian Frank , Lara Glessen This is my paper
classification cs.GT
keywords multiwinnervotingParetooptimalityfractionalutilitarianwelfarecommitteemonotonicityapprovalPAVone-dimensionalpreferences
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

The paper introduces fractional Pareto-optimality to refine the standard notion of Pareto-optimality in multiwinner voting, requiring that no committee is dominated by a convex combination of other committees. This captures committees whose efficiency holds up when candidates are cloned uniformly. The core contribution is a characterization showing that fPO committees are exactly those that maximize weighted utilitarian welfare for appropriate positive weights. This equivalence directly produces a polynomial-time verification procedure and establishes that fPO committees are monotone with respect to committee size and connected via single-candidate swaps.

What carries the argument

The equivalence between fPO and maximization of weighted utilitarian welfare for some positive weights, which converts dominance checks into linear optimization problems.

What would settle it

An election profile containing a committee that maximizes weighted welfare for every positive weight vector yet is fractionally dominated by another committee, or a one-dimensional preference domain containing a Pareto-optimal committee that is fractionally dominated.

Watch

Extended reading notes

Core claim

A committee is fractionally Pareto-optimal if and only if there exist positive weights such that the committee maximizes the weighted sum of voter utilities; this characterization is proved by showing that any non-maximizing committee is dominated by a suitable fractional committee and conversely that welfare maximizers cannot be fractionally dominated.

Load-bearing premise

Non-domination by any convex combination of committees exactly matches the robustness of efficiency when every candidate is uniformly cloned.

Editorial extensions

If this is right

  • Verification of fPO for a given committee can be done in polynomial time via linear programming.
  • The collection of all fPO committees is closed under adding a candidate when the new committee remains fPO.
  • Any two fPO committees can be transformed into each other by a sequence of single-candidate swaps that each preserve fPO.
  • Proportional approval voting can return a committee that is not fPO even when Pareto-optimal committees exist.
  • On one-dimensional preference domains the sets of PO and fPO committees coincide.

Reading between the lines

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

  • The welfare characterization may allow designing new multiwinner rules that explicitly target fPO rather than PO.
  • In large elections the connectivity result suggests local search heuristics could enumerate or sample fPO committees efficiently.
  • The incompatibility with equality-focused rules like PAV indicates a potential trade-off between robustness to cloning and proportionality that future rules might balance differently.
Share X Bluesky LinkedIn Reddit HN

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 / 0 minor

Summary. The paper introduces fractional Pareto-optimality (fPO) for multiwinner voting, defined as the property that a committee is not dominated by any convex combination of committees. It claims fPO refines PO by retaining exactly those PO committees whose efficiency is robust under uniform candidate cloning, proves existence of fPO committees, and gives a characterization of fPO committees as maximizers of weighted utilitarian welfare. This characterization yields a polynomial-time algorithm for verifying fPO, and the paper proves that the set of fPO committees satisfies committee monotonicity and is connected under single-candidate swaps. It further shows an incompatibility between fPO and equality-oriented rules (including that PAV violates fPO in the approval setting) and identifies domains (including various one-dimensional ones) where PO and fPO coincide.

Significance. If the characterization and proofs hold, the work makes a meaningful contribution by identifying a computationally tractable refinement of PO with attractive structural properties (monotonicity and swap-connectedness) and a simple verification algorithm. The explicit credit to the weighted-welfare characterization, the poly-time algorithm, and the domain-collapse results is warranted; these are load-bearing strengths. The incompatibility result with PAV is a clear negative finding of interest to the field. The cloning-robustness interpretation is presented as motivation rather than a load-bearing technical step, so any gap there would affect framing only.

major comments (1)
  1. The central characterization (via weighted utilitarian welfare) and its consequences for the poly-time algorithm, monotonicity, and connectedness appear to follow directly from the fPO definition; no circularity or parameter-fitting is visible in the abstract or reader's summary.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation and recommendation of minor revision. The single major comment is addressed point by point below.

read point-by-point responses

  1. Referee: The central characterization (via weighted utilitarian welfare) and its consequences for the poly-time algorithm, monotonicity, and connectedness appear to follow directly from the fPO definition; no circularity or parameter-fitting is visible in the abstract or reader's summary.

    Authors: We confirm that the characterization is derived directly from the definition of fPO (no committee is dominated by any convex combination of committees). The weighted-utilitarian-welfare maximizers are shown to be exactly the fPO committees by a standard separating-hyperplane argument that does not rely on any auxiliary parameters or circular reasoning; the same argument immediately yields the polynomial-time verification procedure (by solving a linear program), committee monotonicity, and single-swap connectedness. These consequences are therefore intrinsic to the definition rather than additional assumptions. revision: no

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; characterization derived directly from fPO definition

full rationale

The paper defines fPO as non-domination by any convex combination of committees and derives the weighted utilitarian welfare characterization, poly-time verification, monotonicity, and swap-connectedness as mathematical consequences of that definition. No self-citation is load-bearing for the central claims, no parameters are fitted and renamed as predictions, and the cloning-robustness statement is presented only as interpretive motivation for why fPO refines PO, not as a premise in the derivation chain. The technical results remain intact under the stated definition alone.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The work introduces a definitional refinement but relies on standard social choice modeling without new free parameters or invented entities.

assumptions (1)
  • domain assumption Voter preferences admit utility or approval representations over committees
    Invoked for the general multiwinner setting and the approval setting where PAV is analyzed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fractional Pareto-Optimality in Multiwinner Voting." pith.science (2026). https://pith.science/paper/4Y2HA4PJ

@misc{pith2026260611160,
  author       = {Pith},
  title        = {Pith review of: Fractional Pareto-Optimality in Multiwinner Voting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4Y2HA4PJ}},
  note         = {Machine review of arXiv:2606.11160}
}
read the original abstract

Efficiency in multiwinner voting is most naturally captured by Pareto-optimality (PO), yet this notion is computationally and structurally difficult to handle. We therefore study fractional Pareto-optimality (fPO), under which a committee may not be dominated even by a fractional committee, i.e., any convex combination of committees. fPO turns out to be a natural refinement of PO as it retains exactly those Pareto-optimal committees whose efficiency is robust under uniform cloning of candidates. Furthermore, fPO committees are guaranteed to exist and have strong structural properties. We present a characterization of fPO in terms of weighted utilitarian welfare maximization, which yields a polynomial-time algorithm for verifying fPO and shows that the set of fPO committees satisfies committee monotonicity and is connected under single-candidate swaps. Analyzing welfarist rules through the lens of fPO, we further uncover an incompatibility between fPO and equality-oriented objectives. Most notably, we show that proportional approval voting (PAV) violates fPO in the approval setting. We close by pinpointing preference domains, including various one-dimensional ones, on which PO and fPO collapse into one notion.

Figures

Figures reproduced from arXiv: 2606.11160 by the authors.

Figure 1
Figure 1. Counterexamples illustrating the relationships between Pareto-optimality and (weak) frac [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Relationship between score-induced weak orders, weighted utility maximization, and the [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. A counterexample to committee monotonicity of (weak) Pareto-optimality in the additive-valuation model. In the following, we show that both PO and wPO violate monotonicity for the general valuation setting. Consider two voters and seven candidates with valu￾ations v1 = ( 3 2 , 5, 5, 1, 1, 7, 0) and v2 = ( 3 2 , 1, 1, 5, 5, 0, 7). For k = 1, the committee W = {c1} is Pareto-optimal, as it is not dominated by any othe… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Visualization of the coun￾terexample for connectedness with additive valuations. — 12 — [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Geometric illustration of the proof for Theorem 8 with n = 2. Contrasting Theorem 8, we provide in Section A.3 in the ap￾pendix an example showing that a strictly concave and strictly monotone function g can still yield a welfarist rule fg satisfying fPO in the approva…
Figure 6
Figure 6. Figure 6: Thiele rules satisfy￾ing fPO may violate JR. that said, an interesting direction for future work is the compatibility of fractional Pareto-optimality with standard proportionality axioms, such as JR, its extended notion, EJR, and priceability. Structural properties of …
Figure 7
Figure 7. Figure 7: Instance I = (A, k) used for the proof in Proposition 4. The candidates in C1 are approved by all voters in U, the candidates in C2 by all voters in X, and each block Zij contains k candidates approved by all voters except ui and xj . We first show that the committees …
Figure 8
Figure 8. Figure 8: A visualization of a 2D-Euclidean instance in which fPO and PO do not coincide. The coordinates of the candidates and voters for the embedding, together with the disc’s radius, are listed in the table on the right-hand side. — 40 — [PITH_FULL_IMAGE:figures/full_fig_p0…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

46 extracted references · 5 canonical work pages

  1. [1]

    K. J. Arrow. Social Choice and Individual Values. New Haven: Cowles Foundation, 1st edition, 1951. 2nd edition 1963

    1951

  2. [2]

    Computing Thiele Rules on Interval Elections and their Generalizations

    D. Avramidis, A. Lassota, U. Schmidt-Kraepelin, and A. Vetta. Computing T hiele rules on interval elections and their generalizations, 2026. arXiv:2605.03067 [cs.GT]

    work page Pith review arXiv 2026

  3. [3]

    Aziz and J

    H. Aziz and J. Monnot. Computing and testing pareto optimal committees. Autonomous Agents and Multi-Agent Systems, 34: 0 1--20, 2020

    2020

  4. [4]

    H. Aziz, X. Lu, M. Suzuki, J. Vollen, and T. Walsh. Best-of-both-worlds fairness in committee voting, 2023. arXiv:2303.03642 [cs.GT]

    work page arXiv 2023

  5. [5]

    Barman, S

    S. Barman, S. K. Krishnamurthy, and R. Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation (ACM-EC), pages 557--574. ACM , 2018

    2018

  6. [6]

    R. E. Berker, S. Casacuberta, I. Robinson, C. Ong, V. Conitzer, and E. Elkind. From independence of clones to composition consistency: A hierarchy of barriers to strategic nomination. In Proceedings of the 26th ACM Conference on Economics and Computation (ACM-EC), page 1109. ACM , 2025

    2025

  7. [7]

    Explanation Systems for Approval-Based Multiwinner Voting

    N. Boehmer, L. Kreisel, and J. Peters. Explanation systems for approval-based multiwinner voting, 2026. arXiv:2604.24307 [cs.GT]

    work page Pith review arXiv 2026

  8. [8]

    Boyd and L

    S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004

    2004

Show all 46 references
  1. [9]

    Brill and J

    M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC), 2023

    2023

  2. [10]

    Caragiannis, R

    I. Caragiannis, R. LeGrand, E. Markakis, and E. Pountourakis. An impossibility result for strongly group-strategyproof multi-winner approval-based voting. In Proceedings of the 20th International Conference on Web and Internet Economics (WINE), pages 457--475. Springer, 2024

    2024

  3. [11]

    J. Chen, X. Luo, M. Sorge, and N. Talmon. Multi-winner reconfiguration. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024

    2024

  4. [12]

    Cheng, Z

    Y. Cheng, Z. Jiang, K. Munagala, and K. Wang. Group fairness in committee selection. ACM Trans. Economics and Comput. , 8 0 (4): 0 23:1--23:18, 2020

    2020

  5. [13]

    de Keijzer, S

    B. de Keijzer, S. Bouveret, T. Klos, and Y. Zhang. On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT), pages 98--110. Springer, 2009

    2009

  6. [14]

    G. Debreu. Topological methods in cardinal utility theory. Cowles Foundation Discussion Paper 76, Cowles Foundation at Yale University, 1959

    1959

  7. [15]

    T. Dey. Improved bounds for planar k-sets and related problems. Discrete and Computational Geometry, 19: 0 373--382, 03 1998

    1998

  8. [16]

    C. Dong, F. Frank, J. Peters, and W. Suksompong. Reconfiguring proportional committees. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 16829--16837. AAAI Press, 2026

    2026

  9. [17]

    Elkind and M

    E. Elkind and M. Lackner. Structure in dichotomous preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 2019--2025. AAAI Press, 2015

    2019

  10. [18]

    Elkind, P

    E. Elkind, P. Faliszewski, and A. M. Slinko. Cloning in elections: Finding the possible winners. J. Artif. Intell. Res., 42: 0 529--573, 2011

    2011

  11. [19]

    Elkind, P

    E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of multiwinner voting rules. Soc. Choice Welf., 48 0 (3): 0 599--632, 2017

    2017

  12. [20]

    Faliszewski, Łukasz Janeczko, A

    P. Faliszewski, Łukasz Janeczko, A. Kaczmarczyk, G. Lisowski, and G. Pierczyński. Project submission games in participatory budgeting, 2025. arXiv:2508.09741 [cs.GT]

    2025

  13. [21]

    A. M. Feldman and R. Serrano. Welfare Economics and Social Choice Theory. Springer-Verlag, 2nd edition, 2006

    2006

  14. [22]

    Garg and A

    J. Garg and A. Murhekar. Computing fair and efficient allocations with few utility values. Theor. Comput. Sci., 962: 0 113932, 2023

    2023

  15. [23]

    Garg and A

    J. Garg and A. Murhekar. Computing pareto-optimal and almost envy-free allocations of indivisible goods. J. Artif. Intell. Res., 80: 0 1--25, 2024

    2024

  16. [24]

    J. Garg, A. Murhekar, and J. Qin. New algorithms for the fair and efficient allocation of indivisible chores. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 2710--2718. ijcai.org, 2023

    2023

  17. [25]

    M. T. Godziszewski, P. Batko, P. Skowron, and P. Faliszewski. An analysis of approval-based committee rules for 2d-euclidean elections. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5448--5455. AAAI Press, 2021

    2021

  18. [26]

    Gorski, K

    J. Gorski, K. Klamroth, and S. Ruzika. Connectedness of efficient solutions in multiple objective combinatorial optimization. Journal of Optimization Theory and Applications, 138 0 (2): 0 251--266, 2008

    2008

  19. [27]

    S. Janson. Phragm \'e n’s and thiele’s election methods. Technical report, Technical report, 2016

    2016

  20. [28]

    Kawase and R

    Y. Kawase and R. Mahara. Fair and efficient balanced allocation for indivisible goods. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17067--17075. AAAI Press, 2026

    2026

  21. [29]

    Kroer and D

    C. Kroer and D. Peters. Computing L indahl equilibrium for public goods with and without funding caps. In Proceedings of the 26th ACM Conference on Economics and Computation (ACM-EC), page 129, 2025

    2025

  22. [30]

    Lackner and P

    M. Lackner and P. Skowron. Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artificial Intelligence, 288: 0 103366, Nov. 2020

    2020

  23. [31]

    Lackner and P

    M. Lackner and P. Skowron. Consistent approval-based multi-winner rules. J. Econ. Theory, 192: 0 105173, 2021

    2021

  24. [32]

    Lackner and P

    M. Lackner and P. Skowron. Multi-winner voting with approval preferences. Springer Nature, 2023

    2023

  25. [33]

    Lain \'e , J

    J. Lain \'e , J. Lang, \.I . \"O zkal-Sanver, and M. Remzi Sanver. Pareto-efficiency of ordinal multiwinner voting rules. Review of Economic Design, pages 1--35, 2025

    2025

  26. [34]

    Mas-Colell, M

    A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic theory, volume 1. Oxford university press New York, 1995

    1995

  27. [35]

    Peters and P

    D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21nd ACM Conference on Economics and Computation (ACM-EC), pages 793--794, 2020

    2020

  28. [36]

    Pierczy \' n ski and P

    G. Pierczy \' n ski and P. Skowron. Core-stable committees under restricted domains. In Proceedings of the 18th International Conference on Web and Internet Economics (WINE), pages 311--329. Springer, 2022

    2022

  29. [37]

    Sandomirskiy and E

    F. Sandomirskiy and E. Segal - Halevi. Efficient fair division with minimal sharing. Oper. Res., 70 0 (3): 0 1762--1782, 2022

    2022

  30. [38]

    Schrijver

    A. Schrijver. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Chichester, 1986

    1986

  31. [39]

    Schrijver

    A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, Berlin, 2003

    2003

  32. [40]

    J. Schünke. Pareto optimality in approval-based multiwinner voting, 2026. arXiv:2605.30490 [cs.GT]

    2026 arXiv

  33. [41]

    P. Skowron. Proportionality degree of multiwinner rules. In Proceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC), pages 820--840. ACM, 2021

    2021

  34. [42]

    Suzuki and J

    M. Suzuki and J. Vollen. Maximum flow is fair: A network flow approach to committee voting. In Proceedings of the 25th ACM Conference on Economics and Computation (ACM-EC), pages 964--983, 2024

    2024

  35. [43]

    Talmon and P

    N. Talmon and P. Faliszewski. A framework for approval-based budgeting methods. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 2181--2188. AAAI Press, 2019

    2019

  36. [44]

    T. N. Thiele. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 1895: 0 415--441, 1895

  37. [45]

    T. N. Tideman. Independence of clones as a criterion for voting rules. Social Choice and Welfare, 4 0 (3): 0 185--206, 1987

    1987

  38. [46]

    G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer, 1995

    1995

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.