Efficient Algorithms for Electing Successive Committees

1 Introduction

A non-profit organization (NPO) offers a 3-day personal development workshop for teenagers in a remote location. Featured activities include discussion sessions with three expert counselors who tackle the participants' questions in various topics of developing self awareness. Potential counselors agreed to participate in such discussions for at most two consecutive days to avoid excessive traveling and fatigue. Every counselor specializes in a limited selection of topics regarding self-awareness. The NPO wants to select three groups of three counselors, one group per day, to offer the participants as broad experience as possible. Hence, the selected groups must obey the counselors' consecutiveness requirement and also guarantee a diverse selection of topics covered each day by the respective counselor pair.

The NPO's task seemingly can be modeled as a multiwinner voting task [Faliszewski et al., 2017; Lackner and Skowron, 2023]. Identifying counselors as candidates and each subarea as a voter, who approves for the candidates representing counselor's expertise, we want to select a diverse group of candidates. However, the classical model neglects the temporal aspect of the problem and thus misaligns with the task. Precisely, it fails to group the counselors in teams of three to serve on the three days of the workshop while adhering to the consecutiveness requirement.

The described shortcoming has recently been addressed by Bredereck et al. [2020], who proposed a suitable framework of successive committee elections. Here, based on a collection of votes, one selects a collection of multiple, ordered, same-size groups, called committees, of "best" candidates. In line with our toy example, each candidate in the selected committees must be a member of a single contiguous block of at most a given number of committees. Besides introducing the new model, the authors have studied associated problems through algorithmic lens. They studied four successive committee rules focused on maintaining the diversity of the chosen committees based on the Chamberlin-Courant rule [Chamberlin and Courant, 1983]. Further, they considered extensions of the widespread approval voting rule and weakly-separable scoring rules. Their study identified cases solvable in polynomial time mostly related to finding series of committees that consist of two candidates. While they showed that with very few exceptions the same task for committees of size three or more is computationally hard, they abstained from providing algorithms dealing with such cases.

Motivated by the desire of providing means of computing successive committees for criteria considered by Bredereck et al. [2020], we sidestep their hardness results by applying advanced algorithmic methods from parameterized complexity theory. We analyze the same set of rules they did and contribute several positive algorithmic results, as shown in Table 1. Consequently, (1) we provide the first algorithms that deal with the hard scenarios for committee size bigger than two, including cases focusing on diverse committees similar to our introductory example, and (2) our methods are furthermore computationally efficient (in the parameterized sense) for cases with a small number of candidates or committees to be selected. The mentioned cases of interest seem quite likely in practice. Indeed, planning too far ahead usually bears unacceptable risks (like unpredictable changes of voters preferences or dropping out of candidates). Too big pool of candidates is often undesired due to human perception limitation and is usually avoided by shortlisting (in a broad sense, e.g., by requiring petition signatures, deliberation processes, organizing pre-selection). As our algorithmic contributions extend the applicability of successive committee elections, we directly respond to the call of Boehmer and Niedermeier [2021] to consider different paths of tractability of new models 1 better capturing the changing nature of realworld problems.

Some other models incorporate the time aspect into classical committee elections additionally allowing votes to change their vote over time. Bredereck et al. [2022] introduce such a model and analyze the (parameterized) computational complexity of several related questions. Their results, complemented with those of Kellerhals et al. [2021], offer a comprehensive computational landscape. Importantly, their model does not generalize the one we consider, as their requirements for the outcome on a series of committees are focused on (dis)similarity of neighboring committees. Deltl et al. [2023] deepen the study of the model of Bredereck et al. [2022] by studying new questions related mostly to the fairness of the outcomes towards the voters. The dynamic nature of preferences considered by the three listed works makes approaches therein impossible to adapt to our problems. In the light of the mentioned literature, our work takes a significant step towards addressing the somewhat neglected algorithmic study of successive committee elections.

Another related scenario of time-dependent voting where the task is to select a single candidate for each time step can be seen as a series of committees of size one. The literature on this model mostly focuses on proportionality and fairness from axiomatic [Lackner, 2020; Lackner and Maly, 2021; Chandak et al., 2024], algorithmic [Elkind et al., 2024b; Bulteau et al., 2021] and experimental perspectives [Bulteau et al., 2021; Chandak et al., 2024]. See a survey by Elkind et al. [2024a] for more details on this topic.

2 Preliminaries

For a positive integer x, we use [x] to denote set {1, 2, . . . , x}. An election E = (C, V ) consists of m candidates C = {c1, c2, . . . , cm} and a collection V = {v1, v2, . . . , vn} of n voters. We study approval and ordinal preferences. In the former preference type, we associate a voter vi ∈ V with their approval set A(i) of candidates that vi approves. In the ordinal preferences model each voter vi ranks all candidates and so is identified with their (total and strict) preference order ≻i. We denote by posi(c) a position of candidate c ∈ C in some voter vi's ranking ≻i. There are multiple mathematical ways of relating ordinal preferences to approval preferences. 2 However, they all require decisions somewhat arbitrary from the practical perspective.

Fixed-Parameter Tractability. We say a computational problem is fixed-parameter tractable for some parameter x (being a part of the input) if there is an (parameterized) algorithm solving every instance I in time O(f(x)|I|c ) for some constant c. We call such an algorithm an FPT(x)- algorithm. Under standard computational complexity assumptions, fixed-parameter tractability for some parameter x is excluded when the problem is W[t]-hard, t ∈ N with respect to x or when the problem is NP-hard for a fixed value of x.

1 Their taxonomy classifies successive committee elections as the setting of Ordered One profile Multiple solutions (O-OM).

2 For example: approvals are either complete rankings with ties or can be constructed from rankings by letting each voter approve a number of their top candidates.

Committee Series Quality. Let us fix a committee scoring function sc: 2C → N, which assigns a nonnegative natural committee score to each committee W ⊆ C. Given an (ordered) committee series W = (W1,W2, . . . ,Wτ) of τ same-sized committees, util(W) := ∑i∈[τ] sc(Wi) is the utilitarian committee series quality of W and egal(W) := mini∈[τ] sc(Wi) is its egalitarian committee series quality. We study consecutive f-frequency committee series. In such series, each candidate participates in at most f consecutive committees of a series.

Ordinal committee scoring functions. Let E = (C, V ) be an arbitrary ordinal election with m candidates, n voters, and W = {w1,w2, . . . ,wk} ⊆ C be a committee. Following Bredereck et al. [2020] we consider three (families of) ordinal committee scoring functions (1.) ChamberlinCourant (CC), (2.) egalitarian Chamberlin-Courant (eCC), and (3.) weakly separable scoring functions (which we denote collectively by FWS) formally defined as:

1. CC(W) := ∑i∈[n] maxw∈W (m-posi(w))
2. eCC(W) :=mini∈[n] maxw∈W (m-posi(w))
3. a function Q is weakly separable, i.e., Q ∈ FWS, if it can be associated with some function ϕ: [m] → N0 such that Q(W) = ∑i∈[n] ∑w∈W ϕ(posi(w))

The family of weakly-separable functions is very general. Among others, it includes such prominent voting rules as Plurality or Borda. Their respective ϕ functions are ϕplu(x) := max(0, 2 - x) and ϕBor(x) := m - x (both defined for x ∈ [m]).

Approval committee scoring functions. Similarly, for an arbitrary approval election E = (C, V ) with n voters and some committee W ⊆ C, we consider (1.) (approval) Chamberlin-Courant (AppCC), (2.) threshold-α Chamberlin-Courant (trCCγ ), for rational γ ∈ (0, 1], and (3.) approval score (App), defined formally as follows:

Central problem. We focus on the following computational problem, which we define very generally. We use α ∈ {util, egal} as a placeholder for a committee series quality measure and β ∈ {CC, eCC, AppCC, trCCγ , App} ∪ FWS, to indicate a committee scoring function. For readability, we directly substitute β with FWS, when we mean that β is an arbitrary weakly-separable committee scoring function (e.g., egal-FWS -SCE is a placeholder for any problem egal-g-SCE where g ∈ FWS). We do not explicitly specify whether the input consists of ordinal or approval votes. It is to be inferred from the committee scoring function β in question.

α-β-SUCCESIVE COMMITTEES ELECTION (α-β-SCE) Input: Election E = (C, V ) with candidates C and voters V , a number τ of committees in a target series, a size k of committees in a target series, a maximum candidate frequency f , and a minimal committee quality η.

Question: Is there a consecutive f-frequency committee series S of size τ consisting of size-k committees such that α(β(S)) ≥ η?

Bredereck et al. [2020] show that egal-β-SCE is NP-hard for all studied β even when simultaneously k = 3 and f = 1. Except for β′ ∈ {App,FWS}, they prove the same for utilβ′ -SCE. Importantly, these two results immediately exclude efficient parameterized algorithms for small values of k, f, and their sum.

Even though the above formulation is a decision problem, all our algorithms can be used to find a requested committee series. In theorem statements, we give asymptotic running times of algorithms ignoring mostly irrelevant terms polynomial in the input. For clarity, we stress it using O⋆ instead of the standard O. The proofs marked by ⋆, or their parts, are deferred to the full version of our paper [Jain and Kaczmarczyk, 2025].

3 The Case of FewCandidates

Given the general computational hardness results of Bredereck et al. [2020], we start our search of efficient algorithms from cases with a bounded number of candidates. As argued in the introduction, this assumption can naturally be justified from the practical point of view. Parameter "number of candidates," which we denote by m, is too a standard parameter in the literature on the complexity of election problems.

For better accuracy, in some subsequent results (and in Table 1) we give running times using the size k of committees. Because k ≤ m, such results always yield fixed-parameter tractability for parameter m. Naturally, they also show fixedparameter tractability for parameter m+ k. Recall that the hardness results of Bredereck et al. [2020] exclude fixedparameter tractability for k alone.

Finding the winner of every multiwinner voting rule that assigns a score to each committee and chooses the one with the maximum score as the winner is fixed-parameter tractable with respect to the number of candidates (assuming computing the score of a committee is polynomial-time solvable). This observation becomes easy, when one realizes that for such rules it is enough to enumerate all possible committees and compute their scores (for example, see the works of Procaccia et al.; Betzler et al. [2008; 2013]) . However, a committee series is composed of multiple committees whose interdependency is nontrivially governed by the frequency of candidates and the requirement of consecutiveness. Indeed, even if we enumerate all at most 2m committees, to construct a committee series we need to consider that each of them possibly come in any between one and frequency-many copies as demonstrated in Example 3 by Bredereck et al. [2020].

Does this complication to the domain of all possible solutions make finding the right solution computationally harder with respect to parameter "number of candidates"?

For the good news, we answer the above in negative. Quite surprisingly, even though the number of all possible committee series depends nonlinearly on the candidate frequency, the following series of results show fixed-parameter tractability of the problems we study with respect to solely the number of candidates. By this, the results reveal that the increase of the complexity of the domain of solutions is, intuitively, still bounded by a function of the number of candidates.

We start with a foundational result for the case of f = 1. While the result applies to both the utilitarian and egalitarian variants of our problem, it is the latter variant for which the result gives fixed-parameter tractability.

Theorem 1 (⋆). There exists an algorithm that solves utilβ-SCE and egal-β-SCE in O⋆ (2m) time for f = 1 and all studied β.

The importance of Theorem 1 for the egal-β-SCE problem lies in combining it with the subsequent observation by Bredereck et al. [2020].

Proposition 1 (Lemma 1 by Bredereck et al. [2020]). egalβ-SCE with f ≥ 2 can be reduced to egal-β-SCE with f = 1 in linear time.

The reduction in Proposition 1 does not increase the number of candidates. Hence, with Theorem 1, Proposition 1 yields a general result about the egalitarian version of the problem, which shows the sought tractability for small number of candidates.

Theorem 2. There exists an algorithm that solves egal-βSCE in O⋆ (2m) time for all studied β.

Generalizing Theorem 1 in the utilitarian case does not directly lead to such an optimistic result as that for the egalitarian case. Instead, we obtain dynamic programming (DP) algorithms whose running time upper-bounds increase exponentially with the increase of parameter f. To increase readability, we first state our result for f = 2.

Theorem 3. There is an FPT(m)-algorithm running in time O⋆ (42m) solving util-β-SCE for f = 2 and all studied β.

Proof. Let us define a Boolean function F(A, j, s, G), which returns true if among candidates A, there is a series achieving quality at least s and consisting of j committees, each of size 2 such that in the j-th committee candidates from G ⊆ A appear for the first time in the series; F returns false otherwise. Our algorithm computes the values of F and returns true, if at least one of F(C, τ, η,G′ ), for G′ ⊆ C, |G′ | ≤ k is true.

We compute the values of F applying the DP approach to the following recursive formula. Denoting by W(A,G, k) a collection of all size-k sets W such that G ⊆ W ⊆ A we get:

The correctness of the formula follows from the equation. Recall that to compute the left hand side value, we need to check whether it is possible to obtain exactly j 2-consecutive committees yielding quality s such that candidates from G appear in the j-th committee for the first time. To do so, in the formula, we consider each possible committee W containing G as a subset and scoring sc(W). For each such W, we check whether there is a series of j - 1 consecutive committees of the requested size that jointly get quality s - sc(W) consisting of candidates in A \ G. The last conditions follows from the fact that candidates in G must be used for the first time only in W in question. Furthermore, we assure that the j -1th committee contains the candidates that appear in W for the second time, as these have to take part in the committees consecutively; hence the last argument W \ G of F 's evaluation on the right-hand side. To conclude the proof, we define F(A, 0, s,G) = true for s ≤ 0 and false for s > 0. We let the value of the function be false each time W(A, G, k) = ∅.

There are at most τ2mpoly(n,m) values of F to compute, where the polynomial term comes form the maximum score of our committee scoring functions. It takes at most 2m to compute a single value. Hence, as a result we obtain the claimed running time of O⋆ (42m).

The above approach readily generalizes to arbitrary values of f by defining F to take arguments G1 up to Gf-1 instead of just G. Increasing the parameter space, leads to the exponential in f increase of the running time.

Theorem 4 (⋆). There is an FPT(m)-algorithm running in time O⋆ (4fm) that solves util-β-SCE for all studied β.

In the remainder of this section, we present Theorem 5 covering the claimed fixed-parameter tractability for m for utilβ-SCE. There is a clear theoretical advantage of this next result over the one from Theorem 4, as the latter depends exponentially on both m and f. As we shall see, however, the running time of the algorithm from Theorem 5 may be (asymptotically) as large as mm. Such a running time would (asymptotically) be way larger than 4fm coming from Theorem 4 for small values of f. Hence, the algorithm from Theorem 4 (as well as the one from Theorem 1) might be more useful in practice. Especially since one of the motivations of studying candidate frequencies is to avoid excessive overload of committee members, which leads to small values of f [Bredereck et al., 2020]. Finally, the algorithm from the following Theorem 5, albeit interesting from the computational complexity classification perspective, would rather turn out too computationally intensive to be applicable in practice.

Theorem 5. There is an FPT(m)-algorithm which runs in time O⋆ (m!(k + 1)m) and solves α-β-SCE for α ∈ {util, egal} and all studied β.

Proof. Throughout the whole proof we let k be the size of committees in a requested f-consecutive committee series of size τ. Our algorithm computes the sought committee series by repeatedly running a dynamic programming (DP) procedure over a collection of guesses, each of which represents a subspace of the solution space. The proof comes in three parts. We first discuss the guesses, then the DP procedure, and finally we show how to effectively enumerate the guesses.

Guesses. Our algorithm repeatedly guesses a specific structure over candidates C, which we call a division, and which describes a space of possible f -frequency committee series of size τ . Before we describe divisions, let us first consider some order of candidates represented by a bijection ρ: [m] → C; e.g., ρ(2) = c′ means that candidate c′ ∈ C is ordered second. A subset X of candidates is an interval (according to ρ) if the set {i : ρ(i) ∈ X} is an interval; intuitively, the candidates from X form an interval according to ρ. If X is an interval, then we denote by beg(X) the position in ρ of the leftmost candidate of X.

Definition 1. A division D of size d is a 3-tuple (ρ, S, F) with order ρ of candidates, an ordered set S = {S1, S2, . . . Sd} of size-k committees called primitives, a collection F = {F1, F2, . . . , Fd} of interim candidate sets such that jointly:

a) Si is an interval according to ρ for each i ∈ [d],

Together with the following intuitive description of the above definition, we provide an example division in Figure 1. Let us fix some order ρ. Then, the definition says that the primitives in S are d pairwise different interval size-k committees ordered increasingly by their interval beginning according to ρ. Further, the interim candidate sets are pairwise disjoint and consist of candidates that do not belong to any primitive committee. Interim candidate set Fd is always empty, and each interim candidate set Fi, i ∈ [d - 1] can be non-empty only if Y = Si ∩ Si+1 is non-empty; but if Fi is non-empty, then it contains k - |Y | elements.

A division is intended to encode a (sub)space of feasible solutions that can be used for an efficient search for a solution to our problem. So, it is crucial that at least one division describes a space containing the solution, if the latter exists.

Lemma 1 (⋆). For each instance of α-β-SCE, there is a division D whose space contains a committee series maximizing α(β(W)) for the given values of f, τ , and k.

The proof of the above lemma is constructive, but it does not offer an efficient way of finding an optimal solution. Before showing such a way, we present an intuition of how the elements of the space of some division D look like. To ease the presentation, we assume the identity order ρ(i) = ci for i ∈ [m], and lay out some elements of the space in Figure 2.

First, observe that some consecutive f-frequency committee of size τ can be constructed as follows. We assign each primitive Si ∈ S the respective number ri of copies of this primitive ensuring that the sum of ri's is exactly τ. Assuming that our ri's do not violate the frequency limit f, we get a committee series W of size τ by repeating, in order, each primitive Si exactly ri times. Clearly, W is consecutive due to the interval requirements on the primitives in S. There are, however, more committee series similar to W in the space of D. They use the so-far ignored interim candidate sets F. For an example, consider the following case. Assume that W contains a sequence Si, Si, Si+1 of neighboring committees and that Y = Si ∩Si+1 is non-empty. If Fi ̸= ∅, then we can substitute the "middle" Si, with a committee S′ = Y ∪ Fi, thus obtaining a new committee series W′ containing a sequence Si, S′ , Si+1. Note that W′ remains f-consecutive because by definition |Fi| = k - |Y | and Fi ∩ Y = ∅.

The whole space of D consists of the committee series emerging from all valid choices of the multiplicities ri and from all valid substitutions (perhaps multiple at once) analogous to the construction of W′ .

Finding a Solution. Assume some division D = (ρ, S,F), where S = (S1, S2, . . . , Sd) and F = (F1, F2, . . . , Fd). We show a dynamic programming algorithm (DP) running in the claimed FPT-time that tests whether the space of D contains a sought committee. We define a Boolean function T(t, i, q, u, j, r, p), for q > 0, r > 0, which is true if and only if there is an f-consecutive series X such that:

1. X contains t committees (of size k),
2. primitive Si ∈ S is repeated exactly q times in X,
3. if Fi ̸= ∅, committee S′ = Fi ∪ (Si ∩ Si+1), called i-intermediate, is repeated u times in X between the copies of Si and Si+1,
4. in which candidate ρ(j) ∈ Si is part of exactly r consecutive committees of X, and
5. α(β(X)) ≥ p.

Assuming that ρ(j ′ ) is the last candidate in Sd according to ρ, there exists a sough f-consecutive series of size τ achieving a committee series quality η if there is a pair (q′ , r′ ) ∈ [f]×[f] for which T (τ, d, q′ , 0, j ′ , r′ , η) outputs true.

We recursively compute the values T(t, i, q, u, j, r, p) in the order of increasing values of t, i, j, and p; the variables are mentioned in the order of increasing frequency of change during computation iterations. Because the candidates are ordered with respect to ρ, it is convenient to think of combinations of values i and j as cells in a grid, where j is the column number representing candidate ρ(j) and i is the row number representing primitive Si ∈ S. In the grid, primitive Si forms an interval in the i-th row; this interval corresponds to the candidates in Si. As depicted in Figure 3, by convention, we place point (1, 1), corresponding to candidate ρ(1) in primitive S1, in the upper left corner of the corresponding grid.

Some values of T (t, i, q, u, j, r, η) are invalid by definition or in an obvious manner. This is the case for:

• (I1) each i and j ∈ [m] for which ρ(j) /∈ Ci; see dark shaded cells in Figure 3,
• (I2) cases in which q + t > τ , q + u > f , or r > f ,
• (I3) positive values u for i for which Fi = ∅; in particular, by definition of D, this holds when Si ∩ Si+1 ̸= ∅.

For readability, we never explicitly test for these invalid cases assuming, for technical reasons, that T returns false for them.

For the sake of presentation, for each primitive Si ∈ S, we define the head and the tail of Si as, respectively, the first and the last candidate of Si with respect to order ρ (as demonstrated in Figure 3). Formally, head(Si) = j ′ and tail(Si) = j ′′ if for each j ∈ [m] such that ρ(j) ∈ Si, j ′ ≤ j and j ≤ j ′′ . If a candidate is neither the tail nor the head of some primitive Si ∈ S, then it is intermediate in this primitive. Note that a candidate might be the head of one primitive but an intermediate candidate for another primitive.

In what follows, we frequently consider a situation in which we seek a committee series of quality at least p by repeating a primitive Si ∈ S exactly q times and the committee (Si ∩ Si+1) ∪ Fi exactly u times. In such cases, we use rq(i, p, q, u) := p-qβ(Si)-uβ((Si∩Si+1)∪Fi) that describes the required quality of a to-be-constructed committee series prior to using the q + u committees mentioned above. This is where the subtraction in the expression comes from. Our formulas use u = 0 whenever (Si ∩ Si+1) ∪ Fi is not a committee of the requested size (when either Fi = ∅ or Si ∩ Si+1 = ∅). Consequently, the related term vanishes.

We continue with presenting a recursive formula for T, which we split into multiple cases for readability. Values of the base cases T (t, 1, q, u, j, r, p) follow directly from the definition of T .

We first focus on such cases T(t, i, q, u, j, r, p) in which head(Si) = j and Si-1 ∩ Si = ∅. We skip computation at all and return false if q ̸= r. Indeed, q = r is required as all candidates in Si will appear for the first time in the constructed committee series.

In words, the formula's alternative tests whether we can achieve sufficient committee quality rq(i, p, q, u), before we repeat primitive Si exactly q times and committee Si ∩Si+1∪ Fi exactly u times. Since Si-1 ∩ Si = ∅ implies that Fi-1 = ∅, in the alternative we invoke T with the respective parameter equal to 0. Recall that expression rq(·) remains correct even if Fi = ∅, which by Case (I3) implies u = 0.

Next, we consider head(Si) = j under assumption that Si-1 ∩ Si ̸= ∅. Consequently, q < r, as the j-th candidate belongs to Si-1 ∩ Si, and Si-1 has to be repeated at least once (see the domain of T). So, if q ≥ r we return false and otherwise we compute T as follows:

This time, we ensure that before using primitive Si and interim candidates Fi, we used the j-th candidate exactly r-q times. We do not subtract u, as by the fact that primitives are different, j-th candidate cannot be part of (Si∩Si+1)∪Fi, which is repeated u times. Accordingly, the alternative iterates over all possible values of q′ and u′ to check if there is any committee series using primitives up to Si-1 of the required quality (see the discussion in the previous case).

We continue with computing T (t, i, q, u, j, r, p) for cases, in which the j-th candidate is either an intermediate or a tail candidate. Consequently, the j-th candidate (from the respective primitive Si ∈ S) can be part of ℓ-intermediate committees for ℓ ≥ i, i.e., that come after all copies of Si in the built committee series W. Previously, when the j-th candidate was a head candidate, it could only be part of the ℓ-intermediate committees for ℓ < i. For this reason, the following formulas sometimes impose additional conditions.

We start with a simple case. Let the j-th candidate c = ρ(j) be the intermediate or tail of primitive Si. Assume that c /∈ (Si ∩Si+1).

The number repetitions of Si and the score p is always fixed during the computation for Si's head candidate. So in this case the alternative recursively mostly "carries on" function values from previous candidates of Si. We iterate using r′ because the j - 1-th candidate could be part of more (previous) committees than candidate c. Due to our interval requirements and sorting of Si ∈ S, we know that r′ ≥ r.

Next, consider computing T (t, i, q, u, j, r, p) assuming that the j-th candidate c = ρ(j) is an intermediate or tail candidate, c ∈ Si ∩ Si+1, and c /∈ Si-1. We repeat c exactly q + u times as a member of q copies of Si and of u copies of i-intermediate committee. Hence, we immediately return false if r ̸= q + u, and otherwise we have

The lower-bound of iterator r′ follows from the fact that the j - 1-th candidate must be repeated at least as many times as the primitive Si to which the candidate belongs is repeated.

In the final case we consider the, intermediate or tail, j-th candidate c = ρ(j) such that c ∈ Si ∩ Si+1, and c ∈ Si-1.

Since c is used in copies of primitive Si-1, we return false if q + u ≤ r. Otherwise, we compute T as follows:

On top on all conditions of the counterpart case with c /∈ Si-1 described directly above this case, we add further requirements. Observe that here c is used q+u times but it was also previously used. The second alternative of the formula ensures that these q +u uses of candidate c would not make c exceed the frequency f.

The case distinctions is exhaustive so the correctness of the formula stems directly from its description. To compute each value of function T , we need at most O(f 2 ) steps. Further, for some division D of size d, we need to compute d · kτf 3 · poly(n,m) values of T, as there is dk valid pairs of parameters i and j, t ∈ [τ], (q, u, r) ∈ [f]3 . Hence, we obtain a polynomial running-time for each division.

ConstructingGuesses andRunning Time. We run the DP procedure for each possible division D = (ρ, S, F). We first select some order ρ of candidates out of m! of them. Then, we guess the division size d. Note that S = (S1, S2, . . . , Sd) can be represented as a vector (s1, s2, . . . , sd), where si, i ∈ [d], denotes the rightmost candidate of the interval of committee Si given ordering ρ. Hence, the guessed division size d varies from one to at most m, where the upper bound is not tight and describes the maximum number of distinct equisized interval committees coming from taking d = m - k and si = k + i, for i ∈ [d]. Importantly, τ does not contribute to the number of possible values of d, as it is only the DP procedure that achieves τ committees for some D. Next, we guess each entry of the S vector, except for the first one which is fixed. To this end, we choose the value of each si, i ∈ {2, 3, . . . , d}, from range {si-1 + 1, si-1 + 2, . . . , si-1 + k + 1} (recall that all primitives in S have to form an interval according ρ). Finally, for each non-empty intersection X of neighboring primitives, of which there are at most d, we either select an empty interim set or take next unused k - |X| candidates according to ρ (as long as the latter is possible). This totals in at most m!·m·(k+1)m ·2m guesses. Overall, the algorithm is clearly fixed-parameter tractable with respect to m.

The approach behind Theorem 5 in fact works for any quality measures of committee series quality and committee scoring function as long as their values are polynomially bounded by the input size. This leads to a general result covering much more scoring functions than those described in Section 2.

Corollary 1. There is an FPT(m)-algorithm with running time O⋆ (m!(k - 1)m) solving α-β-SCE for arbitrary computable aggregation α and a committee scoring function β whose values are polynomially bounded in the instance size.

4 The Case of Short Time Horizon

The algorithms from the previous section are no longer of use for large pools of candidates. In such cases, approaches tailored to small values of parameter τ, which is a formal framing of short time horizon in our model, might come to the rescue. Imagine, for example, an online streaming platform building daily music recommendation for the following week, based on a user's past-week activity. While such a task might likely include even hundreds of songs, it is still only seven lists (committees) that we want to arrange in a series.

In most cases that we study, however, our expectations cannot be stretched as far as obtaining FPT-algorithms for parameter τ. The Chamberlin-Courant rule, in its variants for approval as well as ordinal preferences, is W[2]- hard for parameter "committee size" already in the multiwinner voting model [Lu and Boutilier, 2011; Betzler et al., 2013]. Because these results are special cases of αβ-SCE for both committee series quality variants and β ∈ {CC, trCCγ , eCC,AppCC} for τ = 1, there is no hope for fixed-parameter tractability for parameter k + τ in this case.

Consequently, we focus on FPT-algorithms with respect to τ assuming a constant committee size. On the one hand, such results are a clear advancement from the theoretical perspective given that util-β-SCE and egal-β-SCE both are NP-hard even for the constant committee size for almost every committee scoring β that we study [Bredereck et al., 2020] (the exceptions are util-FWS-SCE and util-AppSCE). On the other hand, constant values of k are still interesting from the practical point of view as small committee sizes might appear in practice. For example, in our toy example about daily music recommendation, providing too many songs each day would be overwhelming for the user and ineffective in promoting featured tracks.

Our first algorithm reinterprets util-β-SCE with f = 1 as an instance of WEIGHTED SET PACKING and then applies a known procedure of Goyal et al. [2015] for solving the latter.

Theorem 6 (⋆). There exists an algorithm that solves utilβ-SCE in O⋆ (2.851(k-0.5501)τ ) time for all studied β when the committee size k is constant and f = 1.

Next, we prove the result for constant f ≥ 2. Without loss of generality, we assume that τ > f. Otherwise, we find a committee of maximum score in polynomial time and repeat it f times. Since k is a constant, computing a maximum score committee is polynomial-time solvable for every committee scoring β that we study.

Theorem 7 (⋆). There exists an algorithm that solves utilβ-SCE in O⋆ (2kτ(f+1) (2e)kτ (kτ)log(kτ) ) time for all studied β when the committee size k and f are constant.

The proof of Theorem 7 heavily depends on the following randomized algorithm.

Theorem 8 (⋆). There exists a randomized algorithm that given an instance of util-β-SCE for all studied β either reports failure or outputs a solution in O⋆ (2kτ(f+1) (2e)kτ ) time. Moreover, if the algorithm is given a yes-instance, it returns yes with probability at least 1/2, and if the algorithm is given a no-instance, it returns no with probability 1.

Proof sketch. A solution S = (S1, . . . , Sτ ) is called colorful if every pair of candidates s, s′ in ⊎i∈[τ]Si has distinct colors. Now, our algorithm runs in three phases. In the first phase, we uniformly and independently at random color the candidates forming our solution. Then, we discard the sets that cannot be part of our solution under the coloring. In the third phase, we use dynamic programming to turn the coloring into a colorful solution, if the coloring admits one.

We obtain Theorem 7 by derandomizing the algorithm of Theorem 8. To this end we employ a (p, q)-perfect hash family [Alon et al., 1995] that we construct in the requested time applying the results of Naor et al. [1995] and Cygan et al. [2015].

We provide more good news, by presenting an analogous result for the egalitarian committee series evaluation. By this, we cover all of our cases of interest (for constant k).

Theorem 9 (⋆). There exists an algorithm that solves egalβ-SCE in O⋆ (2.851(k-0.5501)τ ) time for all studied β when the committee size k is constant.

5 Conclusions and Future Directions

We have provided first algorithms for solving hard instances emerging from the model of successive committee elections [Bredereck et al., 2020]. Extending the algorithmic understanding of a recent area of temporal elections, our results concern potentially practical scenarios including small numbers of candidates and a short time horizon. In the light of increasing resonance of experiments in computational social choice [Boehmer et al., 2024], our algorithms potentially enable experimental study on successive committee elections.

Theoretical follow-up directions include complementing our picture with parameterizations by "number n of voters" and "committee series quality η." While both these parameters might turn out to be quite large in practical applications, obtaining the respective results would complete the picture of the parameterized complexity of the studied problems. We note that parameter η in part inherits technical intricacies of the study of the parametrization by (mis)representation for Chamberlin-Courant rules [Betzler et al., 2013; Chen and Roy, 2022]. Importantly, Bredereck et al. [2020, Theorem 5] implicitly excludes fixed-parameter tractability of η for egaltrCC1 (W)-SCE, while our results yield it for util-CC-SCE and util-AppCC-SCE for η.

On the more practical side, our algorithms require an empirical treatment to verify its potential applicability in practice. As our study only gives pessimistic running-time upper bounds, a thorough investigation based on synthetic and reallife instances is needed to check the algorithms behavior on more realistic input instances.

Acknowledgements

We thank anonymous reviewers for their helpful comments. Pallavi Jain acknowledges her support from SERB-SUPRA (grant number SPR/2021/000860) and IITJ Seed Grant (grant no I/SEED/PJ/20210119). Andrzej Kaczmarczyk acknowledges support from NSF CCF-2303372 and ONR N0001423-1-2802. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 101002854).