# Computing Thiele Rules on Interval Elections and their Generalizations

arXiv: https://arxiv.org/abs/2605.03067 · HTML: https://mlsanity.com/paper/2605.03067/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 4 May 2026.

## Builds on (most cited first, 17 of 17)

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Participatory Budgeting: Models and Approaches](https://mlsanity.com/paper/2003.00606/) (2020)
- [Proportionality and the Limits of Welfarism](https://mlsanity.com/paper/1911.11747/) (2019)
- [Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation](https://mlsanity.com/paper/1402.3044/) (2014)
- [Phragm'en's Voting Methods and Justified Representation](https://mlsanity.com/paper/2102.12305/) (2021)
- [Computational Aspects of Multi-Winner Approval Voting](https://mlsanity.com/paper/1407.3247/) (2014)
- [Approval-Based Apportionment](https://mlsanity.com/paper/1911.08365/) (2019)
- [Structure in Dichotomous Preferences](https://mlsanity.com/paper/1505.00341/) (2015)
- [Approval-Based Committee Voting in Practice: A Case Study of (Over-)Representation in the Polkadot Blockchain](https://mlsanity.com/paper/2312.11408/) (2023)
- [A verifiably secure and proportional committee election rule](https://mlsanity.com/paper/2004.12990/) (2020)
- [Phragm'en's and Thiele's election methods](https://mlsanity.com/paper/1611.08826/) (2016)
- [Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules](https://mlsanity.com/paper/2212.14173/) (2022)
- [Core-Stable Committees under Restricted Domains](https://mlsanity.com/paper/2108.01987/) (2021)
- [Justifying Groups in Multiwinner Approval Voting](https://mlsanity.com/paper/2108.12949/) (2021)
- [Selecting Interlacing Committees](https://mlsanity.com/paper/2509.02519/) (2025)
- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)

## Built on by (most cited first, 1 of 1)

- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

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.