pith. machine review for the scientific record.
sign in

arxiv: 2604.05953 · v1 · submitted 2026-04-07 · 💻 cs.GT · cs.AI· cs.DS· cs.MA

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

Pasin Manurangsi , Krzysztof Sornat This is my paper

Pith reviewed 2026-05-10 18:23 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.DScs.MA
keywords Thiele rulesvoter intervalcommittee selectionpolynomial-time algorithmconcavityapproval votingLagrangian relaxation
0
0 comments X

The pith

Polynomial-time algorithms compute optimal committees of any size under every Thiele rule when voter approvals form intervals.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that, when voters can be lined up so every candidate is approved by a consecutive block, the best Thiele score for committees of size k is a concave function of k. Concavity follows from a new structural fact: given any two feasible committees of different sizes, an intermediate-size committee can always be built whose score is at least as good as the straight-line interpolation between the two known scores. Because the score is concave, a Lagrangian relaxation of the natural integer program becomes solvable in polynomial time; on interval profiles the relaxed constraint matrix is totally unimodular. The same argument works for the generalized version of Thiele rules in which each voter supplies its own weight sequence. This settles the open question posed for Proportional Approval Voting in 2015 and extended to all Thiele rules in 2018.

Core claim

On any voter-interval profile the optimal total Thiele score is a concave function of committee size. The concavity is proved by a theorem on families of intervals: for any two committees of sizes a < b there exists, for every intermediate size c, a committee of size c whose score is at least the linear interpolation of the scores at a and b. The same concavity holds for generalized Thiele rules with per-voter scoring sequences. Concavity lets the cardinality constraint be moved into the objective via Lagrangian relaxation; the resulting linear program has a totally unimodular constraint matrix on voter-interval instances and is therefore solvable in polynomial time.

What carries the argument

The concavity theorem for families of intervals, which produces an intermediate-size committee whose score is at least the linear interpolation of two given solutions.

If this is right

  • An optimal committee of any requested size k can be returned in polynomial time for every Thiele rule on voter-interval elections.
  • The algorithm extends unchanged to generalized Thiele rules that assign each voter its own sequence of marginal scores.
  • The optimal Thiele score is a concave function of committee size on every voter-interval profile.
  • The same Lagrangian-relaxation approach yields a polynomial-time solution for the generalized version of the problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same concavity argument may apply to other restricted approval domains whose interval structure is similar to voter intervals.
  • If concavity can be proved or approximated for other preference restrictions, the Lagrangian technique could yield fast algorithms beyond the voter-interval case.
  • The structural theorem itself might be useful for proving approximation guarantees or for designing heuristics when the profile is only approximately interval-structured.

Load-bearing premise

The concavity theorem holds: for any two committees of different sizes on a voter-interval profile, some committee of each intermediate size scores at least as well as the straight-line interpolation between them.

What would settle it

An explicit voter-interval profile and Thiele rule together with two committees of sizes a and b such that every committee of some size c between a and b scores strictly below the linear interpolation of the two known scores.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to present a polynomial-time algorithm for computing an optimal committee of size k under any Thiele voting rule (including the generalized version with per-voter weight sequences) on voter-interval approval profiles. The approach rests on a new concavity theorem showing that the optimal Thiele score is a concave function of committee size, which justifies solving a Lagrangian relaxation of the natural ILP; on voter-interval instances the resulting constraint matrix is totally unimodular and therefore the LP can be solved in polynomial time.

Significance. If the concavity theorem and total-unimodularity claim hold, the result resolves a 10-year open problem originally posed for PAV and later generalized to all Thiele rules. The structural theorem on interval families is of independent interest and the Lagrangian-plus-TU technique supplies a clean, parameter-free algorithmic method rather than a mere existence argument. The explicit human-AI collaboration note is a minor but positive transparency feature.

major comments (2)
  1. [Abstract / concavity theorem section] The concavity theorem (abstract and the section presenting the structural result) is load-bearing: the equivalence between the Lagrangian optimum and the original cardinality-constrained optimum holds only if, for any s1 < s2 and any generalized weight sequence, an intermediate-size committee exists whose score is at least the linear interpolation. The manuscript must supply a complete, self-contained proof of this construction that covers arbitrary non-increasing weight sequences; any gap here collapses the polynomial-time claim.
  2. [LP formulation section] The total-unimodularity assertion for the Lagrangian constraint matrix on voter-interval profiles (the section formulating the LP) is load-bearing for polynomial-time solvability. The paper must either prove TU directly or cite a precise known result for the specific matrix arising from interval approvals; without an explicit argument the reduction to an LP does not establish polynomial time.
minor comments (2)
  1. The abstract states that a simplified version of the main theorem was obtained in a single Gemini call; consider adding a short appendix or footnote that records the exact prompt and the precise statement returned by the model, to facilitate future verification of the discovery process.
  2. Notation for the generalized Thiele score function and the per-voter weight sequences should be introduced before the statement of the concavity theorem to avoid forward references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful and constructive review of our manuscript. The comments correctly identify the two load-bearing technical claims, and we will strengthen the presentation by supplying the requested explicit arguments. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract / concavity theorem section] The concavity theorem (abstract and the section presenting the structural result) is load-bearing: the equivalence between the Lagrangian optimum and the original cardinality-constrained optimum holds only if, for any s1 < s2 and any generalized weight sequence, an intermediate-size committee exists whose score is at least the linear interpolation. The manuscript must supply a complete, self-contained proof of this construction that covers arbitrary non-increasing weight sequences; any gap here collapses the polynomial-time claim.

    Authors: We agree that a fully self-contained proof is essential for the concavity theorem. In the revised manuscript we will expand the structural-result section with a complete, step-by-step construction that, for any pair of committee sizes s1 < s2 and any non-increasing per-voter weight sequence, produces an intermediate-size committee whose Thiele score is at least the linear interpolation of the two given scores. The argument will be written to apply directly to the generalized Thiele rules and will be independent of the subsequent algorithmic sections. revision: yes

  2. Referee: [LP formulation section] The total-unimodularity assertion for the Lagrangian constraint matrix on voter-interval profiles (the section formulating the LP) is load-bearing for polynomial-time solvability. The paper must either prove TU directly or cite a precise known result for the specific matrix arising from interval approvals; without an explicit argument the reduction to an LP does not establish polynomial time.

    Authors: We concur that an explicit justification of total unimodularity is required. In the revised version we will add a self-contained proof that the constraint matrix arising from the Lagrangian relaxation is totally unimodular on voter-interval profiles. The proof will exploit the consecutive-ones property of the interval-approval incidence matrix together with the specific form of the Lagrangian objective, showing that the resulting matrix remains totally unimodular and therefore solvable in polynomial time by standard LP methods. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on a newly proved internal theorem plus classical facts.

full rationale

The paper's core chain is: (1) prove a new concavity theorem for families of intervals (showing an intermediate-size committee score is at least the linear interpolation of two given solutions), (2) deduce that the optimal Thiele score is a concave function of committee size on Voter Interval profiles, (3) apply Lagrangian relaxation to the natural ILP by moving the cardinality constraint into the objective, and (4) solve the resulting LP in polynomial time because the constraint matrix is totally unimodular on these profiles. The concavity theorem is presented as a fresh structural result established in the paper (with a simplified version obtained via AI assistance), not imported via self-citation or defined in terms of the target algorithm. No parameters are fitted to data and then relabeled as predictions, no uniqueness theorems are invoked from the authors' prior work, and no known empirical patterns are merely renamed. The TU property is a classical external fact. The overall algorithm therefore rests on independent content rather than reducing to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard mathematical facts about totally unimodular matrices and linear programming, plus one new structural theorem proved in the paper.

axioms (1)
  • standard math A matrix is totally unimodular if every square submatrix has determinant in {-1,0,1}.
    Invoked to guarantee that the Lagrangian relaxation solves in polynomial time and yields integral solutions.

pith-pipeline@v0.9.0 · 5578 in / 1236 out tokens · 30410 ms · 2026-05-10T18:23:09.598896+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Computing Thiele Rules on Interval Elections and their Generalizations

    cs.AI 2026-05 conditional novelty 8.0

    Thiele rules admit polynomial-time computation on voter interval and linearly consistent approval domains via integral solutions to a standard linear program.

  2. Computing Thiele Rules on Interval Elections and their Generalizations

    cs.AI 2026-05 accept novelty 7.0

    Thiele rules are polynomial-time computable on voter interval elections via a standard LP that always has an integral optimum, extending to VCI and LC domains with NP-hardness shown on tree-based generalizations.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    picking” intervalu. It skips the “costly

    Graph Construction.LetG= (V, E)be a directed graph. •Nodes:Createm+ 2nodes labeled0,1, . . . , m, m+ 1. •Node0acts as theSource (S). •Nodem+ 1acts as theSink (T). •The nodes1, . . . , mrepresent the time steps. •Edges:We construct two types of edges:Interval EdgesandBackbone (Coverage) Edges. A. Interval Edges (Representing choice of intervals). For each ...

    work page

  2. [2]

    The Flow Requirement.We require a total flow of exactlykunits from Source (0) to Sink (m+ 1)

    work page

  3. [3]

    Construct the graph as described

    work page

  4. [4]

    Run a standardMin-Cost Max-Flowalgorithm (e.g., successive shortest path using Bellman-Ford or SPFA if weights are negative, or use potentials with Dijkstra) to send exactlykunits of flow from0tom+ 1

    work page

  5. [5]

    The maximum objective value for the original problem is−(M inCost)

    The minimum cost found will be negative. The maximum objective value for the original problem is−(M inCost)

    work page

  6. [6]

    exactlykintervals

    Extracting the Solution.To identify which intervals to pick: •Inspect theInterval Edges. If the edge corresponding to interval[l u, ru]carries flow1, include intervaluin your solution setS. [...] (ABBREVIATED) 22 User Prompt Your algorithm is obviously incorrect since it allows more thankintervals to be picked. Please fix this. If you cannot fix it, try p...

    work page

  7. [7]

    Ineachstepofthebinarysearch, wesolvetheMin-CostCirculation problem described below

    Binary Search forλ.We binary search for a penalty valueλ∈[−M, M](whereMis a sufficientlylargenumber). Ineachstepofthebinarysearch, wesolvetheMin-CostCirculation problem described below. 23

    work page

  8. [8]

    •Nodes:Create nodes0,1,

    Network Construction (Min-Cost Circulation).For a fixedλ, we construct a graph to find the optimal subset of intervals. •Nodes:Create nodes0,1, . . . , m, m+ 1representing the timeline points. •Timeline Edges (Left-to-Right):These represent the “state” of being covered. •For eachj∈ {0, . . . , m}, add edges fromj→j+ 1. •Since the benefit is concave (w1 ≥w...

    work page

  9. [9]

    This algorithm finds a flow that satisfies flow conservation at every node and minimizes total cost

    Solving the Circulation.Run aMin-Cost Circulationalgorithm. This algorithm finds a flow that satisfies flow conservation at every node and minimizes total cost. •Acirculationdecomposes into a set of cycles. •A cycle here corresponds to:

    work page

  10. [10]

    Using an interval edge(ri + 1)→l i (Payingλ)

    work page

  11. [11]

    Flowing back through the timelinel i → · · · →r i + 1(Collecting benefits −w1,−w 2 . . .). •The algorithm will only saturate a cycle if the benefit (sum ofw’s) exceeds the costλ

    work page

  12. [12]

    stitching

    Update Step.Letk ′ be the number of interval edges saturated (carrying flow) in the optimal circulation. •Ifk ′ > k: The penaltyλis too low. Increaseλ. •Ifk ′ < k: The penaltyλis too high. Decreaseλ. •Ifk ′ =k: We found the optimal set. The final answer is: Objective=−(MinCost from Circulation) +k·λ 24 Proof of Correctness (Sketch). 1.Total Unimodularity ...

    work page

  13. [13]

    P y1,i =kand P y2,i =k(Both are feasible for problem sizek)

    work page

  14. [14]

    balanced

    Their coverage profiles are "balanced" to exploit the concavity ofw. Step 2: The Splitting Lemma (via Total Unimodularity). Lemma 11.LetMbe a matrix that is Totally Unimodular (TU). For any integer vectorh, there exist integer vectorsy1, y2 such thaty 1 +y 2 =hand for every rowr: |(M y1)r −(M y 2)r| ≤1 Application to our problem:The constraint matrix desc...

    work page

  15. [15]

    Thus, for integer demandk, there exists an integral optimal flow

    The constraint matrix of this problem is the node-arc incidence matrix of the graphG, which isTotally Unimodular. Thus, for integer demandk, there exists an integral optimal flow

    work page

  16. [16]

    A standard result in network flow theory states that the optimal objective value of a Min- Cost Flow problem with convex edge costs is aconvex functionof the flow amount k

    work page

  17. [17]

    Our original maximization objective isF(k) =−C(k)

    LetC(k)be this minimum cost. Our original maximization objective isF(k) =−C(k)

    work page

  18. [18]

    This validates the WQS Binary Search approach used in the algorithm

    SinceC(k)is convex,F(k)isconcave. This validates the WQS Binary Search approach used in the algorithm. [...] (ABBREVIATED) 30

    work page