Algorithms for Structured Elections under Thiele Voting Rules

• URL: http://arxiv.org/abs/2607.28575v1
• Date: Thu, 30 Jul 2026 17:37:14 GMT
• Title: Algorithms for Structured Elections under Thiele Voting Rules
• Abstract summary: We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules.<n>We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate.<n>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.
• Score: 50.74668888214481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Computing Thiele Rules on Interval Elections and their Generalizations [46.93587966131188]
  We show that computing a Thiele outcome is NP-hard in general.<n>On the candidate interval (CI) domain, they are computable in time via a linear program (LP) that has a totally unimodular constraint matrix.<n>We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections.
  arXiv  Detail & Related papers  (2026-05-04T18:39:48Z)
• Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences [29.61006537058682]
  We present a-time algorithm for computing an optimal committee of size $k$ under any given Thiele voting rule.<n>Our result extends to the Generalized Thiele rule, in which each voter has an individual weight (scoring) sequence.
  arXiv  Detail & Related papers  (2026-04-07T14:46:37Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections.<n>The margin of victory, or simply'margin', is the smallest number of ballots that need to be manipulated to alter the set of winners.<n>Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  We consider a perpetual approval voting method that guarantees that no voter is dissatisfied too many times.<n>We identify a sufficient condition on voter behavior under which a sublinear growth of dissatisfaction is possible.<n>We present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
  arXiv  Detail & Related papers  (2024-12-20T19:58:55Z)
• Multiwinner Temporal Voting with Aversion to Change [30.15852603215344]
  We study two-stage committee elections where voters have dynamic preferences over candidates. At each stage, a committee is chosen under a given voting rule. We show a full complexity dichotomy for the class of Thiele rules.
  arXiv  Detail & Related papers  (2024-08-20T17:16:54Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  We study voting rules that are computable by querying voters about $t m$ candidates. For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
  arXiv  Detail & Related papers  (2024-02-16T22:17:01Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.