Computing Thiele Rules on Interval Elections

A new paper on arXiv (2605.03067) resolves the computational complexity of Thiele rules, including Proportional Approval Voting (PAV), on the voter interval (VI) domain. While Thiele rules are NP-hard in general, they are polynomial-time solvable on the candidate interval (CI) domain via a linear program (LP) with a totally unimodular constraint matrix. The VI domain was an open problem; the authors show that although the LP matrix is not totally unimodular, at least one optimal solution exists, settling the complexity question. Thiele rules are valued for proportional representation, Pareto optimality, and support monotonicity.