# electing_successive_committees_complexity_and_algorithms__eee9e2a6.pdf The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20) Electing Successive Committees: Complexity and Algorithms Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier Technische Universit at Berlin, Chair of Algorithmics and Computational Complexity {robert.bredereck, a.kaczmarczyk, rolf.niedermeier}@tu-berlin.de We introduce successive committees elections. The point is that our new model additionally takes into account that committee members shall have a short term of office possibly over a consecutive time period (e.g., to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e.g., for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a best possible series of committees representing the electorate. We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases. Introduction The study of committee elections, that is, to elect a group of representatives for a group of voters, gained strong interest over the recent years (Faliszewski et al. 2017). In this work, we consider the election of committees whose members have short term of office (possibly in consecutive time slots). This is motivated by, for example, avoiding the overloading of committee members or excluding the danger of elitist power cartels. Modeling this, we arrive at the following, to the best of our knowledge new model for multiwinner voting: The input is a set of preferences over candidates (the votes) and a natural number specifying how many committees, each of same fixed size, should be built. The goal is to output a corresponding series of same-size committees such that, altogether, we get a best possible selection. To this end, we introduce committee evaluation functions (based on multiwinner voting rules) together with egalitarian and utilitarian aggregation functions, thus yielding an overall evaluation of the quality of a series of committees. Moreover, we allow to model constraints such as a committee member having to serve in a subseries of consecutive committees and allowing only a limited number of committee participations Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. language skills A B C D E F Mandarin Spanish French Arabic Hindi Table 1: The company s available data on individual employees qualifications. Symbol denotes approval. per member. Notably, our setting is still an offline, not an online scenario. Our model can be applied when a selection of a best series of same-sized groups (committees) of candidates is needed. For illustration, consider the following simple example. Imagine we are operating a big company providing a complex service system to customers. More specifically, at the beginning of every month the task is to build and schedule weekly size-two service teams throughout the month. The company follows a travel policy aimed at keeping a necessary trade-off between their employees travel friction and its business outcomes (see a field study on road warriors (Airlines Reporting Corporation 2018) describing the importance of such policies). Thus, each employee can be on external service (including traveling and hotel stays) for at most two weeks per month. For the same reason, the company favors consecutive service periods for every employee. Moreover, for each employee there is data (provided both by the customers and by the internal files of the company) that, in the simplest form, approves or disapproves each employee for certain qualifications (e.g., language skills). At first glance, it seems beneficial to select the highest scoring employees according to the data to form the service teams. However, if these employees hold very similar qualifications (i.e., are supported by a relatively coherent set of the voters ), then this simple greedy strategy fails to provide a good selection of (matched-up) service teams. In particular, it may suffer from lack of diversity. Such a situation is exhibited in Example 1. For clarity, the example features a very small election where an optimal outcome can be found by checking all possible solutions. However, this approach starts to be computationally infeasible for only little bigger instances (e.g. selecting ten committees of size three out of ten candidates), which are likely to happen in real world. Example 1. Suppose that we consider seven potential service employees A, B, . . . , F for four service weeks. According to Table 1, the four most qualified employees are A, B, C, and D. They all have at least two language skills. Thus, a greedy solution based on individual qualifications may select {A, C} for the first two weeks and {B, D} for the last two weeks. However, a (more diverse) group of employees that will gather the largest collective set of qualifications is A, B, E, and F. Selecting {A, E} for the first two weeks and {B, F} for the last two weeks allows to cover three instead of two distinct qualifications per week (and covers all qualifications over the whole month). The phenomenon described in Example 1 shows that one has to be very careful when selecting successive committees in our example these size-two committees consist of the selected employees. Compared with our forthcoming concept of electing successive committees, classic multiwinner elections are too limited to fully capture the above indicated setting. They could easily be used to distinguish between {A, B, C, D} and {A, B, E, F} but not to distinguish between {A, B}, {E, F} and {A, E}, {B, F}. Summarizing, classic multiwinner elections are not suitable to model tasks as described in our service science example. These include issues like how to choose employees and arrange them in weekly teams, how to arrange teams such that each employee is on external service for at most two consecutive weeks, and how to make sure that the customer satisfaction is maximized. All this leads us to our new mathematical model (referred to as electing successive committees), which can be interpreted as an extension of multiwinner elections. Our model is capable of capturing series of same-sized committees with additional requirements on the number of committees candidates can be part of, indeed going significantly beyond the questions described in the example. Our model is quite flexible also in terms of used voting rules and in terms of defining the value (or quality) of a committee series (we study both utilitarian and egalitarian evaluation); however, this needs some mathematical machinery and that is why we defer the formal problem definitions and statements of results to the next section. Now, we provide a high-level overview of our contributions. Our Contributions. To the best of our knowledge, our serial view on committees selected in multiwinner elections is new. Our mathematical model, which is parameterized by various committee evaluation functions (e.g., approval, coverage, Chamberlin-Courant variants, and weakly separable functions), and two committee quality evaluations (egalitarian versus utilitarian), turns out to be structurally very rich. Concerning the corresponding computational complexity of determining the each time best possible series of committees, we experience sharp borders between polynomialtime solvability and NP-hardness. Very roughly, our central message here is that size-two committees (recall the service teams example) allow for their efficient computation whereas size three or more leads to NP-hardness with, however, notable tractable exceptions in the utilitarian setting (which generally seems easier to handle). Many of our proofs rely on intimate and subtle relations to matching problems in algorithmic (hyper)graph theory. Refer to Table 2 for a fairly comprehensive overview on the complexity landscape. Modeling successive committees elections, we believe having added a new and well-motivated dimension to studying multiwinner elections. For instance, as a sideeffect we provide new variants of prominent voting rules emerging from our modeling. Related work. In the spirit of adding new dimensions to classic multiwinner voting, our work is somewhat related to the current study of other dimensions such as robustness recently considered by Bredereck et al. (2017) and Misra and Sonar (2019); diversity recently considered by Bredereck et al. (2018), Celis, Huang, and Vishnoi (2018), and Lang and Skowron (2018) (see therein for more literature on diversity); or participatory budgeting recently considered by Fluschnik et al. (2019) and Talmon and Faliszewski (2019) (see therein for a broader literature review on participatory budgeting). Specifically, let us mention two related directions in terms of modeling. First, Freeman, Zahedi, and Conitzer (2017) studied dynamic social choice where candidates are selected sequentially and repeatedly. This is an online scenario (ours is offline) and has quite different features; for instance, there, the agents/voters may change their candidate valuations at each time step, they do report utilities (not approvals or rankings), and, with the help of greedy algorithms, the aim is to maximize long-term Nash social welfare. Second, Aziz and Lee (2018) studied subcommittee voting in the context of approval voting; here a single committee consisting of subcommittees is selected. In their model, selected subcommittees are independent (in terms of candidates they are consisting of) of each other and there is no explicit time dimension and corresponding ordering of subcommittees. All missing (parts of) proofs are deferred to a full version of the paper. Basic Definitions and Problem For a positive integer x, we use [x] to denote set {1, 2, . . . , x}. An election E is a pair (C, V ) where C = {c1, c2, . . . , cm} is a set of candidates and V = {v1, v2, . . . , vn} is a collection of voters. In our work, we focus on the two perhaps most popular election models: the approval model and the ordinal model. In the former, each voter vi specifies a set A(i) C of approved candidates. In the latter, each voter vi gives a ranking (i.e., a strict order) i of candidates; the top candidate according to i is the candidate that is preferred the most by vi. For some voter vi and a candidate c, by posi(c), we denote the position of c in vi s ranking. Committees and Their Evaluation. A group of k candidates is called a committee of size k. A function mapping a committee to a nonnegative integer is called a committee evaluation function while its output for a particular committee is called a committee quality. Chamberlin-Courant (CC) egal. Chamberlin-Courant (e CC) weakly separable ( FWS) k = 2 k 3 k = 2 k 3 k = 2 k 3 util P, f 2 ( Thm. 2) NP-h ( Thm. 6) P, f 2 ( Thm. 2) NP-h ( Thm. 6) P ( Thm. 1) P ( Thm. 1) P, t = f x ( Cor. 2) P, t = f x ( Cor. 2) egal P ( Thm. 3, Cor. 3) NP-h ( Thm. 6) P ( Thm. 3, Cor. 3) NP-h ( Thm. 6) P ( Thm. 3, Cor. 3) NP-h ( Thm. 7) Approval (App) threshold Approval CC (tr CCα) Approval CC (App CC) k = 2 k 3 k = 2 k 3 k = 2 k 3 util P ( Thm. 2, Cor. 1) P ( Cor. 1) P ( Thm. 2, Cor. 2) NP-h ( Thm. 5) P, f 2 ( Thm. 2) NP-h ( Thm. 5) P, t = f x ( Cor. 2) egal P ( Thm. 3, Cor. 3) NP-h ( Thm. 7) P ( Thm. 3, Cor. 3) NP-h ( Thm. 5) P ( Thm. 3, Cor. 3) NP-h ( Thm. 5) Table 2: The summary of the results for the approval (top) and the ordinal (bottom) model of elections. If not stated differently, then the results hold for any frequency value (f) and for any size of a target time series (t). Evaluating committees in the ordinal model comes naturally with extending the committee scoring functions introduced by Elkind et al. (2017) and further studied by Aziz et al. (2018) focusing on egalitarian variants of committee scoring functions. Although several of our results are general enough to cover all computable committee scoring functions, we focus on the rules described in Definition 1 below. We picked a varied selection of rules; from rules that assign each candidate a number of points separately (weakly separable committee scoring rules) to more complicated ones that try to cover a concept of representing a set of voters by, intuitively, relating a value of a single candidate to the other candidates in a committee (variants of the Chamberlin-Courant misrepresentation measure (Chamberlin and Courant 1983; Betzler, Slinko, and Uhlmann 2013)). Definition 1. Consider election E = (C, V ) with candidates C = {c1, c2, . . . , cm}, voters V = {v1, v2, . . . , vn} with ordinal-based preferences, and a committee S = {w1, w2, . . . , wk} of size k. We consider the following committee evaluation functions: CC: Chamberlin-Courant (Borda scores): CC(S) = i [n] maxj [k](m posi(wj)), e CC: egalitarian Chamberlin-Courant (Borda scores): e CC(S) = mini [n] maxj [k](m posi(wj)), FWS: the family of weakly separable committee scoring functions: a committee evaluation function Q, is weakly separable if, for some function φ: [m] N0, Q(S) = j [k] φ(posi(wj)). In the approval model, we use adaptations of the Chamberlin-Courant rule to approval-based preferences (Procaccia, Rosenschein, and Zohar 2008; Betzler, Slinko, and Uhlmann 2013; Skowron, Faliszewski, and Lang 2016) and a basic sum of all approvals given to the candidates in the committee. Definition 2 below formally describes the committee evaluation functions we use in the approval model. Definition 2. Consider election E = (C, V ) with C = {c1, c2, . . . , cm}, voters V = {v1, v2, . . . , vn} with approval-based preferences, and a committee S = {w1, w2, . . . , wk} of size k. We consider the following committee evaluation functions: App: Approval voting: App(S) = i [n] |A(i) S|, tr CCα: threshold-α Chamberlin-Courant, α (0, 1]: tr CCα(S) = 1 if |{i [n]|A(i) S = }| αn, 0 otherwise. App CC: (approval score) Chamberlin-Courant/Max Cover: App CC(S) = |{i [n] | A(i) S = }|. Committee Series and Their Quality. Let C = {c1, c2, . . . , cm}. A committee series SC of size t is a sizet vector of same-size committees consisting of candidates from C; we usually omit a subscript if a set of candidates is clear from the context. Consider some committee series S = (S1, S2, . . . , St) of size t. For each candidate c C, we define a participation set P(c) = {i | c Si}. We call S an f-frequency committee series if each candidate participates in at most f committees, that is, for all c C it holds that | P(c)| f. If additionally in an f-frequency committee series each candidate participates in consecutive committees only, then the series is a consecutive f-frequency committee series. Formally, an f-frequency committee series S is consecutive if for each candidate c C such that P(c) = it holds that maxj P(c) j minj P(c) j+1 = | P(c)|. For some committee evaluation function Q, let U = (u1, u2, . . . , ut) be a size-t vector such that ui = Q(Si), that is, U is a vector of quality values of all committees in S. We define two variants of committee series quality: utilitarian: util(U) = i [t] ui and egalitarian: egal(U) = mini [t] ui. To simplify our notation, in a natural way we extend committee evaluation functions to operate on vectors of committees. Thus, applying a committee evaluation function Q to a committee series S = (S1, S2, . . . , St), we obtain a vector Q(S) = (Q(S1), Q(S2), . . . , Q(St)) of quality values of the committees in S. Problem Definition. Our central problem reads as follows. X-Y -SUCCESSIVE COMMITTEES ELECTION (X-Y -SCE) X {util, egal}, Y {App, tr CC, e CC, CC, App CC} FWS Input: Election E = (C, V ) with candidates C and voters V , a number t 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 p. Question: Is there a consecutive f-frequency committee series S of size t consisting of size-k committees such that X(Y (S)) p? Example 2. Consider an election E with six candidates c1 to c6 and three voters v1, v2, and v3 with the following preferences: v1 : c1 c2 c3 c4 c5 c6, v2 : c1 c6 c3 c4 c5 c2, v3 : c6 c5 c4 c3 c2 c1. Suppose that we seek a 2-frequency committee series of size t = 4 consisting of committees of size k = 2. For the egalitarian variant of committee series quality and the Borda-CC committee scoring rule, it turns out that S = ({c1, c5}, {c1, c5}, {c2, c6}, {c2, c6}) has quality 13. To obtain this score, observe that CC({c1, c5}) = 14 and CC({c2, c6}) = 13. Thus, egal(CC(S )) = min(13, 14) = 13. The quality of the utilitarian variant with Borda-CC is obtained by summing the values of all committees which gives util(CC(S )) = 13 2 + 14 2 = 54. Observe that a sequential greedy selection of the bestscoring committees gives a worse result. It can be easily verified that this strategy leads to a committee series S = ({c1, c6}, {c1, c6}, {c3, c5}, {c3, c5}) that is worse than S with respect to both the utilitarian and egalitarian aggregation for Borda-CC: util(CC(S )) = 50 and egal(CC(S )) = 10. Basic Observations In this section, we present several helpful structural observations which may also be of independent interest. They will later help to significantly ease our proofs. First, we observe a simple lower bound on the number of pairwise disjoint committees in every consecutive ffrequency committee series. Observation 1. A consecutive f-frequency committee series of size t contains at least t f pairwise disjoint committees. A minor, yet useful, consequence resulting from Observation 1 is that, for committee size k, we can assume without loss of generality that there are always at least k t f candidates. In fact, for every possible committee evaluation function Y , egal-Y -SCE with an arbitrary candidate frequency boils down to a very similar instance of egal-Y -SCE with candidate frequency being one. This leads to the following. Lemma 1. egal-Y -SCE with f 2 can be many-one reduced to egal-Y -SCE with f = 1 in linear time. It is tempting to try to transfer Lemma 1 to the utilitarian variant. However, Example 3 below shows that in general, the fact, which is essential to prove Lemma 1, that if there exists a solution, then there is a solution that consists of the fewest possible different committees does not hold anymore. Indeed, Example 3 shows that we cannot have an analogue of Lemma 1 for utilitarian aggregation. Example 3. Consider an election with four candidates c1, c2, c3, c4 and the following six voters: 1 voter: c1 c2 c3 c4, (1) 3 voters: c2 c4 c1 c3, (2) 2 voters: c4 c2 c1 c3. (3) How does an optimal 3-frequency committee series of size four look if we consider the utilitarian committee series evaluation with committee scoring function CC ? By inspecting all possible combinations, it turns out that a quality-maximizing committee series ({c1, c4}, {c2, c4}, {c2, c4}, {c2, c3}) achieves quality 15 + 2 17 + 15 = 64. Additionally, there is no 3-frequency committee series of size four consisting only of two disjoint committees (possibly used several times consecutively) that reaches the optimal quality 64. For instance, committee series ({c2, c4}, {c2, c4}, {c2, c4}, {c1, c3}), which looks promising at first glance, achieves only quality 3 17 + 8 = 59. Example 3 shows that, unlike in the egalitarian variant, candidate frequencies indeed have an influence on the structure of the solutions in case of utilitarian aggregation. More precisely, with f > 1 non-trivially intersecting committees may be needed. The following lemma, however, shows that to some extent even with utilitarian aggregation, we may restrict ourselves to committee series that consist of blocks of disjoint committees. Lemma 2. When t = f x for some integer x, then util Y -SCE with f > 1 can be many-one reduced in polynomial time to util-Y -SCE with f = 1. Moreover, utiltr CCα-SCE with f > 1 can be many-one reduced in polynomial time to util-tr CCα-SCE with f = 1. For weakly separable scoring functions and utilitarian aggregation we further exploit Observation 1 as follows. Observation 2. Consider a set C of candidates, a committee size k, a candidate frequency f, a number t of committees and a committee evaluation function Y FWS. Then, there exists an f-frequency committee series S of size t that maximizes util(Y (S)) and consists of exactly t f pairwise disjoint committees. The next lemma allows us to simplify the analysis of the threshold-α Chamberlin-Courant committee evaluation function. It reveals a relation between tr CC1 and tr CCα for parameter α (0, 1) in form of a polynomial-time manyone reduction from the former to the latter (assuming that the candidate frequency is one). Lemma 3. For X {util, egal} and candidate frequency f = 1, there exists a polynomial-time many-one reduction from X-tr CC1-SCE to X-tr CCα-SCE for any rational α (0, 1). General Tractability Results We start with weakly separable scoring functions for which we obtain the most general, polynomial-time solvability results. Recall that for this family of rules we obtained the strongest structural properties in the previous section. Indeed, Observation 2 reveals a way to design a polynomialtime algorithm to find a quality-maximizing committee series for util-Y -SCE where Y is a weakly separable committee scoring function. The algorithm greedily picks bestscoring candidates to build t f committees maximizing the overall quality. Hence, util-Y -SCE for Y FWS and arbitrary committee sizes can be solved in quasilinear time (we essentially need to sort the candidates). Theorem 1. For Y FWS computable in time y, util-Y -SUCCESSIVE COMMITTEES ELECTION is solvable in O(ymn + m log m) time. Theorem 1 holds due to the so-called separability property of weakly separable scoring rules, that is, the fact that one can compute scores for every candidate independently. In the approval evaluation function the score of each candidate can also be computed separately. As a result, we obtain a quasilinear algorithm for util-App-SCE. Corollary 1. util-App-SUCCESSIVE COMMITTEES ELECTION is solvable in O(mn + m log m) time. Many prominent multiwinner voting rules based on ordinal preferences, like for example the k-Approval, Bloc or Borda rules, are weakly separable, and thus, the respective committee evaluation functions are covered by Theorem 1. However, weak separability fails, for example, for the Chamberlin-Courant rule that is considered to be suitable for finding a diverse committee (Faliszewski et al. 2019). Hence, there is a need for another effective way of solving util-Y -SCE for non weakly separable committee evaluation functions. We address this need in the next two sections. Committees of Size Two We devote this section to the computational complexity of X-Y -SCE (for non weakly separable scoring rules) for committee size k = 2, that is, finding a good sequence of candidate pairs. We will see that for almost all cases this task remains tractable; only Chamberlin-Courant-based evaluation functions (except for threshold Approval CC) for candidate frequency f > 2 remain open. However, for these cases we give a polynomial-time 1 2-approximation algorithm. The subsequent theorem shows that there exists a polynomial-time algorithm for arbitrary scoring functions in case of utilitarian aggregation and committee size k = 2. This generalization, however, comes at a cost of lowered efficiency and applicability when compared to Theorem 1. The solution presented in Theorem 2 is slower and does not allow for candidate frequencies greater than two. At high-level, our approach is based on a reduction of the considered election problem to the graph problem (ℓ, h)- SUBGRAPH (Gabow 2018). Theorem 2. Let Y be a committee evaluation function computable in time y. Then, util-Y -SUCCESSIVE COMMITTEES ELECTION with m candidates, f 2, and k = 2 is solvable in O(m3 + ym2) time. Proof for f = 1. We reduce util-Y -SCE to (ℓ, h)- SUBGRAPH. Given an undirected multigraph G = (V, E) (an edge may have multiple copies) with the number n of vertices and the number m of edges; two functions ℓ, h: V N {0}; a weight function w: E R; and an integer q, (ℓ, h)-SUBGRAPH asks whether there exists a multiset H E of edges whose total weight is at least q, forming a subgraph GH such that for each v GH the degree of v is between ℓ(v) and h(v). Gabow (2018) showed that the problem can be solved in O(h(V )(m + n log n )) time where h(V ) is the sum of all upper bounds. The high-level idea of our proof is to construct a graph where each candidate is associated with a vertex and each feasible committee of size two is an edge with the weight equal to the committee s quality. Suppose we have an instance of util-Y -SCE with an election E = (C, V ), candidate frequency f = 1, committee size k = 2, size t of a committee series, and a quality lower bound p. To create an instance of (ℓ, h)-SUBGRAPH, we first construct a complete graph over a set of vertices V = C {v}. Then, for each pair of two distinct candidates c, c we set the weight of the corresponding edge e = {c, c } to Y (e). For each candidate c, we let the weight of edge {v, c} be zero. Next, for every vertex c C, we set its lower and upper bound to one. We set the lower bound and the upper bound of v to |C| 2t. Finally, we look for a subgraph of minimum weight of q = p. To prove the correctness of the reduction, let us start with some committee series S = (S1, S2, . . . , St) that is a solution to the original util-Y -SCE instance. Because f = 1, we construct a set H by taking t edges representing committees in S and |C| 2t 0 edges adjacent to vertex v and candidates that take part in no committee from S. A subgraph GH formed by H is a correct (ℓ, h)-subgraph of weight at least p. Observe that set H consists of exactly |C| t edges. There are exactly |C| 2t edges adjacent to vertex v in GH, so the degree of v is exactly ℓ(v) = h(v). Also, there are exactly 2t vertices that are not adjacent to v in GH. Since these vertices are adjacent to t edges, the degree of each of these vertices in GH is exactly one, as it is required. Since all edges have nonnegative weights and the edges representing committees in S altogether have weight at least p, then graph GH s weight is also at least p. The reverse direction can be shown analogously. In every feasible set H there is a subset H of exactly t edges that are not incident to v. We construct a committee series S by choosing committees (in an arbitrary order) represented by the edges in H . Since the weights of edges in H are directly reflecting the qualities of the corresponding committees in S and the total weight of edges in H \ H is zero, it follows that util(Y (S)) p. The running time of (ℓ, h)-SUBGRAPH, for our particular case, is O(m(m2 + m log m)) = O(m3). The presented reduction works in O(ym2) time. Combining the running times of the reduction and of solving an emerging (ℓ, h)-SUBGRAPH instance gives the desired running time of O(m3 + ym2). Using Lemma 2 and Lemma 3 we obtain the following. Corollary 2. For Y {App CC, e CC, CC} util-Y - SUCCESSIVE COMMITTEES ELECTION is solvable in polynomial time when t = f x for some nonnegative integer x and util-tr CCα-SUCCESSIVE COMMITTEES ELECTION is solvable in polynomial time for any f and any α. For the egalitarian variant of successive committees elections we show a significantly more general result that does not constrain the candidate frequency. The first step is to apply an approach similar to the one used in Theorem 2, again for candidate frequency f = 1. Theorem 3. Let Y be a committee evaluation function computable in time y. Then, egal-Y -SUCCESSIVE COMMITTEES ELECTION with m candidates, f = 1, and k = 2 is solvable in O(m3 + ym2) time. Using Lemma 1, we extend Theorem 3 in a second step to the case where the candidate frequency is unconstrained. Corollary 3. Let Y be a committee evaluation function computable in time y. Then, egal-Y -SUCCESSIVE COMMITTEES ELECTION for committees of size two is solvable in O(m3 + ym2) time. There remain few cases for which we were unable to settle complexity bounds for committee size k = 2 and candidate frequency f > 2. For these cases, the structure of possible solutions seems quite complicated, yet too constrained to construct a hardness proof. There are examples where no committee in an optimal solution appears f times. However, such examples are not symmetric enough to simulate multiple choices that seem to be essential in hardness constructions. To sidestep this issue, below we give a polynomial-time 1 2-approximation algorithm. Interestingly, the larger size of a target committee series is, the better approximation the algorithm outputs. Theorem 4. Let Y be a committee evaluation function computable in time y. Then, util-Y -SUCCESSIVE COMMITTEES ELECTION with m candidates, k = 2, candidate frequency f 3, and number t = xf +r of committees, where 0 < x and 0 < r < f, can be (1 1 x+1)-approximated in time O(m3 + ym2). Algorithm description. Let t = xf + r, where 0 < r < f, 0 < x and let t := xf. To find an approximate solution to an instance I of util-Y -SCE with the target number of committees t, we consider a new instance I that is identical to I except for the target number of committees being t . Then, thanks to Lemma 2 (t is a multiple of x), we use the algorithm from Theorem 2 to find a solution S to I . After pairing two arbitrarily chosen unused candidates (they always exist) and adding such a committee r < f times to S , we get an approximate solution to I. Committees of Size at Least Three The root of polynomial-time solvability of X-Y -SCE for committees of size at most two lies in the fact that suitable matching problems on graphs are also polynomial-time solvable. A natural question is what happens for larger sizes of committees. There is, however, not much hope to obtain a generally efficient algorithm since already finding a winning committee under Chamberlin-Courant is NPhard (Procaccia, Rosenschein, and Zohar 2008). Hence, it is clear that in general X-Y -SCE is NP-hard for X {util, egal} and Y {tr CC, e CC, CC}. Winning committees for Chamberlin-Courant can, however, be computed in polynomial-time when the committee size is constant (Procaccia, Rosenschein, and Zohar 2008). So, the question (for Chamberlin-Courant-based scoring function) is for what sizes of committees are we able to compute good committee series efficiently? In this section, we show that, with the exception of the case of weakly separable and approval committee scoring functions under utilitarian aggregation (Theorem 1, Corollary 1), all considered cases become NP-hard already for committee size k = 3. Indeed, in all proofs in this section we use committee size exactly 3. However, the constructions can be adapted to use any constant committee size greater than three. This usually requires special voters that ensure that every feasible committee contains a specified number of dummy candidates. These candidates fill up all committees leaving only three places for meaningful candidates in each committee. We start with the approval-based CC functions. Theorem 5. For every Y {tr CCα | α (0, 1] Q} {App CC}, egal-Y -SUCCESSIVE COMMITTEES ELECTION and util-Y -SUCCESSIVE COMMITTEES ELECTION with f = 1 and k = 3 are NP-hard. Proof. We show NP-hardness by giving a polynomial-time reduction from a restricted variant of 3-DIMENSIONAL MATCHING. Given three disjoint sets X, Y , Z of the same cardinality and a subset J of X Y Z, 3-DIMENSIONAL MATCHING asks whether there exists a size-|X| set M J such that for each pair of distinct triples (x, y, z) M and (x , y , z ) M it holds that x = x , y = y , z = z ; set M is called a 3-dimensional matching. It remains NPhard if each element x X belongs to exactly three sets from J (Garey and Johnson 1979). Let us consider an instance I = (X, Y, Z, J ) of 3-DIMENSIONAL MATCHING such that |X| = 2n 6. We build an instance I = (C, V, f, k, t, p) of egal-tr CC1-SCE where we are searching for a committee series of committees of size k = 3 assuming candidate frequency f = 1. We set the size t of the searched committee series to 4n and the committee series quality lower bound to p = 1. We start with set V containing all elements from X Y Z and for each xi S we add three voters v1 i , v2 i , v3 i denoted by Vi. Finally, we add a special voter v . Without loss of generality, let sets X, Y , and Z be arbitrarily ordered. Then, for any of X, Y , Z, denote a corresponding set without the i-th element by X i, Y i, Z i. We refer to the first half of elements of X as X and to the second half as X. For the sake of readability, we do not specify approvals of the voters explicitly. Equivalently, below we list every candidate in C together with the list of voters that approve the candidate. 1. For each xi X consider all three triples (xi, yj, zk), (xi, yj , zk ), and (xi, yj , zk ) in J to which xi belongs. We add three key candidates c1 i , c2 i , c3 i referring to these triplets approved by the following voters: c1 i : {xi, v1 i , v2 i , v } Y j Z k (4) c2 i : {xi, v2 i , v3 i , v } Y j Z k (5) c3 i : {xi, v3 i , v1 i , v } Y j Z k (6) 2. For each element xi X we add one candidate approved by the following voters: cxi : X i Y Z V1 . . . Vi 1 Vi+1 . . . V2n 3. For each element yi Y we add one candidate approved by the following voters: cyi : {yi} X V1 . . . Vn 4. For each element zi Z we add one candidate approved by the following voters: czi : {zi} X Vn+1 . . . V2n The idea behind the correspondence between a 3dimensional matching M = {M1, M2, . . . , M2n} and the solution S of the constructed egal-tr CC1-SCE instance is as follows. The committee series S contains the following two groups of committees: 1. For each Mi = (xi, yj, zk) M, there is a committee consisting of candidates cyj, czk, and one of the candidates c1 i , c2 i , c3 i that exactly corresponds to set Mi. 2. For each xi X, there is a committee consisting of candidate cxi and two candidates from c1 i , c2 i , and c3 i that were not selected to be part of any committee in group 1. Committee series S consists of exactly 4n committees of size three. Since M is a matching, building the first group of committees as described is always possible we use every candidate representing elements from Y and Z exactly once, one key candidate corresponding to each element of X. One can verify that by the construction of the approval lists, each committee in the first group contains candidates that are representing every voter. Moving on to the second group of voters, assuming that M is a matching, it must be the case that we are able to follow the instructions to build this group. In every committee in the second group, every voter is also represented. Indeed, for some i [2n], candidate cxi is approved by voters X i, Y , Z, and V1, V2, . . ., Vi, Vi+1, Vi+2, . . ., V2n, and voters in Vi are represented by every two candidates among c1 i , c2 i , and c3 i . Finally, the quality of S is at least one; thus, a feasible matching M implies a feasible committee series S. To show the opposite direction assume that S is a solution to egal-tr CC1-SCE. By construction, v approves only key candidates. Thus, each committee in S contains at least one key candidate. In fact, each committee contains at most two candidates at the same time. If a committee is formed solely of key candidates, then, since each candidate is approved by only one voter in X, at least one voter x X is not represented (observe that |X| 6). Hence, in each committee there are either one or two key candidates. Let us call committees with one key candidate matching implementing and those with two key candidates filling. Since we have 6n key candidates, S contains exactly 2n matching implementing committees and 4n filling committees. Let us focus on the filling committees first. For every i [2n], neither cyi nor czi could be the third candidate in a filling committee. It is because at least one voter x X would not have its approved candidate in the committee (note that |X| 6). Consequently, the only possibility to complete filling committees is to use candidates cxi, i [2n], one per filling committee. Consider some candidate cxi. Then, the only possibility to obtain a filling committee with positive quality (according to tr CC1), is to pick two arbitrarily chosen candidates of c1 i , c2 i , and c3 i . As a result, for each i [2n], there is exactly one key candidate left to participate in matching implementing committees. Consider some key candidate c1 i representing triplet (xi, yj, zk) J . By the construction, to form a matching implementing committee with positive quality, c1 i has to be accompanied by candidates cyj and czk. Thus, indeed, matching implementing committees in S must represent a perfect matching of the original instance. The reduction clearly works in polynomial time and hence the theorem for egal-tr CC1-SCE holds. Observe that for each committee S (and a fixed election), it holds that tr CC1(S) = 1 App CC(S) = m. Thus, changing the lower bound on the committee series quality to m gives a correct reduction for egal-App CC-SCE. Observe that the presented reductions for the egalitarian committee series quality always require maximum possible quality of committee. Thus, for both tr CC1 and App CC, reductions for the respective utilitarian variants can by obtained by multiplying the respective lower bounds on committee series quality by the size of the target committee series. Finally, thanks to Lemma 3, NP-hardness for tr CCα holds for any rational α (0, 1]. For Chamberlin-Courant with ordinal preferences, we obtain analogous results via reductions from the NP-hard RAINBOW MATCHING problem (Garey and Johnson 1979). Theorem 6. For each X {egal, util} and Y {CC, e CC}, X-Y -SUCCESSIVE COMMITTEES ELECTION with f = 1 and k = 3 is NP-hard. Finally, giving a reduction from 3-PARTITION (Garey and Johnson 1979), we show that already with committee size three, egal-Y -SCE becomes intractable for every non-trivial weakly separable rule Y . Herein, a weakly separable rule Y is called non-trivial if for a large-enough number of candidates it does not assign the same score to every position. More formally, there exists some constant m0 such that for every number of candidates m m0 there exists a position z(m ) such that φ(z(m )) = φ(z(m )+1), where φ denotes the scoring function of rule Y . All reasonable weakly separable rules we are aware of are non-trivial. Theorem 7. egal-Y -SUCCESSIVE COMMITTEES ELECTION with committee size k = 3 is NP-hard for Y being Approval or any non-trivial weakly separable rule from FWS. We introduced successive committees elections, a new model extending classic multiwinner scenarios with new optimization goals. Our results indicate that evaluating the quality of a committee series in an egalitarian setting seems richer in structure, but the utilitarian setting sometimes may allow tractability where the egalitarian does not. As an intriguing question we leave open the computational complexity of util-Y -SUCCESSIVE COMMITTEES ELECTION with f > 2, k = 2, and Y {App CC, e CC, CC}. However, for this case, we provided a polynomial-time algorithm providing a 1 2-approximate solution (the approximation ratio gets better with growing size of a target committee series). Since we provided multiple NP-hardness results, it is of interest to also study the influence of parameters such as the number of rounds on (parameterized) computational complexity. Finally, the range of natural further models in the context of committee series is far from being exhausted. For instance, for some applications one may demand that there is a certain overlap between consecutive committees this aspect is not captured by our model. Acknowledgments We are grateful to anonymous reviewers for their useful comments. AK was supported by the DFG project AFFA (BR 5207/1 and NI 369/15). We thank Piotr Skowron for initial discussion on the topic of this work. References Airlines Reporting Corporation. 2018. Achieving Better Business Travel Results: Insights from U.S. Road Warriors. Presented at the ARC s 2018 Travel Connect conference. https://gillespie411.files.wordpress.com/2019/10/achievingbetter-business-results-insights-from-u.s.-road-warriors2018-10.pdf. Online; accessed 11/21/2019. Aziz, H., and Lee, B. E. 2018. Sub-committee approval voting and generalized justified representation axioms. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society (AIES), AIES 18, 3 9. Aziz, H.; Faliszewski, P.; Grofman, B.; Slinko, A.; and Talmon, N. 2018. Egalitarian committee scoring rules. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 56 62. Betzler, N.; Slinko, A.; and Uhlmann, J. 2013. On the computation of fully proportional representation. Journal of Artificial Intelligence Research 47(1):475 519. Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Niedermeier, R.; Skowron, P.; and Talmon, N. 2017. Robustness among multiwinner voting rules. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), 80 92. Bredereck, R.; Faliszewski, P.; Igarashi, A.; Lackner, M.; and Skowron, P. 2018. Multiwinner elections with diversity constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 933 940. Celis, L. E.; Huang, L.; and Vishnoi, N. K. 2018. Multiwinner voting with fairness constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 144 151. Chamberlin, J. R., and Courant, P. N. 1983. Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review 77(3):718 733. Elkind, E.; Faliszewski, P.; Skowron, P.; and Slinko, A. 2017. Properties of multiwinner voting rules. Social Choice and Welfare 48(3):599 632. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner Voting: A New Challenge for Social Choice Theory. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 2, 27 47. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2019. Committee scoring rules: Axiomatic characterization and hierarchy. ACM Transactions on Economics and Computation 7:3:1 3:39. Fluschnik, T.; Skowron, P.; Triphaus, M.; and Wilker, K. 2019. Fair knapsack. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 1941 1948. Freeman, R.; Zahedi, S. M.; and Conitzer, V. 2017. Fair and efficient social choice in dynamic settings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 4580 4587. Gabow, H. N. 2018. Data structures for weighted matching and extensions to b-matching and f-factors. ACM Transactions on Algorithms 14(3):39:1 39:80. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. Lang, J., and Skowron, P. 2018. Multi-attribute proportional representation. Artificial Intelligence 263:74 106. Misra, N., and Sonar, C. 2019. Robustness radius for Chamberlin-Courant on restricted domains. In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 341 353. Procaccia, A. D.; Rosenschein, J. S.; and Zohar, A. 2008. On the complexity of achieving proportional representation. Social Choice and Welfare 30(3):353 362. Skowron, P.; Faliszewski, P.; and Lang, J. 2016. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence 241:191 216. Talmon, N., and Faliszewski, P. 2019. A framework for approval-based budgeting methods. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2181 2188.