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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 7 Apr 2026.

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

- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Accelerating Scientific Research with Gemini: Case Studies and Common Techniques](https://mlsanity.com/paper/2602.03837/) (2026)
- [On the Computation of Fully Proportional Representation](https://mlsanity.com/paper/1402.0580/) (2014)
- [Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation](https://mlsanity.com/paper/1402.3044/) (2014)
- [Computational Aspects of Multi-Winner Approval Voting](https://mlsanity.com/paper/1407.3247/) (2014)
- [Preference Restrictions in Computational Social Choice: A Survey](https://mlsanity.com/paper/2205.09092/) (2022)
- [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)
- [Consistent Approval-Based Multi-Winner Rules](https://mlsanity.com/paper/1704.02453/) (2017)
- [Tight Approximation Bounds for Maximum Multi-Coverage](https://mlsanity.com/paper/1905.00640/) (2019)
- [Tight Approximation Guarantees for Concave Coverage Problems](https://mlsanity.com/paper/2010.00970/) (2020)
- [Parameterized Complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability](https://mlsanity.com/paper/2107.04685/) (2021)
- [Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules](https://mlsanity.com/paper/2212.14173/) (2022)
- [Proportional Approval Voting, Harmonic k-median, and Negative Association](https://mlsanity.com/paper/1704.02183/) (2017)
- [Selecting Interlacing Committees](https://mlsanity.com/paper/2509.02519/) (2025)
- [Proportional Representation under Single-Crossing Preferences Revisited](https://mlsanity.com/paper/2010.08637/) (2020)
- [More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules](https://mlsanity.com/paper/2505.12699/) (2025)

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

- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

We present a polynomial-time algorithm for computing an optimal committee of size k under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when voters can be ordered so that each candidate is approved by a consecutive voters). Our result extends to the Generalized Thiele rule, in which each voter has an individual weight (scoring) sequence. This resolves a 10-year-old open problem that was originally posed for Proportional Approval Voting and later extended to every Thiele rule (Elkind and Lackner, IJCAI 2015; Peters, AAAI 2018). Our main technical ingredient is a new structural result -- a concavity theorem for families of intervals. It shows that, given two solutions of different sizes, one can construct a solution of any intermediate size whose score is at least the corresponding linear interpolation of the two scores. As a consequence, on Voter Interval profiles, the optimal total Thiele score is a concave function of the committee size. We exploit this concavity within an optimization framework based on a Lagrangian relaxation of a natural integer linear program formulation, obtained by moving the cardinality constraint into the objective. On Voter Interval profiles, the resulting constraint matrix is totally unimodular, so it can be solved in polynomial time. Our main algorithm and its proof were obtained via human--AI collaboration. In particular, a slightly simplified version of the main structural theorem used by the algorithm was obtained in a single call to Gemini Deep Think.