Complexity of Thiele voting on voter-interval profiles
Follow the latest progress by email.
Can an optimal size-k committee for a Thiele voting rule be found in polynomial time when each candidate’s approving voters form an interval in one voter order? The target also allows voter-specific scoring sequences.
Why it matters and what counts as progress
Why it matters: The restricted domain may make winner determination tractable even for rules difficult on general profiles.
What counts as progress: A polynomial-time algorithm for every stated Thiele rule on voter-interval profiles, or a hardness result within that same domain.
How the problem developed
- 2015 · Domain question [1]
Edith Elkind and Jörg Lackner Introduced voter-interval preferences as a structured approval domain and posed polynomial-time Proportional Approval Voting as an open problem.
- 2018 · Generalized question [1]
Dominik Peters Extended the open problem from Proportional Approval Voting to all Thiele rules on voter-interval profiles.
- 7 Apr 2026 · Algorithm [1]
Pasin Manurangsi and Krzysztof Sornat Gave a polynomial-time algorithm for finding an optimal size-k committee under every Thiele rule on voter-interval approval profiles.
AI contribution
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
A polynomial-time algorithm finds an optimal size-k committee for any Thiele rule on voter-interval approval profiles, including voter-specific scoring sequences.
Sources
Website timeline
Publication dates and editorial changes.
Gemini ideas support polynomial-time Thiele voting on voter intervals