arxiv: 2605.03067 · v2 · submitted 2026-05-04 · 💻 cs.AI · cs.GT

Computing Thiele Rules on Interval Elections and their Generalizations

Dimitris Avramidis , Alexandra Lassota , Ulrike Schmidt-Kraepelin , Adrian Vetta This is my paper

Pith reviewed 2026-05-11 01:00 UTC · model grok-4.3

classification 💻 cs.AI cs.GT

keywords Thiele rulesApproval votingVoter interval domainLinear programmingComputational social choiceProportional approval votingInterval electionsLinearly consistent domain

0 comments

The pith

Thiele rules admit polynomial-time algorithms on voter interval approval profiles via an integral linear program.

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

This paper resolves the computational status of Thiele rules, such as proportional approval voting, for approval profiles that follow voter interval structure. These rules are NP-hard to compute in unstructured settings, but the authors show that a standard linear programming formulation still yields an optimal integral solution on voter interval profiles even though its constraint matrix is not totally unimodular. They supply a fast algorithm to recover the integral optimum and extend the same guarantee to the voter-candidate interval and linearly consistent domains. They further establish that linearly consistent domains strictly contain voter-candidate interval domains and that Thiele rules become NP-hard again on tree-structured generalizations of interval profiles.

Core claim

The paper establishes that for approval profiles belonging to the voter interval domain, the natural linear programming relaxation used to optimize Thiele rules always has at least one integral optimal solution. A polynomial-time algorithm is given to find such a solution. This extends to the generalizations known as the voter-candidate interval domain and the linearly consistent domain. The authors prove that the linearly consistent domain strictly contains the voter-candidate interval domain and provide a graph-theoretic characterization along with an alternative definition of linear consistency that aligns with approval election structures. In contrast, on tree-based generalizations of a

What carries the argument

The standard LP relaxation for maximizing Thiele score subject to interval-domain constraints on approval profiles.

If this is right

Thiele rules can be computed in polynomial time for any voter interval approval profile.
The same polynomial-time method applies to voter-candidate interval and linearly consistent profiles.
Linearly consistent domains strictly contain voter-candidate interval domains.
Thiele rule computation is NP-hard on tree-structured generalizations of interval domains.
An alternative graph-theoretic definition of linear consistency is equivalent to the original and admits a natural approval-election interpretation.

Where Pith is reading between the lines

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

Interval structure appears to be the property that separates tractable from intractable instances for Thiele rules.
Graph-theoretic characterizations of preference domains may help classify other families of approval profiles for which similar LPs remain integral.
If real-world approval data often lies close to interval domains, these algorithms could be used directly or as warm starts for heuristics.
The alternative definition of linear consistency may simplify the task of recognizing or generating instances in this class for experimental studies.

Load-bearing premise

The input approval profile must exactly satisfy the voter interval property so that the LP constraints correctly capture the feasible set of committees.

What would settle it

An explicit voter interval approval profile together with a Thiele rule for which every optimal solution to the corresponding LP is fractional.

read the original abstract

Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Voting (PAV), stand out for desirable properties such as proportional representation, Pareto optimality, and support monotonicity. Their main drawback is that computing a Thiele outcome is NP-hard in general. A glimpse of hope comes from the fact that Thiele rules are better behaved under structured preferences. On the candidate interval (CI) domain, they are computable in polynomial time via a linear program (LP) that has a totally unimodular constraint matrix. Surprisingly, this approach fails for the related voter interval (VI) domain, and the complexity of the problem has repeatedly been posed as an open question. Our main result resolves this question: although the relevant matrix is not totally unimodular, the ``standard'' LP still admits at least one optimal integral solution, and we provide a fast algorithm for finding it. Our technique naturally extends to the voter-candidate interval (VCI) domain, also known as the 1-dimensional voter-candidate range (1D-VCR) domain, and to the linearly consistent (LC) domain, both of which generalize the candidate and voter interval domains. Although both the VCI and LC domains have been studied in social choice, their relationship was unknown. We show, through connections to graph theory, that LC strictly contains VCI. We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections; this equivalence may be of independent interest. Finally, we study an alternative tree-based generalization of VCI and show that Thiele rules become NP-hard to compute on this domain.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the open question on Thiele rules for voter-interval profiles by proving the standard LP has an optimal integral solution and giving a poly-time algorithm, even without total unimodularity.

read the letter

The core result is that Thiele rules, including PAV, are polynomial-time computable on voter-interval approval profiles. They show the usual LP formulation still has at least one optimal integral solution on these instances and supply an algorithm to recover it. This directly answers the question that had been left open after the candidate-interval case was settled via total unimodularity. The same technique carries over to the voter-candidate interval and linearly consistent domains, which properly generalize the basic interval settings. They also give a graph-theoretic proof that LC strictly contains VCI and supply an alternative, more approval-friendly definition of LC that may stand on its own. The matching NP-hardness result on the tree generalization is a useful boundary marker. The argument for integrality looks direct and avoids circularity or fitted parameters. The only real caveat is that the guarantees require the input profile to sit exactly inside the domain; the paper does not address how to test membership or how the results degrade under small noise. That is a standard limitation for domain-specific positive results rather than a flaw in the claims themselves. The work is aimed at researchers in computational social choice who care about structured preferences and the complexity of proportional rules. Anyone working on interval or single-peaked domains will find the algorithms and the LC characterization worth having. It is the sort of paper that deserves a serious referee because it closes a repeatedly posed open question with a clean positive result and some reusable structural observations.

Referee Report

0 major / 3 minor

Summary. The paper claims that Thiele rules (including PAV) can be computed in polynomial time on voter-interval (VI) approval profiles via the standard LP formulation, which admits an optimal integral solution despite its constraint matrix not being totally unimodular; a fast algorithm is given to recover such a solution. The same technique extends to the voter-candidate interval (VCI) and linearly consistent (LC) domains. The authors prove via graph theory that LC strictly contains VCI, supply an alternative definition of LC with a natural approval-election interpretation, and establish NP-hardness of Thiele rules on a tree-based generalization of these domains.

Significance. If the integrality result and algorithm hold, the work resolves a repeatedly posed open question on the complexity of Thiele rules under VI preferences and supplies a practical polynomial-time method for an important class of structured elections. The graph-theoretic clarification that LC properly contains VCI (with an equivalent definition) is a clean contribution that may be of independent interest to domain studies in social choice. The matching hardness result on trees delineates the boundary of tractability. The explicit algorithm and domain-inclusion proof are concrete strengths that strengthen the manuscript.

minor comments (3)

[Section 3] A small concrete example matrix demonstrating that the VI constraint matrix is not TU (while still having an integral optimum) would help readers verify the non-TU claim in §3.
[Section 4.2] The alternative definition of the LC domain (Definition 4.2) would benefit from an explicit approval profile that is LC but not VCI, to illustrate the strict containment.
[Figure 1] Figure 1 (domain relationships) could be augmented with a brief caption explaining the arrow directions and the tree generalization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The referee's summary accurately reflects the paper's contributions, including the polynomial-time algorithm for Thiele rules on voter-interval profiles, the extensions to VCI and LC domains, the graph-theoretic clarification of the relationship between LC and VCI, and the NP-hardness result on tree-based generalizations.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central contribution is a direct integrality proof for the standard Thiele LP on the voter-interval domain (and its VCI/LC generalizations), together with a polynomial-time algorithm to recover an integral optimum. This is established via new graph-theoretic arguments and explicit algorithmic constructions that do not reduce to any fitted parameter, self-definitional equivalence, or load-bearing self-citation chain. The non-TU observation is used only to motivate the need for a fresh proof, not to derive the result itself. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard LP formulation of Thiele rules from prior literature and on the definitions of the interval and linearly consistent domains; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption Thiele rules admit a standard integer linear programming formulation whose continuous relaxation is the LP studied in the paper
Invoked throughout as the modeling tool for the computational problem.
domain assumption Voter interval, VCI, and LC domains are well-defined via interval or range structures on a line or graph
Core structural assumptions enabling the LP and graph-theoretic arguments.

pith-pipeline@v0.9.0 · 5625 in / 1299 out tokens · 60277 ms · 2026-05-11T01:00:54.787113+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

65 extracted references · 65 canonical work pages · 1 internal anchor

[1]

Proceedings of the 32nd

Dominik Peters , title =. Proceedings of the 32nd

work page
[2]

Alexander Schrijver , title =

work page
[3]

Noga Alon and Raphael Yuster and Uri Zwick , title =. J

work page
[4]

Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (

Haris Aziz and Serge Gaspers and Joachim Gudmundsson and Simon Mackenzie and Nicholas Mattei and Toby Walsh , title =. Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (

work page 2015
[5]

Tight Approximation Guarantees for Concave Coverage Problems , booktitle =

Siddharth Barman and Omar Fawzi and Paul Ferm. Tight Approximation Guarantees for Concave Coverage Problems , booktitle =

work page
[6]

Tight Approximation Bounds for Maximum Multi-coverage , journal =

Siddharth Barman and Omar Fawzi and Suprovat Ghoshal and Emirhan G. Tight Approximation Bounds for Maximum Multi-coverage , journal =

work page
[7]

Nadja Betzler and Arkadii Slinko and Johannes Uhlmann , title =. J. Artif. Intell. Res. , volume =

work page
[8]

Computing Small Partial Coverings , journal =

Markus Bl. Computing Small Partial Coverings , journal =

work page
[9]

Approval-Based Committee Voting in Practice:

Niclas Boehmer and Markus Brill and Alfonso Cevallos and Jonas Gehrlein and Luis S. Approval-Based Committee Voting in Practice:. Proceedings of the 38th. 2024 , volume=

work page 2024
[10]

Proceedings of the Thirty-Fourth

Robert Bredereck and Piotr Faliszewski and Andrzej Kaczmarczyk and Dusan Knop and Rolf Niedermeier , title =. Proceedings of the Thirty-Fourth. 2020 , volume=

work page 2020
[11]

Proceedings of the 4th Conference on Algorithmic Decision Theory (

Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Piotr Skowron and Nimrod Talmon , title =. Proceedings of the 4th Conference on Algorithmic Decision Theory (

work page
[12]

Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier and Piotr Skowron and Nimrod Talmon , title =. Theor. Comput. Sci. , volume =

work page
[13]

Proceedings of the 24th

Markus Brill and Jannik Peters , title =. Proceedings of the 24th

work page
[14]

Proportional Approval Voting, Harmonic k-Median, and Negative Association , booktitle =

Jaros. Proportional Approval Voting, Harmonic k-Median, and Negative Association , booktitle =

work page
[15]

Chamberlin and Paul N

John R. Chamberlin and Paul N. Courant , title =. Am. Political Sci. Rev. , volume =. 1983 , pages =

work page 1983
[16]

Proceedings of the 35th

Andrei Costin Constantinescu and Edith Elkind , title =. Proceedings of the 35th

work page
[17]

Fomin and

Marek Cygan and Fedor V. Fomin and. Parameterized Algorithms , publisher =

work page
[18]

Proceedings of the 29th International Joint Conference on Artificial Intelligence (

Szymon Dudycz and Pasin Manurangsi and Jan Marcinkowski and Krzysztof Sornat , title =. Proceedings of the 29th International Joint Conference on Artificial Intelligence (

work page
[19]

The Price of Justified Representation , journal =

Edith Elkind and Piotr Faliszewski and Ayumi Igarashi and Pasin Manurangsi and Ulrike. The Price of Justified Representation , journal =

work page
[20]

Proceedings of the 24th International Joint Conference on Artificial Intelligence (

Edith Elkind and Martin Lackner , title =. Proceedings of the 24th International Joint Conference on Artificial Intelligence (

work page
[21]

Trends in Computational Social Choice , chapter =

Edith Elkind and Martin Lackner and Dominik Peters , title =. Trends in Computational Social Choice , chapter =

work page
[22]

CoRR , volume =

Edith Elkind and Martin Lackner and Dominik Peters , title =. CoRR , volume =

work page
[23]

Hemaspaandra and J

Piotr Faliszewski and Edith Hemaspaandra and Lane A. Hemaspaandra and J. The Shield that Never was:. Inf. Comput. , volume =

work page
[24]

Social Choice and Welfare , volume =

Piotr Faliszewski and Piotr Skowron and Arkadii Slinko and Nimrod Talmon , title =. Social Choice and Welfare , volume =

work page
[25]

An Analysis of Approval-Based Committee Rules for

Micha. An Analysis of Approval-Based Committee Rules for. Proceedings of the 35th

work page
[26]

and Lovász, L

Grötschel, M. and Lovász, L. and Schrijver, A. , title =

work page
[27]

CoRR , volume =

Sushmita Gupta and Pallavi Jain and Souvik Saha and Saket Saurabh and Anannya Upasana , title =. CoRR , volume =

work page
[28]

Proceedings of the 29th International Joint Conference on Artificial Intelligence (

Pallavi Jain and Krzysztof Sornat and Nimrod Talmon , title =. Proceedings of the 29th International Joint Conference on Artificial Intelligence (

work page
[29]

, title =

Khachiyan, L. , title =. Doklady Akademii Nauk SSSR , pages =. 1979 , volume=

work page 1979
[30]

Marc Kilgour , editor =

D. Marc Kilgour , editor =. Approval Balloting for Multi-Winner Elections , booktitle =

work page
[31]

Martin Lackner and Piotr Skowron , title =. J. Econ. Theory , volume =

work page
[32]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (

Alexandra Lassota and Koen Ligthart , title =. Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (

work page
[33]

Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems (

Hong Liu and Jiong Guo , title =. Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems (

work page 2016
[34]

Schulman and Aravind Srinivasan , title =

Moni Naor and Leonard J. Schulman and Aravind Srinivasan , title =. Proceedings of the 36th Annual Symposium on Foundations of Computer Science (

work page
[35]

Dominik Peters and Martin Lackner , title =. J. Artif. Intell. Res. , volume =

work page
[36]

Finding a Collective Set of Items:

Piotr Skowron and Piotr Faliszewski and J. Finding a Collective Set of Items:. Artificial Intelligence , volume =

work page
[37]

Near-Tight Algorithms for the

Krzysztof Sornat and Virginia. Near-Tight Algorithms for the. Proceedings of the 31st International Joint Conference on Artificial Intelligence (

work page
[38]

Om Flerfoldsvalg , year =

Thorvald Thiele , booktitle =. Om Flerfoldsvalg , year =

work page
[39]

Yongjie Yang and Jianxin Wang , title =. Auton. Agents Multi Agent Syst. , volume =

work page
[40]

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (

Yongjie Yang and Jianxin Wang , title =. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (

work page
[41]

Proceedings of the 28th International Joint Conference on Artificial Intelligence (

Yongjie Yang , title =. Proceedings of the 28th International Joint Conference on Artificial Intelligence (

work page
[42]

Karp , title =

Richard M. Karp , title =. Complexity of Computer Computations , series =

work page
[43]

Social Choice and Welfare , volume=

On the complexity of achieving proportional representation , author=. Social Choice and Welfare , volume=. 2008 , publisher=

work page 2008
[44]

Selecting Interlacing Committees , year =

Dong, Chris and Bullinger, Martin and W. Selecting Interlacing Committees , year =. Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =

work page
[45]

Core-Stable Committees Under Restricted Domains

Pierczy \' n ski, Grzegorz and Skowron, Piotr. Core-Stable Committees Under Restricted Domains. Proceedings of the 18th International Conference on Web and Internet Economics (WINE). 2022

work page 2022
[46]

Journal of Graph Theory , author =

Interval digraphs:. Journal of Graph Theory , author =. 1989 , pages =

work page 1989
[47]

Permutation bigraphs and interval containments , volume =

Saha, Pranab and Basu, Asim and Sen, Malay and West, Douglas , month = oct, year =. Permutation bigraphs and interval containments , volume =. Discrete Applied Mathematics , publisher =

work page
[48]

2023 , author =

Justifying groups in multiwinner approval voting , journal =. 2023 , author =

work page 2023
[49]

Martin Lackner and Piotr Skowron , title =

work page
[50]

Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

Approval-based committee voting in practice: A case study of (over-) representation in the Polkadot blockchain , author=. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

work page
[51]

Proceedings of the 3rd ACM Conference on Advances in Financial Technologies , pages=

A verifiably secure and proportional committee election rule , author=. Proceedings of the 3rd ACM Conference on Advances in Financial Technologies , pages=

work page
[52]

Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations , editor=

Participatory budgeting: Models and approaches , author=. Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations , editor=. 2020 , publisher=

work page 2020
[53]

Janson, Svante , journal=. Phragm

work page
[54]

2010 , author =

On orthogonal ray graphs , journal =. 2010 , author =

work page 2010
[55]

SIAM Journal on Discrete Mathematics , author =

Min-. SIAM Journal on Discrete Mathematics , author =. 2020 , pages =

work page 2020
[56]

1987 , author =

Bipartite permutation graphs , journal =. 1987 , author =

work page 1987
[57]

Social Choice and Welfare , volume=

Justified representation in approval-based committee voting , author=. Social Choice and Welfare , volume=. 2017 , publisher=

work page 2017
[58]

Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

Proportionality degree of multiwinner rules , author=. Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

work page
[59]

Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

On the complexity of extended and proportional justified representation , author=. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

work page
[60]

Proceedings of the 21st ACM Conference on Economics and Computation (EC) , pages=

Proportionality and the limits of welfarism , author=. Proceedings of the 21st ACM Conference on Economics and Computation (EC) , pages=

work page
[61]

Mathematical Programming , volume=

Approval-based apportionment , author=. Mathematical Programming , volume=. 2024 , publisher=

work page 2024
[62]

Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI) , pages=

Tight approximation for proportional approval voting , author=. Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI) , pages=

work page
[63]

Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

Algorithms for Structured Elections Under Thiele Voting Rules , author=. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume=

work page
[64]

Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences

Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences , author=. arXiv preprint arXiv:2604.05953 , year=

work page internal anchor Pith review Pith/arXiv arXiv
[65]

Brill, Markus and Freeman, Rupert and Janson, Svante and Lackner, Martin , journal=. Phragm. 2024 , publisher=

work page 2024