{"id":"74c34aca-462d-4bda-a654-34f50f97c371","arxiv_id":"2608.05397","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"FJR-GJCR is a polynomial-time approval-based multiwinner rule satisfying Full Justified Representation, and MES committees are shown to be not always extendable to satisfy FJR.","lead":"A polynomial-time voting rule for approval-based multiwinner elections now guarantees Full Justified Representation, a strong proportionality axiom that previously required an exponential-time algorithm. The paper also shows that Method of Equal Shares committees cannot always be extended to satisfy FJR, settling two open problems in computational social choice.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's polynomial-time proof claims p_ℓ(c) has denominator k(k+1), but p_ℓ(c) can have denominator k(k+1)·lcm(1..k); the complexity bound is unproven as written.","rationale":"I stress-tested both central theorems. The FJR proof (Theorem 1) is a potential-function argument. I checked the base case, the inductive step for candidates bought at ℓ≥β, and the two cases (c∈T and c∉T). The algebra is correct provided that when an approving voter already has β−1 approved candidates, the proof stops because FJR is satisfied; the paper omits this boundary case, but it is easily patched. No fatal flaw emerged. The MES counterexample (Proposition 2) also checks out: MES buys B, D, F, G in that order, spending all money except 2 units that cannot be pooled, and any extension leaves V1∪V2 voters with at most 26 approvals against the required 27. The abstract's claim that MES selects k candidates is a minor error (the example selects 76 instead of 77) but does not affect the extension result. The serious issue is in Theorem 2. The proof asserts that p_ℓ(c) has denominator k(k+1). This is false: p_ℓ(c) is a sum of fractions with denominators ℓ−|A_i∩W| ranging over 1..k, so the common denominator can be k(k+1)·lcm(1..k). For k=4, a sum of 1/3 and 1/4 gives 7/12, whose denominator does not divide 20. Thus the polynomial-time proof is invalid as written. The theorem may still be true — the corrected denominator L has O(k) bits and k≤m, so the input size is at least m — but the paper must replace the incorrect denominator claim with a correct complexity analysis. This is a load-bearing gap because 'Polynomial-Time' is half of the paper's central contribution, and the reader's identified weakest assumption (the FJR potential invariant) is not the point of failure.","tokens_in":8790,"tokens_out":44548,"duration_ms":350189,"concrete_test":"Construct an instance with k=4 where, at level ℓ=4, one voter has p(i)=0 and |A_i∩W|=0, and another has p(i)=0 and |A_i∩W|=1 (the latter obtained through a zero-payment purchase). Then p_ℓ(c)=1/4+1/3=7/12, whose denominator 12 does not divide k(k+1)=20, contradicting the claim in the proof of Theorem 2. Next, re-derive Theorem 2 using the correct common denominator L=k(k+1)·lcm(1,...,k); verify that L has O(k) bits and that every arithmetic operation (summation, comparison with n/k, floor computation) runs in time polynomial in n and m. If the corrected proof goes through, the central claim survives; if not, the polynomial-time assertion is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithm 1 is both polynomial-time and satisfies FJR. I examined the FJR proof (Theorem 1) and found the potential-function argument essentially sound: the base case is correct, the inductive step for candidates bought at ℓ≥β works, and the two cases (c∈T and c∉T) are algebraically valid provided one stops when an approving voter already has β−1 approved candidates (the paper omits this boundary case, but it is easily patched). The MES counterexample (Proposition 2) also checks out: MES buys B, D, F, G in that order, leaving only 2 units of unpoolable budget, and any extension leaves V1∪V2 voters with at most 26 approvals against the required 27. The real problem is in Theorem 2. Its proof asserts that each p_ℓ(c) is a rational number with denominator k(k+1). This is false. p_ℓ(c) is a sum of terms (1−p(i))/(ℓ−|A_i∩W|), where the denominators ℓ−|A_i∩W| range from 1 to k. The common denominator of the sum can be k(k+1)·lcm(1,...,k), not merely k(k+1). For example, with k=4, ℓ=4, and two voters with p(i)=0, one with |A_i∩W|=0 and one with |A_i∩W|=1, the sum is 1/4 + 1/3 = 7/12, and 12 does not divide 20 = k(k+1). Consequently, the proof does not establish that p_ℓ(c) can be represented or compared in polynomial time. A corrected proof using the common denominator L = k(k+1)·lcm(1,...,k) is plausible — L has O(k) bits and k ≤ m, so the input size is at least m — but the paper's stated argument is invalid. Since Theorem 2 provides half of the paper's central contribution, this is a load-bearing gap in the written proof.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new approval-based multiwinner voting rule, FJR-GJCR (Algorithm 1), which is designed to satisfy Full Justified Representation (FJR). The central claims are that the rule selects at most k candidates (Lemma 1), satisfies FJR (Theorem 1), is polynomial-time computable (Theorem 2), and also satisfies EJR+ (Corollary 1). The paper additionally presents an instance showing that a committee returned by the Method of Equal Shares cannot always be extended to an FJR committee (Proposition 2).","tokens_in":9211,"tokens_out":17543,"duration_ms":159395,"significance":"If the results are correct, the paper resolves a central open question in the area by giving the first polynomial-time rule satisfying FJR. The proof of Theorem 1 is, in substance, a sound potential-function argument, and the MES counterexample in Proposition 2 is convincing and correctly shows that the natural extension question has a negative answer. The paper is also careful in that the main FJR guarantee is derived directly from the algorithm's payment schedule rather than from fitted parameters or circular assumptions. The main weakness is that the proof of Theorem 2, which is half of the paper's central claim, contains a false statement about the denominators of the quantities p_ell(c).","major_comments":[{"comment":"The proof of Theorem 2 claims that each p_ell(c) is a rational number with denominator k(k+1). This is false. Since p(i) is a multiple of 1/(k(k+1)), each summand (1-p(i))/(ell - |A_i cap W|) has denominator k(k+1) * d_i for some d_i in {1,...,k}, so p_ell(c) has a denominator dividing k(k+1) * lcm(1,...,k). For example, with k=4, ell=4, p(i)=0 for two voters with |A_i cap W| equal to 0 and 1, the sum is 1/4 + 1/3 = 7/12, and 12 does not divide 20 = k(k+1). Therefore the polynomial-time claim is not established as written. A corrected proof using the common denominator L = k(k+1) * lcm(1,...,k) is plausible, because L has O(k) bits and k <= m, but the argument in the manuscript must be rewritten.","section":"Section 3, Theorem 2"},{"comment":"The inductive step in Theorem 1 divides by beta - |A_i cap W_j| - 1. If a voter in the weakly cohesive group has beta - |A_i cap W_j| = 1 before a candidate is bought, this denominator is zero after the purchase. The proof does not address this boundary case. The gap is repairable by arguing under a contradiction assumption that no voter in the group has yet reached beta approvals, or by explicitly removing voters who become satisfied from the potential, but the current text is formally incomplete.","section":"Section 3, Theorem 1 proof"},{"comment":"The proof of Corollary 1 asserts that adding clones of an unelected candidate does not change the execution of FJR-GJCR. This independence-of-cloning-losers property is not proved, and it is not obvious from the pseudocode, since Algorithm 1 does not specify a tie-breaking rule for choosing among candidates with equal p_ell(c). If the rule is intended to select a candidate with maximal p_ell(c), the clone-invariance claim needs a proof or a carefully chosen tie-breaking convention; without this, the EJR+ conclusion is not justified.","section":"Corollary 1"}],"minor_comments":[{"comment":"The quantifier \"for every ell in [k]\" in Definition 2 is unused in the condition and conclusion; the definition only depends on beta and the weakly cohesive group. This should be cleaned up for clarity.","section":"Definition 2"},{"comment":"The pseudocode in lines 8-10 does not specify which candidate c is selected when multiple candidates satisfy p_ell(c) >= n/k, although the prose above the algorithm says the candidate with largest total payment is added. The pseudocode and prose should be made consistent.","section":"Algorithm 1"},{"comment":"The introduction to Proposition 2 says the instance is one \"in which the method of equal shares selects k candidates,\" but the proof shows that MES selects 76 candidates while k=77. The wording should be corrected to say that MES selects a committee of size at most k or that it leaves one seat unfilled.","section":"Section 3, Proposition 2"},{"comment":"In the last paragraph of the proof, \"approves 27 voters in the extension\" should read \"approves 27 candidates in the extension.\"","section":"Proposition 2 proof"},{"comment":"There are several typographical errors, including \"could bought\" in the first sentence of Theorem 1, \"reasearch\" in the acknowledgments, and \"intersting\" and \"approp-priatly\" in the conclusion. These should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main FJR proof and the MES counterexample are, in my assessment, essentially sound, and the polynomial-time issue in Theorem 2 appears fixable with a standard common-denominator argument. I therefore do not see grounds for rejection. However, because the polynomial-time claim is a central advertised contribution and the proof as written is invalid, a major revision is appropriate. The authors should also tighten the proof of Theorem 1's boundary case and either prove or remove the cloning-losers assertion in Corollary 1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper settles the open question of whether a committee satisfying Full Justified Representation can be computed in polynomial time. The main theorem is essentially right: I checked the potential function argument in Theorem 1 and it holds, with one small boundary case that is easy to patch (when a voter reaches beta and the denominator would hit zero). The algorithm itself, FJR-GJCR, is a genuinely new combination of the GJCR framework with a payment-scheme rounding trick, and the FJR proof is a real contribution. The negative result about MES extensions also checks out with the numbers I ran.\n\nThe soft spots are real but not fatal. Theorem 2 contains a false statement: each p_l(c) does not have denominator k(k+1) as claimed, because the sum over voters has denominators l - |A_i∩W| that range up to k, so the common denominator can be k(k+1)*lcm(1..k). This is still polynomially many bits: lcm has O(k) bits and k <= m, so the theorem is true and the fix is routine, but the proof as written is wrong. A referee should catch this. Corollary 1 (EJR+) is underargued: the claim that adding clones does not change the execution of FJR-GJCR is asserted without proof, and it is not obvious. The MES example in Proposition 2 says MES selects k candidates but the construction yields 76 out of k=77; the argument still works, but the text should be corrected. The informal Proposition 1 is fine as motivation.\n\nWho is this for? Researchers in approval-based multiwinner voting and computational social choice. The central result is significant and the proof technique is inventive. The issues are patchable, not fundamental. I would send it to peer review and ask for a corrected Theorem 2 proof, a proper proof of the clone-independence claim or a reference, and a cleanup of the MES example. After that, it would be a strong paper.","headline":"Resolves the polynomial-time FJR open question with a sound main proof; the polynomial-time proof has a correctable gap and the EJR+ corollary needs work.","tokens_in":578,"tokens_out":4807,"would_cite":true,"duration_ms":69023,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that FJR-GJCR, a polynomial-time variant of the Greedy Justified Candidate Rule, always returns a committee of at most k candidates satisfying Full Justified Representation, and that MES committees cannot always be…","keywords":["approval-based multiwinner voting","full justified representation","extended justified representation plus","greedy justified candidate rule","method of equal shares","proportional representation","polynomial-time committee selection","virtual payment scheme"],"falsifier":"Run FJR-GJCR on an instance that contains a weakly $(\\beta,T)$-cohesive group and inspect the returned committee $W$: the central claim would be refuted by any output where every member of that group has fewer than $\\beta$ candidates in $W$. A more local falsifier would be an intermediate step in the algorithm, while the level is still at least $\\beta$, at which $\\sum_{t\\in T\\setminus W}\\sum_{i\\in N'\\cap N_t}\\frac{1-p_i}{\\beta-|A_i\\cap W|}$ is strictly smaller than $|T\\setminus W|\\cdot n/k$, since the proof's invariant says that cannot happen.","tokens_in":8573,"feed_emoji":"🗳️","tokens_out":13344,"duration_ms":104420,"temperature":0.7,"pith_summary":"Approval-based multiwinner voting asks how to pick a committee of fixed size so that no large bloc of voters approving the same candidates is left without proportional representation. Full Justified Representation (FJR) is one of the strongest forms of that guarantee: whenever a sufficiently large group all approves at least $\\beta$ candidates in some set $T$, some voter in the group must approve $\\beta$ candidates on the committee. Before this paper, FJR was only known to be achievable by an algorithm that could take exponentially long. The paper resolves this by proposing FJR-GJCR, a polynomial-time variant of the Greedy Justified Candidate Rule that always returns an FJR committee of size at most $k$. Its payment scheme charges voters according to how many approved candidates they still lack, rounded to common denominators so every number stays rational and polynomial-size. The paper also shows that committees returned by the method of equal shares cannot always be extended to satisfy FJR, so a dedicated rule is genuinely needed.","feed_headline":"Committee rule meets Full Justified Representation in polynomial time","feed_subtitle":"The FJR-GJCR rule answers a key open question, and MES cannot always be patched to FJR.","key_machinery":"The carrying object is a virtual payment scheme grafted onto the Greedy Justified Candidate Rule. At each target level $\\ell$, a candidate $c$ is buyable when the total over its approvers of the quotient $\\frac{1-p(i)}{\\ell-|A_i\\cap W|}$ is at least $n/k$, where $p(i)$ is voter $i$'s already spent budget and $|A_i\\cap W|$ their number of approved candidates in the current committee; buying $c$ charges voters a rounded fraction of that quotient, with all payments multiples of $\\frac{1}{k(k+1)}$. The rounding does two jobs: each purchase provably spends more than $\\frac{n}{k+1}$, bounding the committee size by $k$, and every intermediate number stays rational with polynomial-size representation. The FJR proof maintains a potential for every weakly $(\\beta,T)$-cohesive group — a voter set $N'$ whose members each approve at least $\\beta$ candidates in $T$ while $|N'|\\ge |T|n/k$ — namely that while all group members still have fewer than $\\beta$ approved candidates and the algorithm is still running at level $\\ell\\ge\\beta$, the group's remaining payments toward unbought candidates in $T$ never drop below $|T\\setminus W|\\cdot n/k$, forcing some member to reach $\\beta$ approvals.","core_discovery":"On the paper's own terms, the central discovery is that Full Justified Representation is compatible with efficient computation: Algorithm 1 runs in time polynomial in $n$, $m$, and $k$, selects at most $k$ candidates, and satisfies FJR for every approval profile. The rule also satisfies Extended Justified Representation Plus (EJR+), showing FJR and EJR+ are compatible. As a second contribution, Proposition 2 provides an explicit instance where the method of equal shares selects $k$ candidates and no extension of its committee can meet FJR, answering an open question negatively.","pith_inferences":["The quotient $\\frac{1-p(i)}{\\ell-|A_i\\cap W|}$ is a voter-specific price per missing approved seat; an editor's reading is that any purchase rule which locally minimizes such ratios may inherit FJR, so the invariant might transfer to other greedy payment rules.","The non-extension result for MES suggests a broader negative landscape: other rules whose purchases are constrained by a fixed per-voter budget may also resist patchings, so a natural next step is to classify which priceable rules can be extended to FJR.","Since all payments are multiples of $\\frac{1}{k(k+1)}$, scaling by $k(k+1)$ turns the algorithm into integer arithmetic, which could make it practical on large election data.","The Droop-FJR variant sketched at the end points toward a testable conjecture: the potential-invariant argument should carry over to participatory budgeting whenever an 'up to one project' version of FJR is used."],"forward_implications":["FJR committees can now be produced efficiently for every instance, converting an open question into a polynomial-time algorithm.","The same committee simultaneously satisfies EJR+, so FJR and EJR+ can be met without sacrificing either.","Because MES committees cannot always be extended to FJR, any guarantee at the FJR level has to come from a rule built for it, not from post-processing MES.","Replacing $n/k$ by $\\frac{n}{k+1}+\\frac{1}{k(k+1)}$ yields a Droop-style version of FJR with the same polynomial-time behavior."],"supporting_citations":[{"why":"Frames approval-based committee voting and introduces core stability and extended justified representation, the axioms FJR strengthens.","marker":"Aziz et al. [2017]"},{"why":"Introduces the method of equal shares and priceability; MES is the benchmark rule that the paper shows cannot always be extended to FJR.","marker":"Peters and Skowron [2020]"},{"why":"Defines Full Justified Representation, proves FJR committees exist via a non-polynomial rule, and supplies the payment lemma the FJR proof builds on.","marker":"Peters et al. [2021]"},{"why":"Defines EJR+ and the Greedy Justified Candidate Rule, whose level-by-level structure Algorithm 1 adapts.","marker":"Brill and Peters [2023]"},{"why":"Shows GJCR satisfies FJR when it selects exactly k candidates; the EJR+ corollary follows its argument.","marker":"Peters [2024]"},{"why":"Introduces the weaker FPJR axiom and flags polynomial-time FJR as a central open question, the question this paper answers.","marker":"Kalayci et al. [2025]"},{"why":"Provides the Droop-quota rounding trick of paying strictly more than n/(k+1), which bounds the committee size and guides the Droop-FJR extension.","marker":"Casey and Elkind [2025]"}],"fun_headline_variants":["Polynomial-time rule satisfies Full Justified Representation","Full Justified Representation now achievable in polynomial time","Open question answered: FJR committee in polynomial time","MES cannot always be patched to satisfy FJR","New rule: polynomial-time FJR, and MES extension fails"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on a potential invariant: for every weakly $(\\beta,T)$-cohesive group whose members all still have fewer than $\\beta$ approved candidates while the algorithm runs at level $\\ell\\ge\\beta$, the group's remaining virtual payments toward the unbought candidates in $T$ must stay at least $|T\\setminus W|\\cdot n/k$; if the invariant ever failed, the algorithm could stop at level $\\beta$ with none of those voters represented.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time rule satisfies Full Justified Representation","Full Justified Representation now achievable in polynomial time","Open question answered: FJR committee in polynomial time","MES cannot always be patched to satisfy FJR","New rule: polynomial-time FJR, and MES extension fails"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000803,"raw_usage":{"total_tokens":3443,"prompt_tokens":777,"completion_tokens":2666,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":393,"completion_tokens_details":{"reasoning_tokens":2588}},"tokens_in":393,"tokens_out":2666,"duration_ms":17964,"temperature":1.0,"reasoning_tokens":2588,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:56:04.471795+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FJR-GJCR on an instance that contains a weakly $(\\beta,T)$-cohesive group and inspect the returned committee $W$: the central claim would be refuted by any output where every member of that group has fewer than $\\beta$ candidates in $W$. A more local falsifier would be an intermediate step in the algorithm, while the level is still at least $\\beta$, at which $\\sum_{t\\in T\\setminus W}\\sum_{i\\in N'\\cap N_t}\\frac{1-p_i}{\\beta-|A_i\\cap W|}$ is strictly smaller than $|T\\setminus W|\\cdot n/k$, since the proof's invariant says that cannot happen.","supporting_citations":[],"review_version":1}