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

• URL: http://arxiv.org/abs/2604.05953v1
• Date: Tue, 07 Apr 2026 14:46:37 GMT
• Title: Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
• Abstract summary: 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.
• Score: 29.61006537058682
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 Proportional Approval Voting and later extended to every Thiele rule (Elkind and Lackner, IJCAI 2015; Peters, AAAI 2018). Our main technical ingredient is a new structural result -- a concavity theorem for families of intervals. It shows that, given two solutions of different sizes, one can construct a solution of any intermediate size whose score is at least the corresponding linear interpolation of the two scores. As a consequence, on Voter Interval profiles, the optimal total Thiele score is a concave function of the committee size. We exploit this concavity within an optimization framework based on a Lagrangian relaxation of a natural integer linear program formulation, obtained by moving the cardinality constraint into the objective. On Voter Interval profiles, the resulting constraint matrix is totally unimodular, so it can be solved in polynomial time. Our main algorithm and its proof were obtained via human--AI collaboration. In particular, a slightly simplified version of the main structural theorem used by the algorithm was obtained in a single call to Gemini Deep Think.

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)
• 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)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• 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 Efficient Computation of DiRe Committees [2.741266294612776]
  Consider a committee election consisting of (i) a set of candidates who are divided into arbitrary groups each of size $atmost$ two.<n>A diversity constraint stipulates the selection of $atleast$ one candidate from each group.<n>A representation constraint stipulates the selection of $atleast$ one candidate from each population who has a non-null set of approved candidates.
  arXiv  Detail & Related papers  (2024-02-29T17:13:30Z)
• 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)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• 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)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)

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.