Pith. sign in

REVIEW 2 major objections 5 minor 24 references

Structural constraints on winning committees make Thiele winner determination fixed-parameter tractable on voter-interval ballots, for a parameter that is already hard on unrestricted instances.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 03:19 UTC pith:F3NHN3K3

load-bearing objection Solid FPT/poly-time results that cleanly resolve two Yang–Wang opens and give a reusable structural handle on Thiele optima, with the VI advance later completed by others. the 2 major comments →

arxiv 2607.28575 v1 pith:F3NHN3K3 submitted 2026-07-30 cs.GT cs.AIcs.DScs.MA

Algorithms for Structured Elections under Thiele Voting Rules

Alexandra Lassota , Krzysztof Sornat This is my paper
classification cs.GT cs.AIcs.DScs.MA
keywords Thiele voting rulesProportional Approval Votingvoter intervalwinner determinationfixed-parameter tractabilitydominancy graphapproval-based multiwinner elections
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Approval-based committee elections under Thiele rules (including PAV) ask which k candidates maximize a weighted satisfaction score. Finding winners is NP-hard in general, even when each candidate is approved by only three voters and each voter approves only two candidates. This paper shows that the approval sets themselves induce a dominance hierarchy among candidates, and that an optimal committee can always be chosen to be non-dominated. On the voter-interval domain—where voters can be lined up so each candidate’s supporters form a consecutive block—that structure collapses into a chain of small “triangles,” which a dynamic program can search in FPT time for the joint parameter (maximum approvals per candidate plus maximum approvals per voter). The same parameter remains hard without the interval restriction. The paper also settles two open questions: winner determination is polynomial-time solvable when every candidate has at most two approvers, and it is FPT in the total score of an optimal committee.

Core claim

There always exists an optimal committee under any Generalized Thiele rule that is non-dominated with respect to the inclusion order on supporter sets; on voter-interval profiles this forces an optimal committee to take a prefix of every triangle in a canonical candidate ordering, yielding an FPT dynamic program parameterized by Δ_C + Δ_V (and XP in Δ_C alone). Separately, when Δ_C = 2 the natural ILP can be rewritten as a generalized matching ILP and solved in polynomial time, and color-coding plus partial set cover yields FPT algorithms parameterized by k + Δ_C and hence by the optimal total score d.

What carries the argument

The dominancy graph (directed edge c → c′ when the supporters of c′ are a proper subset of those of c) and the induced non-dominated committees; on VI profiles these interact with a partition of candidates into triangles C_i = {candidates whose last supporter is voter i}, so that an optimal non-dominated committee takes a prefix of each triangle.

Load-bearing premise

That every optimal non-dominated committee, under the stated ordering of candidates by last supporter then first supporter, must take a consecutive prefix of every triangle; if that geometric claim fails for some weights or profiles, the dynamic program searches only a proper subset of committees and can miss the optimum.

What would settle it

Construct a small voter-interval PAV (or other Thiele) instance together with an optimal committee that is non-dominated yet does not select a prefix of some triangle under the paper’s candidate ordering; if such an instance exists, Theorem 7’s dynamic program is incomplete.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Every Thiele rule on voter-interval elections is FPT in Δ_C + Δ_V, a parameterization that is para-NP-hard on unrestricted elections even for constant values.
  • Winner determination under any Thiele rule is polynomial-time solvable whenever each candidate is approved by at most two voters.
  • Winner determination is FPT in the total score d of an optimal committee (with only linear dependence on the number of voters after normalization w_1 = 1).
  • It suffices to search the first k dominancy levels (or the first ℓ levels for ℓ-Coverage), shrinking the candidate set before any algorithm is run.
  • The same structural reduction supplies an O*(k^{Δ_C})-time algorithm on VI, exponentially better in k than the general double-exponential FPT algorithm for k + Δ_C.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The prefix-of-triangle property is the precise geometric reason VI is algorithmically easier than CI’s total-unimodularity route; any larger domain that preserves both non-dominance and a bounded-interaction partition should inherit similar FPT algorithms.
  • Because the methods already handle pre-selected candidates via adjusted Thiele sequences, they immediately give algorithms for possible and necessary winners under ties, a direction the conclusion only sketches.
  • A purely combinatorial matching algorithm for the Δ_C = 2 case would unify the polynomial results for VI and for two-approver instances and answer the open question left for both CI and Δ_C = 2.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies winner determination for approval-based multiwinner elections under Thiele rules (including PAV, CC, and Generalized Thiele). It introduces a dominancy graph on candidates induced by strict inclusion of supporter sets, proves that an optimal committee may always be taken non-dominated (Theorem 4), and derives consequences for the relevant dominancy levels. Using this structure together with a max-then-min ordering of candidates on Voter Interval (VI) profiles, it obtains an FPT algorithm for Generalized Thiele on VI parameterized by Δ_C+Δ_V via dynamic programming over “triangles” C_i (Theorem 7 / Corollary 8), a parameterization that is para-NP-hard on unrestricted instances. Independently, it gives a polynomial-time algorithm for Δ_C=2 by rewriting the standard ILP into a generalized matching matrix (Theorem 10), and an FPT algorithm parameterized by k+Δ_C (hence by the optimal total score d) via splitters, color-coding of approvals, and reduction to weighted p-partial set cover (Theorem 14 / Proposition 15). Two open questions of Yang & Wang are thereby resolved; concurrent polynomial-time algorithms for PAV on VI are disclosed in the conclusion.

Significance. The structural non-dominance lemma and the VI triangle DP are genuine progress on a long-standing open question (complexity of PAV on VI), even though that question has since been settled affirmatively by concurrent work that the authors properly cite. Resolving the Δ_C=2 case and FPT-by-score in full generality for Thiele rules closes two explicit open problems from the parameterized-complexity literature. The techniques are standard but carefully adapted (exchange argument; Schrijver’s generalized matching matrices after an equality rewrite; color-coding of approvals rather than of candidates/voters). The linear dependence on n in the score-FPT bound is a concrete improvement over a concurrent independent algorithm. Strengths that should be credited: explicit proofs for all main claims, clear disclosure of concurrent poly-time VI results, and extension of every algorithmic result from PAV to Generalized Thiele.

major comments (2)
  1. [Section 5.2, Theorem 14] §5.2, proof of Theorem 14: the color-class semantics are written as if each class c contributes “1/c” (PAV-style). For arbitrary Thiele sequences (and especially voter-specific sequences in Generalized Thiele) the marginal weights w_i^v are arbitrary nonincreasing sequences in [0,1]. The reduction must therefore place those weights on the universe elements of the p-partial set cover instance (or on the sets). The present write-up only sketches the unweighted counting argument and the 2k! block construction; a short, explicit paragraph stating how the weights of U are defined from (w_i^v) and why an optimal weighted partial cover recovers an optimal Thiele committee is needed for the claim to hold in the generality asserted by the theorem statement and by Proposition 15.
  2. [Section 4, Theorem 7] §4, proof of Theorem 7: the load-bearing “prefix of every triangle” claim is derived from non-dominance (Theorem 4) plus the max-then-min candidate order, but the argument is only one sentence. A short explicit verification that any non-dominated set intersects each C_i in a prefix (or that any non-prefix can be exchanged for a prefix without decreasing score) would make the completeness of the DP state space immediate and would remove the only residual correctness risk identified for the central VI result.
minor comments (5)
  1. [Abstract / Introduction] Abstract still presents PAV-on-VI as open; the Conclusion correctly records the concurrent polynomial-time resolutions. Align the abstract (and the final sentence of the introduction) with the Conclusion so that a reader of the abstract alone is not misled.
  2. [Section 3] Figure 1 is helpful; a second small figure illustrating a dominancy graph and its levels L_1..L_δ would make Section 3 easier to parse on a first reading.
  3. [Section 5.2] In the running-time display after Theorem 14 the exponent is written 2^{O(k^4·k!Δ_C log(k!Δ_C))}; a parenthetical remark that the same bound is 2^{d^{O(d)}} after the reductions of Proposition 15 would help readers comparing with [GJS+25].
  4. Several minor typos: “StructureofthePaper”, “weshowthateveryThielerule”, “adominancerelation”, “thetotalscoreachievedbyacommittee”, and missing spaces after periods in a few places in Sections 1 and 4.
  5. [Section 5.1, Theorem 10] The dummy-voter construction that forces every candidate to have exactly two approvals (proof of Theorem 10) should note that the dummy voter receives weight sequence (0,0,…) so that it does not alter the objective; this is implicit but worth one explicit sentence.

Circularity Check

0 steps flagged

No circularity: algorithmic upper bounds and structural lemmas derived from definitions, not from fitted inputs or self-justifying citations.

full rationale

This is a pure algorithms/complexity paper. Optimal committees are defined by maximizing the Thiele score; the structural lemmas (non-dominated committees, triangle prefixes under VI ordering) are proved from that definition plus the geometry of Voter Interval profiles; the FPT/poly-time claims are then obtained by dynamic programming, ILP reduction to generalized matching matrices, and color-coding/splitters. None of these steps fits a parameter to data and re-labels the fit as a prediction, nor does any central claim reduce to a self-citation whose content is the claim itself. Citations to the conference version, concurrent FPT-by-score work, and later poly-time VI resolutions are contextual or comparative and are not used as unexamined premises that force the theorems. The derivation chain is self-contained against its own definitions and standard external tools (Bläser partial set cover, Schrijver generalized matching, Naor–Schulman–Srinivasan splitters). Score 0 is the honest finding.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 2 invented entities

Pure algorithmic theory: no fitted constants. Load-bearing background is standard parameterized complexity, Thiele/VI definitions from the literature, Bläser’s p-partial set cover, Naor–Schulman–Srinivasan splitters, and Schrijver’s poly-time solvability of generalized matching ILPs. The paper’s own invented structure is the dominancy graph/levels and the triangle partition of VI profiles.

axioms (6)
  • domain assumption w-Thiele / Generalized Thiele score definitions with normalization w_1 = 1 (or per-voter sequences in [0,1])
    Section 2; standard in the multiwinner literature the paper cites. Normalization is discussed explicitly to avoid para-NP-hardness artifacts for parameter d.
  • domain assumption Voter Interval: voters orderable so each candidate’s supporter set is contiguous; axis findable in poly time
    Definition 1 and preamble to Section 4; inherited from ELP structured-preferences line.
  • standard math ILPs whose constraint matrices are generalized matching matrices (column absolute-sum ≤2, entries in {-2,-1,0,1,2}) are solvable in strongly polynomial time (Schrijver)
    Theorem 9 citing Schrijver 2003; used as black box for Δ_C=2.
  • standard math Minimum p-partial set cover (and weighted variant) is solvable in 2^{O(p)}·s·t time (Bläser)
    Theorem 11; used in the FPT-by-score reduction.
  • standard math (n,k,k)-splitters of size e^k k^{O(log k)} log n exist and are constructible in the stated time (Naor–Schulman–Srinivasan)
    Lemma 13; derandomizes color coding in Theorem 14.
  • standard math Standard FPT/XP and hardness baselines: P≠NP, FPT≠W[1], ETH lower bounds cited from AGG+15, SFL16, SVX22 for unstructured Thiele
    Used only to position para-NP-hardness contrast; not needed for correctness of upper bounds.
invented entities (2)
  • Dominancy graph and dominancy levels L_1..L_δ of an approval profile independent evidence
    purpose: Characterize non-dominated optimal committees under Generalized Thiele and prune search space (only first k levels, etc.).
    Section 3; coincides with an independently introduced relation [DBW+25] but is developed here for Thiele scores and VI algorithms.
  • Triangles C_i = {candidates whose last supporter is voter v_i} under the VI-axis and max-then-min candidate order no independent evidence
    purpose: Partition candidates so optimal non-dominated committees take prefixes; enable local DP states of size f(Δ_C,Δ_V).
    Proof of Theorem 7 / Figure 1; geometry-specific to VI.

pith-pipeline@v1.2.0-daily-grok45 · 21444 in / 3197 out tokens · 61085 ms · 2026-07-31T03:19:12.242626+00:00 · methodology

0 comments
read the original abstract

We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.

Figures

Figures reproduced from arXiv: 2607.28575 by Alexandra Lassota, Krzysztof Sornat.

Figure 1
Figure 1. Figure 1: An example of a VI approval profile, where the voters are ordered according to the VI [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 3 linked inside Pith

  1. [1]

    Computationalaspectsofmulti-winnerapprovalvoting

    [AGG+15] Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, andTobyWalsh. Computationalaspectsofmulti-winnerapprovalvoting. InProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), pages 107–115,

    2015

  2. [10]

    Se- lecting interlacing committees

    [DBW+25] Chris Dong, Martin Bullinger, Tomasz Wąs, Larry Birnbaum, and Edith Elkind. Se- lecting interlacing committees. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), pages 630–638,

    2025

  3. [12]

    Structure in dichotomous preferences

    [EL15] Edith Elkind and Martin Lackner. Structure in dichotomous preferences. InProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 2019–2025,

    2015

  4. [16]

    Participatory budgeting with project interactions

    [JST20] Pallavi Jain, Krzysztof Sornat, and Nimrod Talmon. Participatory budgeting with project interactions. InProceedings of the 29th International Joint Conference on Ar- tificial Intelligence (IJCAI 2020), pages 386–392,

    2020

  5. [17]

    Parameterized complexity of winner determination in mini- max committee elections

    [LG16] Hong Liu and Jiong Guo. Parameterized complexity of winner determination in mini- max committee elections. InProceedings of the 2016 International Conference on Au- tonomous Agents and Multiagent Systems (AAMAS 2016), pages 341–349,

    2016

  6. [19]

    Algorithms for structured elections under Thielevotingrules

    [LS26] Alexandra Lassota and Krzysztof Sornat. Algorithms for structured elections under Thielevotingrules. InProceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026), pages 17084–17092,

    2026

  7. [20]

    Polynomial-time algorithm for Thiele voting rules with voter interval preferences.CoRR, abs/2604.05953,

    [MS26] Pasin Manurangsi and Krzysztof Sornat. Polynomial-time algorithm for Thiele voting rules with voter interval preferences.CoRR, abs/2604.05953,

    Pith/arXiv arXiv

  8. [21]

    Schulman, and Aravind Srinivasan

    17 [NSS95] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. InProceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pages 182–191,

    1995

  9. [23]

    Near-tight algo- rithms for the Chamberlin-Courant and Thiele voting rules

    [SVX22] Krzysztof Sornat, Virginia Vassilevska Williams, and Yinzhan Xu. Near-tight algo- rithms for the Chamberlin-Courant and Thiele voting rules. InProceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022), pages 482–488,

    2022

  10. [1895]

    Parameterized complexity of multi-winner determi- nation: More effort towards fixed-parameter tractability

    [YW18] Yongjie Yang and Jianxin Wang. Parameterized complexity of multi-winner determi- nation: More effort towards fixed-parameter tractability. InProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), pages 2142–2144,

    2018

  11. [1983]

    Proportional representation under single-crossing preferences revisited

    [CE21] Andrei Costin Constantinescu and Edith Elkind. Proportional representation under single-crossing preferences revisited. InProceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 5286–5293,

    2021

  12. [1995]

    Single-peakedness and total unimodularity: New polynomial-time al- gorithms for multi-winner elections

    [Pet18] Dominik Peters. Single-peakedness and total unimodularity: New polynomial-time al- gorithms for multi-winner elections. InProceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pages 1169–1176,

    2018

  13. [2003]

    Robust and verifiable proportionality axioms for mul- tiwinner voting

    [BP23] Markus Brill and Jannik Peters. Robust and verifiable proportionality axioms for mul- tiwinner voting. InProceedings of the 24th ACM Conference on Economics and Com- putation (EC 2023), page 301,

    2023

  14. [2015]

    Computing Thiele rules on interval elections and their generalizations.CoRR, abs/2605.03067,

    [ALSV26] Dimitris Avramidis, Alexandra Lassota, Ulrike Schmidt-Kraepelin, and Adrian Vetta. Computing Thiele rules on interval elections and their generalizations.CoRR, abs/2605.03067,

    Pith/arXiv arXiv

  15. [2016]

    Parameterized algorithms for matching integer programs with additional rows and columns

    [LL25] Alexandra Lassota and Koen Ligthart. Parameterized algorithms for matching integer programs with additional rows and columns. InProceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 112:1– 112:18,

    2025

  16. [2017]

    Preference restrictions in compu- tational social choice: A survey.CoRR, abs/2205.09092v2,

    [ELP25] Edith Elkind, Martin Lackner, and Dominik Peters. Preference restrictions in compu- tational social choice: A survey.CoRR, abs/2205.09092v2,

    Pith/arXiv arXiv

  17. [2018]

    An analysis of approval-based committee rules for 2D-Euclidean elections

    [GBSF21] Michał Tomasz Godziszewski, Paweł Batko, Piotr Skowron, and Piotr Faliszewski. An analysis of approval-based committee rules for 2D-Euclidean elections. InProceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 5448–5455,

    2021

  18. [2020]

    Elections with few candidates: Prices, weights, and covering problems

    [BFN+15] Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Elections with few candidates: Prices, weights, and covering problems. In 15 Proceedings of the 4th Conference on Algorithmic Decision Theory (ADT 2015), pages 414–431,

    2015

  19. [2021]

    More efforts towards fixed-parameter approximability of multiwinner rules

    [GJS+25] Sushmita Gupta, Pallavi Jain, Souvik Saha, Saket Saurabh, and Anannya Upasana. More efforts towards fixed-parameter approximability of multiwinner rules. InProceed- ings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025), pages 3891–3899,

    2025

  20. [2022]

    Parameterized algorithms for finding a collective set of items

    [BFK+20] Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Dusan Knop, and Rolf Nie- dermeier. Parameterized algorithms for finding a collective set of items. InProceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pages 1838–1845,

    2020

  21. [2023]

    Proportional approval voting, harmonic k-median, and negative association

    [BSS18] Jarosław Byrka, Piotr Skowron, and Krzysztof Sornat. Proportional approval voting, harmonic k-median, and negative association. InProceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 26:1– 26:14,

    2018

  22. [2024]

    Tight approximation guarantees for concave coverage problems

    [BFF21] Siddharth Barman, Omar Fawzi, and Paul Fermé. Tight approximation guarantees for concave coverage problems. InProceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 9:1–9:17,

    2021

  23. [2025]

    Tight approximation for proportional approval voting

    [DMMS20] Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, and Krzysztof Sornat. Tight approximation for proportional approval voting. InProceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), pages 276–282,

    2020

  24. [2026]

    Approval-based committee voting in practice: A case study of (over-)representation in the polkadot blockchain

    [BBC+24] Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein, Luis Sánchez Fernán- dez, and Ulrike Schmidt-Kraepelin. Approval-based committee voting in practice: A case study of (over-)representation in the polkadot blockchain. InProceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pages 9519–9527,

    2024