{"id":"4ae9a44b-090d-4d52-bbce-c6918d02a765","arxiv_id":"2501.12015","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new axiom, Full Proportional Justified Representation, fills the fourth cell in the justified-representation taxonomy; priceable rules and Monroe's rule satisfy it, while PAV does not.","lead":"The paper defines a new proportional-fairness criterion, FPJR, for elections where each voter approves a set of candidates. It proves that several standard selection methods satisfy FPJR and that Proportional Approval Voting does not, giving algorithm designers a sharper choice of guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Greedy Monroe's FPJR guarantee fails for k∤n: a concrete 6-voter, 4-seat election violates FPJR, so the abstract's unqualified claim is false.","rationale":"The paper's central positive claim about Greedy Monroe is stated without qualification in the abstract, while the theorem only covers k|n. The reader identified the unstated divisibility premise as the weakest assumption. A concrete counterexample confirms that the concern lands: Greedy Monroe can violate FPJR when k∤n, because FPJR implies PJR and the example is a straightforward PJR violation produced by the paper's own algorithm with unspecified tie-breaking. The proof of Theorem 3.11 relies on exact n/k loads in Lemma 3.12 and on assigning exactly n/k voters to the witness candidate; when k∤n, the floor/ceil loads permit an under-supported candidate to steal voters from a cohesive coalition, exactly as in the counterexample. This does not invalidate the k|n theorem, the priceability result, or the coNP-completeness results; it requires a precise qualifier in the abstract and introduction and an acknowledgement of the counterexample. Therefore the verdict remains CONDITIONAL rather than ACCEPT, and no stronger action is warranted because the mathematical core of the paper is otherwise defensible.","tokens_in":18447,"tokens_out":27706,"duration_ms":313150,"concrete_test":"Run Greedy Monroe on the explicit instance n=6, k=4 with ballots v1=v2=v3={a,b}, v4={d}, v5={e}, v6={f}, using tie-breaking first a, then d, then e, then f. The output is W={a,d,e,f}; check the coalition S={v1,v2,v3} with witness T={a,b}: it is 2-cohesive and |W∩{a,b}|=1<2, so FPJR is violated. This settles that the k|n restriction in Theorem 3.11 cannot be dropped and that the abstract's unqualified statement needs revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3.11 proves Monroe and Greedy Monroe satisfy FPJR only when k divides n, but the abstract and introduction state this without the divisibility condition. The restriction is essential. Under the paper's own Greedy Monroe procedure (§2.2.2), take n=6, k=4, with voters v1,v2,v3 approving {a,b}, v4 approving {d}, v5 approving {e}, and v6 approving {f}. The algorithm uses loads ceil(6/4)=2, 2, 1, 1. A legitimate execution (ties are not specified) picks a first, assigning v1,v2; then, with all remaining candidates tied at one approval, picks d, assigning v4 plus arbitrary v3; then picks e, assigning v5; then f, assigning v6. The output is W={a,d,e,f}. The coalition S={v1,v2,v3} is 2-cohesive with witness T={a,b}: |S|/6 = 1/2 = 2/4, and every voter in S approves both a and b. Yet W ∩ ∪_{v∈S} A_v = {a}, so |W ∩ ∪_{v∈S} A_v| = 1 < 2, violating FPJR (and PJR). Thus the unqualified claim that Greedy Monroe satisfies FPJR is false. The paper's own caveat in §2.2.2 that divisibility is essential for PJR should be carried over to every FPJR statement about Monroe and Greedy Monroe.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1379,"tokens_out":2932,"duration_ms":228028,"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":[{"comment":"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":"Abstract, Section 1, Theorem 3.11"},{"comment":"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.","section":"Section 3.1, proof of Theorem 3.6, Eq. (2)"}],"minor_comments":[{"comment":"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.","section":"Proof of Theorem 3.11"},{"comment":"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.","section":"Example 3.4"},{"comment":"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.","section":"Theorem 4.4"},{"comment":"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).","section":"Definition 3.1"}],"recommendation":"major_revision","confidential_remarks":"The abstract overclaims the Greedy Monroe result, and the counterexample is decisive. The gap in Theorem 3.6 is fixable with a restricted summation. I recommend major revision, as the current version should not be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"FPJR is the missing cell in the justified-representation taxonomy, and the paper gives it real content: priceable committees satisfy it, PER implies it, PAV violates it, and verification is coNP-complete. Those results are new and worth having. I checked the main proofs, including the priceability theorem and the balanced-biclique reductions, and they are largely sound. The hardness results for FJR and core stability are a bonus that fills gaps in the literature.\n\nThe soft spot is the Greedy Monroe claim. Theorem 3.11 is carefully qualified to k|n, but the abstract and introduction say the greedy Monroe rule satisfies FPJR without that condition. That is false. Take n=6, k=4. Voters 1-3 approve {a,b}; voters 4,5,6 approve {d}, {e}, {f}. Under the paper's own greedy procedure, a legitimate execution picks a, then d (with one arbitrary voter), then e, then f, giving W={a,d,e,f}. The coalition {1,2,3} is weakly 2-cohesive with witness {a,b}: 3/6 = 2/4, and each approves both. But W contains only {a} from their approved union, so FPJR is violated. The paper itself notes in Section 2.2.2 that divisibility is essential for PJR; the same caveat has to be attached to every Monroe/FPJR statement. The abstract's unqualified claim is a real overstatement and should be fixed.\n\nThere is also a small local gap in Theorem 3.6: the priceability bound for unelected candidates is applied to T\\O, but T\\O may contain candidates who are actually elected winners outside S. The reader's suggested repair—remove such winners from the witness set—works, but the proof as written needs that extra line.\n\nNone of this undermines the central contribution. FPJR is a natural axiom, the priceability implication is clean, and the hardness reductions are solid. The paper is a serious piece of computational social choice with correct core results and an overbroad claim that is easily corrected. I would send it to peer review, but I would ask the authors to make all Monroe statements carry the k|n condition and patch the Theorem 3.6 gap before it is accepted.","headline":"FPJR is a genuine completion of the taxonomy, but the unqualified Greedy Monroe guarantee in the abstract is false for k∤n.","tokens_in":19295,"tokens_out":3122,"would_cite":true,"duration_ms":29924,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["approval-based multiwinner voting","proportional justified representation","full proportional justified representation","priceability","Monroe rule","method of equal shares","coNP-completeness","core stability"],"falsifier":"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.","tokens_in":18188,"feed_emoji":"🗳️","tokens_out":9725,"duration_ms":88642,"temperature":0.7,"pith_summary":"This paper introduces and studies Full Proportional Justified Representation (FPJR), the missing fourth combination in the standard taxonomy of approval-based proportionality axioms: it uses the weak-cohesiveness condition from Full Justified Representation and the collective-utility representation condition from Proportional Justified Representation. The central claim is that FPJR is a viable middle ground: it is strictly stronger than PJR, strictly weaker than FJR, and incomparable with EJR, yet it is satisfied by priceable committees and, when $k$ divides $n$, by the Monroe rule and its greedy variant. The paper also establishes that Proportional Approval Voting can fail FPJR, showing that EJR does not imply FPJR, and that verifying FPJR, FJR, or core stability for a given committee is coNP-complete. A sympathetic reader would care because FPJR names a fairness guarantee that efficient and commonly discussed rules actually deliver, while still capturing the harder weakly cohesive notion of group solidarity.","feed_headline":"Priceable committees pass a stronger fairness test than thought","feed_subtitle":"Axiom FPJR is satisfied by priceable rules and Monroe, violated by PAV; verification is coNP-complete.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines priceability and proves priceable committees satisfy PJR; the FPJR priceability proof invokes the $|T|=\\ell$ case of that result for the Method of Equal Shares and Phragmén.","marker":"[Peters and Skowron, 2020b]"},{"why":"Supplies the Balanced Biclique construction and hardness reduction for PJR that the FPJR verification proof adapts, and the LS-PAV rule shown to violate FPJR.","marker":"[Aziz et al., 2018a]"},{"why":"Defines JR, EJR, and the core, and gives the EJR hardness reduction reused for FJR and core stability.","marker":"[Aziz et al., 2017]"},{"why":"Defines FJR and provides the example of a weakly cohesive coalition that PAV under-represents, which the paper uses to show EJR does not imply FPJR.","marker":"[Peters et al., 2021b]"},{"why":"Defines PJR and perfect representation and proves PER implies PJR, the comparison baseline for placing FPJR in the axiom hierarchy.","marker":"[Sánchez-Fernández et al., 2017]"},{"why":"Introduces the greedy Monroe rule and establishes its PJR guarantee when $k$ divides $n$; the FPJR proof for Greedy Monroe builds on that assignment scheme.","marker":"[Faliszewski et al., 2018]"},{"why":"Defines the Monroe rule and its optimal assignment objective, which the swap argument of Theorem 3.11 manipulates.","marker":"[Monroe, 1995]"}],"fun_headline_variants":["New axiom strengthens proportional representation in multiwinner voting","Fair committees: priceable rules satisfy new proportional fairness test","FPJR: More proportional fairness than EJR, still achievable","Stronger proportional fairness via priceable rules, not PAV","Method of Equal Shares passes new FPJR test; PAV fails"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New axiom strengthens proportional representation in multiwinner voting","Fair committees: priceable rules satisfy new proportional fairness test","FPJR: More proportional fairness than EJR, still achievable","Stronger proportional fairness via priceable rules, not PAV","Method of Equal Shares passes new FPJR test; PAV fails"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1684,"prompt_tokens":1131,"completion_tokens":553,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":747,"completion_tokens_details":{"reasoning_tokens":470}},"tokens_in":747,"tokens_out":553,"duration_ms":5766,"temperature":1.0,"reasoning_tokens":470,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:39:20.680277+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Justified representation in approval-based committee voting","cited_arxiv_id":null,"evidence_quote":"Defines JR, EJR, and the core, and gives the EJR hardness reduction reused for FJR and core stability."},{"cited_title":"Achieving fully proportional representation by clustering voters","cited_arxiv_id":null,"evidence_quote":"Introduces the greedy Monroe rule and establishes its PJR guarantee when $k$ divides $n$; the FPJR proof for Greedy Monroe builds on that assignment scheme."}],"review_version":1}