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

📰 ArXiv cs.AI

Polynomial-time algorithm for Thiele voting rules with voter interval preferences

advanced Published 8 Apr 2026

Action Steps

Identify the voting rule and voter preferences
Construct a weighted graph representing voter approvals
Apply dynamic programming to compute the optimal committee
Extend the algorithm to the Generalized Thiele rule with individual voter weights

Who Needs to Know This

Researchers and developers working on voting systems and algorithms can benefit from this breakthrough, as it provides an efficient solution for computing optimal committees under various voting rules.

Key Insight

💡 The algorithm resolves a 10-year-old open problem and provides an efficient solution for computing optimal committees

Key Takeaways

Polynomial-time algorithm for Thiele voting rules with voter interval preferences

Full Article

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

Abstract:
arXiv:2604.05953v1 Announce Type: cross Abstract: 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 Prop

Read full paper → ← Back to Reads