Computing Thiele Rules on Interval Elections and their Generalizations

• URL: http://arxiv.org/abs/2605.03067v2
• Date: Thu, 07 May 2026 21:11:28 GMT
• Title: Computing Thiele Rules on Interval Elections and their Generalizations
• Abstract summary: 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.
• Score: 46.93587966131188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Voting (PAV), stand out for desirable properties such as proportional representation, Pareto optimality, and support monotonicity. Their main drawback is that computing a Thiele outcome is NP-hard in general. A glimpse of hope comes from the fact that Thiele rules are better behaved under structured preferences. On the candidate interval (CI) domain, they are computable in polynomial time via a linear program (LP) that has a totally unimodular constraint matrix. Surprisingly, this approach fails for the related voter interval (VI) domain, and the complexity of the problem has repeatedly been posed as an open question. Our main result resolves this question: although the relevant matrix is not totally unimodular, the ``standard'' LP still admits at least one optimal integral solution, and we provide a fast algorithm for finding it. Our technique naturally extends to the voter-candidate interval (VCI) domain, also known as the 1-dimensional voter-candidate range (1D-VCR) domain, and to the linearly consistent (LC) domain, both of which generalize the candidate and voter interval domains. Although both the VCI and LC domains have been studied in social choice, their relationship was unknown. We show, through connections to graph theory, that LC strictly contains VCI. We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections; this equivalence may be of independent interest. Finally, we study an alternative tree-based generalization of VCI and show that Thiele rules become NP-hard to compute on this domain.

Related papers

• Algorithms for Structured Elections under Thiele Voting Rules [50.74668888214481]
  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.
  arXiv  Detail & Related papers  (2026-07-30T17:37:14Z)
• Search as Computation Allocation [52.080489413778]
  Many algorithms spend an internal resource before returning a decision and are evaluated only by the quality of that terminal output.<n>We formalize such procedures as terminal computation-allocation problems.<n>Bellman equations characterize optimal allocation under fixed budgets, priced computation, and exact certification.
  arXiv  Detail & Related papers  (2026-07-30T08:45:14Z)
• 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)
• Optimized Distortion in Linear Social Choice [28.227695590829086]
  We study distortion of linear social choice for deterministic and randomized voting rules.<n>We introduce poly-time instance-optimal algorithms for minimizing distortion given a collection of candidates and votes.
  arXiv  Detail & Related papers  (2025-10-22T20:42:49Z)
• 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)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [11.180055556912208]
  Conditional Minisum (CMS) is a voting rule for multi-issue elections with preferential dependencies.<n>We show that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency.
  arXiv  Detail & Related papers  (2022-02-03T16:15:54Z)
• Core-Stable Committees under Restricted Domains [27.621521330479208]
  We study the setting of committee elections, where a group of individuals needs to collectively select a given size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location.
  arXiv  Detail & Related papers  (2021-08-04T12:04:29Z)
• 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)
• Adaptive Combinatorial Allocation [77.86290991564829]
  We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints. Our model covers two-sided and one-sided matching, even with complex constraints.
  arXiv  Detail & Related papers  (2020-11-04T15:02:59Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  We study the conservative learning problem in the contextual linear bandit setting and introduce a novel algorithm, the Conservative Constrained LinUCB (CLUCB2) We derive regret bounds for CLUCB2 that match existing results and empirically show that it outperforms state-of-the-art conservative bandit algorithms in a number of synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-02-08T19:35:01Z)

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.