{"id":"2f2e3244-abf0-4d99-bd1f-6d8587df857c","arxiv_id":"2608.05417","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A descending-budget algorithm with gap-normalized voter offers computes Hare-FJR and Droop-FJR committees in polynomial time, resolving an open problem in approval-based multiwinner voting.","lead":"This paper presents a new algorithm that computes committees satisfying Full Justified Representation, a strong proportionality guarantee, in polynomial time for both Hare and Droop quota conventions. Previously, such committees could only be found by the computationally demanding Greedy Cohesive Rule, so this settles an open question in multiwinner voting theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the historical-payment invariant and the Hare/Droop double-counting proofs appear sound.","rationale":"I verified the main proof chain: Lemma 5.1 budget conservation, Lemma 5.2 historical-payment invariant, Corollary 5.3, Lemma 5.5 row lower bound, Lemma 5.6 column bounds, the normal-terminal double counting, and the full-seat arguments in Lemmas 5.7 and 5.9. The phase-ordering reasoning in Theorems 5.8 and 5.10 is sound: if the paid committee fills at phase g, a violation at level ell forces g<ell for Hare and ell>g for Droop, so phase ell was processed earlier and must have ended normally. The strict inequality in the unselected column sum is justified because T\\P is nonempty and every terminal bid is strictly below lambda. Complexity and denominator bounds in Section 4 are correct, and padding only increases utility, so using P subset of W in the violation argument is valid. I found no circular reasoning, no fitted parameters, and no step where an active voter's historical payment could exceed her current offer. The absence of code is a minor reproducibility issue for a theory paper, not a correctness concern.","tokens_in":17149,"tokens_out":14605,"duration_ms":143045,"concrete_test":"Implement Algorithm 2 exactly and an exhaustive FJR checker for all profiles with n,m<=7 and k<=m; enumerate every nonempty S, T, and ell in [1,k] satisfying the Hare or Droop quota condition and u_i(T)>=ell, then verify that the algorithm's output has no violation witness for either lambda_H or lambda_D. If any counterexample appears, re-examine Lemma 5.2's induction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the core proof, I have no load-bearing objection. The real risk point is the historical-payment invariant (Lemma 5.2), exactly as the Reader flags: if it failed, the Lemma 5.5 row bound and both double-counting contradictions would collapse. I re-derived the invariant and it holds. In the same-phase transition, an active voter's offer changes from r/d to (r-x)/(d-1), which is at least r/d because x is capped by r/d; since d>=2 and x<=r/d, (r-x)/(d-1) >= r/d. In the phase-down transition, alpha_h = r/(h-u) >= r/(h+1-u) = alpha_{h+1}, and voters with |Ai|=h have no prior payments because they were ineligible in all higher phases. The full-seat Lemmas 5.7 and 5.9 also check out: the Hare case exhausts all budgets, and the Droop residual lower bound (g-ell+1)/g follows from a>=1/g and d>=g-ell+1 or g-ell+2. I found no missing case or hidden assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a deterministic polynomial-time algorithm, termed the descending-budget algorithm, that constructs committees satisfying Full Justified Representation (FJR) under both Hare and Droop quota conventions. For any approval-based multiwinner election and fixed voter/candidate orders, the algorithm with candidate price λH = n/k returns a Hare-FJR committee, while with price λD = n/(k+1) it returns a committee satisfying the more demanding Droop-FJR axiom of Casey and Elkind. The algorithm maintains a virtual budget per voter, computes gap-normalized offers, and uses capped charging; the proof relies on a historical-payment invariant and a row–column double-counting argument. The paper also establishes an O(kmn) rational-operation bound with polynomial bit complexity.","tokens_in":17189,"tokens_out":15889,"duration_ms":122010,"significance":"If the result holds, it resolves an open problem: FJR committees were previously known to exist via the non-polynomial Greedy Cohesive Rule, and no polynomial-time construction was known for either Hare-FJR or Droop-FJR. The proof is self-contained and the key invariant (Lemma 5.2) is verified carefully; the double-counting arguments are elegant and the Droop full-seat lemma is a neat use of residual budgets. The algorithm is deterministic and parameter-free, and the runtime is polynomial in the input size. These strengths make the paper a substantial contribution to the justified-representation literature. I verified the core lemmas (5.2, 5.5, 5.7, 5.9) independently and found no gap.","major_comments":[],"minor_comments":[{"comment":"The first sentence of the abstract reads 'I studyFull Justified Representation'; a space is missing between 'study' and 'Full'. This is the only typographical issue I found in the abstract.","section":"Abstract"},{"comment":"The two 'break' statements inside the for-loop of Algorithm 2 exit only the inner 'while' loop. After the paid construction reaches t = k, the outer 'for' loop continues through the remaining phases, each with an empty while iteration. Consider restructuring the control flow or adding a comment so that readers do not mistakenly think the entire algorithm halts at that point.","section":"Algorithm 2 (Section 3.4)"},{"comment":"In the same-phase case of the proof, the equality a' - a = (a - x)/(d-1) uses r = a d; spelling out this substitution would improve readability.","section":"Section 5.1, Lemma 5.2"},{"comment":"The implication chain 'Core Stability =⇒ FJR' is mentioned without a formal definition of core stability. Since the paper does not rely on core stability, a one-sentence informal definition or a pointer to the references would be enough for readers outside the subfield.","section":"Section 1.2"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and makes a significant contribution. The only issues I identified are minor editorial/presentation items. I recommend acceptance after minor revisions. The self-citation [AT26] is used only for terminology in the related-work section and does not affect the novelty of the main result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper closes the polynomial-time FJR construction problem, and the proof is solid. I went through the key lemmas the way you would, and they hold. The gap-normalized offer is the right new ingredient; without it, MES-style budgets don't track how far a voter is from the current threshold. The descending phase order plus the historical-payment invariant (Lemma 5.2) is what makes the double counting work, and the Droop full-seat case is a genuinely separate argument, not a rehash of the Hare one.\n\nWhat's new: both a Hare-FJR and a Droop-FJR construction in O(kmn) rational operations, deterministic given fixed orders. The proofs are by contradiction from invariants, not by assuming the conclusion. The row-column accounting is standard in spirit, but the mixed cost (historical payments for selected, current offers for unselected) is clever, and Lemma 5.5 is the moment where everything clicks.\n\nSoft spots are minor. The algorithm is not neutral or anonymous; the paper says so. The bit-complexity bound is polynomial but the exponent depends on k^2 log k; that's fine for a theory result but could matter in practice, not that anyone would run this on large instances. The related-work section includes a hierarchy of SJR/AJR that isn't used later; it's a bit of a detour but not wrong. There's no code, but for a computational social choice theory paper that's not a red flag. The self-citation [AT26] is only for terminology, so no issue.\n\nThe paper deserves a serious referee. If I were the editor, I'd send it out. The central claim is important and the proof looks correct; the only things a referee might quibble with are presentation-level. I'd also bring it to the reading group.","headline":"This is the real thing: a polynomial-time algorithm for Hare- and Droop-FJR, and the proofs survive a close read.","tokens_in":17896,"tokens_out":2036,"would_cite":true,"duration_ms":17910,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single descending-budget algorithm now computes exact justified representation in polynomial time.","keywords":["approval-based multiwinner elections","Full Justified Representation","Hare quota","Droop quota","proportional representation","budget-based algorithm","polynomial-time construction"],"falsifier":"Exhaustively enumerate all approval profiles with small parameters (for instance n up to 7, m up to 7, k up to 4) together with all voter and candidate orders; for each run of the algorithm, brute-force check every triple (S,T,l) for a Hare- or Droop-FJR violation. A single violating committee would refute the theorem; finding none in the full enumeration would strongly support it but would not prove it.","tokens_in":16755,"feed_emoji":"🗳️","tokens_out":7107,"duration_ms":64417,"temperature":0.7,"pith_summary":"This paper presents a single deterministic algorithm for approval-based multiwinner elections and proves that it satisfies Full Justified Representation (FJR), the strongest standard proportionality guarantee in this setting. With candidate price n/k it outputs a Hare-FJR committee, and with candidate price n/(k+1) it outputs a committee satisfying the stricter Droop-FJR axiom; both runs use O(kmn) rational operations. The result matters because efficient rules previously guaranteed only weaker axioms such as EJR, while the known FJR constructions were not known to run in polynomial time. The proof rules out every possible FJR violation by a double-counting argument anchored on one invariant about voters' payments.","feed_headline":"One budget algorithm delivers full representation in polynomial time","feed_subtitle":"The same rule, with two candidate prices, resolves the open search for efficient Full Justified Representation.","key_machinery":"Gap-normalized offers $\\alpha$^(t)_{i,h} = r^(t)_i / (h - u_i(P^(t))) together with the historical-payment invariant carry the argument. The invariant says that whenever a voter is active at a decision snapshot, her current offer is at least every payment she made for an earlier selected candidate; this allows past payments on candidates outside a potential witness set to be replaced by current offers, so each active voter assigns mixed cost at least 1 to any approved set of size h. The same invariant and row-column accounting give both FJR theorems, with the Droop proof adding only the full-seat residual-budget lemma.","core_discovery":"At each representation target h, the algorithm treats every voter who approves at least h candidates but currently has fewer than h winners as active; her offer to each unselected approved candidate is her remaining budget divided by the number of additional winners she still needs. A candidate is purchased when the offers of active approvers reach the common price. The paper's central claim is that this process cannot output an FJR-violating committee: at the terminal snapshot of the witness level, each witness voter has mixed cost at least 1 on her approved part of the witness set, while the same costs summed by candidate fall strictly below the quota-scaled size of the witness set, contradicting the definition. For the Droop price, the case where all k seats are purchased before the witness phase ends is handled by a separate residual-budget lemma showing the witness voters would need to retain more than the exact leftover total n/(k+1).","pith_inferences":["The same gap-normalized idea should transfer to additive-utility participatory budgeting, where the representation gap is a real-valued utility shortfall rather than an integer approval count; such a transfer would need a new proof of the analogue of the historical-payment invariant.","A likely route to anonymity and neutrality is to replace the fixed candidate order with any tie-breaking rule that preserves the invariant, since the proof does not otherwise use the order.","Because FJR verification is coNP-complete, the algorithm's output cannot be certified by direct search; in practice, a proof certificate would have to encode the invariant chain itself, pointing toward machine-checkable verification of the double-counting argument."],"forward_implications":["Every explicitly represented approval-based election admits a size-k Hare-FJR committee, and the algorithm constructs one deterministically in O(kmn) rational operations once voter and candidate orders are fixed.","Every such election also admits a Droop-FJR committee, so the stronger Droop-quota version of FJR is constructible in polynomial time, not just known to exist.","Because FJR implies EJR, PJR, and JR, every output committee satisfies the full classical justified-representation hierarchy from EJR downward.","The Droop-price output automatically satisfies Hare-FJR, so the same algorithm covers both quota conventions with only a one-line price change.","All arithmetic is exact rational arithmetic with denominators of bounded bit length, so the polynomial bound holds in the binary input model, not merely in a value-based model."],"supporting_citations":[{"why":"Introduced FJR and the Greedy Cohesive Rule, the existence result for which this paper gives an efficient construction.","marker":"[PPS21]"},{"why":"Defined the Droop-FJR axiom and showed a modified GCR satisfies it, the target of the Droop-price instantiation.","marker":"[CE26]"},{"why":"Introduced FPJR and proved FJR verification coNP-complete, the obstacle that motivates an implicit witness-elimination proof.","marker":"[KLK25]"},{"why":"Provided the descending-level organization of GJCR, from which the algorithm's phase structure is taken.","marker":"[BP23]"},{"why":"Formulated the virtual-budget and candidate-price interpretation of the Method of Equal Shares, which the new algorithm adapts.","marker":"[PS20]"},{"why":"Introduced the original JR, PJR, and EJR axioms whose hierarchy FJR extends.","marker":"[ABC+17]"}],"fun_headline_variants":["Polynomial-time FJR under Hare and Droop quotas","One budget algorithm, two quotas, full representation fast","Budget rule achieves FJR for Hare and Droop in poly time","Efficient FJR: single algorithm solves both quota cases","Hare and Droop FJR now polynomial with a budget method"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire result rests on the invariant that a voter who is still short of the current representation target never offers less for her next seat than she paid for any earlier seat; if that invariant could fail on some valid run, both FJR theorems would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time FJR under Hare and Droop quotas","One budget algorithm, two quotas, full representation fast","Budget rule achieves FJR for Hare and Droop in poly time","Efficient FJR: single algorithm solves both quota cases","Hare and Droop FJR now polynomial with a budget method"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00061,"raw_usage":{"total_tokens":2797,"prompt_tokens":863,"completion_tokens":1934,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":1850}},"tokens_in":479,"tokens_out":1934,"duration_ms":11859,"temperature":1.0,"reasoning_tokens":1850,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:34:08.332748+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively enumerate all approval profiles with small parameters (for instance n up to 7, m up to 7, k up to 4) together with all voter and candidate orders; for each run of the algorithm, brute-force check every triple (S,T,l) for a Hare- or Droop-FJR violation. A single violating committee would refute the theorem; finding none in the full enumeration would strongly support it but would not prove it.","supporting_citations":[],"review_version":1}