Research map / Learning theory and algorithms / Submodular and game algorithms

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

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Committee voting rules · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a polynomial-time algorithm for optimal committee selection under any (generalized) Thiele rule on Voter Interval profiles, via a concavity theorem for interval families and a Lagrangian relaxation with binary search, with the main ideas developed through human-AI collaboration with Gemini.

Problem

Computing an optimal size-k committee under Thiele voting rules (e.g., PAV) on Voter Interval approval profiles has been an open complexity question for about 10 years.

Approach

A concavity theorem for families of intervals shows the optimal Thiele score is concave in committee size on VI profiles; combined with Lagrangian relaxation of the cardinality constraint (which leaves a TU matrix on VI), a binary search over the multiplier recovers an optimal size-k committee by interpolating two bracketing solutions.

Key results

• Polynomial-time algorithm for optimal size-k committee under any Thiele rule and the Generalized Thiele rule on Voter Interval profiles, resolving a 10-year-old open problem.
• Concavity theorem: on VI profiles the optimal total Thiele score is concave in committee size, via a construction producing intermediate-size committees whose score is at least the linear interpolation.
• Lagrangian relaxation of the ILP yields a TU constraint matrix on VI, so each multiplier is solvable in polynomial time; binary search over the multiplier with O(log n + B) iterations.

Surprising findings

• Gemini Deep Think produced a correct concavity proof in a single call, after earlier Gemini Pro attempts at the proof were incorrect and proposed an incorrect max-flow algorithm.
• During the AI interaction, Gemini's proposed claim that an interval matrix augmented with an all-ones row is TU was shown to be false by a counterexample with determinant 2.

Limitations

• Solution relies on linear programming / TU structure rather than a purely combinatorial algorithm.
• Result applies only to the Voter Interval domain (and EN profiles for generalized Thiele via CI).

Experimental setup

Builds on: Thiele rules Candidate Interval domain algorithm integer linear programming formulation of Thiele rules

Closest papers by meaning

• Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.88)
• Refined Characterizations of Approval-Based Committee Scoring Rules (AAAI 2024 · similarity 0.88)
• Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.87)
• On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.86)
• Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.86)
• Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.85)