# Algorithms for Structured Elections under Thiele Voting Rules

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 30 Jul 2026.

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

- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Robust and Verifiable Proportionality Axioms for Multiwinner Voting](https://mlsanity.com/paper/2302.01989/) (2023)
- [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)
- [The Price of Justified Representation](https://mlsanity.com/paper/2112.05994/) (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)
- [Mixed Integer Programming with Convex/Concave Constraints: Fixed-Parameter Tractability and Applications to Multicovering and Voting](https://mlsanity.com/paper/1709.02850/) (2017)
- [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)
- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)

## Abstract (arXiv)

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.