{"id":"4960e7f7-3ee9-4c7f-b7f2-fb6f112bc754","arxiv_id":"2505.12699","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper gives fixed-parameter approximation schemes, a lossy kernel, and an additive approximation for submodular multiwinner election on K_{d,d}-free profiles, and proves FPT for PAV parameterized by total score.","lead":"This paper designs fixed-parameter approximation algorithms for selecting committees in approval-based multiwinner elections when voters have diverse approval patterns, meaning no d voters approve the same set of d candidates. It also answers an open question by showing that, under the proportional approval voting rule, the problem is fixed-parameter tractable when the required score is the parameter.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 5's K_{d,d}-free edge bound is asserted without proof and false as stated; it blocks Theorem 1's high-threshold case and the kernel/additive results built on it.","rationale":"I focused on Claim 5 because Theorem 1's high-threshold case is the central engine of the paper: Claim 6, the lossy kernel (Theorem 2), and the additive approximation (Theorem 3) all call on it. The reader's weakest assumption identified exactly this edge-count gap and also the Section 6 harmonic-number errors. I agree with the reader's conditional verdict. The contributions are significant and may be repairable, but the current proof of the central theorem contains an unjustified—and, as the K_{2,2}-free example shows, numerically false—graph-theoretic bound. The Section 6 PAV argument has a separate, easily checked false inequality, so the claimed open-question resolution is also not supported by the text as written. I therefore keep the reader's CONDITIONAL verdict unchanged rather than accepting the proofs at face value or rejecting the paper's claims outright.","tokens_in":21586,"tokens_out":17728,"duration_ms":195657,"concrete_test":"Test Claim 5's edge bound with d=2, k=2, r=10. Let B be the 8 candidates of Cr\\Oℓ and let U be 4 candidates representing O∪Oℓ. Take four edge-disjoint perfect matchings of K_8 (a 1-factorization provides them); for each matching M_s and each edge {b_i,b_j} in M_s, add one voter approving {u_s,b_i,b_j}. Every pair of candidates has at most one common voter, so the profile graph is K_{2,2}-free, and every added voter is in N(O∪Oℓ) and has degree 3 > d. The number of edges from these high-degree voters to B is 2·(4 matchings × 4 edges) = 32, whereas the paper's bound for this instance is |Cr|d(d−1) = 10·2 = 20. Recomputing Claim 5's inequality with the true edge count shows the asserted upper bound fails; any repair must supply a different counting argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is Claim 5 in Section 3, Case 2 of Theorem 1. To upper-bound the edges between Cr\\Oℓ and N(O∪Oℓ), the proof asserts that voters of degree > d can contribute at most |Cr|d(d−1) edges, justified only by K_{d,d}-freeness. This is not a standard consequence of K_{d,d}-freeness: with a fixed candidate side of size |Cr|, the voter side can be arbitrarily large, and Kővári–Sós–Turán-type counting does not give a linear bound in |Cr|. In fact, the claimed bound is false as a graph-theoretic statement: K_{d,d}-free graphs can have high-degree voters whose total incident edges exceed |Cr|d(d−1) (see concrete test). Since the only mechanism in Claim 5 converts the per-step replacement loss α_i into the final ε-scaled guarantee via (|Cr|−k)α_i ≤ 2d·sco(O)/λmin + |Cr|d(d−1), a larger high-degree term destroys the high-threshold case of Theorem 1. Claim 6, the lossy kernel in Theorem 2, and the additive approximation in Theorem 3 all inherit this gap. Separately, Section 6 contains an independent false inference: from t ≥ H_k = Σ 1/i it concludes k ≤ 2t (false for all large k), and later concludes δ < 2t from t > H_δ (also false). These inequalities are the steps that remove k from the PAV parameter, so the claimed resolution of the Yang–Wang open question is also not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Submodular Multiwinner Election (SM-MWE) problem under Thiele rules, assuming the approval profile graph is K_{d,d}-free. It claims an FPT approximation scheme with running time (dk/ε)^{O(d^2 k)} n^{O(1)} (Theorem 1), a (1-ε)-approximate polynomial-time lossy kernel (Theorem 2), an additive one-member approximation (Theorem 3), and an FPT algorithm for the PAV rule parameterized by the score threshold t, which would resolve an open question of Yang and Wang. The framework also allows voter-specific Thiele functions. The proof of Theorem 1 splits into a low-threshold case handled by a sunflower-based reduction and a high-threshold case based on restricting to the top r candidates. The lossy kernel combines a candidate-reduction step and a voter-reduction step. The PAV FPT algorithm uses color coding with additional case distinctions to eliminate the committee size k from the parameter.","tokens_in":21977,"tokens_out":18015,"duration_ms":169089,"significance":"If correct, the results would generalize Skowron's FPT approximation scheme from bounded approval sets to K_{d,d}-free profiles, would provide the first lossy kernel for SM-MWE, and would settle an open question on PAV. The paper also introduces voter-specific OWA vectors, which is a useful modeling generalization. However, two central technical pillars are not sound as written: the edge-count bound in Claim 5 is false, and the harmonic-number inequalities in Section 6 are mathematically incorrect. These flaws invalidate the high-threshold case of Theorem 1 and the claimed FPT parameterization by t for PAV.","major_comments":[{"comment":"The proof of Claim 5 asserts that in a K_{d,d}-free bipartite graph, the high-degree vertices contribute at most |C_r|d(d-1) edges to N(O∪Oℓ), and the surrounding text alternatively claims the bound \\binom{|C_r|}{d}(d-1). The linear bound is false: for d=3, take C_r as the point set of an affine plane of order q and V as the set of all q^2+q lines. Each line has degree q, and any three lines have at most one common point, so the graph is K_{3,3}-free; yet the total number of edges is q^3+q^2, which exceeds 6q^2 = |C_r|·3·2 for q≥7. The binomial bound, while true, is not the bound used in the displayed inequality and is superlinear in |C_r|, so the subsequent derivation of Σ α_i ≤ ε·sco(O) in Claim 5 fails. Therefore the high-threshold case of Theorem 1, and with it Theorem 2 and Theorem 3, are not established as written.","section":"Section 3, Claim 5 (Theorem 1, Case 2)"},{"comment":"The case analysis for the PAV rule relies on the inferences 'if t ≥ H_k then k ≤ 2t' and 'if t > H_δ then δ < 2t', where H_m is the m-th harmonic number. These inferences are false: H_m = ln m + γ + o(1), so H_m ≥ t only implies m ≥ e^{t-γ}, which is not bounded by 2t for large t. The same type of error appears when bounding |O| ≤ t·2t. Because these steps are what remove k from the parameter, Lemma 18 only yields an FPT algorithm for the combined parameter (t,k). The claimed resolution of the Yang-Wang open question is therefore not proved.","section":"Section 6, Lemma 18 and PAV parameterization"}],"minor_comments":[{"comment":"There are several typographical artifacts, including 'Manurangasi 2025', 'Aziz et el. 2015', 'PA V', and 'FPT -AS', which should be corrected before any resubmission.","section":"Abstract and Introduction"},{"comment":"The text uses both \\binom{|C_r|}{d}(d-1) and |C_r|d(d-1) for the same claimed edge bound; this inconsistency should be resolved, and the actual bound used in the inequality must be stated unambiguously.","section":"Section 3, Claim 5"},{"comment":"The definition of an (n,k)-perfect hash family as one that 'splits S evenly' is nonstandard; the authors should either use the standard injective perfect hash family and argue via permutations of the color names, or cite a construction that guarantees balanced splits.","section":"Section 6, derandomization paragraph"},{"comment":"The symbol n is used inconsistently for both |C| and |V| in the counting argument; the bounds on the number of voters with degree at least d and with unique neighborhoods should be restated with explicit cardinalities such as |C| and |V|.","section":"Section 4, Lemma 13"},{"comment":"The algorithm defines r = 4dk/(ε λmin) + k and uses C_r as the ⌈r⌉ highest-score candidates, but the proof then writes |C_r| = r; the rounding should be handled consistently throughout the inequalities.","section":"Section 3, Algorithm 1 and Case 2 analysis"}],"recommendation":"reject","confidential_remarks":"The paper's central claims rest on two mathematical errors that are not local presentation issues: the Claim 5 edge bound is false as a graph-theoretic statement (the affine-plane construction is a concrete counterexample), and the harmonic-number inequalities in Section 6 are plainly incorrect. Although the sunflower-based Case 1 of Theorem 1 and parts of the kernelization framework may hold in isolation, the main advertised results—the FPT-AS, the lossy kernel, the additive approximation, and the PAV FPT—are not established. I therefore recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper does something genuinely new: it extends the FPT-AS and lossy kernel results for MAX COVERAGE on K_{d,d}-free graphs to all monotone submodular Thiele rules, and adds a one-additive FPT approximation. The sunflower-based low-threshold case (Case 1 of Theorem 1) looks sound, and the use of Manurangsi's sunflower lemma and Jain et al.'s high-degree set bound is legitimate black-box use, not circular. Second, the high-threshold case has a real hole that propagates. Claim 5 asserts that in the graph induced on Cr\\Oℓ and N(O∪Oℓ), voters of degree > d contribute at most |Cr|d(d−1) edges, justified solely by K_{d,d}-freeness. That is not a consequence of K_{d,d}-freeness. Kővári–Sós–Turán-type counting only gives O(|Cr|^{1+1/d}) such voters, and their total incident edges can be far larger than linear in |Cr|. The bound is false as stated, and it is exactly what converts the per-step replacement loss α_i into the final ε guarantee. Claim 6, the lossy kernel of Theorem 2, and the additive approximation of Theorem 3 all inherit the gap.\n\nSection 6 has independent trouble. To get PAV FPT parameterized by t, the paper infers k ≤ 2t from t ≥ H_k and δ < 2t from t > H_δ. Both are false; H_k ≈ ln k, so the first gives k ≤ exp(t) at best. The harmonic steps are the ones that remove k from the parameter; without them, the algorithm is FPT in t+k, which was already known. So the claimed resolution of the Yang–Wang open question is not established.\n\nWhat is good: the OWA reformulation and Lemma 1 are clean, the reduction rules are carefully argued, and the paper is honest about what it builds on. The contributions are significant if the gaps can be closed. Researchers working on parameterized approximation for multiwinner voting will want to read this carefully; it is a good test case for where K_{d,d}-free counting arguments can go wrong.\n\nThe paper deserves a serious referee, but it is not ready for publication. I would send it to review with a clear request to fix Claim 5 and Section 6, and to re-check the derived kernel and additive results once the edge-count bound is repaired.","headline":"Genuinely new results and a clean generalization to submodular Thiele rules, but a false K_{d,d}-free edge bound in Claim 5 and false harmonic-number inequalities in Section 6 put the main theorems at risk.","tokens_in":22489,"tokens_out":3008,"would_cite":false,"duration_ms":29945,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","68W25","91B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"For approval profiles with no d voters approving the same d candidates, this paper gives fixed-parameter approximation schemes, a lossy kernel, a one-extra-seat approximation, and an FPT algorithm for PAV parameterized by score threshold.","keywords":["approval-based multiwinner elections","Thiele rules","submodular maximization","fixed-parameter approximation schemes","lossy kernelization","biclique-free graphs","proportional approval voting","parameterized complexity"],"falsifier":"Construct a $K_{d,d}$-free instance with $r = 4dk/(\\varepsilon\\lambda_{\\min})+k$ top-scoring candidates and voters each approving slightly more than $d$ of them, arranged so the induced approval-edge count exceeds $|C_r|d(d-1)$ by the amount standard biclique-free counting allows; then evaluate the inequality $(|C_r|-k)\\alpha_i \\le 2d\\,\\mathrm{sco}(O)/\\lambda_{\\min} + |C_r|d(d-1)$ from Claim 5 and check whether the summation bound still holds.","tokens_in":21425,"feed_emoji":"🗳️","tokens_out":12830,"duration_ms":122689,"temperature":0.7,"pith_summary":"This paper studies approval-based multiwinner elections, where each voter approves a set of candidates and a committee of $k$ candidates is scored by summing a monotone submodular satisfaction function over voters. Its central claim is that when the approval profile is $K_{d,d}$-free (no $d$ voters approve the same $d$ candidates), committee selection becomes fixed-parameter approximable: an algorithm running in time $(dk/\\varepsilon)^{O(d^2 k)} n^{O(1)}$ returns a committee whose score is at least $(1-\\varepsilon)$ times the target. The paper further claims a lossy kernel that shrinks the election to $(dk/\\varepsilon)^{O(d^2)}$ candidates and $(dk/\\varepsilon)^{O(d^3)}$ voters, an algorithm that finds a $(k+1)$-member committee matching the optimal $k$-member score, and an FPT algorithm for the PAV (proportional approval voting) rule parameterized by the score threshold $t$, resolving an open question from earlier work. If these results hold, many practically used approval rules become tractable exactly on profiles where voting patterns are diverse rather than tightly clustered.","feed_headline":"Approval voting gets fast approximations when voter tastes are diverse","feed_subtitle":"Near-optimal committees via small cores, an extra seat, and a PAV threshold algorithm.","key_machinery":"The central object is the bipartite approval profile graph $G=(C,V,E)$, with an edge between candidate and voter when the voter approves the candidate; the structural assumption is that $G$ is $K_{d,d}$-free, and $d$ is the smallest integer such that no $d$ voters approve the same set of $d$ candidates. The scoring is carried by per-voter OWA vectors $\\lambda^v_j = f(j)-f(j-1)$, which are non-increasing exactly when each voter's satisfaction function is monotone submodular. The algorithmic workhorses are a sunflower lemma for $K_{a,b}$-free bipartite graphs, which justifies deleting low-score candidates without losing the optimum, and a counting argument showing that the $r$ highest-singleton-score candidates contain a near-optimal committee; the threshold-FPT proof uses color-coding and perfect hash families to isolate an optimal committee and the voters it satisfies.","core_discovery":"The paper's main theorem says that SM-MWE (submodular multiwinner election), with voter-specific non-increasing OWA vectors $\\lambda^v$ encoding monotone submodular satisfaction, admits a $(1-\\varepsilon)$-approximation in time $(dk/\\varepsilon)^{O(d^2 k)} n^{O(1)}$ whenever the profile graph is $K_{d,d}$-free. The proof splits at a threshold: when the target score $t$ is low, a sunflower-based reduction rule deletes low-score candidates until exhaustive search becomes feasible; when $t$ is high, the top $r = 4dk/(\\varepsilon\\lambda_{\\min})+k$ candidates by singleton score are shown to contain a near-optimal committee. The same machinery yields a polynomial-time lossy kernel and, by running the approximation on a carefully chosen high-score set $H$, a $(k+1)$-member committee whose score is at least the optimal $k$-member score. Section 6 additionally claims that under the PAV rule (the OWA vector $\\lambda_i = 1/i$), winner determination is FPT parameterized by the score threshold $t$, via color-coding over candidate and voter color classes derandomized with perfect hash families.","pith_inferences":["The high-threshold counting step invites a testable generalization: replace the asserted linear edge bound with the standard biclique-free counting bound; the approximation may survive with a worse dependence on $d$, or may force a larger choice of $r$.","The color-coding scheme in the threshold algorithm suggests a neighbouring problem: whether the same FPT result holds for other Thiele rules whose OWA weights decay, or only for rules with a harmonic structure such as PAV.","The lossy kernel implies a practical workflow: reduce a large election to a small residual instance in polynomial time, then search exactly; the usefulness in practice depends on $d$ being small in real approval data, which is an empirical question.","The one-extra-seat theorem gives a policy reading: allowing $k+1$ seats instead of $k$ can remove the approximation loss entirely, which may matter for committees with flexible size."],"forward_implications":["Theorem 1 gives a $(1-\\varepsilon)$-approximation for any monotone submodular Thiele rule in time $(dk/\\varepsilon)^{O(d^2 k)} n^{O(1)}$ on $K_{d,d}$-free profiles, where $d$ can be much smaller than the maximum approval-set size.","Theorem 2 shrinks any such instance in polynomial time to $(dk/\\varepsilon)^{O(d^2)}$ candidates and $(dk/\\varepsilon)^{O(d^3)}$ voters, so exact search on the reduced instance is feasible when $k$ is small.","Theorem 3 says one additional committee seat suffices to recover the full optimal score of a size-$k$ committee, so approximation loss disappears when committee size is flexible.","If Section 6 is correct, PAV winner determination is FPT by the score threshold $t$, matching the Chamberlin-Courant rule's known status and closing the open question.","All these algorithms work with a different Thiele function per voter, so they cover a strictly wider model than the standard single-rule formulation."],"supporting_citations":[{"why":"supplies the OWA reformulation and the FPT-AS baseline for bounded approval sets that this paper generalizes to $K_{d,d}$-free profiles.","marker":"Skowron [2017]"},{"why":"provides the $K_{a,b}$-free sunflower lemma and the lossy-kernel framework used for the reduction rule and the approximate kernel.","marker":"Manurangsi [2024]"},{"why":"gives the FPT-AS and the high-degree-set bound for max coverage on $K_{d,d}$-free graphs that the additive-approximation proof reuses.","marker":"Jain et al. [2023]"},{"why":"establishes the hardness landscape and leaves open the PAV fixed-parameter tractability by score threshold that Section 6 addresses.","marker":"Yang and Wang [2023]"},{"why":"provides the polynomial-time $(1-1/e)$-approximation for monotone submodular maximization used inside the lossy kernel.","marker":"Nemhauser et al. [1978]"},{"why":"supplies the perfect-hash-family derandomization that turns the randomized threshold-FPT algorithm into a deterministic one.","marker":"Cygan et al. [2015]"},{"why":"defines approximate polynomial-time preprocessing and approximate kernels, the formal target of Theorem 2.","marker":"Lokshtanov et al. [2017]"}],"fun_headline_variants":["Diverse approval profiles speed up near-optimal committee selection","Extra seat yields exact score approximation in multiwinner voting","PAV rule's winner problem turns fixed-parameter tractable","Diversity-driven FPT approximation schemes for Thiele rules","One extra committee member closes the score gap exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The high-threshold proof assumes that the voters who approve more than $d$ of the top-scoring candidates contribute at most $|C_r|d(d-1)$ approval edges in total; this bound is asserted without proof and is not implied by the no-$K_{d,d}$ condition, so Theorem 1 (and the kernel and additive results that lean on it) would fall if the bound is false.","fun_headline_variants_meta":{"raw":{"variants":["Diverse approval profiles speed up near-optimal committee selection","Extra seat yields exact score approximation in multiwinner voting","PAV rule's winner problem turns fixed-parameter tractable","Diversity-driven FPT approximation schemes for Thiele rules","One extra committee member closes the score gap exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000377,"raw_usage":{"total_tokens":2112,"prompt_tokens":1155,"completion_tokens":957,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":771,"completion_tokens_details":{"reasoning_tokens":878}},"tokens_in":771,"tokens_out":957,"duration_ms":8927,"temperature":1.0,"reasoning_tokens":878,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:31:17.294248+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a $K_{d,d}$-free instance with $r = 4dk/(\\varepsilon\\lambda_{\\min})+k$ top-scoring candidates and voters each approving slightly more than $d$ of them, arranged so the induced approval-edge count exceeds $|C_r|d(d-1)$ by the amount standard biclique-free counting allows; then evaluate the inequality $(|C_r|-k)\\alpha_i \\le 2d\\,\\mathrm{sco}(O)/\\lambda_{\\min} + |C_r|d(d-1)$ from Claim 5 and check whether the summation bound still holds.","supporting_citations":[{"cited_title":"Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back","cited_arxiv_id":"2403.06335","evidence_quote":"provides the $K_{a,b}$-free sunflower lemma and the lossy-kernel framework used for the reduction rule and the approximate kernel."},{"cited_title":"Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability","cited_arxiv_id":null,"evidence_quote":"establishes the hardness landscape and leaves open the PAV fixed-parameter tractability by score threshold that Section 6 addresses."}],"review_version":1}