# committee_selection_with_intraclass_and_interclass_synergies__216e4f70.pdf

Committee Selection with Intraclass and Interclass Synergies

Rani Izsak Weizmann Institute of Science Rehovot, Israel ran.izsak@weizmann.ac.il

Nimrod Talmon Weizmann Institute of Science Rehovot, Israel nimrodtalmon77@gmail.com

Gerhard J. Woeginger RWTH Aachen Aachen, Germany woeginger@algo.rwth-aachen.de

Voting is almost never done in void, as usually there are some relations between the alternatives on which the voters vote on. These relations shall be taken into consideration when selecting a winning committee of some given multiwinner election. As taking into account all possible relations between the alternatives is generally computationally intractable, in this paper we consider classes of alternatives; intuitively, the number of classes is significantly smaller than the number of alternatives, and thus there is some hope in reaching computational tractability. We model both intraclass relations and interclass relations by functions, which we refer to as synergy functions, and study the computational complexity of identifying the best committee, taking into account those synergy functions. Our model accommodates both positive and negative relations between alternatives; further, our efficient algorithms can also deal with a rich class of diversity wishes, which we show how to model using synergy functions.

Introduction The study of multiwinner elections is quite established by now, however it is usually assumed that the alternatives (over which the voters vote) are indistinguishable; the only differences between them are imposed by the preferences of the voters. Many times, however, this is not the case; for example, consider selecting a committee where it is desired to have: (1) the same proportion of men and women; and (2) as many experienced people as possible. In a case like that, we would like to not only select people with great support from the electorate, but also to take diversity wishes into account. Notice how the alternatives are no longer indistinguishable, as there are in fact certain classes of alternatives (e.g., men and women). Indeed, in many cases the alternatives can be naturally partitioned into classes, and some intraclass or interclass synergies are known or are desired: as further examples, consider: (1) selecting different cutlery items, where the utility gained from selecting one fork and one knife might be greater than the utility gained from selecting two forks; (2) selecting cellphones with their power adapters, where the utility gained from selecting one cellphone with its matching power adapter might be greater than the utility gained from selecting two cellphones; or (3)

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

selecting tables with matching chairs, where selecting one table with 100 chairs might not increase the utility gained from selecting the same table with, e.g., 8 chairs. In this paper we consider partitions of the set of alternatives into certain natural classes, and model (positive and negative) synergistic relations between alternatives of the same class (intraclass synergies), as well as synergistic relations and diversity wishes between alternatives of different classes (interclass synergies). Our main modelling tool is what we refer to as synergy functions (formal definitions are given in the Preliminaries section). We concentrate on the computational complexity of identifying a winning committee, while taking into account such intraclass and interclass synergies. Intuitively, we would like each committee member to have reasonable support from the electorate while maximizing (minimizing) the sum of the positive (negative) synergies. We show that, while the corresponding optimization problem is generally intractable (specifically, for general synergy functions the problem is not even fixed-parameter tractable for the number of classes; roughly speaking, this means that even with very few classes no efficient algorithm for selecting an optimal committee exists), there are various cases for which efficient algorithms do exist. Specifically, we describe efficient algorithms that can identify committees satisfying certain diversity wishes, as well as committees that optimize certain non-trivial positive and negative synergies between the alternatives.

Related Work

The most relevant work is the recent work of Izsak 2017 about committee selection with synergies between the candidates. Through set functions, Izsak allows voters to express their preferences of being represented by several specific candidates together; e.g., the score a voter gives to two candidates together can be higher than the sum of their individual scores (say, if they are known to work extremely well together). As set functions might be too complex, Izsak considers preference elicitation and algorithms based on the supermodular degree (Feige and Izsak 2013) and showed that existing algorithms (Feldman and Izsak 2014; 2017) can be used to obtain approximation guarantees that depend on the supermodular degree. The supermodular degree, however, might be too large when some candidates

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

have synergy with many other candidates. For example, assume that there are m/2 chairs and m/2 tables, where every chair is worth more together with every table. Then, the supermodular degree depends on m, and the guarantees of algorithms tailored for the supermodular degree might not be useful. Contrary, in the current paper we have an exact and efficient algorithm for this case. On the other hand, in an instance where one views the items as an ordered list, where every two consecutive items in the list have positive synergy, then, in the model of Izsak 2017, the supermodular degree is 2, while in our model, we need one class for every single item. Another related model is the well-studied model of Marginal Contribution nets (MC-nets) (Ieong and Shoham 2005). MC-nets, which are vastly studied for cooperative game theory, are general and flexible; in particular, they can also capture synergies. We stress, however, that our model is different than that of MC-nets. Other works within computational social choice consider relations between the alternatives. Among these, perhaps the most relevant are works related to voting in social networks, such as work studying the influence of social networks on election outcomes (Conitzer 2012; Doucette et al. 2015; Procaccia, Shah, and Sodomka 2015; Salehi-Abari and Boutilier 2014; Sina et al. 2015) and the effect of social networks on manipulative actions performed by external agents (Bredereck et al. 2015b; Bulteau et al. 2015; Chen et al. 2015).

Preliminaries

Below we briefly discuss parameterized complexity and treewidth. We denote the set {1, . . . , n} by [n].

Parameterized Complexity

While the number m of alternatives in a given election might be huge, the number z of classes of alternatives might be significantly smaller than m. Therefore, considering z as a parameter, and studying our optimization problem from a parameterized complexity point of view is useful. Parameterized complexity is a very active research field; here we only briefly discuss it, and point the reader to the textbooks of Downey and Fellows 2013, Flum and Grohe 2006, or Niedermeier 2006. An instance (I, k) of a parameterized problem consists of an instance I of a non-parameterized problem and an integer k, referred to as the parameter. A parameterized problem is called fixed-parameter tractable (or, is said to be in FPT ) if there is an algorithm solving it in f(k) |I|O(1) time, where f is some computable function. In contrast, an algorithm with running-time |I|f(k) only shows membership in the class XP. Trivially, it holds that FPT XP. One can show that a parameterized problem L is (presumably) not fixed-parameter tractable by devising an FPT reduction from a W[1]-hard problem to L. An FPT reduction from a parameterized problem L to another parameterized problem L is a function that, given an instance (I, k), computes in f(k) |I|O(1) time an instance (I , k ), such

that k g(k) and (I, k) L (I , k ) L , where g can be any computable function.

Treewidth Treewidth (see, e.g., (Downey and Fellows 2013)) is a measure of similarity of graphs to trees, where graphs which are similar to trees (in some specific sense) have small treewidth. Let G be an undirected graph, let T be a tree and let B : V (T) 2V (G). The pair (T, B) is a valid tree decomposition of G if T is a tree in which every vertex x V (T) has an assigned set of vertices Bx V (G) (called a bag) such that the following properties are satisfied: (P1): x V (T ) Bx = V (G).

(P2): For each {u, v} E(G), there exists an x V (T) such that u, v Bx. (P3): For each v V (G), the set of vertices of T whose bags contain v induces a connected subtree of T. The width of the tree decomposition (T, B) is maxx V (T ) |Bx| 1. The treewidth of a graph G, usually denoted by ω(G), is the minimum width over all the valid tree decompositions of G.

The CSC Problem and its Modeling Power We are ready to describe our formal model and the specific combinatorial problem we aim at solving. First, we present our model. Then, we provide examples to demonstrate its power: (1) its applicability to situations where the winning committee shall adhere to some diversity requirements; (2) its ability to incorporate both positive and negative synergies; and (3) its ability to model both interclass and intraclass synergies.

Formal Model and Problem Definition We are given an integer k, a set A = {a1, . . . , am} of alternatives, and a partition of A into z subsets: A = C1 Cz, and Ci Cj = for every i = j. For every i [z], we refer to Ci as the ith class (of alternatives). Our aim is to select a (winning) committee S A that consists of exactly k alternatives. We would like our winning committee to consist of alternatives with reasonable support from the given electorate, which we model by individual weight functions, and, importantly, to maximize the additional weight gained by synergies between alternatives within the classes of alternatives or between different classes of alternatives, which we model by synergy functions. Formally speaking, we associate an individual weight/score w(ai) for every alternative ai A. We mention that these weights are sufficient to incorporate any separable committee scoring function, such as SNTV, k-Borda, and Bloc. (Intuitively, a separable committee scoring function is a multiwinner voting rule where the score given to a committee by a voter is the sum of the individual scores this voter gives to each committee member; see, e.g., (Faliszewski et al. 2016).) Additionally, we associate a synergy function for every set of classes of alternatives. Formally, let C {C1, . . . , Cz} be

a set of classes containing exactly d classes. Then, we associate with C a synergy function w C : [m]d N of dimension d. Intuitively, the value of w C(x1, . . . , xd) is the amount of additional weight (i.e., score) gained by selecting the given numbers of alternatives of each corresponding classes contained in C (when, without loss of generality, we assume some canonical ordering over the classes contained in C). Indeed, there are at most m items at each of the classes and not exactly m, but for clarity, we neglect that, and allow one to give a value of 0 for every non relevant combination. Further, sometimes we list the members of a set of classes without using set notation. For example, consider the 2-dimensional synergy function w C1,C4: the value w C1,C4(2, 4) measures the additional weight gained to a committee that includes exactly 2 alternatives of the class C1 and exactly 4 alternatives of the class C4. The main problem we study in this paper is the following.

COMMITTEE SELECTION WITH CLASSES (CSC) Input: A set of alternatives A = {a1, . . . , am} partitioned into z classes C1, . . . , Cz, integer weights w(ai) for the alternatives (i [m]), synergy functions of dimension d, and committee size k [m]. Question: Output a committee S A of size k that maximizes the committee score: ai S w(ai) + j1,...,jd [z] w Cj1,...,Cjd (|S Cj1|, . . . , |S Cjd|).

Note that a synergy function of dimension d can easily model a synergy function of a lower dimension, by giving strictly positive values only for tuples containing zeros for a fixed subset of the coordinates.

Example 1. Consider the alternatives {a1, a2, b1, b2}, partitioned into C1 = {a1, a2} and C2 = {b1, b2}. Let w(a1) = w(b1) = 1, w(a2) = 2 and w(b2) = 3. Let the 2dimensional synergy function w C1,C2 be w C1,C2(x1, x2) = 2x1 and set k = 2. Then, two committees tie as winners, both with committee score 7: {a1, a2} and {a2, b2}.

Modeling Power and Examples

Here we demonstrate some aspects of our model s modeling power. The following examples are meant to be toy examples to point to different modeling possibilities.

Example 2 (Positive and negative synergies). Assume selecting a small committee from a given set of alternatives {a, b, c, d, e, f}. The committee members shall work together towards a certain goal. Therefore, it is desirable to satisfy both the following goals: (1) the committee members shall be well respected (say, very professional); and (2) the committee members should be able to work well together as a team. For the first goal, one may ask an assumed electorate for alternatives approvals and count the number of approvals for each alternative separately; for the sake of the example, assume that a, b, and c receive 3 approvals each, while d, e, and f receive 5 approvals each. For the second goal, one may try to assess how well different alternatives work well together; for the sake of the example, assume that both a and b work well with c, while both d and e do not work well with f.

We can model the problem of choosing the best committee as a CSC instance as follows. The set of alternatives is A = {a, b, c, d, f, e} with the following weights: w(a) = w(b) = w(c) = 3 and w(d) = w(e) = w(f) = 5. To model the positive and negative synergies, it is useful to first partition the set of alternatives into 4 classes, as follows: A = C1 C2 C3 C4, where, C1 = {a, b}, C2 = {c}, C3 = {d, e}, and C4 = {f}. Then, the synergy functions might be as follows: w C1,C2(1, 1) = 10, w C1,C2(2, 1) = 20, w C3,C4(1, 1) = 10, w C3,C4(2, 1) = 20. Notice how the positive synergies correspond to positive values while the negative synergies correspond to negative values.

Example 3 (d-dimensional synergy functions). Consider selecting cutlery, such as forks, knives and spoons: assume the alternatives A = {f1, f2, k1, k2, s1, s2}, where, fi are forks, ki are knives, and si are spoons. Indeed, the set of alternatives can be naturally partitioned into A = {C1, C2, C3}, where, C1 = {f1, f2}, C2 = {k1, k2} and C3 = {s1, s2}. Furthermore, one might prefer to select sets consisting of one fork, one knife, and one spoon (as compared to, say, two forks and one spoon). As a CSC instance, one shall first assign weights to the individual cutlery items. Then, to account for the relations between the cutlery types, one may define the synergy functions to be, say, as follows: w C1,C2,C3(1, 1, 1) = 10, w C1,C2,C3(2, 2, 2) = 20, while all other values are 0.

In the previous examples we demonstrated modeling interclass synergies, such as the utility added by selecting one fork together with one knife and one spoon. One can model intraclass synergies using CSC, as we show next.

Example 4 (Intraclass synergies). Assume selecting a national soccer team, where the available athletes are A = {a1, a2, b1, c1, c2, c3}. Further, a1 and a2 currently play in the same soccer club, while c1, c2, c3 are in a different club. The set of alternatives can be naturally partitioned as follows: A = C1 C2 C3, where C1 = {a1, a2}, C2 = {b1}, and C3 = {c1, c2, c3}. As athletes from the same club play well together, we do not only want to select the best athletes to the team, but take this aspect into account, as well. As a CSC instance, one might define the following synergy functions: w C1(2) = 20, w C3(2) = 20, w C3(3) = 40. Notice how, e.g., selecting all three athletes form C3 increases the committee score by 40. Further, notice how intraclass synergies are modeled using 1-dimensional synergy functions, while, in other examples, interclass synergies are modeled using d-dimensional (d > 1) synergy functions.

In many cases diversity in the elected committee is required, or at least desired to some extent. Later we discuss general ways to model diversity goals using CSC; specifically, Theorem 2 and Theorem 3 describe an efficient algorithm for that task. Here we provide a simple example.

Example 5 (Diversity requirements). Consider selecting a committee to include 4 committee members out of the set of alternatives A = {m1, m2, m3, w1, w2, w3}, where mi are men, wi are women, and it is required to have the same number of men and women in the committee. First we may assign weights to the alternatives based on their support from

the electorate. Then, after naturally partitioning the set of alternatives to A = {C1, C2}, where C1 = {m1, m2, m3} and C2 = {w1, w2, w3}, we can define the synergy functions to be, say: w C1,C2(2, 2) = 100, while all other values of the synergy functions are 0, and the individual weights are much smaller than 100.

CSC is Computationally Intractable

As examplified in the previous section, many scenarios can be modeled as CSC instances. Therefore, a natural question to ask is whether solutions to CSC instances can be found efficiently. In this section, we start our computational journey by investigating the computational complexity of CSC. First, perhaps not surprisingly, we face intractability; interestingly, we even face parameterized hardness with respect to the number of classes.

Theorem 1. CSC is NP-hard and W[1]-hard with respect to the number z of classes.

Proof. We reduce from the W[1]-hard problem MULTICOLORED CLIQUE (MCC) (Downey and Fellows 2013): given a graph G = (V, E) whose vertices are partitioned into h disjoint color classes V = l [h] Vl, where for every j [h], |Vj| = n and Vj is an independent set by G, the goal is to decide whether a set of h pairwise adjacent vertices v1, . . . , vh with vi Vi for every i [h], exists. Let n and h be integers. Given an instance of MCC with h color classes V1, . . . , Vh, where Vj = {v1 j , . . . vn j }, for every j [h], we show how to reduce it to an instance of CSC. We introduce z = h + 1 classes of alternatives, C1, . . . , Ch and D, where, for every j [h], Cj = {a1 j, . . . , an j } and D = {d1, . . . , dnh} (thus, we have m = 2nh alternatives in total). We set all the individual weights to zero: w(ai j) = 0 (j [h], i [n]) and w(di) = 0 (i [nh]). We set k to nh. For every pair of classes Ci and Cj (i = j [h]), we define a synergy function of dimension 2, such that f Ci,Cj(x, y) = 1, if the edge {vx i , vy j } is present in the graph G, and f Ci,Cj(x, y) = 0, otherwise. This finishes the reduction. We associate with each committee (of the reduced CSC instance), a set of at most h vertices (of the given MCC instance): with a committee S we associate the set of vertices VS = {v|S Cj| j : j [h]}; that is, as S has |S Cj| members of the j-th class, VS has the |S Cj|-th vertex of color j. Notice that we do not consider the class D. The crucial observation now is that the committee score of S equals the number of edges between the vertices of VS; this is so since all individual weights are set to zero, and every synergy function that corresponds to two classes Ci and Cj adds 1 to the committee score, if and only if there is an edge between the corresponding vertices of the ith and jth color. It follows that the committee score of S is maximum when VS is a multicolored clique.

The negative result above means that (as long as W[1] FPT , which is widely believed), CSC is not fixedparameter tractable with respect to the number z of classes.

Breaking CSC s Computational Intractability

As in practice we might still want to find solutions to CSC instances, we continue our computational journey by considering possible ways of overcoming the intractability shown in the last section. First, we observe that if the number z of classes is a constant, then there is a polynomial-time algorithm for CSC.

Observation 1. CSC is XP wrt. the number z of classes.

Proof. Consider the following brute-force algorithm: For every class Cj (j [z]), guess (i.e., do exhaustive search for) a number kj [k] which stands for the number of committee members to be selected from the jth class, and make sure that j [z] kj = k. Then, for every class Cj (j [z]), choose the kj heaviest alternatives from that class. Since the highest number we should guess is k, the number of possibilities we check is upper bounded by kz, which is polynomial in k, by our assumption that z is a constant.

Next we consider certain kinds of synergy functions; specifically, we consider separable functions, monotone functions, piece-wise linear functions, and so-called constant-bounded functions (formally defined below). We show that CSC instances with synergy functions that are separable can be solved in polynomial time. We also show that CSC instances with synergy functions that are piece-wise linear concave or constant-bounded can be solved in FPT time with respect to the number of classes.

Separable Synergies and Diversity Wishes

A function f : Nd N is separable if there are functions f1, . . . , fd such that f(x1, . . . , xd) =

i [d] fi(xi). Below we describe an efficient algorithm that solves CSC instances with only separable functions, and later we show how to model diversity wishes using such CSC instances. Note that if all the synergy functions are separable, then we can actually model the problem with only intraclass synergy functions (i.e. synergy functions of dimension 1). So, in fact we show how to compute exactly an optimal solution in the case of only intraclass synergies. Interestingly, such functions can model also diversity wishes between different classes.

Theorem 2. Any instance of CSC containing only separable synergy functions is polynomial-time solvable.

Proof. We describe an algorithm based on dynamic programming. We use the fact that, as all synergy functions are separable, it is sufficient to decide the number of committee members from each class individually. Informally speaking, our algorithm is as follows: we arbitrarily sort the classes and then apply dynamic programming according to that order, while remembering only the number of committee members that remain to be selected to the committee. Formally, let C1, . . . , Cz be the alternative classes, and consider them in this (arbitrary) order. We define Rec(j, k ) to be a committee with the maximum score possible when selecting k alternatives from the the first j classes, C1, . . . , Cj. We show how to compute the values of the table

Rec(j, k ), for every j z, k k. At the end, we will return the committee stored at Rec(z, k). Note that the scores of the committees in Rec can be stored as well. We start by computing committees for Rec for j = 1, for every k k. This can be done as follows: one needs to choose k alternatives from C1 of maximum individual weights. Given the values of Rec(j , k ) for every k k and j < j, in order to compute the committee for Rec(j, k ), we check all the possibilities of selecting a committee that contains k k (heaviest) alternatives from Cj, and the rest from C1, . . . , Cj 1, and choose the best. Observe that the number of possibilities is polynomial in k and the size of the table Rec is polynomial, thus the claimed complexity follows.

To see how separable functions help to select committees with diversity desires, consider the following example.

Example 6. Consider selecting a committee of 6 members, given an election containing 6 men and 6 women. One natural diversity desire would be to have, if possible, the same number of men and women (i.e., 3) in the selected committee. We emphasize that this is not a requirement , as one shall be aware of the inherent tradeoff between the support each alternative has from the electorate, and the degree of diversity achieved. One possible way to incorporate such diversity desire into an instance of CSC is to consider two classes, of men and of women, and to define one synergy function of dimension two fmen,women where fmen,women(x1, x2) = fmen(x1)+ fwomen(x2); then,

fmen(0) = fwomen(0) = 0, fmen(1) = fwomen(1) = 1, fmen(2) = fwomen(2) = 2, fmen(3) = fwomen(3) = 3, fmen(4) = fwomen(4) = 3, fmen(5) = fwomen(5) = 3, fmen(6) = fwomen(6) = 3.

Notice how the maximum of fmen,women is achieved at fmen,women(3, 3) = 6, and how the value of fmen,women decreases for less diverse committees.

Interestingly, we can generalize the above example to incorporate various kinds of diversity desires from a winning committee, even for an arbitrary dimension.

Theorem 3. Consider an election with z classes of alternatives and diversity preferences of the form at least xi elected members are from class i , where

i xi k. Then, finding an optimal winning committee can be done in polynomial time.

Proof. We formulate the problem as an instance of CSC with separable functions and generalize the idea shown in Example 6. Specifically, for every class i, we define the synergy function: fi(t) = max{t, xi} .

Then, the maximum possible value of i fi(ti) is i xi and this value is achieved if and only if iti xi. Moreover, for every i, if ti < xi, then

i fi(ti) is less than the optimum by at least xi ti, which is the distance of ti from the objective for the class i.

Monotone Synergies

Here we consider monotone functions: a function f : Nd N is monotone if, fixing any d 1 values, the residual onedimensional function is monotone. This means that adding candidates to a subset can never decrease its value (intuitively, a candidate cannot interrupt to the rest of the committee). The next result, which follows by modifying the construction given in the proof of Theorem 1, shows that CSC remains intractable even if all the synergy functions are monotone.

Theorem 4. CSC is NP-hard and W[1]-hard with respect to the number z of classes even if all the synergy functions are monotone.

Proof. The result follows by modifying the reduction constructed in the proof of Theorem 1. Specifically, recall that in the proof of Theorem 1, we defined the synergy functions f Ci,Cj (i = j [h]) to be f Ci,Cj(x, y) = 1 if the edge {vx i , vy j } is present in the graph G, and 0 otherwise; here, we define the synergy functions to be f Ci,Cj(x, y) = 2x+2y+1 if the edge {vx i , vy j } is present in the graph G, and 2x + 2y otherwise. Further, instead of defining w(di) = 0 (i [nz]; as done in the proof of Theorem 1), here we define w(di) = 2(h 1)i (i [nz]). The proof of correctness follows similar lines as the proof of theorem 1 when observing that all synergy functions are monotone, and the committee score of a committee S with k candidates is equal to 2(h 1)k plus the number of edges between the vertices of VS.

Piece-wise Linear Synergies

While the last section shows that CSC remains intractable even if all the synergy functions are monotone, in this section we consider concave functions over linear combinations (defined within the next proof), and achieve (fixedparameter) tractability. We mention that the following theorem implies that CSC is fixed-parameter tractable if all the synergy functions are concave. Intuitively, concave synergy functions correspond to situations with decreasing marginal utilities; as motivating examples, consider (1) purchasing product clones (e.g. a second phone) and (2) having several committee members with the same expertise.

Theorem 5. CSC is fixed-parameter tractable with respect to the number z of classes, if all the synergy functions are concave functions over linear combinations.

Proof. We show how to reduce the problem into maximizing an integer linear program (ILP) with piece-wise linear concave functions; the claim then follows by applying the method developed by Bredereck et al. 2015a.

We define z integer variables, zl (l [z]), where zl stands for the number of committee members selected from the lth class, Cl. For each l [z] we add a constraint 0 zl |Cl|, as we cannot select more than |Cl| committee members from the class Cl. We add an additional constraint, namely l [z] zl = k, to respect the required committee size. It is convenient to define the following function for each l [z]: for x [|Cl|], let gl(x) be the total weight of the x heaviest alternatives in the class Cl. Notice that (1) we can precompute the values of gl(x) (l [z], x [|Cl|]); and (2) all the gl functions are concave: roughly speaking, this is so since we take the heaviest items. To see the last claim more formally, order the alternatives of the lth class in decreasing weights, and denote them, w.l.o.g, by a1, . . . , a|Cl|, such that ai ai+1 (i [|Cl| 1]). Then, concavity follows since gl(x + 1) gl(x) = ax+1 ax = gl(x) gl(x 1). Logically, to maximize the committee score we shall first maximize the sum l [z] gl(zl); as it is not linear, we utilize its concavity, and transform it using extra real-valued variables, following the technique of Bredereck et al. 2015a. Further, we shall consider the addition to the committee score gained by the synergy functions. Here we assume that each d-dimensional synergy function wj1,...,jd is such that it is a (piece-wise linear) concave function over linear combinations, that is, wj1,...,jd(x1, . . . , xd) = gj1,...,jd(f(x1, . . . , xd)), where gj1,...,jd is a piece-wise linear concave function and f(x1, . . . , xd) is a linear combination of x1, . . . , xd. Thus, for each d-dimensional synergy function, wj1,...,jd we define an integer variable zj1,...,jd with the intent that zj1,...,jd is the value of wj1,...,jd(zj1, . . . , zjd). Logically, we shall add the constraint zj1,...,jd wj1,...,jd(zj1, . . . , zjd); again, following concavity, we can optimize it by transforming it using extra real-valued variables (Bredereck et al. 2015a). Finally, we maximize the following objective function:

j1 =... =jd zj1,...,jd,

and notice that we maximize piece-wise linear concave functions, thus our result follows by applying the method developed by Bredereck et al. (Bredereck et al. 2015a).

We end this section with an open question: Is CSC W[1]- hard with respect to the number of synergy functions even if all synergy functions are convex functions over linear combinations (i.e., does CSC remains fixed-parameter tractable for increasing marginal utilities)?

Constant-bounded Synergies Consider a synergy function f Cj1,...,Cjd of dimension d. We say that f Cj1,...,Cjd is constant-bounded if it is defined only for constant values. That is, there are constants cj1, . . . , cjd such that, for each i and every possible values x1, . . . , xd, if xi ci, then fxi1,...,xid (x1, . . . , xd) = f Ci1,...,Cid (x1, . . . , xi 1, ci, xi+1, . . . , xd). We refer to ci as the synergistic upper bound of class i. The next result describes an efficient algorithm for instances of CSC consisting only of constant-bounded synergy functions.

Proposition 1. CSC with constant-bounded synergy functions is in FPT with respect to the number of classes z.

Proof. The idea is to guess a number bi between 0 and ci, for every class Ci with synergistic upper bound of ci (i [z]). This bi will be the number of representatives selected from this class, unless the number selected is ci, and then we will select at least ci representatives from the corresponding class. After this guessing phase, we select the guessed number of representatives from each class according to the guess, as described above, in a greedy way; specifically, we always select the heaviest alternatives. Finally, if we have not yet selected k alternatives, then we complete the committee with alternatives selected greedily over all those classes Ci for which our guessed number is ci. Note that our guesses can be implemented by an exhaustive search. So, for cmax = maxi ci, our running time is polynomial in (cmax)z and the number of alternatives, which proves Proposition 1, since cmax is a constant by the definition of constant-bounded synergy functions.

Structural Restrictions Consider instances of CSC with dimension at most 2, and let the classes-graph be a graph containing one vertex for each class of alternatives and an edge between two vertices if there is a non-trivial (i.e. not the zero function) synergy function between the corresponding classes. In this section we show that instances of CSC with classes-graph of bounded treewidth can be solved in polynomial time. We mention that such classes-graphs contain as a special case graphs with (only) small connected components, which seem of high relevance to the motivating examples given in the Introduction.

Theorem 6. Any instance of CSC with classes-graph of constant treewidth is solvable in polynomial time.

Proof. The main idea of our polynomial-time algorithm is as follows. Let ω be the treewidth of the classes-graph corresponding to the given instance of CSC. Since there exist small separators of size O(ω) which separates the graph into two disconnected parts, it is possible, in polynomial time, to brute-force over all possibilities of selecting alternatives from classes within these separators. Intuitively, the latter possibilities suffice: in the classes-graph, there are no edges crossing these separators; thus, there are no synergies between classes from opposite sides of those separators. For technical convenience, we will use a special type of tree-decompositions called nice tree-decompositions.

Definition 1. A tree-decomposition (T, B) of G is said to be nice if T is a rooted binary tree such that each vertex t T is one of the following four types:

Leaf Node: t is a leaf in T and Bt = {v} for some v G. Introduce Node: t has exactly one child t and Bt = Bt {v} for some v / Bt . Forget Node: t has exactly one child t and Bt = Bt \{v} for some vertex v Bt . Join Node: t has exactly two children t , t such that Bt = Bt = Bt .

The advantage of using nice tree-decompositions is that, when writing a dynamic program, as we do below, we only need to handle four types of nodes (intuitively, these node types distinguish between certain types of separators). It is known (Bodlaender and Koster 2008; Kloks 1994) that a general tree decomposition (T, B) (of treewidth ω) can be converted, in linear time, into a nice tree decomposition (T , B ) of the same width such that |T | = O(ω n). As mentioned, we solve CSC using dynamic programming. In fact, we solve a slightly generalized version of CSC (it is more general, since we are given specific requirements for different classes); specifically, we evaluate the following values recursively: For a node t T whose bag vertices are (without loss of generality) Bt = {v1, . . . , v|Bt|}, an integer k [k], and a vector [k 1, . . . , k |Bt|], we define Rec(t, k , [k 1, . . . , k |Bt|]) to be the maximum committee score possible when selecting k alternatives from the alternatives contained in the classes at the subtree rooted at t (including t), when we select exactly k j alternatives from the class corresponding to the jth bag vertex vj of t. Below we describe how to evaluate these Rec(t, k , [k 1, . . . , k |Bt|]) values. First we mention that, as our output, we return the committee corresponding to the value of max[k 1,...,k |Bt|] [n]|Bt| Rec(r, k, [k 1, . . . , k |Bt|], where r is the root of the tree-decomposition of the classes-graph of the given CSC instance (i.e., we consider all vectors [k 1, . . . , k |Bt|] and maximize over them). Next we describe how to compute the values Rec(t, k , [k 1, . . . , k |Bt|]) for each node type in the nice tree decomposition. We let Wj(k j) to denote the total weight of k j heaviest alternatives of the class corresponding to vj.

LEAF NODE. Let t be a leaf node whose bag vertices are Bt = {v1, . . . , v|Bt|}. First, make sure that k = j [|Bt|] k j. If so, then select k j heaviest alternatives from each vj Bt. Then, compute the committee score, taking into account synergies between the vertices of Bt. More formally, we return Rec(t, k , [k 1, . . . , k |Bt|]) =

j [|Bt|] Wj(k j) +

j1 =j2 [|Bt|] wvj1,vj2 (k j1, k j2).

INTRODUCE NODE. Let t be an introduce node whose bag vertices are Bt = {v1, . . . , v|Bt|}, and where v1 is the introduced node; i.e., t has a single child, t , and Bt = {v2, . . . , v|Bt|}. Select k 1 heaviest alternatives from v1 and compute the sum of synergies corresponding to pairs of vertices v1, vj (2 vj |Bt|); then, recursively call t . More formally, Rec(t, k , [k 1, . . . , k |Bt|]) = W1(k 1) + 2 j |Bt| wv1,vj(k 1, k j)+Rec(t , k k 1, [k 2, . . . , k |Bt|]).

FORGET NODE. Let t be a forget node whose single child is t with Bt = {v1, . . . , v|Bt |}, where v1 is the forgotten node; i.e., t = {v2, . . . , v|Bt |}. Guess how many alternatives to select from the class corresponding to the forgotten node, and recursively call t . More formally, let k = k 2 j |Bt | k j (i.e., k is the number of remaining alternatives to select from classes in the subtree

of t, not including t); then, Rec(t, k , [k 2, . . . , k |Bt |]) = maxk 1 k Rec(t , k k 1, [k 1, . . . , k |Bt |]).

JOIN NODE. Let t be a join node whose two children are t and t , such that Bt = Bt = Bt = {v1, . . . , v|Bt|}. Recursively call the two children, but, since the synergies within the bag vertices are computed in each of the children, decrease the total value accordingly. More formally, Rec(t, k , [k 1, . . . , k |Bt|]) = Rec(t , k , [k 1, . . . , k |Bt|]) + Rec(t , k , [k 1, . . . , k |Bt|])

j1 =j2 [|Bt|] wvj1,vj2 (k j1, k j2).

This finishes the description of our dynamic program whose correctness follows by its exhaustive nature. The number of recursive values computed is z k kω where z is the number of classes (kω is the number of different vectors of the form [k 1, . . . , k |Bt|] and is bounded by kω since ω is the treewidth of the classes graph); as ω is assumed to be constant, the number of recursive values computed is polynomial in the input size. Each of these values is computed by issuing a polynomial number of recursive calls, thus complexity follows.

Discussion We introduced the CSC problem, which is concerned with identifying winning committees in multiwinner elections, when some (positive and negative) relations between certain alternatives are present; specifically, we utilized the fact that in many cases (but not all; see below) there is a natural partition of the set of alternatives, such that the relations between them can be expressed as synergy functions involving these classes. We have demonstrated that CSC can model various of real-world scenarios, including scenarios involving both positive and negative relations, scenarios with both interclass and intraclass relations, and scenarios where some diversity requirements or desires are to be satisfied by the winning committee. Even though, in its most general form, CSC is computationally intractable, We have developed algorithms which efficiently solve many CSC instances. We end the paper by discussing generalizations of CSC and other avenues for future research, as well as some other subtle points concerning our modeling.

In our formal model, we used individual weights for the alternatives as well as synergy functions to model the synergies between the alternatives. The individual weights for the alternatives can naturally correspond to scores corresponding to any weakly separable multiwinner voting rule operating on an implicit multiwinner election (see Example 2 and the discussion concerning weakly separable multiwinner voting rules in the section describing the Formal Model). One might generalize CSC and study a similar problem, but one where the assumed underlying multiwinner voting rule is not weakly separable, but, say, Chamberlin Courant or PAV. As another problem variant, notice that here we assumed that the values of the synergy functions are given explicitly. It might be interesting to see whether different

access models to their values (e.g., as oracle functions) correspond better to some real-world scenarios, and if so, whether efficient (exact, parameterized, or approximation) algorithms exist for such variants of CSC.

It is natural to try to further extend the modeling power of CSC; as some example, consider (1) A generalization of CSC where not only one partition of the set of alternatives is given, but several partitions: this might correspond to diversity wishes across multiple dimensions, such as both gender diversity and ethnic diversity; and (2) A generalization of CSC with individual synergy functions: it seems plausible to assume that, for different voters, different synergies play different roles and importance.

Acknowledgements

We are very grateful to Irit Dinur for useful discussions and for her help with showing hardness. We are also very grateful to Uri Feige, Inbal Livni-Navon and Maayan Meir for useful discussions.

Bodlaender, H. L., and Koster, A. 2008. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal 51(3):255 269. Bredereck, R.; Faliszewski, P.; Niedermeier, R.; Skowron, P.; and Talmon, N. 2015a. Elections with few candidates: Prices, weights, and covering problems. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 15), 414 431. Bredereck, R.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2015b. Large-scale election campaigns: Combinatorial shift bribery. In Proceedings of AAMAS 15, 67 75. Bulteau, L.; Chen, J.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2015. Combinatorial voter control in elections. Theoretical Computer Science 589:99 120. Chen, J.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2015. Elections with few voters: Candidate control can be easy. In Proceedings of AAAI 15, 2045 2051. Conitzer, V. 2012. Should social network structure be taken into account in elections? Mathematical Social Sciences 64(1):100 102. Doucette, J. A.; Hosseini, H.; Tsang, A.; Larson, K.; and Cohen, R. 2015. Voting with social networks: Truth springs from argument amongst friends. Presented at the 2nd Workshop on Exploring Beyond the Worst Case in Computational Social Choice; Held as part of AAMAS 15. Downey, R. G., and Fellows, M. R. 2013. Fundamentals of Parameterized Complexity. Springer. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2016. Committee scoring rules: Axiomatic classification and hierarchy. In Proceedings of IJCAI 16, 250 256. Feige, U., and Izsak, R. 2013. Welfare maximization and the supermodular degree. In Innovations in Theoretical Computer Science, ITCS, 247 256.

Feldman, M., and Izsak, R. 2014. Constrained monotone function maximization and the supermodular degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, 160 175. Feldman, M., and Izsak, R. 2017. Building a good team: Secretary problems and the supermodular degree. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1651 1670. Flum, J., and Grohe, M. 2006. Parameterized Complexity Theory. Springer. Ieong, S., and Shoham, Y. 2005. Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), Vancouver, BC, Canada, June 5-8, 2005, 193 202. Izsak, R. 2017. Working together: Committee selection and the supermodular degree. In Proceedings of AAMAS 17, 1578 1580. Kloks, T. 1994. Treewidth: computations and approximations, volume 842. Springer Science & Business Media. Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford. Procaccia, A. D.; Shah, N.; and Sodomka, E. 2015. Ranked voting on social networks. In Proceedings of IJCAI 15, 2040 2046. Salehi-Abari, A., and Boutilier, C. 2014. Empathetic social choice on social networks. In Proceedings of AAMAS 14, 693 700. Sina, S.; Hazon, N.; Hassidim, A.; and Kraus, S. 2015. Adapting the social network to affect elections. In Proceedings of AAMAS 15, 705 713.