REVIEW 2 major objections 4 minor 2 cited by
Full Proportional Justified Representation
T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read This paper introduces Full Proportional Justified Representation, a mid-strength proportionality axiom that priceable rules and the Monroe rule satisfy and that PAV can violate; verifying a committee satisfies it is coNP-complete.
desk verdict FPJR is a genuine completion of the taxonomy, but the unqualified Greedy Monroe guarantee in the abstract is false for k∤n. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the weakly $\ell$-cohesive coalition with witness set $T$, defined by the size constraint $|S|/n \geq |T|/k$ and the per-voter approval constraint $|A_v \cap T| \geq \ell$ for every $v \in S$. The engine of the argument is Lemma 3.2, an averaging step: summing $|A_v \cap T|$ over $S$ shows that some candidate $c \in T$ is approved by at least $\ell \cdot n/k$ voters of $S$. That high-approval candidate is what converts a supposed FPJR violation into a contradiction: in the priceability proof it exposes leftover voter budget that could buy the unelected candidate, and in the Monroe proof it yields a committee-and-assignment swap or a greedy-move improvement that increases the Monroe score. The hardness results are carried by the same Balanced Biclique reductions used for PJR and EJR, with more involved analyses of the weakly cohesive coalition that emerges.
What would settle it
Exhibit an election with committee size $k$ not dividing the number of voters $n$ on which the Monroe rule or Greedy Monroe rule returns a committee containing a weakly $\ell$-cohesive coalition whose members collectively approve fewer than $\ell$ winners; a single such instance would refute the abstract's unqualified claim that these rules satisfy FPJR.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that the fourth cell of the cohesiveness-versus-representation table is occupied by a meaningful axiom rather than an incidental variant. A committee satisfies FPJR exactly when every weakly $\ell$-cohesive coalition $S$—one large enough to be entitled to a candidate set $T$ of proportional size, with each member approving at least $\ell$ candidates of $T$—collectively approves at least $\ell$ members of the committee. The paper proves that every priceable committee has this property, which carries the Method of Equal Shares and Phragmén-type rules along with it, and that when the committee size divides the electorate, the Monroe rule and the efficient Greedy Monroe rule satisfy it as well. It then shows the boundary is real: PAV can violate FPJR, so neither EJR nor FPJR implies the other, and some FPJR committees are not priceable. Finally, the same Balanced Biclique reductions used for earlier axioms yield coNP-completeness for verifying FPJR, FJR, and core stability.
Load-bearing premise
The boundary of the main algorithmic result is the divisibility premise: Theorem 3.11 proves FPJR for Monroe and Greedy Monroe only when $k$ divides $n$, because the swap argument relies on every committee candidate having exactly $n/k$ assigned voters; without that equality the proof breaks and the paper supplies no replacement argument or counterexample.
Editorial extensions
If this is right
- Any committee produced by a priceable rule—the Method of Equal Shares, Phragmén's method, and similar rules—automatically satisfies FPJR, strengthening the proportionality guarantee those rules were already known to give.
- When the desired committee size divides the number of voters, the Monroe rule and its greedy variant satisfy FPJR, so FPJR is achievable in polynomial time even though verifying it is coNP-hard.
- PAV and sequential PAV can elect committees that violate FPJR, which means the popular EJR guarantee does not protect against weak-coalition underrepresentation; the Monroe rule provides the reverse separation.
- Core stability implies FJR, FJR implies FPJR, and FPJR implies PJR; the new axiom therefore slots between PJR and FJR in the implication hierarchy while remaining incomparable with EJR.
- Verifying FPJR, FJR, or core stability for a proposed committee is coNP-complete, closing a gap in the complexity landscape of proportionality axioms.
Reading between the lines
- Editorial inference: the divisibility assumption in the Monroe result is likely not a proof artifact but a genuine boundary; searching for a counterexample with $k \nmid n$, or proving a modified statement with floor and ceiling assignments, is the most direct next test.
- Editorial inference: because priceability implies FPJR but not conversely, FPJR offers a way to certify a class of non-priceable committees as proportionally sound; whether every FPJR committee can be realized by a mild perturbation of a price system is a natural open question.
- Editorial inference: the coNP-completeness of verifying FPJR suggests that a verifiable FPJR+ analogue in the style of PJR+ and EJR+ would require a different cohesiveness condition, and the paper's open question about efficiently verifiable stronger axioms points exactly there.
- Editorial inference: in participatory budgeting, generalizing FPJR with candidate costs and voter budgets would likely give a proportionality axiom that the Method of Equal Shares satisfies, extending the paper's priceability result to the budgeted setting.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a new proportionality axiom, Full Proportional Justified Representation (FPJR), defined as requiring every weakly ell-cohesive coalition to have collective approval utility at least ell. It studies the relations of FPJR to PJR, EJR, FJR, priceability, perfect representation, and PAV, proves that priceable committees and perfectly representative committees satisfy FPJR, and claims that the Monroe rule and Greedy Monroe rule satisfy FPJR when k divides n. It proves coNP-completeness of verifying FPJR, FJR, and core stability via balanced-biclique reductions. The central claims are mostly coherent, but the unqualified Greedy Monroe statement in the abstract is false for k not dividing n, and the proof of Theorem 3.6 has a gap.
Significance. The paper fills a natural gap in the justified-representation taxonomy and gives the first systematic study of the (C2)-(R1) cell. The implication from priceability to FPJR, the PAV counterexample, and the hardness results for FPJR, FJR, and core stability are useful additions; the latter two indeed appear to be missing from the literature. The proofs are constructive, and the hardness reductions are modeled carefully on the existing EJR and PJR constructions. The main caveat is that the headline Monroe and Greedy Monroe claim is false as stated when k does not divide n, and the proof of Theorem 3.6 contains a localized but load-bearing gap. Both issues are repairable within the scope of the manuscript, and with those corrections the paper would be a solid contribution.
major comments (2)
- [Abstract, Section 1, Theorem 3.11] The abstract and introduction state without the divisibility condition that the Monroe rule and Greedy Monroe rule satisfy FPJR. Theorem 3.11 is proved only for k dividing n, and the restriction is essential. For n=6, k=4, let voters v1,v2,v3 approve {a,b}, v4 approve {d}, v5 approve {e}, and v6 approve {f}. Under the Greedy Monroe procedure in Section 2.2.2, a legitimate tie-breaking run selects a first, assigning v1 and v2; then d, assigning v4 and one arbitrary remaining voter, say v3; then e, assigning v5; then f, assigning v6. The output is W={a,d,e,f}. The coalition S={v1,v2,v3} is weakly 2-cohesive with witness T={a,b}, because |S|/6=1/2=|T|/4 and every voter in S approves both a and b. Yet the union of approvals of S intersects W in {a}, of size 1, which is less than 2, violating FPJR. Thus the unqualified claim is false; every FPJR statement about Monroe and Greedy Monroe must be restricted to k dividing n.
- [Section 3.1, proof of Theorem 3.6, Eq. (2)] The upper bound in Eq. (2) is applied to all candidates in T \ O on the ground that none of them are in W, but T \ O can contain elected candidates that are not approved by any voter in S; for such candidates the priceability condition for unelected candidates does not apply. The proof can be repaired by summing only over N_c ∩ S in both Eq. (1) and Eq. (2): for elected candidates in T \ O, the set N_c ∩ S is empty, while for unelected candidates priceability gives the needed bound. As written, however, the argument contains a genuine gap in the main implication from priceability to FPJR.
minor comments (4)
- [Proof of Theorem 3.11] The line saying that c in T prime and c not in W_S implies c not in W is false as stated, because c could be in W but not approved by any voter in S. The contradiction is restored because Lemma 3.2 gives a nonempty N_c ∩ S prime; the proof should say this explicitly.
- [Example 3.4] The text says that Sequential PA V also selects this committee, but the related discussion concerns LS-PAV; please use the established name of the sequential variant.
- [Theorem 4.4] The theorem statement says that the problem is coNP-hard, while the proof establishes coNP-completeness; uniform phrasing with Theorems 4.2 and 4.3 would be clearer.
- [Definition 3.1] The expression W ∩ S v∈S A_v in Definition 3.1 appears to be a rendering artifact and should be W ∩ (union over v in S of A_v).
Circularity Check
No significant circularity: FPJR results are derived forward from definitions and external theorems; no fitted input or self-citation chain is load-bearing.
full rationale
The paper's central claims are forward derivations from its definitions. FPJR is defined in Definition 3.1, and the main positive results show that priceable committees satisfy FPJR (Theorem 3.6) and that Monroe and Greedy Monroe satisfy FPJR when k divides n (Theorem 3.11). These proofs use only the paper's own definitions, standard counting arguments, and cited external results, notably Proposition 1 of Peters and Skowron 2020b for the priceability-to-PJR implication. The hardness results in Theorems 4.2-4.4 explicitly build on reductions due to Aziz et al. 2017 and 2018a, with the paper supplying the additional verification arguments; those reductions are external benchmarks rather than self-referential assumptions. No parameter is fitted to any subset of data and then renamed as a prediction; the paper is purely axiomatic. The only self-citation, Kalayci et al. 2024 in the Related Work section, is not load-bearing for the main results. The known restriction that Theorem 3.11 is proved only when k divides n is stated in the theorem and in Section 2.2.2, and the abstract's unqualified wording that greedy Monroe satisfies FPJR is a correctness/scoping concern about an overclaim, not a circularity: it does not reduce the derivation to its own inputs. Under the requested circularity standard, no step in the derivation chain is equivalent to its inputs by construction, so the appropriate finding is no significant circularity with score 0.
Assumptions & free parameters
assumptions (8)
- standard math Balanced Biclique is NP-complete (Garey and Johnson).
- domain assumption The Aziz et al. [2018a] reduction from Balanced Biclique proves a PJR violation for the constructed instance.
- domain assumption The Aziz et al. [2017] reduction from Balanced Biclique proves an EJR violation for the Algorithm 2 instance.
- domain assumption Priceability implies PJR (Proposition 1 of Peters and Skowron 2020b).
- domain assumption The Method of Equal Shares and Phragmen's rule always output priceable committees (Peters and Skowron 2020b).
- domain assumption Priceable committees may violate EJR (Peters and Skowron 2020b).
- domain assumption Monroe's rule can violate EJR, and EJR+ is stronger than EJR (Aziz et al. 2017, Brill and Peters 2023).
- domain assumption Core stability implies FJR, FJR implies EJR, and EJR implies PJR.
Cite this review
Pith. "Pith review of Full Proportional Justified Representation." pith.science (2026). https://pith.science/paper/2I7LKCZT
@misc{pith2026250112015,
author = {Pith},
title = {Pith review of: Full Proportional Justified Representation},
year = {2026},
howpublished = {\url{https://pith.science/paper/2I7LKCZT}},
note = {Machine review of arXiv:2501.12015}
}
read the original abstract
In multiwinner approval voting, forming a committee that proportionally represents voters' approval ballots is an essential task. The notion of justified representation (JR) demands that any large "cohesive" group of voters should be proportionally "represented". The "cohesiveness" is defined in different ways; two common ways are the following: (C1) demands that the group unanimously approves a set of candidates proportional to its size, while (C2) requires each member to approve at least a fixed fraction of such a set. Similarly, "representation" have been considered in different ways: (R1) the coalition's collective utility from the winning set exceeds that of any proportionally sized alternative, and (R2) for any proportionally sized alternative, at least one member of the coalition derives less utility from it than from the winning set. Three of the four possible combinations have been extensively studied: (C1)-(R1) defines Proportional Justified Representation (PJR), (C1)-(R2) defines Extended Justified Representation (EJR), (C2)-(R2) defines Full Justified Representation (FJR). All three have merits, but also drawbacks. PJR is the weakest notion, and perhaps not sufficiently demanding; EJR may not be compatible with perfect representation; and it is open whether a committee satisfying FJR can be found efficiently. We study the combination (C2)-(R1), which we call Full Proportional Justified Representation (FPJR). We investigate FPJR's properties and find that it shares PJR's advantages over EJR: several proportionality axioms (e.g. priceability, perfect representation) imply FPJR and PJR but not EJR. We also find that efficient rules like the greedy Monroe rule and the method of equal shares satisfy FPJR, matching a key advantage of EJR over FJR. However, the Proportional Approval Voting (PAV) rule may violate FPJR, so neither of EJR and FPJR implies the other.
Figures
Forward citations
Cited by 2 Pith papers
-
Metritocracy: Representative Metrics for Lite Benchmarks
Defines positional representation and positional proportionality for metric subset selection, with nearly tight worst-case bounds, greedy algorithms, and case studies on LLM and hospital benchmarks.
-
Artificial Intelligence for Mathematical Reasoning: An Integrated Survey of Language Models, Neuro-symbolic Systems, and Verified Discovery
An integrated survey organizing AI mathematical reasoning into informal, formal, discovery, and technique axes while cataloging benchmarks and assessing failure modes.
Reference graph
Works this paper leans on
-
[1]
Haris Aziz and Barton E. Lee. Proportionally representative participatory budgeting with ordinal preferences. In Proc. 35th AAAI Conf. on Artificial Intelligence, pages 5110--5118, 2021. doi:10.1609/aaai.v35i6.16646
-
[2]
Participatory budgeting: Models and approaches
Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. In Tam \'a s Rudas and G \'a bor P \'e li, editors, Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, pages 215--236. Springer International Publishing, 2021. ISBN 978-3-030-54936-7. doi:10.1007/978-3-030-54936-7_10. URL http...
-
[3]
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. In Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014
work page 2014
-
[4]
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, 48 0 (2): 0 461--485, 2017
work page 2017
-
[5]
On the complexity of extended and proportional justified representation
Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis S \'a nchez-Fern \'a ndez, and Piotr Skowron. On the complexity of extended and proportional justified representation. In Proc. 32nd AAAI Conf. on Artificial Intelligence, pages 902--909, 2018 a
work page 2018
-
[6]
Haris Aziz, Barton E. Lee, and Nimrod Talmon. Proportionally representative participatory budgeting: Axioms and algorithms. In Proc. 17th Intl. Conf. on Autonomous Agents and Multiagent Systems, pages 23--31. International Foundation for Autonomous Agents and Multiagent Systems, 2018 b
work page 2018
-
[7]
Brams, Markus Brill, and Anne-Marie George
Steven J. Brams, Markus Brill, and Anne-Marie George. The excess method: a multiwinner approval voting procedure to allocate wasted votes. Social Choice and Welfare, 58 0 (2): 0 283--300, February 2022. ISSN 1432-217X. doi:10.1007/s00355-021-01358-3. URL https://doi.org/10.1007/s00355-021-01358-3
- [8]
Show all 34 references
-
[9]
Robust and verifiable proportionality axioms for multiwinner voting
Markus Brill and Jannik Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proc. 24th ACM Conf. on Economics and Computation, page 301. Association for Computing Machinery, 2023. ISBN 9798400701047. doi:10.1145/3580507.3597785. URL https://doi.org/...
2023
-
[10]
Proportionality in approval-based participatory budgeting
Markus Brill, Stefan Forster, Martin Lackner, Jan Maly, and Jannik Peters. Proportionality in approval-based participatory budgeting. In Proc. 37th AAAI Conf. on Artificial Intelligence. AAAI Press, 2023. ISBN 978-1-57735-880-0. doi:10.1609/aaai.v37i5.25686. URL https://doi.or...
2023 doi
-
[11]
Phragm\' e n's voting methods and justified representation
Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. Phragm\' e n's voting methods and justified representation. Mathematical Programming, 203 0 (1): 0 47--76, 2024. ISSN 1436-4646. doi:10.1007/s10107-023-01926-8. URL https://doi.org/10.1007/s10107-023-01926-8
2024 doi
-
[12]
Voudouris
Ioannis Caragiannis, Nisarg Shah, and Alexandros A. Voudouris. The metric distortion of multiwinner voting. In Proc. 36th AAAI Conf. on Artificial Intelligence, pages 4900--4907, 2022. doi:10.1609/aaai.v36i5.20419
2022 doi
-
[13]
Chamberlin and Paul N
John R. Chamberlin and Paul N. Courant. Representative deliberations and representative decisions: Proportional representation and the borda rule. American Political Science Review, 77 0 (3): 0 718–733, 1983. doi:10.2307/1957270
1983 doi
-
[14]
Voting Procedures
Michael Dummett. Voting Procedures. Oxford University Press, 1984
1984
-
[15]
Boosting sortition via proportional representation, 2024
Soroush Ebadian and Evi Micha. Boosting sortition via proportional representation, 2024. URL https://arxiv.org/abs/2406.00913
2024 arXiv
-
[16]
Multiwinner voting: A new challenge for social choice theory
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74 0 (2017): 0 27--47, 2017. Publisher: AI Access Foundation El Segundo
2017
-
[17]
Achieving fully proportional representation by clustering voters
Piotr Faliszewski, Arkadii Slinko, Kolja Stahl, and Nimrod Talmon. Achieving fully proportional representation by clustering voters. Journal of Heuristics, 24 0 (5): 0 725–756, 2018. ISSN 1381-1231. doi:10.1007/s10732-018-9376-y. URL https://doi.org/10.1007/s10732-018-9376-y
2018 doi
-
[18]
Garey and David S
Michael R. Garey and David S. Johnson. Computers and intractability. Freeman San Francisco, 1979
1979
-
[19]
Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto
Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation, 7 0 (2), July 2019. ISSN 2167-8375. doi:10.1145/3340230. URL https://doi.org/10.1145/3340230
2019 doi
-
[20]
Humphreys
John H. Humphreys. Proportional Representation: A Study in Methods of Election. Methuen & Co, 1911
1911
-
[21]
Phragm\' e n's and thiele's election methods, 2018
Svante Janson. Phragm\' e n's and thiele's election methods, 2018. URL https://arxiv.org/abs/1611.08826
2018 arXiv
-
[22]
Proportional representation in metric spaces and low-distortion committee selection
Yusuf Kalayci, David Kempe, and Vikram Kher. Proportional representation in metric spaces and low-distortion committee selection. Proc. 38th AAAI Conf. on Artificial Intelligence, 38: 0 9815--9823, 2024. doi:10.1609/aaai.v38i9.28841. URL https://ojs.aaai.org/index.php/AAAI/art...
2024 doi
-
[23]
Approval-Based Committee Voting, pages 1--7
Martin Lackner and Piotr Skowron. Approval-Based Committee Voting, pages 1--7. Springer International Publishing, Cham, 2023. ISBN 978-3-031-09016-5. doi:10.1007/978-3-031-09016-5_1. URL https://doi.org/10.1007/978-3-031-09016-5_1
2023 doi
-
[24]
Burt L. Monroe. Fully proportional representation. American Political Science Review, 89 0 (4): 0 925–940, 1995. doi:10.2307/2082518
1995 doi
-
[25]
Choosing from a tournament
Herv\' e Moulin. Choosing from a tournament. Social Choice and Welfare, 3 0 (4): 0 271--291, 1986
1986
-
[27]
Proportionality and the limits of welfarism
Dominik Peters and Piotr Skowron. Proportionality and the limits of welfarism. In Proc. 21st ACM Conf. on Economics and Computation, pages 793--–794, New York, NY, USA, 2020 b . Association for Computing Machinery. ISBN 9781450379755. doi:10.1145/3391403.3399465. URL https://d...
2020
-
[28]
Proportional participatory budgeting with additive utilities
Dominik Peters, Grzegorz Pierczy \'n ski, and Piotr Skowron. Proportional participatory budgeting with additive utilities. Proc. 35th Advances in Neural Information Processing Systems, 34: 0 12726--12737, 2021 a
2021
-
[29]
Proportional participatory budgeting with additive utilities
Dominik Peters, Grzegorz Pierczy\' n ski, and Piotr Skowron. Proportional participatory budgeting with additive utilities. In Proc. 35th Advances in Neural Information Processing Systems, Red Hook, NY, USA, 2021 b . Curran Associates Inc. ISBN 9781713845393
2021
-
[30]
Approval-based elections and distortion of voting rules
Grzegorz Pierczy\' n ski and Piotr Skowron. Approval-based elections and distortion of voting rules. In Proc. 28th Intl. Joint Conf. on Artificial Intelligence, pages 543--549, 2019
2019
-
[31]
The (computational) social choice take on indivisible participatory budgeting, 2023
Simon Rey and Jan Maly. The (computational) social choice take on indivisible participatory budgeting, 2023. URL https://arxiv.org/abs/2303.00621
2023 arXiv
-
[32]
Proportional justified representation
Luis S \'a nchez-Fern \'a ndez, Edith Elkind, Martin Lackner, Norberto Fern \'a ndez, Jes \'u s Fisteus, Pablo Basanta Val, and Piotr Skowron. Proportional justified representation. In Proc. 31st AAAI Conf. on Artificial Intelligence, pages 670--676, 2017
2017
-
[33]
Fisteus, and Rafael L\' o pez-Zaragoza
Luis S\' a nchez-Fern\' a ndez, Jes' u s A. Fisteus, and Rafael L\' o pez-Zaragoza. Data as voters: instance selection using approval-based multi-winner voting, 2024. URL https://arxiv.org/abs/2304.09995
2024 arXiv
-
[34]
Proportional rankings
Piotr Skowron, Martin Lackner, Markus Brill, Dominik Peters, and Edith Elkind. Proportional rankings. In Proc. 26th Intl. Joint Conf. on Artificial Intelligence, pages 409--415, 2017. doi:10.24963/ijcai.2017/58. URL https://doi.org/10.24963/ijcai.2017/58
2017 doi
-
[35]
Thorvald N. Thiele. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 1895: 0 415--441, 1895
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.