Paper deep dive
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
Pasin Manurangsi, Krzysztof Sornat
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 3:32:26 AM
Summary
The paper presents a polynomial-time algorithm for computing optimal committees under Thiele voting rules for elections on the Voter Interval (VI) domain. It resolves a 10-year-old open problem by proving that the optimal total Thiele score is a concave function of the committee size on VI profiles, utilizing a new concavity theorem for families of intervals and a Lagrangian relaxation of an integer linear program.
Entities (5)
Relation Signals (3)
Thiele voting rules → operateson → Voter Interval domain
confidence 100% · 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
Concavity Theorem → enables → polynomial-time algorithm
confidence 95% · Our main technical ingredient is a new structural result—a concavity theorem for families of intervals.
Gemini Deep Think → contributedto → polynomial-time algorithm
confidence 90% · 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.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2604.05953v1
- Canonical: https://arxiv.org/abs/2604.05953v1
Trouble viewing inline? Open PDF directly →
Full Text
75,477 characters extracted from source content.
Expand or collapse full text
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences Pasin Manurangsi Google Research pasin@google.com Krzysztof Sornat AGH University, Poland sornat@agh.edu.pl 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. 1 Introduction Approval-based committee (ABC) elections are an important topic in computational social choice literature [LS23] having applications beyond committee selection, e.g., in recommendation sys- tems [SFL16] and blockchain [BBC + 24]. In ABC elections, voters cast votes in a form of approval ballots, i.e., every voter indicates a subset of candidates. An ABC voting rule takes a collection of approval ballots (an approval profile) and outputs a committee of a given size k. One of a general class of ABC voting rules are Thiele rules [Thi95] which contains, as spe- cial cases, such basic voting rules as: Multiwinner Approval Voting (AV), Proportional Approval Voting (PAV) [AGG + 15] and Approval Voting Chamberlin-Courant (C) [C83], which covers dif- ferent properties from efficiency via proportionality to excellence [LS21]. A Thiele voting rule is parameterized by an a non-increasing infinite sequence of weights (w 1 ,w 2 ,... ). The partial sum w 1 +w 2 +· +w R models satisfaction of a voter (score of a voter) from receiving R representatives in a committee. A w-Thiele rule selects a committee of size k that maximizes total score, i.e., sum of voters scores. 1 arXiv:2604.05953v1 [cs.GT] 7 Apr 2026 From the computational complexity point of view, selecting an optimal committee under Thiele rules is NP-hard (except for AV) [AGG + 15, SFL16]. Therefore, computability of Thiele rules has been investigated under different paradigms: approximation algorithms [SFL16, BSS18, DMMS20, BFF21, BFGG22], parameterized algorithms [BSU13, EL15, YW18, BFK + 20, SVX22, YW23, GJS + 25, LS26] and structured domains [BSU13, EL15, ELP17, CE21, SVX22, ELP25, LS26]. In particular, Thiele rules on Candidate Interval (CI) domain (i.e., when candidates can be ordered so that each voter approves consecutive candidates) are polynomial-time solvable by a proper Integer Linear Pro- gramming (ILP) formulation which has been proven to be totally unimodular (TU) [Pet18]. This result extends to dichotomous Single-Peaked on a Circle profiles (this domain generalizes approving intervals of candidates on a path into approving intervals of candidates on a circle graph) [PL20]. An analogous to CI is the Voter Interval (VI) domain which contains all approval profiles with the property that voters can be ordered so that each candidate is approved by a consecutive voters. Despite the effort made over the years and tackling Thiele rules under different paradigms and using different techniques, the computational complexity of solving any given Thiele rule on a VI profile is already a 10-year-old open problem [EL15, ELP17, Pet18, YW18, PL20, GBSF21, LS23, YW23, ELP25, LS26]. It did not help that VI profiles are analogous to CI profiles by transposing voters with candidates. In particular, as observed by Peters [Pet18], a corresponding ILP formulation for VI profiles is not TU, in contrast to ILP formulation for CI profiles. This comes from the fact that the constraint matrix for VI has consecutive-ones property column-wise, but the cardinality constraint correspond to a row of ones. A concrete family of non-TU instances (with unbounded determinant prohibiting TU property) has been given in [LS26]. Although, the constraint matrix not being TU does not imply hardness of the problem. Over the time, partial progress has been established with two approaches. First, for some particular Thiele rules on VI there have been designed polynomial time algorithms. Namely, for C [BSU13] and for all Thiele rules that are ℓ-truncated, i.e., when w i = 0 for i ≥ ℓ + 1 [EL15]. Without knowing the problem is NP-hard, second approach was designing FPT algorithms, e.g., algorithms parameterized by the size of an approval ballot and by the support size [EL15, LS26]. 1.1 Our Contribution We resolve this open problem by giving a polynomial-time algorithm that, for any fixed Thiele voting rule, computes an optimal size-k committee for elections on the Voter Interval domain. Our result also extends to the Generalized Thiele rule, in which each voter has an individual weight (scoring) sequence. Our main technical ingredient is a novel structural result—a concavity theorem for VI profiles (see Section 3): given any two committees S,S ′ (not necessarily optimal) of sizes k 1 < k 2 , we can construct, for any k ∈ [k 1 ,k 2 ], a size-k committee contained in S ∪ S ′ whose total score is at least the corresponding linear interpolation of the scores of S and S ′ . By recursively applying this construction, we can obtain committees of all intermediate sizes in polynomial time. In particular, it implies that the optimal total score is a concave function of the committee size on VI profiles. To compute an optimal size-k committee (see Section 4), we use a Lagrangian relaxation of a natural ILP formulation, moving the cardinality constraint into the objective. On VI profiles, the remaining constraint matrix becomes TU, so for any Lagrange multiplier we can compute an integral optimum in polynomial time. We then perform a binary search over the multiplier values to obtain solutions bracketing size k—either it finds a solution of size exactly k or it finds two committees: one of size at most k and one of size at least k. In the latter case, using the concavity theorem, we 2 convert such bracketing solutions into an optimal committee of size exactly k. Finally, we remark that key ideas for our main proofs are obtained via human–AI collaboration through iterative interactions with Gemini. In particular, both the main idea of using Lagrangian relaxation and the main structural result (concavity theorem) are generated by Gemini—which later were adapted, fully verified and slightly generalized by the authors. We view this as a concrete case study of AI-assisted research in theoretical computer science open problems. A detailed account of our interaction with the model is given in Section 5. 2 Preliminaries We use the notation [n] = 1, 2,...,n. Let C = c 1 ,...,c m be a set of candidates and V = v 1 ,...,v n be a set of voters. A v ⊆ C denotes an approval ballot of voter v ∈ V . A collection of approval ballots A = (A v ) v∈V is called an approval profile. Any subset W ⊆ C is called a committee. The set of supporters of c∈ C is denoted by V c : =v ∈ V : c∈ A v . An approval-based committee (ABC) election is usually defined as a tuple E = (C,V,A,k), where k ∈N is the required committee size. In this paper, however, we represent an election simply by a pair (A,k), since from (A,k) we can infer the set of voters and the set of candidates C = S v∈V A v , i.e., the candidates that receive at least one approval. For the computational problems studied in this paper, candidates with zero approvals are relevant only in the trivial case S v∈V A v < k. An ABC voting rule is a function that maps an election to a set of winning committees of size k. In this paper, we focus on w-Thiele voting rules, which is a class of ABC voting rules that are parameterized by an infinite non-increasing sequence w = (w 1 ,w 2 ,... ), called a Thiele sequence. Winning committees under w-Thiele rules are those that achieve the maximum total score: max W⊆C,|W|=k score w (W ), where score w (W ) : = X v∈V |A v ∩W| X i=1 w i . In the corresponding computational optimization problem w-Thiele one has to find a winning committee (of a given size). By w-Thiele(A,k) we denote the maximum total score achieved by a winning committee of size k on a given instance (A,k) and we use a shortcut Thiele(k) if A and w are clear from the context. As is standard in the literature, we assume w.l.o.g. that w 1 = 1 as scaling the values of w does not change the set of optimal solutions. Multiwinner Approval Voting (AV) is a Thiele rule with w = (1, 1,... ). Proportional Approval Voting (PAV) is a Thiele rule with w i = 1/i. Approval Voting Chamberlin-Courant (C) is a Thiele rule with w = (1, 0, 0,... ). Our main results hold for a more general problem than w-Thiele and, for clarity, we use a separate name: the Generalized Thiele problem generalizes w-Thiele by allowing each voter to use a different Thiele sequence [SVX22]: Generalized Thiele takes as input an approval election (with n voters) and additionally a collection of n Thiele sequences w : V ×N → [0, 1], where (w v i ) i∈N is a Thiele sequence of voter v ∈ V (values of weights being in [0, 1] are due to normalization; note that we do not require w v 1 to be 1 for every v ∈ V ). For generality, we assume that all weights (w v i ) i∈[m],v∈V are given as rational numbers, with numerators and denominators encoded in binary. Thiele(A,k,w) (and Thiele(k) if A and w are clear from the context) is the 3 maximum total score achieved by a winning committee of size k on a given instance (A,k,w), i.e., max W⊆C,|W|=k score w (W ), where score w (W ) : = X v∈V |A v ∩W| X i=1 w v i . An approval profile is Voter Interval (VI) if there exists an ordering of voters such that every candidate is approved by an interval of voters in this ordering [EL15, ELP17, ELP25]. Analogously, an approval profile is Candidate Interval (CI) if there exists an ordering of candidates such that every voter approves an interval of candidates in this ordering. If a profile is VI (or CI), the respective ordering can be found in linear time [EL15]. Both VI and CI profiles can be interpreted as a family 1 of intervals over V and C respectively. We define a few types of families of intervals which are used in this paper; a family U of intervals over (1, 2,...,n) is: • inclusion-free if for every I,I ′ ∈ U we have I ̸⊆ I ′ and I ′ ̸⊆ I. • dominancy-free if for every I,I ′ ∈ U such that I ⊆ I ′ we have min(I) = min(I ′ ) and max(I) = max(I ′ ), i.e., I = I ′ [DBW + 25, LS26]. • endpoint-nested if for every I,I ′ ∈ U such that I ⊆ I ′ we have min(I) = min(I ′ ) or max(I) = max(I ′ ). Inclusion-freeness and dominancy-freeness can be defined on any family of sets (non necessarily intervals). Every family of sets that is inclusion-free is also dominancy-free. When considering a family of intervals, by the definitions of these properties, additionally we have that dominancy- freeness implies endpoint-nestedness. Moreover, all these implications are strict. A matrix M ∈ −1, 0, 1 p×q is totally unimodular (TU) if every square submatrix of M has determinant −1, 0 or 1. A matrix M ∈ 0, 1 p×q has the consecutive-ones property (for columns) if its rows can be permuted so that, in every column, the entries equal to 1 appear in a single consecutive block (possibly empty). Note that a VI approval profile interpreted as a binary matrix from 0, 1 V×C has consecutive-ones property. It is a well known fact, that a binary matrix with consecutive-ones property is TU [Sch99, p. 279]. Moreover, every integer linear program with a TU constraint matrix has integral basic solutions which implies that a linear programming solver can find an integral optimal solution, i.e., we can solve the ILP with TU constraint matrix in polynomial time. For more on theory of linear programming we defer to [Sch99]. In the remainder of this section we make a few observations. First we give an equivalent definition of endpoint-nestedness. Lemma 1. A family U of intervals over (1, 2,...,n) is endpoint-nested, if and only if, there exists an ordering (I 1 ,I 2 ,...,I |U| ) of intervals from U such that: min(I j ) ≤ min(I j+1 ) and max(I j ) ≤ max(I j+1 ), for every j ∈ [|U|− 1]. Proof. ( =⇒ ) We define the ordering ⪰ of intervals from U as follows: for I,I ′ ∈ U we set I ≻ I ′ when either: 1) min(I) < min(I ′ ) and max(I) ≤ min(I ′ ), or 2) min(I) = min(I ′ ) and max(I) < min(I ′ ). Additionally, I,I ′ ∈ U are in the same equivalency class with respect to ⪰ if 1 Throughout the paper, a family is understood as an indexed collection. In particular, different voters or candidates may correspond to identical approval ballots or supporters sets, but they are still treated as distinct objects. 4 I = I ′ . We note that the case min(I) < min(I ′ ) and max(I) > min(I ′ ) cannot appear because then I ′ ⊆ I and endpoint-nestedness of U requires that min(I) = min(I ′ ) or max(I) = max(I ′ ). Now, we show that the ordering (I 1 ,I 2 ,...,I |U| ) of intervals from U defined by⪰ (i.e., I j ⪰ I j+1 ) has the desired property. We consider any j ∈ [|U|]. From conditions that defines ⪰ we have that min(I j ) < min(I j+1 ) and max(I j ) ≤ min(I j+1 ), or min(I j ) = min(I j+1 ) and max(I j ) < min(I j+1 ), or min(I j ) = min(I j+1 ) and max(I j ) = min(I j+1 ). In all cases it is true that min(I j ) ≤ min(I j+1 ) and max(I j )≤ min(I j+1 ), which finishes the proof of the first implication. ( ⇐= ) Let (I 1 ,I 2 ,...,I |U| ) be an ordering of intervals from U such that: min(I j ) ≤ min(I j+1 ) and max(I j ) ≤ max(I j+1 ), for every j ∈ [|U|]. Consider any I j ,I j ′ ∈ U where j < j ′ . We have min(I j ) ≤ min(I j ′ ) and max(I j ) ≤ max(I j ′ ). Thus, if I j ⊆ I j ′ , we must have min(I j ) = min(I j ′ ). Similarly, if I j ′ ⊆ I j , then max(I j ) = max(I j ′ ). Hence, U is endpoint-nested. We introduce a new structured domain of approval profiles, based on the endpoint-nestedness property. Definition 2. An approval profile A is Endpoint-Nested (EN) if there exists an ordering of voters such that the family of sets of supporters (V c ) c∈C is endpoint-nested over the ordering. It is known that a VI profile that is dominancy-free is also CI [DBW + 25]. This leads to a poly- nomial time algorithm for Generalized Thiele on VI dominancy-free profiles using the algorithm for CI profiles [Pet18, PL20]. Below we show that EN profiles, that form a strict superset of VI dominancy-free profiles, are also CI, so Generalized Thiele can be solved in polynomial time on EN profiles (Corollary 4). Theorem 3. An Endpoint-Nested approval profile is Candidate Interval. Proof. Let A be an EN approval profile and let (v 1 ,v 2 ,...,v n ) be the corresponding ordering of voters. Since EN is VI and we fixed the ordering of voters, instead of (v 1 ,v 2 ,...,v n ) and V we will use simply voters’ indices, i.e., (1, 2,...,n) and [n] to denote the order of voters and the set of voters, respectively. For any arbitrary voter i ∈ [n], we have c ∈ A i if and only if min(V c ) ≤ i ≤ max(V c ). Using Lemma 1 we can also order candidates into sequence (c 1 ,c 2 ,...,c m ) such that min(V c j )≤ min(V c j+1 ) and max(V c j ) ≤ max(V c j+1 ), for every j ∈ [m− 1]. It means that both left and right endpoint sequences are non-decreasing. This implies that the condition min(V c j ) ≤ i defines a prefix of indices 1,...,p, and the condition max(V c ) ≥ i defines a suffix of indices q,...,m. Thus, the candidates approved by voter i correspond exactly to a contiguous block of indices q,q + 1,...,p, therefore A is CI. Corollary 4. Generalized Thiele on Endpoint-Nested profiles can be solved in polynomial time. 3 Concavity of the Objective Function In this section we prove that, for a given VI approval profile A, Thiele(k) is concave, i.e., the maximum achievable total score is a concave function of the committee size (Corollary 9). This follows from Theorem 5 which actually states a more general result and we believe it is of independent interest (therefore we stated it in terms of families of intervals). One of the instantiations of Theorem 5 is a polynomial-time procedure for combining two solu- tions of sizes s and s ′ (not necessarily optimal) from a VI profile, where s +s ′ is even, into a solution 5 (being a subset of union of these two solutions) of size (s + s ′ )/2 that achieves the objective value at least the average of the scores of these two solutions. Theorem 5 is stated in general terms of non-decreasing, concave functions f i ’s. In order to see that this applies to Generalized Thiele it is enough to define f v (j) = P j i=1 w v i which, indeed, are non-decreasing and concave functions because w v j ≥ w v j+1 for all v ∈ V,j ∈N. Then we have F (X) = score w (X) since c X (i) = |A i ∩ X|. Note that a solution (winning committee) to Generalized Thiele on VI is a family of intervals (corresponding to candidates selected to the committee). Recall that we treat families of intervals as multisets, and so, we interpret set operators such as ∪, ∩, and \ as the corresponding multiset union/intersection/difference (i.e., with multiplicities). Theorem 5. Let f 1 ,...,f n :Z ≥0 →R ≥0 be non-decreasing, concave functions. For any family X of intervals over (1, 2,...,n), let F (X) : = P n i=1 f i (c X (i)) where c X (i) := |I ∈ X : i ∈ I| is the coverage at point i∈ [n]. Given two families of intervals S and S ′ over (1, 2,...,n), such that |S| < |S ′ |, there is a polynomial-time algorithm that computes P = R∪R ′ ∪ (S∩S ′ ) of size |P|∈ nj |S|+|S ′ | 2 k , l |S|+|S ′ | 2 mo such that R⊆ S\ S ′ ,R ′ ⊆ S ′ \ S and F (P )≥ (1− θ)· F (S) + θ· F (S ′ ),where θ : = |P|−|S| |S ′ |−|S| . Proof. First we prove the theorem for the case that S ∩ S ′ = ∅. In the last part of the proof, we show how to handle the case S∩ S ′ ̸=∅. The Case S∩ S ′ =∅. Let U : = S∪ S ′ be the union of the given families, which has a total size of u : =|S| +|S ′ |. Step 1: The Canonical Endpoint-Nested Family U ∗ . Extract all u left endpoints and u right endpoints from the intervals in U, and independently sort them into non-decreasing sequences: L = (l 1 ,l 2 ,...,l u )such that l 1 ≤ l 2 ≤·≤ l u , R = (r 1 ,r 2 ,...,r u )such that r 1 ≤ r 2 ≤·≤ r u . We define a canonical family of intervals U ∗ : = J j = [l j ,r j ] u j=1 by pairing the j-th smallest left and right endpoints. Claim 6 verifies validity of definition of U ∗ by showing that the intervals J j = [l j ,r j ] u j=1 are well defined. Claim 6. For all j ∈ [u] it holds that l j ≤ r j . Proof of Claim 6. For i∈ [n] we define U L (i) as the number of intervals in U that have left endpoint being strictly less than i, i.e., U L (i) = I ∈ U : min(I) < i. Analogously for right endpoints we define U R (i) = I ∈ U : max(I) < i. For every i ∈ [n] we have U R (i) ⊆ U L (i) since for every I ∈ U R (i) we have i > max(I) ≥ min(I), hence also I ∈ U L (i). Now, for any j ∈ [u], l j is the j-th smallest left endpoint in U. It implies that at most j − 1 intervals in U have left endpoint being strictly less than l j , hence j − 1 ≥ |U L (l j )| ≥ |U R (l j )|. It means that also at most j − 1 intervals in U have right endpoint being strictly less than l j , therefore the j-th smallest right endpoint is at least l j , i.e., r j ≥ l j . 6 We note that the canonical family of intervals U ∗ is endpoint-nested since the definition of U ∗ matches the condition of Lemma 1. Step 2: Alternating Partition of U ∗ . Since U ∗ is endpoint-nested, using the same arguments as in the proof of Theorem 3 we obtain that the intervals in U ∗ covering i correspond exactly to a contiguous block of indices q,q + 1,...,p, for some q,p∈ [u]. We partition U ∗ into two families A ∗ and B ∗ with sizes ⌊u/2⌋ and ⌈u/2⌉ respectively, according to index parity: A ∗ : =J 2 ,J 4 ,... =J j ∈ U ∗ : j is even, B ∗ : =J 1 ,J 3 ,... =J j ∈ U ∗ : j is odd. We call such (A ∗ ,B ∗ ) an alternating partition of U ∗ . Because any contiguous sequence of integers alternates between even and odd, the coverage made by intervals from A ∗ and B ∗ at any point i∈ [n] must differ by at most 1: |c A ∗ (i)− c B ∗ (i)|≤ 1.(1) Step 3: The Alternating Partition Yields the Convexity Bound. Since (S,S ′ ) is a partition of U and (A ∗ ,B ∗ ) is a partition of U ∗ , we have c S (i) + c S ′ (i) = c U (i) and c A ∗ (i) + c B ∗ (i) = c U ∗ (i). Furthermore, because U and U ∗ share the same endpoint sets L and R, their total point-wise coverage is identical: c U ∗ (i) = c U (i). Putting these equalities together we obtain c S (i) + c S ′ (i) = c U (i) = c A ∗ (i) + c B ∗ (i), for every i∈ [n]. For every i ∈ [n], the function x 7→ f i (x) + f i (c U (i)− x) is concave (since f i is concave) and symmetric around c U (i)/2. Therefore, it is maximized when the split of c U (i) into (x,c U (i)− x) is as balanced as possible 2 , i.e., when the two arguments in (x,c U (i)− x) differ by at most 1. Since this property holds for (A ∗ ,B ∗ ) (due to Equation (1)), we get f i (c A ∗ (i))+f i (c B ∗ (i)) =max x∈0,1,...,c U (i) f i (x)+f i (c U (i)−x) ≥ f i (c S (i))+f i (c S ′ (i)), for all i∈ [n]. Summing the above inequality over all i∈ [n], we obtain F (A ∗ ) + F (B ∗ )≥ F (S) + F (S ′ ).(2) Let θ A ∗ : = |A ∗ |−|S| |S ′ |−|S| and θ B ∗ : = |B ∗ |−|S| |S ′ |−|S| . Since |A ∗ | +|B ∗ | = u =|S| +|S ′ |, we have θ A ∗ + θ B ∗ = 1.(3) If F (A ∗ ) ≥ (1− θ A ∗ )· F (S) + θ A ∗ · F (S ′ ), then we set P ∗ : = A ∗ . Otherwise, F (A ∗ ) < (1− θ A ∗ )· F (S) + θ A ∗ · F (S ′ ) and we obtain F (B ∗ ) (2) ≥ F (S) + F (S ′ )− F (A ∗ ) > F (S) + F (S ′ )− (1− θ A ∗ )· F (S) + θ A ∗ · F (S ′ ) = θ A ∗ · F (S) + (1− θ A ∗ )· F (S ′ ) 2 This inequality is in fact a special case of Karamata’s inequality [Kar32, MOA11]. 7 (3) = (1− θ B ∗ )· F (S) + θ B ∗ · F (S ′ ). Hence, in this case we set P ∗ : = B ∗ . Therefore, there exists P ∗ ∈ A ∗ ,B ∗ which satisfies the inequality from the theorem statement, i.e., F (P ∗ )≥ (1− θ P ∗ )· F (S) + θ P ∗ · F (S ′ ),where θ P ∗ : = |P ∗ |−|S| |S ′ |−|S| .(4) Moreover, |P ∗ | ∈ |A ∗ |,|B ∗ | = ⌊u/2⌋,⌈u/2⌉ as desired. This does not finish the proof of the theorem because P ∗ ⊆ U ∗ , i.e., P ∗ is a subset of canonical family, but we need to construct a subset of original input intervals U = S∪S ′ (recall that we consider the case S∩S ′ =∅). In the next step, we will show how to transform any subset of U ∗ to a subset of U without decreasing its coverage at any point i∈ [n]. Step 4: Transformation Back to U. In order to construct P ⊆ U based on P ∗ ⊆ U ∗ we rely on the following structural lemma, which shows how to transform U ∗ , the canonical form of U, back into U via swaps of right endpoints. This lemma applies to any family of intervals but we state it in terms of U and its canonical form U ∗ for concreteness. Lemma 7 (Transformation via Right-Endpoint Swaps). Any family of intervals U can be obtained from its canonical endpoint-nested form U ∗ by a sequence of at most O(|U| 2 ) right-endpoint swap operations, where such an operation replaces two intervals I 1 = [l a ,r a ] and I 2 = [l b ,r b ] satisfying l a ≤ l b ≤ r a ≤ r b with the two intervals I ∪ = [l a ,r b ] and I ∩ = [l b ,r a ], that is, with their union and intersection. Proof of Lemma 7. We show the reverse: U can be transformed into its canonical endpoint-nested form U ∗ by a finite sequence of right-endpoint swap operations. Consider the intervals in U ordered by their left endpoints l 1 ≤ · ≤ l |U| . Let r ′ 1 ,...,r ′ |U| be their corresponding right endpoints. If U ̸= U ∗3 , the right endpoints are not perfectly sorted, meaning there exists an adjacent inversion: an index i such that r ′ i > r ′ i+1 . Because l i ≤ l i+1 ≤ r ′ i+1 < r ′ i , the interval [l i+1 ,r ′ i+1 ] is strictly contained in [l i ,r ′ i ]. A right-endpoint swap operation replaces them with [l i ,r ′ i+1 ] and [l i+1 ,r ′ i ]. This strictly decreases the number of inversions in the sequence of right endpoints. Since the number of inversions is at most O(|U| 2 ), this process must terminate, which occurs precisely when the right endpoints become sorted, i.e., when the resulting family is U ∗ . Reversing this process provides the required sequence of right-endpoint swap operations from U ∗ to U. Let U ∗ = U 0 → U 1 → · → U T = U be the transformation sequence of right-endpoint swap operations from Lemma 7. We create a sequence of families P t ⊆ U t , initialized with P 0 = P ∗ , such that |P t | = |P ∗ | for every t ∈ 0, 1,...,T. For each transition from U t to U t+1 replacing I 1 ,I 2 ⊆ U t with I ∪ ,I ∩ ⊆ U t+1 we proceed as follows: • Case 1: If both I 1 ,I 2 ∈ P t , we set P t+1 = (P t \I 1 ,I 2 )∪I ∩ ,I ∪ . The point-wise coverage contribution of both pairs is identical, i.e., c I 1 ,I 2 (i) = c I ∪ ,I ∩ (i) for every i ∈ [n], so the point-wise coverage of P t and P t+1 is the same, hence F (P t+1 ) = F (P t ). • Case 2: If neither is in P t , we set P t+1 = P t , so F (P t+1 ) = F (P t ). 3 Note that every interval familyU has a unique canonical formU ∗ . 8 • Case 3: If exactly one is in P t (call it I a ), we set P t+1 = (P t \I a )∪I ∪ . Because I ∪ contains I a , the coverage at every point i ∈ [n] does not decrease, i.e., c I ∪ (i) ≥ c I a (i), so F (P t+1 )≥ F (P t ). Since |P T | =|P ∗ |, the constructed sequence of families P t ⊆ U t satisfies: F (P T )≥·≥ F (P 1 )≥ F (P 0 ) = F (P ∗ ) (4) ≥ (1− θ P T )· F (S) + θ P T · F (S ′ ),where θ P T : = |P T |−|S| |S ′ |−|S| .(5) Family P : = P T fulfills all constraints of the theorem statement: P satisfies the concavity inequality due to Equation (5); |P|∈|A ∗ |,|B ∗ | =⌊u/2⌋,⌈u/2⌉; and P = R∪R ′ ∪ (S∩S ′ ) with R : = P ∩ S ⊆ S\ S ′ and R ′ : = P ∩ S ′ ⊆ S ′ \ S. This concludes the proof for the case S∩ S ′ =∅. The Case S∩ S ′ ̸= ∅. Finally, consider the general case when S∩ S ′ ̸= ∅. Let D : = S∩ S ′ and for every i∈ [n] we define g i (x) : = f i (x + c D (i)). Since each f i is non-decreasing and concave, so is each g i . Let S 0 : = S\ D and S ′ 0 : = S ′ \ D. Then S 0 ∩ S ′ 0 = ∅ and |S 0 | < |S ′ 0 |. Applying the disjoint-case construction to S 0 and S ′ 0 with functions g 1 ,...,g n , we obtain a family P 0 ⊆ S 0 ∪ S ′ 0 such that |P 0 |∈ |S 0 | +|S ′ 0 | 2 , |S 0 | +|S ′ 0 | 2 (6) and, for G(X) : = P n i=1 g i (c X (i)) for a family X of intervals over (1, 2,...,n), we have G(P 0 )≥ (1− θ P 0 )· G(S 0 ) + θ P 0 · G(S ′ 0 ),where θ P 0 : = |P 0 |−|S 0 | |S ′ 0 |−|S 0 | .(7) Now let P : = P 0 ∪ D = P 0 ∪ (S∩ S ′ ), so P has the required form and size since |P| =|P 0 | +|D| (6) ∈ |S 0 | +|S ′ 0 | + 2|D| 2 , |S 0 | +|S ′ 0 | + 2|D| 2 = |S| +|S ′ | 2 , |S| +|S ′ | 2 . By the definition of g i (·) and c X (i) we have F (P ) = F (P 0 ∪ D) = n X i=1 f i (c P 0 ∪D (i)) = n X i=1 f i (c P 0 (i) + c D (i)) = n X i=1 g i (c P 0 (i)) = G(P 0 ) (8) Using the analogous chain of equalities for S = S 0 ∪ D and S ′ = S ′ 0 ∪ D, we obtain F (S) = G(S 0 )and F (S ′ ) = G(S ′ 0 )(9) This implies F (P ) (8) = G(P 0 ) (7) ≥ (1− θ P 0 )· G(S 0 ) + θ P 0 · G(S ′ 0 ) (9) = (1− θ P 0 )· F (S) + θ P 0 · F (S ′ ). (10) 9 Moreover, θ P 0 (7) = |P 0 |−|S 0 | |S ′ 0 |−|S 0 | = (|P 0 | +|D|)− (|S 0 | +|D|) (|S ′ 0 | +|D|)− (|S 0 | +|D|) = |P|−|S| |S ′ |−|S| .(11) Hence F (P ) (10),(11) ≥(1− θ)· F (S) + θ· F (S ′ ),where θ : = |P|−|S| |S ′ |−|S| . This completes the proof. For two families of intervals S and S ′ given, by applying Theorem 5 recursively, in polynomial time we can construct a family of solutions of all intermediate sizes|S|,|S|+1,...,|S ′ | that satisfy the concavity property from Theorem 5. In order to construct a solution of a given size p,|S| < p <|S ′ | it is enough to apply Theorem 5 iteratively at most O(log(|S ′ |−|S|)) times (in the binary-search manner). We state it as a separate proposition below and prove it for completeness. Proposition 8. Let f 1 ,...,f n ,c X ,F,S,S ′ be as in Theorem 5. Then, for any k ∈ [m] such that |S| < k <|S ′ |, there is a polynomial-time algorithm that computes P = R∪ R ′ ∪ (S∩ S ′ ) of size k such that R⊆ S\ S ′ ,R ′ ⊆ S ′ \ S and F (P )≥ (1− θ)· F (S) + θ· F (S ′ ),where θ : = |P|−|S| |S ′ |−|S| . Proof. We define a recursive procedure on pairs (X,Y ) of families of intervals over (1, 2,...,n) satisfying S ∩ S ′ ⊆ X ∩ Y ⊆ S ∪ S ′ and |X| ≤ k ≤ |Y|. The procedure maintains the following invariant (the inequality from the proposition statement) for both families X and Y : F (Z)≥ (1− θ Z )· F (S) + θ Z · F (S ′ ),where Z ∈X,Y and θ Z : = |Z|−|S| |S ′ |−|S| . (12) Initially, we call the procedure on (S,S ′ ) and the invariant holds with equality. We apply Theorem 5 to X and Y . It returns a family M = X ′ ∪Y ′ ∪(X∩Y ) such that X ′ ⊆ X ,Y ′ ⊆ Y , and |M|∈ nj |X|+|Y| 2 k , l |X|+|Y| 2 mo . Moreover, F (M )≥ (1− η)· F (X) + η· F (Y ),where η : = |M|−|X| |Y|−|X| .(13) Since S∩ S ′ ⊆ X ∩ Y , we also have S∩ S ′ ⊆ M, and clearly M ⊆ X ∪ Y ⊆ S∪ S ′ . Substituting the invariant bounds for F (X) and F (Y ) in Equation (13) yields F (M ) (12),(13) ≥(1− η)· (1− θ X )· F (S) + θ X · F (S ′ ) + η· (1− θ Y )· F (S) + θ Y · F (S ′ ) . (14) A direct calculation shows that (1− η)· θ X + η· θ Y = |M|−|S| |S ′ |−|S| , and therefore F (M ) (14) ≥ (1− θ M )· F (S) + θ M · F (S ′ ), θ M : = |M|−|S| |S ′ |−|S| . Thus the invariant (12) is preserved if we replace one of the endpoints by M: if k <|M|, we recurse on (X,M ); if k >|M|, we recurse on (M,Y ); otherwise, if |M| = k, we simply return P : = M. 10 In each recursive step, the interval of feasible sizes shrinks from length |Y|−|X| to at most l |Y|−|X| 2 m . Hence after at most O(log(|S ′ |−|S|)) recursive calls we reach a family M ∗ of size exactly k. By construction, S∩S ′ ⊆ M ∗ ⊆ S∪S ′ . Thus, if we define P : = M ∗ and R : = M ∗ ∩ (S ′ ),R ′ : = M ∗ ∩ (S ′ \ S), then P = R∪ R ′ ∪ (S∩ S ′ ), with R ⊆ S\ S ′ and R ′ ⊆ S ′ \ S as required. Finally, the invariant (12) for the family M ∗ is equivalent to the inequality from the theorem statement on P : = M ∗ . This finishes the proof. By applying Theorem 5 on two optimal solutions S and S ′ of sizes k− 1 and k + 1 respectively, we obtain concavity of the objective Thiele(k) as a function of the committee size k. Corollary 9. For a given approval profile A and a collection of Thiele sequences w, the maximum total score achieved by a winning committee of size k under the Generalized Thiele rule is a concave function of k, i.e., for every k ≥ 1 we have Thiele(k)≥ Thiele(k + 1) + Thiele(k− 1) 2 . 4 Polynomial-Time Algorithm In this section we prove our main result which implies a polynomial-time solvability of any Thiele voting rule, in particular PAV, on VI. Theorem 10. There is a polynomial-time algorithm for Generalized Thiele on Voter Interval profiles. Proof. We describe how to compute an optimal solution to Generalized Thiele instance (A,k,w), where A is VI, in polynomial time. Excluding trivial cases, we assume that k ∈1, 2,...,m− 1. Standard ILP. We use a standard Integer Linear Programming (ILP) formulation of the prob- lem [Pet18, PL20, SVX22, LS26]: maximize X v∈V X i∈[k] w v i · x v,i (15) subject to X c∈C y c = k(16) X i∈[k] x v,i ≤ X c∈A v y c ∀v ∈ V(17) x v,i ∈0, 1 ∀v ∈ V,i∈ [k] y c ∈0, 1 ∀c∈ C, where selection variable y c = 1 means selecting candidate c to the committee and counting variable x v,i = 1 means that voter v approves at least i selected committee members. Cardinality constraint (16) forces selecting exactly k candidates. The constraint (17) for v ∈ V transfers the number of selected approved candidates P c∈A v y c into counting variables x v,i which are used in the objective function (15). 11 Lagrangian Relaxation. We modify the ILP by removing the cardinality constraint P c∈C y c = k (Equation (16)) and adding penalty λ· (k− P c∈C y c ) to the objective function, for some value of Lagrange multiplier λ > 0. This operation (called Lagrangian relaxation of a constraint) moves a constraint into the objective by penalizing violating the constraint, where the penalty has linear dependence on the original constraint. Additionally, we remove the constant term λ· k from the objective. We call the resulting integer linear program as LR and we use notation LR(λ) when we mean LR with a specific value of Lagrange multiplier: maximize X v∈V X i∈[k] w v i · x v,i − λ· X c∈C y c (18) subject to X i∈[k] x v,i ≤ X c∈A v y c ∀v ∈ V x v,i ∈0, 1∀v ∈ V,i∈ [k] y c ∈0, 1∀c∈ C The LR removes a problematic cardinality constraint: on VI profiles the remaining constraint matrix is TU (as shown in [Pet18]), and thus the LR has an integral optimum and can be found in polynomial time. Lagrange Multipliers. Corollary 9 says that the optimal score Thiele(t) achieved by a com- mittee of size t is a concave function on VI profiles. Therefore, every λ ∈ [Thiele(k + 1) − Thiele(k), Thiele(k)−Thiele(k− 1)]⊆ [0,n] is a slope of an affine function i7→ Thiele(k) +λ· (i−k) that passes through the point (k,F (k)) and upper-bounds Thiele(i) for all i∈0, 1,...,m, i.e., Thiele(k) + λ· (i− k)≥ Thiele(i), This is equivalent to Thiele(k)− λ· k ≥ Thiele(i)− λ· i which implies that the maximum value of LR(λ) objective (18), for every λ ∈ [Thiele(k + 1)− Thiele(k), Thiele(k)− Thiele(k− 1)]⊆ [0,n], is achieved for a solution of size k. We will search for a fixed Lagrangian multiplier from this interval, i.e., λ k : = Thiele(k)− Thiele(k− 1). Binary Search forλ k . In order to find λ k = Thiele(k)− Thiele(k− 1)∈ [0,n] we use binary search over λ ∈ [0,n]. This leads us either to an optimal solution of size k or to two solutions S,S ′ such that |S| < k < |S ′ |. This type of Lagrange-multiplier binary search and producing two bracketing solutions is standard, for example, Lagrangian relaxation of the cardinality constraint in the k-Median problem is equivalent to the Uncapacitated Facility Location problem with uniform opening cost. In this problem one searches for multipliers that bracket k open facilities before combining the resulting solutions (see, e.g., [JV01, CGL + 25]). For completeness, we provide the full binary-search argument below. For a tested value λ, we solve LR(λ) (in polynomial time) and obtain an optimal committee W λ . If |W λ | = k, we can stop and output W λ . Otherwise, we do not interpret |W λ |̸= k as meaning that λ is already incorrect—it may happen that λ = λ k and LR(λ k ) has optimal committees of different sizes, and the solver returns one of them. Instead, we maintain a bracketing interval [λ − ,λ + ] with 12 the property that maxT (λ − ) ≥ k and minT (λ + ) ≤ k, where T (λ) denotes the set of sizes of optimal committees for LR(λ). Initially, this holds for λ − = 0 and λ + = n. At each step we test λ = λ − +λ + 2 ; if |W λ | > k we set λ − ← λ, and if |W λ | < k we set λ + ← λ. This update rule remains valid since as λ increases, larger committees are penalized more by the term −λ· P c∈C y c , and thus both minT (λ) and maxT (λ) are monotone non-increasing functions of λ. Consequently, observing an optimal solution of size strictly greater than k certifies that the considered multiplier λ is (weakly) too small, while observing an optimal solution of size strictly smaller than k certifies that the considered multiplier λ is (weakly) too large, which justifies maintaining a bracketing interval in the binary search. We continue the binary search until the length of the search interval is below additive precision ε (as defined below), i.e., λ + −λ − ≤ ε. (Recall that if at any point we obtain an optimal committee W λ with |W λ | = k, we stop and output it.) To bound the number of iterations, recall that all weights (w v i ) i∈[m],v∈V are given as rational numbers, with numerators and denominators encoded in binary. Let D be a common denominator of all input weights (e.g., the least common multiple of their denominators). Then every committee total score is a multiple of 1/D. Every breakpoint slope λ at which the set of optimal sizes T (λ) changes is of the form Thiele(t)−Thiele(t− 1), for t∈ [m], therefore it is also a multiple of 1/D. Hence any two distinct breakpoints differ by at least 1/D and it suffices to run the binary search to additive precision 1 2D . In particular, letting B denote the total bit-length of the denominators in the input, we have D ≤ 2 B and may take ε : = 1/2 B+1 , which yields O(log(n/ε)) = O(logn + B) iterations. Since the input size is Ω(nm + B), the number of binary-search iterations is at most linear in the input size. Now, we describe the next steps of the algorithm (assuming that during the binary-search procedure a committee of size k has not been found). Let ̄ λ : = (λ − + λ + )/2 and solve LR( ̄ λ), obtaining a committee W ̄ λ . If |W ̄ λ | = k, we stop and output W ̄ λ . Otherwise, since λ + − λ − ≤ ε and ε is chosen smaller than the minimum distance between two distinct breakpoints, the interval [λ − ,λ + ] contains at most one breakpoint. Moreover, by construction of the bracketing interval, the unique breakpoint in [λ − ,λ + ] must be λ k , and there is no open interval of multipliers for which an LR-optimal committee has size exactly k. Equivalently, k lies on a linear segment of Thiele(·) (i.e., |T (λ k )| > 1). In this case we perturb the multiplier and solve LR( ̄ λ− ε) and LR( ̄ λ + ε), obtaining two LR- optimal committees S,S ′ such that |S| < k < |S ′ |. Intuitively, this perturbation selects the two endpoints of the size-interval T (λ k ): decreasing λ slightly weakens the size penalty and yields a larger optimal committee, while increasing λ slightly strengthens the penalty and yields a smaller optimal committee. By concavity, this implies that Thiele(t) is linear on the whole interval of sizes between |S| and |S ′ |, and in particular Thiele(a)− λ k · a = Thiele(k)− λ k · k,for every a∈|S|,|S| + 1,...,|S ′ |. (19) Now, using Proposition 8 to committees S and S ′ , we can construct a committee W of size exactly k (after at most log(|S ′ |−|S|)≤ log(m) calls to Theorem 5) which for θ : = k−|S| |S ′ |−|S| satisfies the following: F (W )≥ (1− θ)· F (S) + θ· F (S ′ ) = (1− θ)· (Thiele(|S|)− λ k ·|S|) + θ· (Thiele(|S ′ |)− λ k ·|S ′ |) (19) = (1− θ)· (Thiele(k)− λ k · k) + θ· (Thiele(k)− λ k · k) = Thiele(k)− λ k · k. 13 This inequality means that W achieves a maximal objective value among all size-k committees, so it is an optimal solution of the Generalized Thiele instance. This finishes the proof. 5 AI Assistance In this section, we describe how Gemini (Deep Think), an AI-assistance tool, helped in achieving the results presented in this paper. Analogous descriptions appeared recently [WCAJ + 26, Knu26], where results in theoretical computer science were achieved with AI-assistance. We had two separate interactions with Gemini [Tea25]. Initial Interactions: Arriving at Lagrangian Relaxation. As a first step, we use Gemini Pro to generate the main ideas for the algorithm. In particular, we simply prompt the model to solve the problem, using the full problem description. Originally, the model proposed an incorrect polynomial- time algorithm based on Maximum Flow. Fortunately, once we point out to the model that this algorithm is incorrect, the model immediately suggests the Lagrangian relaxation approach, which is essentially the same as the one we eventually used. However, once we ask the model to provide the proof of correctness, it provides an incorrect proof. In particular, the concavity argument is incorrect. After several attempts to prompt the model to correct this proof, the model still fails. The sequence of interactions we have with the model—with full prompts but with responses abbreviated—is given in Appendix B. Final Step: Proof of Concavity of the Objective. As concavity of the objective function was a crucial missing part of the Lagrangian relaxation approach, in a second step, we reformulate the concavity property in a self-contained manner. Using this reformulation, we prompt Gemini Deep Think. In the very first response, the model gives us the correct proof of the statement, which is the basis for our main concavity theorem (Theorem 5). We remark our eventual theorem is slightly more generalized than the version we asked the model. Specifically, we only ask the model to combine two solutions whose size differ by exactly two and did not ask for a polynomial time algorithm. Moreover, the concavity formulation assumes that the two solutions are disjoint, since their common elements might be included in the combined solution. Formally, the solution created by the model might use the same interval twice, which is not allowed in the final solution. The model did not specifically discuss this issue. Nevertheless, our final proof is essentially the same as produced by the model. The exact user prompt and response for this second step are given in Appendix A. 6 Conclusion In this work we gave a polynomial-time algorithm for computing an optimal size-k committee for Thiele voting rules on the Voter Interval domain, thereby resolving a 10-year-old open problem [EL15, ELP17, Pet18, YW18, PL20, GBSF21, LS23, YW23, ELP25, LS26]. We also extended the result to the Generalized Thiele rule. A key ingredient is our concavity theorem for families of intervals, which we view as a structural result of independent interest. An interesting direction for future work is to obtain a purely combinatorial algorithm for Thiele rules on the Voter Interval domain (and, analogously, on the Candidate Interval domain [Pet18, PL20]), avoiding linear-programming solvers. Achieving this may require further structural insights 14 beyond concavity, which could deepen our understanding of why these domains admit efficient exact algorithms and may be of independent interest. Finally, our results illustrate how human–AI collaboration can help identify useful structural conjectures and guide proof development in theoretical computer science. We hope this experience will encourage further systematic study of such workflows on other open problems in theoretical computer science. Acknowledgements Krzysztof Sornat was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854). References [AGG + 15] Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational Aspects of Multi-Winner Approval Voting. In Pro- ceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), pages 107–115, 2015. [BBC + 24] Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein, Luis Sánchez Fernán- dez, and Ulrike Schmidt-Kraepelin. Approval-Based Committee Voting in Practice: A Case Study of (over-)Representation in the Polkadot Blockchain. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pages 9519–9527, 2024. [BFF21]Siddharth Barman, Omar Fawzi, and Paul Fermé. Tight Approximation Guarantees for Concave Coverage Problems. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 9:1–9:17, 2021. [BFGG22] Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, and Emirhan Gürpinar. Tight Approximation Bounds for Maximum Multi-Coverage. Math. Program., 192(1):443– 476, 2022. [BFK + 20] Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Dusan Knop, and Rolf Niedermeier. Parameterized Algorithms for Finding a Collective Set of Items. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pages 1838–1845, 2020. [BSS18]Jarosław Byrka, Piotr Skowron, and Krzysztof Sornat. Proportional Approval Voting, Harmonic k-Median, and Negative Association. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 26:1– 26:14, 2018. [BSU13]Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the Computation of Fully Proportional Representation. J. Artif. Intell. Res., 47:475–519, 2013. [C83]John R. Chamberlin and Paul N. Courant. Representative Deliberations and Repre- sentative Decisions: Proportional Representation and the Borda Rule. Am. Political Sci. Rev., 77:718–733, 9 1983. 15 [CE21]Andrei Costin Constantinescu and Edith Elkind. Proportional Representation under Single-Crossing Preferences Revisited. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 5286–5293, 2021. [CGL + 25] Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson. A (2+ε)-Approximation Algorithm for Metric k-Median. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 615–624, 2025. [DBW + 25] Chris Dong, Martin Bullinger, Tomasz Wąs, Larry Birnbaum, and Edith Elkind. Se- lecting Interlacing Committees. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), pages 630–638, 2025. [DMMS20] Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, and Krzysztof Sornat. Tight Approximation for Proportional Approval Voting. In Proceedings of the 29th Interna- tional Joint Conference on Artificial Intelligence (IJCAI 2020), pages 276–282, 2020. [EL15]Edith Elkind and Martin Lackner. Structure in Dichotomous Preferences. In Proceed- ings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 2019–2025, 2015. [ELP17]Edith Elkind, Martin Lackner, and Dominik Peters. Structured Preferences. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 10, pages 187–207. AI Access, 2017. [ELP25]Edith Elkind, Martin Lackner, and Dominik Peters. Preference Restrictions in Com- putational Social Choice: A Survey. CoRR, abs/2205.09092v2, 2025. [GBSF21] Michał Tomasz Godziszewski, Paweł Batko, Piotr Skowron, and Piotr Faliszewski. An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections. In Pro- ceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 5448–5455, 2021. [GJS + 25] Sushmita Gupta, Pallavi Jain, Souvik Saha, Saket Saurabh, and Anannya Upasana. More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025), pages 3891–3899, 2025. [JV01]Kamal Jain and Vijay V. Vazirani. Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Re- laxation. J. ACM, 48(2):274–296, 2001. [Kar32]Jovan Karamata. Sur une inégalité relative aux fonctions convexes. (French). Publ. Math. Univ. Belgrade, 1:145–148, 1932. [Knu26]Donald E. Knuth. Claude’s cycles. Manuscript, Stanford Computer Science Depart- ment, February 2026. Dated 28 February 2026; revised 16 March 2026. [LS21]Martin Lackner and Piotr Skowron. Consistent Approval-based Multi-winner Rules. J. Econ. Theory, 192:105173, 2021. 16 [LS23]Martin Lackner and Piotr Skowron. Multi-Winner Voting with Approval Preferences. Springer, 2023. [LS26]Alexandra Lassota and Krzysztof Sornat. Algorithms for Structured Elections un- der Thiele Voting Rules. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026), page To appear, 2026. [MOA11] Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics. Springer, 2 edition, 2011. [Pet18]Dominik Peters. Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pages 1169–1176, 2018. [PL20]Dominik Peters and Martin Lackner. Preferences Single-Peaked on a Circle. J. Artif. Intell. Res., 68:463–502, 2020. [Sch99]Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1999. [SFL16]Piotr Skowron, Piotr Faliszewski, and Jérôme Lang. Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation. Artif. Intell., 241:191–216, 2016. [SVX22]Krzysztof Sornat, Virginia Vassilevska Williams, and Yinzhan Xu. Near-Tight Algo- rithms for the Chamberlin-Courant and Thiele Voting Rules. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022), pages 482–488, 2022. [Tea25]Gemini Team. Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Mul- timodality, Long Context, and Next Generation Agentic Capabilities. CoRR, abs/2507.06261, 2025. [Thi95]Thorvald Thiele. Om flerfoldsvalg. In Oversigt over det Kongelige Danske Vidensk- abernes Selskabs Forhandlinger (in Danish), pages 415–441. København: A.F. Høst, 1895. [WCAJ + 26] David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, Mo- hammadHossein Bateni, Simina Branzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken ichi Kawarabayashi, Ravi Ku- mar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Ben- jamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, and Vahab Mirrokni. Accelerating Scientific Research with Gemini: Case Studies and Common Techniques. Technical Report arXiv:2602.03837 [cs.CL], arXiv.org, February 2026. 17 [YW18]Yongjie Yang and Jianxin Wang. Parameterized Complexity of Multi-Winner Determi- nation: More Effort Towards Fixed-Parameter Tractability. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), pages 2142–2144, 2018. [YW23]Yongjie Yang and Jianxin Wang. Parameterized Complexity of Multiwinner Deter- mination: More Effort Towards Fixed-Parameter Tractability. Auton. Agents Multi Agent Syst., 37(2):28, 2023. A Human–AI Interaction Log I: Proof of Concavity Below, we include the exact user prompt and response from the model that provides the proof of concavity (Theorem 5). We stress that this is a single call to Gemini Deep Think without further interaction. The response is a correct proof of the required statement. User Prompt Consider the following objective. We have non-decreasing functions f 1 ,...,f n from non- negative integers to non-negative reals such that they are concave. For given a multiset of intervals S = I 1 ,...,I k , its *total value* is computed as follows: For every i ∈ [n], let c i denote the number of intervals containing i. Then, let the total value be F (S) = f 1 (c 1 ) +· + f k (c k ). Prove the following statement: Given two multiset of intervals S,S ′ of size k− 1,k + 1 respectively (where k is a positive integer). Then, we can always find a sub-multiset S ′ ⊆ S∪ S ′ of size k such that F (S ′ )≥ (F (S) + F (S ′ ))/2. AI Response To prove this statement, we can use a constructive combinatorial approach. The problem asks us to find a sub-multiset S ′ ⊆ S ∪ S ′ of size k whose total value is at least the average of the values of S and S ′ . Let U = S∪ S ′ be the multiset union of the two given collections of intervals. The size of U is (k− 1) + (k + 1) = 2k. Step 1: The Canonical Uncrossed Multiset U ∗ . First, we extract all 2k left endpoints and 2k right endpoints from the intervals in U. We sort both multisets independently in non- decreasing order: Left endpoints L: l 1 ≤ l 2 ≤ · ≤ l 2k Right endpoints R: r 1 ≤ r 2 ≤ · ≤ r 2k We define a canonical multiset of intervals U ∗ = J m = [l m ,r m ] 2k m=1 by pairing the m-th smallest left endpoint with the m-th smallest right endpoint. Validity: For any m, there are exactly m − 1 left endpoints strictly less than l m . Thus, at most m− 1 intervals in U can finish strictly before l m . This implies at least 2k− (m− 1) right endpoints in U must be≥ l m . Consequently, the m-th smallest right endpoint r m must be≥ l m . Therefore, all intervals in U ∗ are strictly valid. Identical Total Coverage: Because U and U ∗ share the exact same sets of endpoints L and R, their total pointwise coverage is identical. For 18 any point x∈ [n], c U ∗ (x) = c U (x) = c S (x) + c S ′ (x). Step 2: Alternating Partition of U ∗ . Consider the ordered sequence of intervals J 1 ,J 2 ,...,J 2k in U ∗ . For any arbitrary point x, an interval J m covers x if and only if l m ≤ x≤ r m . Because l m is non-decreasing, the condition l m ≤ x is satisfied by a prefix of indices1, 2,...,p. Because r m is non-decreasing, r m ≥ x is satisfied by a suffix of indices q,q + 1,..., 2k. There- fore, the subset of intervals in U ∗ covering x corresponds exactly to a contiguous subsegment of indices q,q + 1,...,p. We partition U ∗ into two sub-multisets of size k by alternating the sorted indices: A ∗ = J 1 ,J 3 ,J 5 ,...,J 2k−1 , B ∗ = J 2 ,J 4 ,J 6 ,...,J 2k . Because any contiguous block of integers is split as evenly as mathematically possible into evens and odds, the number of covering intervals at point x distributed to A ∗ and B ∗ will differ by at most 1: |c A ∗ (x)− c B ∗ (x)|≤ 1 Step 3: Majorization and Lower Bound. For every point x, the integers c A ∗ (x) and c B ∗ (x) sum to c S (x) +c S ′ (x) and differ by at most 1. This means they form the most balanced possible pair of integers for that sum. By the Hardy-Littlewood-Pólya majorization inequality, a more balanced distribution maximizes the sum of any concave functions. Since each f x is concave: f x (c A ∗ (x)) + f x (c B ∗ (x))≥ f x (c S (x)) + f x (c S ′ (x)) Summing this across all points x∈ [n] yields: F (A ∗ ) + F (B ∗ )≥ F (S) + F (S ′ ) Since A ∗ and B ∗ both have a size of exactly k, the Pigeonhole Principle dictates that at least one of them (assume A ∗ without loss of generality) satisfies: F (A ∗ )≥ F (S) + F (S ′ ) 2 Step 4: Transformation Back to U. We have found a size-k subset A ∗ from M ∗ that achieves the required threshold, but we need a subset S ′ drawn from our original multiset U. Any original configuration U can be reached from the canonical U ∗ via a finite sequence of "crossing" operations. A crossing operation takes two crossing intervals I 1 = [l a ,r a ] and I 2 = [l b ,r b ] (where l a ≤ l b ≤ r a ≤ r b ) and replaces them with their union I ∪ = [l a ,r b ] and intersection I ∩ = [l b ,r a ]. (This is equivalent to reversing the standard "uncrossing" algorithm, meaning it takes adjacent inversions of the right-endpoint permutation and sorts them back into the configuration found in U). Let U ∗ = M 0 → M 1 → · → M N = U be this sequence. We can maintain a sub-multiset Z i ⊆ M i of size k at every step starting with Z 0 = A ∗ : If Z i contains both I 1 ,I 2 , we place both I ∪ ,I ∩ into Z i+1 . The sum of their point-wise coverages is perfectly identical since 1 I 1 + 1 I 2 = 1 I ∪ + 1 I ∩ . If Z i contains neither, we put neither into Z i+1 . If Z i contains exactly one of I 1 ,I 2 , we strictly place the union I ∪ into Z i+1 . Because 19 the union strictly covers the spans of both I 1 and I 2 , the coverage at any point either strictly increases or remains the same. By induction, we arrive at a size-k sub-multiset Z N ⊆ U. Because coverage never decreases at any step and the given functions f x are non-decreasing, evaluations only increase or stay constant: F (Z N )≥ F (A ∗ )≥ F (S) + F (S ′ ) 2 Setting S ′ = Z N fulfills all constraints, concluding the proof. B Human–AI Interaction Log I: Arriving at Lagrangian Relax- ation In this section, we include the sequence of interactions with Gemini Pro model that lead to the formulation of the Lagrangian relaxation approach together with the concavity theorem. At the beginning, the model suggested a different (incorrect) algorithm using Maximum Flow, but after pointing out that its algorithm is incorrect, the model converges to the Lagrangian relaxation approach. However, as noted earlier, the proof given by the model is incorrect. While we have attempted to make the model corrects its mistake, the proof remains wrong until the very end. Since the model’s responses are quite long, we abbreviate part of the responses (that we believe are less relevant)—this is denoted by “[...] (ABBREVIATED)” in the responses below. We also note that there is in fact an error in the problem formulation in the very first user prompt where P j∈[m] P i∈[w c(j) ] w i should instead be P j∈[m] P i∈[c(j)] w i . This is a genuine mistake on our part. Despite this typo, the model immediately starts working on the correct version of the problem. User Prompt Consider the following problem: We have intervals [l 1 ,r 1 ],..., [l n ,r n ] where l i ,r i are integers in 0,...,m. Furthermore, we also have scores w 1 ≥ · ≥ w k ≥ 0. The goal is to pick k intervals that maximizes the following objective P j∈[m] P i∈[w c(j) ] w i where c(j) denotes the number of times j is covered by the picked intervals. (Note that c(j) is always a number from 0,...,k.) Can you prove that this problem is NP-hard? AI Response Based on the problem statement provided, the problem is not NP-hard. In fact, it can be solved in polynomial time. The problem describes a variation of the Maximum Coverage Problem specialized for In- tervals, with an objective function characterized by diminishing returns (concavity). While the general Maximum Coverage problem (on arbitrary sets) is NP-hard, the interval structure 20 and the concavity of the weights allow for efficient solutions using Min-Cost Flow or Linear Programming. [...] (ABBREVIATED) User Prompt Ok, this is good. Can you please help write a full algorithm together with a full formal proof of correctness? You may assume that m is not too large and just create a graph on the m time steps directly without identifying the unique endpoints first. AI Response Here is the full algorithm and a formal proof of correctness. Problem Restatement. We are given n intervals [l 1 ,r 1 ],..., [l n ,r n ] within the range 0,...,m. We have weights w 1 ≥ · ≥ w k ≥ 0. We must select a subset of indices S ⊆1,...,n with |S| = k to maximize: X j∈[m] c(j) X i=1 w i where c(j) is the number of selected intervals covering point j. Part 1: The Algorithm (Min-Cost Flow Construction). We reduce this problem to a Min-Cost Max-Flow problem on a directed acyclic graph. 1. Graph Construction. Let G = (V,E) be a directed graph. • Nodes: Create m + 2 nodes labeled 0, 1,...,m,m + 1. • Node 0 acts as the Source (S). • Node m + 1 acts as the Sink (T). • The nodes 1,...,m represent the time steps. • Edges: We construct two types of edges: Interval Edges and Backbone (Coverage) Edges. A. Interval Edges (Representing choice of intervals). For each interval I u = [l u ,r u ] in the input (where u∈1,...,n): 21 • Add a directed edge from l u to r u + 1. • Capacity: 1 • Cost: 0 • Intuition: Flowing through this edge represents “picking” interval u. It skips the “costly” backbone edges between l u and r u + 1. B. Backbone Edges (Representing coverage count). For each position j ∈ 0,...,m, add k parallel edges from node j to node j + 1. Let’s index these parallel edges by t∈1,...,k. • Capacity: 1 (per parallel edge) • Cost: −w t • Intuition: These edges represent the benefit of covering point j. If 1 unit of flow goes through the backbone at j, we gain w 1 (cost −w 1 ). If 2 units go through, we gain w 1 +w 2 (cost −w 1 − w 2 ). 2. The Flow Requirement. We require a total flow of exactly k units from Source (0) to Sink (m + 1). 3. Execution. 1. Construct the graph as described. 2. Run a standard Min-Cost Max-Flow algorithm (e.g., successive shortest path using Bellman-Ford or SPFA if weights are negative, or use potentials with Dijkstra) to send exactly k units of flow from 0 to m + 1. 3. The minimum cost found will be negative. The maximum objective value for the original problem is −(MinCost). 4. Extracting the Solution. To identify which intervals to pick: • Inspect the Interval Edges. If the edge corresponding to interval [l u ,r u ] carries flow 1, include interval u in your solution set S. [...] (ABBREVIATED) 22 User Prompt Your algorithm is obviously incorrect since it allows more than k intervals to be picked. Please fix this. If you cannot fix it, try proving that it is NP-hard instead. AI Response You are absolutely correct. My previous construction was flawed because it failed to strictly enforce the “exactly k intervals” constraint (it allowed “stitching” disjoint intervals into a single unit of flow). The problem is not NP-hard. It is solvable in polynomial time (O(Poly(n,m) · log(Precision))). The correct approach requires handling the “exactly k” constraint using Lagrangian Relax- ation (often called the WQS Binary Search or “Alien’s Trick” in competitive programming) coupled with a Min-Cost Circulation algorithm. Here is the corrected algorithm and the logic behind it. The Core Logic: Lagrangian Relaxation. The constraint “pick exactly k intervals” is hard to model directly in flow networks because “count” is a global property. However, we can move this constraint into the objective function. Instead of fixing k, let’s assign a cost λ to the act of picking any interval. We then solve the simpler unconstrained problem: Subproblem: Pick any set of intervals to maximize: X j c(j) X i=1 w i − λ· (number of picked intervals) Intuitively: • If λ is very high (expensive), the optimal solution picks few intervals. • If λ is low (cheap), the optimal solution picks many intervals. • Since the marginal gain of adding intervals is diminishing (concavity), the number of inter- vals picked is monotonic with respect to λ. We can binary search for the λ that results in picking exactly k intervals. The function G(k) = Optimal Score with k intervals is concave. This allows the binary search to find the optimal solution effectively. The Algorithm 1. Binary Search for λ. We binary search for a penalty value λ ∈ [−M,M ] (where M is a sufficiently large number). In each step of the binary search, we solve the Min-Cost Circulation problem described below. 23 2. Network Construction (Min-Cost Circulation). For a fixed λ, we construct a graph to find the optimal subset of intervals. • Nodes: Create nodes 0, 1,...,m,m + 1 representing the timeline points. • Timeline Edges (Left-to-Right): These represent the “state” of being covered. • For each j ∈0,...,m, add edges from j → j + 1. • Since the benefit is concave (w 1 ≥ w 2 ... ), we model this with Convex Cost flow. • Add n parallel edges from j → j + 1: – Edge 1: Capacity 1, Cost −w 1 . – Edge 2: Capacity 1, Cost −w 2 . – . . . and so on. • Note: Maximizing positive weight is equivalent to minimizing negative cost. • Interval Edges (Right-to-Left): These represent the decision to “pick” an interval. • For each available interval i given as [l i ,r i ], add a directed edge from (r i + 1)→ l i . • Capacity: 1 (each interval can be picked at most once). • Cost: λ. 3. Solving the Circulation. Run a Min-Cost Circulation algorithm. This algorithm finds a flow that satisfies flow conservation at every node and minimizes total cost. • A circulation decomposes into a set of cycles. • A cycle here corresponds to: 1. Using an interval edge (r i + 1)→ l i (Paying λ). 2. Flowing back through the timeline l i → · → r i + 1 (Collecting benefits −w 1 ,−w 2 ... ). • The algorithm will only saturate a cycle if the benefit (sum of w’s) exceeds the cost λ. 4. Update Step. Let k ′ be the number of interval edges saturated (carrying flow) in the optimal circulation. • If k ′ > k: The penalty λ is too low. Increase λ. • If k ′ < k: The penalty λ is too high. Decrease λ. • If k ′ = k: We found the optimal set. The final answer is: Objective =−(MinCost from Circulation) + k· λ 24 Proof of Correctness (Sketch). 1. Total Unimodularity (TU): The constraint matrix of the interval problem (an interval matrix) is Totally Unimodular. This ensures that the Linear Programming relaxation of the problem has an integral optimal solution. 2. Concavity: The function f (x) = max coverage with x intervals is concave (discrete con- cave) due to the diminishing returns of overlaps (w i ≥ w i+1 ) and the TU property. 3. WQS Binary Search Validity: The concavity ensures that for any k, there exists a “slope” λ such that the unconstrained optimization with penalty λ yields an optimal solu- tion with exactly k items (or allows us to interpolate between k and k + 1). 4. No Stitching: The “stitching” issue of the previous algorithm is solved by the topology. Flow travels L → R on the timeline and R → L on interval edges. To reuse the timeline flow (stitching), one would need to jump from the end of one interval to the start of another against the flow direction, which is impossible without using another costly interval edge or traversing the timeline (which correctly accounts for coverage). Thus, the problem is solvable in polynomial time using Min-Cost Circulation within a binary search. User Prompt Can you give some more justification regarding concavity? I actually don’t see how it holds. AI Response This is an excellent question. The claim of concavity is the cornerstone of the polynomial-time solution (specifically for the WQS binary search), so it requires a rigorous proof rather than just an appeal to “diminishing returns.” The concavity holds because the problem can be transformed into a Min-Cost Flow problem with a parameter k as the flow demand. A fundamental property of Min-Cost Flow networks is that the minimum cost is a convex function of the flow amount. [...] (ABBREVIATED) User Prompt Your proof is wrong: We already discussed this but the minimum cost flow formulation you used in the proof is incorrect because it does *not* take the cardinality constraint into 25 account. Can you just try to prove this from first principle? Namely, just try to argue, if we have two solutions for k− 1 and k + 1, how do we combine them to get the solution for k? Again, be completely formal and self-contained. AI Response You are asking for a direct, first-principles justification for why the algorithm works. The core of the correctness relies on the concavity of the optimal objective function F (k) (the max score with k intervals). If F (k) is concave (i.e., 2F (k) ≥ F (k − 1) + F (k + 1)), then the local marginal gains are diminishing, and the WQS Binary Search (Lagrangian Relaxation) is guaranteed to find the global optimum. Below is the formal proof of concavity. It avoids flow networks and relies on the geometric properties of intervals—specifically, the Total Unimodularity (TU) of the interval matrix. Problem Setup LetI be a collection of n intervals. Let A be the m×n coverage matrix, where A ji = 1 if interval i covers point j, and 0 otherwise. Let w :Z ≥0 →R be a function defining the score of covering a point c times: w(c) = min(c,k) X t=1 w t Since w 1 ≥ w 2 ≥ ... , the function w(c) is concave. The total objective for a selection vector x∈0, 1 n is: Obj(x) = m X j=1 w((Ax) j ) Let F (k) be the maximum objective value subject to P x i = k. The Claim. We prove that F (k) is concave. Specifically, for any k: F (k− 1) + F (k + 1)≤ 2F (k) The Proof Step 1: Combining Solutions. Let x be an optimal solution for k− 1 (so P x i = k− 1). Let z be an optimal solution for k + 1 (so P z i = k + 1). Consider the sum vector h = x + z. Note that h ∈ 0, 1, 2 n . The total number of intervals in h is (k − 1) + (k + 1) = 2k. The coverage depth at point j for this combined multiset is C j = (Ax) j + (Az) j . We wish to decompose h into two new integer vectors y 1 ,y 2 ∈0, 1 n such that: 1. y 1 + y 2 = h (They partition the multiset h). 26 2. P y 1,i = k and P y 2,i = k (Both are feasible for problem size k). 3. Their coverage profiles are "balanced" to exploit the concavity of w. Step 2: The Splitting Lemma (via Total Unimodularity). Lemma 11. Let M be a matrix that is Totally Unimodular (TU). For any integer vector h, there exist integer vectors y 1 ,y 2 such that y 1 + y 2 = h and for every row r: |(My 1 ) r − (My 2 ) r |≤ 1 Application to our problem: The constraint matrix describing our problem consists of: 1. The interval coverage matrix A (which has consecutive ones in columns). 2. The cardinality constraint (a row of all 1s). It is a known result that an interval matrix augmented with a row of 1s is Totally Unimodular. Applying the lemma to h = x + z: We can find y 1 ,y 2 such that y 1 + y 2 = h, and: • Cardinality Balance: | P y 1,i − P y 2,i | ≤ 1. Since the total sum is 2k, the sums must be exactly k and k. Thus, y 1 ,y 2 are valid feasible solutions for the size k problem. • Coverage Balance: For every point j, the coverages c 1 = (Ay 1 ) j and c 2 = (Ay 2 ) j satisfy |c 1 − c 2 |≤ 1. Since c 1 + c 2 = C j (total coverage at j), the condition |c 1 − c 2 | ≤ 1 implies that c 1 and c 2 are the floor and ceiling of the average: c 1 ,c 2 = C j 2 , C j 2 Step 3: Discrete Concavity Argument. We now compare the total scores. We know that for any concave function w and any integers a,b: w(a) + w(b)≤ w a + b 2 + w a + b 2 (Intuitively: pushing values closer to the mean increases the sum for concave functions). Applying this to every point j: w((Ax) j ) + w((Az) j )≤ w((Ay 1 ) j ) + w((Ay 2 ) j ) Summing over all points j: Obj(x) + Obj(z)≤ Obj(y 1 ) + Obj(y 2 ) Since x and z were optimal for k− 1 and k + 1: F (k− 1) + F (k + 1)≤ Obj(y 1 ) + Obj(y 2 ) Since y 1 and y 2 are valid solutions for k, their scores cannot exceed optimal F (k): Obj(y 1 )≤ F (k) and Obj(y 2 )≤ F (k) Combining these inequalities: F (k− 1) + F (k + 1)≤ 2F (k) 27 Conclusion. This proves that the objective function F (k) is concave. Consequently, the WQS Binary Search algorithm (Lagrangian Relaxation) is mathematically justified and will correctly find the global maximum in polynomial time. User Prompt You claim that an interval matrix augmented with a row of 1s is Totally Unimodular. This is clearly wrong as can be seen by the following matrix [[1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [1, 1, 1, 1]] which has determinant 2. Can you fix this issue? AI Response You are absolutely correct. The matrix you provided is a valid counterexample. The “interval matrix augmented with an all-ones row” is not totally unimodular (TU) in general. I apologize for that error. While the specific matrix formulation involving the cardinality row is not TU, the Maximum Weight k-Interval Coverage problem is still solvable in polynomial time. The correctness of the algorithm relies on the concavity of the objective function F (k). We can prove this concavity via a reduction to Min-Cost Flow, relying on the fact that the node-arc incidence matrix of a network is always TU (unlike the interval coverage matrix with a cardinality constraint). Here is the corrected formal proof that resolves the issue by shifting the perspective from generic linear programming to network flow theory. Addressing the Matrix Issue. The user correctly identified that the constraint matrix formed by interval coverage constraints plus a global cardinality constraint is not necessarily Totally Unimodular (TU). Therefore, we cannot rely on the standard LP relaxation of that specific matrix formulation. However, we can model the problem exactly using a Network Flow formulation. The constraint matrix of a network flow problem (the node-arc incidence matrix) is always TU. The cardinality constraint k is handled as the flow demand, which acts as the right-hand side of the linear system rather than a row in the matrix itself. This preserves the integrality of the solution. Formal Proof Theorem 12. Let F (k) be the maximum score achievable using exactly k intervals. The function F (k) is concave. Proof. We construct a Min-Cost Flow network G = (V,E) such that the minimum cost of sending k units of flow is exactly −F (k) + C constant . Since the minimum cost of a flow network with convex edge costs is a convex function of the flow amount, this implies F (k) is concave. Network Construction. Create a graph with nodes 0, 1,...,m,m + 1. 28 • Source/Sink: We inject k units of flow at node 0 and extract k units at node m + 1. • Interval Arcs (Selection): For every interval i given as [l i ,r i ], create a directed edge u i from l i to r i + 1. – Capacity: 1. – Cost: 0. – Interpretation: Flow x i = 1 on this arc means interval i is selected. • Timeline Arcs (Non-coverage): For every j ∈ 0,...,m, create a directed edge v j from j to j + 1. – Capacity: k. – Cost Function Φ j (y): Depends on flow y through this arc. Flow Conservation and Costs. Let y j be the flow on the timeline arc (j,j + 1). Let S j be the set of intervals covering point j. In the network, these correspond to interval arcs that "jump over" the timeline segment (j,j + 1). Consider the cut separating 0,...,j from j + 1,...,m + 1. The total flow across this cut must be k. The edges crossing this cut are exactly the timeline arc v j and the interval arcs covering j. y j + X i∈S j x i = k Thus, the number of active intervals covering j is c(j) = P x i = k − y j . The flow y j on the timeline represents the "missed" coverage opportunities (or the number of empty slots). We want to maximize P c(j) t=1 w t . In terms of y j , we maximize P k−y j t=1 w t . This is equivalent to minimizing the negative score. We define the cost function Φ j (y j ) for the timeline arc as: Φ j (y j ) =− k−y j X t=1 w t Convexity of Edge Costs. To use the properties of Min-Cost Flow, the edge cost functions Φ j (y) must be convex. Let us examine the marginal cost ∆Φ j (y) = Φ j (y + 1)− Φ j (y). Φ j (y) =−(w 1 +· + w k−y ) Φ j (y + 1) =−(w 1 +· + w k−y−1 ) ∆Φ j (y) = Φ j (y + 1)− Φ j (y) = w k−y The sequence of marginal costs for y = 0, 1,... is w k ,w k−1 ,...,w 1 . Since the problem specifies non-increasing weights w 1 ≥ w 2 ≥·≥ w k , the sequence of marginal costs is non-decreasing. A discrete function with non-decreasing marginal differences is convex. 29 Conclusion. 1. The constraint matrix of this problem is the node-arc incidence matrix of the graph G, which is Totally Unimodular. Thus, for integer demand k, there exists an integral optimal flow. 2. A standard result in network flow theory states that the optimal objective value of a Min- Cost Flow problem with convex edge costs is a convex function of the flow amount k. 3. Let C(k) be this minimum cost. Our original maximization objective is F (k) =−C(k). 4. Since C(k) is convex, F (k) is concave. This validates the WQS Binary Search approach used in the algorithm. [...] (ABBREVIATED) 30