Algorithms for Structured Elections under Thiele Voting Rules

This paper investigates the computational complexity of winner determination in approval-based committee elections under Thiele voting rules. While these rules—such as Proportional Approval Voting (PAV) and Chamberlin-Courant (CC)—are highly desirable for balancing diversity and proportionality, they are generally NP-hard to compute. The authors seek to identify structural properties of voter preferences that make these problems tractable.

To overcome computational hardness, the authors analyze the structure of winning committees by examining the dependencies between candidates based on their sets of supporters. They introduce a dominance relation, where a candidate is dominated if their supporters are a strict subset of another candidate's supporters. By characterizing optimal committees as non-dominated, they develop new algorithmic techniques. Specifically, they focus on the Voter Interval (VI) domain, where voters can be ordered such that each candidate's supporters form a contiguous segment. They combine this structural insight with dynamic programming to design FPT algorithms.

The authors demonstrate that for any Thiele rule, the winner determination problem on the VI domain is FPT when parameterized by the maximum number of approvals a candidate receives and the maximum number of approvals a voter provides. This is a significant result because the same problem remains NP-hard on general instances even when these parameters are constant. Additionally, the paper resolves two open questions from the literature: it provides 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 the winning committee.

Winner determination is a bottleneck for deploying sophisticated voting rules in real-world applications like recommendation systems and blockchain governance. By proving that specific structural domains (like VI) allow for efficient computation, this work provides a roadmap for practitioners to use these rules in structured settings. Furthermore, the theoretical tools developed here, particularly the dominance-based characterization of optimal committees, offer a new framework for future research into the complexity of multi-winner elections.