# a_model_of_winners_allocation__c6d5a68b.pdf

A Model of Winners Allocation

Yongjie Yang Chair of Economic Theory, Saarland University, Saarbr ucken, Germany yyongjiecs@gmail.com

We propose a model of winners allocation. In this model, we are given are two elections where the sets of candidates may intersect. The goal is to ﬁnd two disjoint winning committees from respectively the two elections that are subjected to certain reasonable restrictions. For our model, we ﬁrst propose several desirable properties. Then, we investigate the implication relationships among these properties. Finally, we study the complexity of computing winners allocations providing these properties. For hardness results, we also study some ﬁxed-parameter algorithms.

Introduction Multiwinner voting has attracted a considerable amount of attention of AI community very recently, due to its significant and wide applications in many areas. Standard multiwinner voting aims to select exactly k winning candidates based on the preferences of voters over candidates, where k is a given integer. In this paper, we propose a model of winners allocation. In particular, in our model there are two elections (C1, V1) and (C2, V2), where C1 and C2 are two sets of candidates, and V1 and V2 are two multisets of votes over C1 and C2 respectively. Given two nonnegative integers k1 and k2, our model aims to select (allocate) two disjoint subsets w1 C1 and w2 C2 of cardinalities k1 and k2 respectively and of high quality, based on the votes in V1 and V2. The quality of the allocated candidates are measured via certain utility functions. For simplicity, we study only approval-based elections. To see the applicability of our model, let us ﬁrst consider two special cases. When C1 C2 = , our model is equivalent to performing two independent standard multiwinner voting. Additionally, when one of k1 and k2 is 0, our model is equivalent to performing one standard multiwinner voting. Besides these two special cases, in general our model is relevant for several real-world applications.

Awards (grants) assignment. Assume that a community is going to allocate two types of awards/grants to a number of applicants (nominees), where each type of awards is given to a respectively ﬁxed number of applicants. Each applicant may be eligible for one or two types of awards,

Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

which results in two sets of candidates. However, for some kind of fairness, every applicant is only allowed to receive at most one award, corresponding to that the two selected winning committees are disjoint in our model. As each type of awards has its own feature, the organizer may invite two committees to valuate the applicants.

Sister conferences organization. Suppose two sister conferences are going to be held soon and they have the same submission deadlines. As the program committees of the conferences share many common scholars, they want to organize a cooperative review procedure to reduce their workload. In this case, a meaningful review procedure would be as follows. When submitting a paper, the authors are free to decide whether they are only interested in one particular conference or they are indifferent of the two conferences. Therefore, submitted papers are classiﬁed into two sets C1 and C2 which may intersect. However, the copyright policy allows each paper to be published in at most one of the conference proceedings.

Committee evaluations. Criticisms over the peer review processes of many AI conferences have been posted a number of times recently (see, e.g., (Brezis and Birukou 2020)), mainly triggered by the existence of high-quality papers being rejected. It is speculated that a paper may receive different results when evaluated by two independent committee members. To test this speculation, NIPS 2014 organizers select two independent program committees to handle 10 percent of the submissions. The result more or less conﬁrms the speculation. Such a review procedure is related to a special case of our model where C1 = C2 (each Ci, i [2], consists of the 10% of the submissions).

For our model, we study winners allocations that provide the maximum utilitarian/egalitarian/Nash social welfare (USW/ESW/NSW) or some envy-freeness properties, and investigate their implication relationships. In addition, we study the complexity of calculating a winners allocation belonging to these properties. Some of our results are quite interesting. For instance, we prove that computing a (k1, k2)-winners allocation of maximum USW is polynomial-time solvable as long as the utility functions adopted by the two voting communities V1 and V2 are (weakly) additive. The complexity is consistent with the polynomial-time solvability of computing winning com-

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

mittees with respect to additive functions. However, we show that the complexity of computing a winners allocation with the maximum ESW/NSW can be signiﬁcantly different: there are both natural additive functions which lead to polynomial-time solvability results and natural additive functions which lead to NP-hardness results. It is also notable that the hardness results hold even when the given elections are both voters interval (VI) and candidates interval (CI). Recall that an election is VI (CI) if the candidates (votes) can be linearly ordered so that each vote approves only consecutive candidates (each candidate is approved in consecutive votes). It is known that when restricted to only one of these two domains, many NP-hard problems become already polynomial-time solvable (Brandt et al. 2015; Elkind and Lackner 2015; Liu and Guo 2016; Peters 2018b; Faliszewski et al. 2011).

Related Works

As an extension of approval-based multiwinner voting (ABMV), our study is clearly related to the large body of literature on ABMV (see, e.g., (Aziz et al. 2018; Aziz and Lee 2020; Cygan et al. 2017; Kocot et al. 2019; Peters 2018a; Yang 2019, 2020)). Recently, extensions of standard ABMV have been proposed in the literature, including for instance ABMV with a variable number of winners (Kilgour 2016; Faliszewski, Slinko, and Talmon 2020), ABMV with labeled candidates (Bredereck et al. 2018; Celis, Huang, and Vishnoi 2018), ABMV with graph structured candidate set (Yang and Wang 2018), etc. However, to the best of our knowledge, our extension of ABMV has not been considered in the literature heretofore. It is also worth mentioning that a model which captures parallel single-winner elections with a common set of candidates has been studied recently (Boehmer et al. 2020). Particularly, this model aims to identify a highquality allocation of a set of candidates to a number of positions so that every position receives exactly one candidate and every candidate is allocated to at most one position. Our model is also related to the model of allocating indivisible goods. In this model, a set of indivisible goods are supposed to be allocated to several agents so that every good is allocated to exactly one agent and all goods are allocated. Each agent has a utility function to valuate the goods allocated to her. The goal is to compute an allocation that achieves some optimization objectives or fulﬁlls some desirable properties. We refer to Chapters 12 13 of (Brandt et al. 2016) for a comprehensive survey on this topic.

Preliminaries

We assume the reader is familiar with the basic notions of (parameterized) complexity such as NP-hardness and ﬁxedparameter tractability (FPT). For readers without these background, we refer to (Tovey 2002; Downey 2012). For an integer i, let [i] = {j N : 1 j i}. Multiwinner voting. An approval-based election is a tuple (C, V ) where C is a set of candidates and V is a multiset of votes cast by a set of voters. Each vote v V is deﬁned as a subset of C consisting of all the candidates approved by the corresponding voter. A committee is a subset

of candidates, and a k-committee is a committee of cardinality k. A k-committee selection rule (k-CSR) is a function that maps each election (C, V ) such that |C| k to a class of k-committees of C, called the winning k-committees. We focus on k-CSRs each of which determines the k-winning committees via a particular utility function. Precisely, a utility function maps each tuple (w, V ) of a committee w C and a multiset V of votes over C to a nonnegative rational number, which is the utility of V derived from w. We also call f(w, V ) the f score of w from V . The rule selects all kcommittees that yield the maximum possible utility among all k-committees. For notational brevity, throughout this paper we write x for a singleton {x}. For instance, f(c, V ) is exactly f({c}, V ). Table 1 summarizes utility functions widely studied in the literature. In this paper, we consider only utility functions f such that f( , V ) = f(w, ) = 0, which is the case for all utility functions in Table 1.

utility f(w, V )

AV P v V |v w| SAV P v V,v = |v w|

|v| CSAV P v V |v w|

|w| MSAV P v V,v = |v w| min{|v|,|w|} PAV P v V,v w = P|v w| i=1 1

i WAV P v V,v w = P|v w| i=1 1 2i 1 CCAV |{v V : v w = }|

Table 1: Where a value is not well-deﬁned, it is 0.

A utility function f is additive if for every nonempty w C, it holds that f(w, V ) = P c w f(c, V ). Moreover, f is weakly additive if for every integer k there is a utility function gk such that f(w, V ) = P c w gk(c, V ) for every k-committee w C. We call gk an additive realization of f of order k. Apparently, additive functions must be weakly additive. It is fairly easy to check that AV and SAV are additive, but other functions given in Table 1 are not. However, CSAV and MSAV are weakly additive. We assume that all utility functions are given as oracles. In addition, for weakly additive utility functions, we assume that their additive realizations of all possible orders are available when needed. Winners allocation. Let C be a set of candidates. In addition, let C1 C and C2 C be two subsets of C such that C1 C2 = C, and let V1 and V2 be two multisets of votes over C1 and C2, respectively. Let E1 = (C1, V1) and E2 = (C2, V2). We call (E1, E2) a double-election, and call each of V1 and V2 a voting community. For two nonnegative integers k1 and k2 such that k1 |C1|, k2 |C2|, and k1 + k2 |C1 C2|, a (k1, k2)-winners allocation of (E1, E2) is a tuple (w1, w2) such that

w1 C1 and w2 C2;

w1 w2 = ; and

|w1| = k1 and |w2| = k2.

In other words, w1 C1 and w2 C2 are the subsets of candidates allocated to the two communities V1 and V2 respectively so that no candidate is allocated to two subsets. As in the standard setting, we assume that each Vi, i [2], uses a utility function fi to valuate the committees. The goal of the model is to ﬁnd a winners allocation that provides certain desirable properties with respect to f1 and f2. These properties are deﬁned in the next section.

Social Welfare and Envy-freeness Needless to say, not all winners allocations of a double election are equally important. We start our exploration by studying numerous notions and properties which are helpful for us to distinguish important winners allocations from less important ones. Here, each property is deﬁned as a subset of winners allocations. We ﬁrst give the deﬁnitions of the properties, and then we study their implication relationships.

Properties of Winners Allocations First, we study three notions of social welfare. In the following notions, let (w1, w2) be a (k1, k2)-winners allocation of a double-election E = (E1 = (C1, V1), E2 = (C2, V2)). Let f1 and f2 be two utility functions.

Deﬁnition 1. Three types of social welfare with respect to (f1, f2) are deﬁned as follows.

Utilitarian social welfare (USW):

f1(w1, V1) + f2(w2, V2).

Egalitarian social welfare (ESW):

min{f1(w1, V1), f2(w2, V2)}.

Nash social welfare (NSW): (f1(w1, V1) f2(w2, V2))

For each X {USW, ESW, NSW}, we use XO(E, (k1, k2), (f1, f2)) to denote the property consisting of all optimal (k1, k2)-winners allocations of the double election E with respect to the utility functions f1 and f2. (In the notions, O stands for optimal ). By optimal, we meant a (k1, k2)-winners allocation of E with the maximum possible value of X among all (k1, k2)-winners allocations. It should be pointed out that the above social welfare have been also applied in other settings such as resource allocations (see, e.g., (Nguyen et al. 2014)). Each of the above notions has its own merits and which one is the best to apply tightly depends on the concrete settings. We refer to (Nguyen, Roos, and Rothe 2013) for a nice discussion on this issue. Next, we study three notions of envy-freeness aimed to identify winners allocations such that each of the two voting communities is happier with its own allocated winners than with those allocated to the other community. In particular, the ﬁrst notion states that it is impossible to make any of the voting communities better off by replacing some winners allocated to the community with the same number of winners allocated to the other community.

Deﬁnition 2 (envy-freeness (EF)). For each i [2], we say that Vi envy w3 i with respect to fi if there are w (w3 i

Ci) and w wi such that |w| = |w | and fi((wi \ w ) w, Vi) > fi(wi, Vi). The allocation (w1, w2) is EF with respect to (f1, f2) if the community Vi does not envy w3 i for both i [2].

The above notion concerns only whether one of V1 and V2 can be made better off by replacing some winners but ignores whether after the replacement the other community is guaranteed to have a committee not worse than the previously allocated one. This motivates us to study the protective envy-freeness (PEF) deﬁned as follows.

Deﬁnition 3 (PEF). For each i [2], we say that Vi protectively envy w3 i with respect to (f1, f2) if there are w (w3 i Ci), w wi, and w ((C3 i \ (wi w3 i)) (w C3 i)) such that

(1) |w| = |w | = |w |; (2) fi((wi \ w ) w, Vi) > fi(wi, Vi); and (3) the lose of the community V3 i after removing w can be compensated by the addition of w , i.e.,

f3 i((w3 i \ w) w , V3 i) f3 i(w3 i, V3 i).

The allocation (w1, w2) is PEF with respect to (f1, f2) if Vi does not protectively envy w3 i for both i [2].

The next notion, named replacement envy-freeness (REF), is stronger than the above one in the sense that replacements only take place inside w1 w2.

Deﬁnition 4 (REF). We sat that V1 and V2 replacement envy each other with respect to (f1, f2) if there are w 1 (w1 C2) and w 2 (w2 C1) such that

(1) |w 1| = |w 2|; (2) f1((w1 \ w 1) w 2, V1) f1(w1, V1); (3) f2((w2 \ w 2) w 1, V2) f2(w2, V2); and (4) at least one of the inequalities in (2) and (3) strictly holds.

The allocation (w1, w2) is REF with respect to (f1, f2) if V1 and V2 do not replacement envy each other.

Finally, we study the notion of Pareto optimality. A (k1, k2)-winners allocation is Pareto optimal (PO) if there are no other (k1, k2)-winners allocations which strictly improve the utility of one community without hurting the other.

Deﬁnition 5 (PO). The (k1, k2)-winners allocation (w1, w2) is PO if there does not exist a different (k1, k2)-winners allocation (w 1, w 2) such that f1(w 1, V1) f1(w1, V1), f2(w 2, V2) f2(w2, V2), and at least one of the two inequalities holds strictly.

For a notion X being one of EF, PEF, REF, and PO, let X(E, (k1, k2), (f1, f2)) be the property consisting of all (k1, k2)-winners allocations of the double election E that are X with respect to (f1, f2).

Implication Relationships Now we study the implication relationships among the notions introduced above. We say that a property (strictly) implies another if for every double election E, every two integers k1 and k2, and every two utility functions f1 and f2, the former with the arguments E, (k1, k2), and (f1, f2) is a

Figure 1: An arc from a property X to another property Y means that X implies Y.

(proper) subset of the latter with the same arguments. Two properties are independent if neither implies the other. The following theorem offers the implication relationships among the properties. The relationships hold for all utility functions and, moreover, for many natural utility functions the implication relationships are strict. In the general case, two different utility functions value k-committees differently. However, when every voter approves exactly one candidate and we want to select only one winner, almost all natural utility functions degenerate to the AV function. Let FAV be the set of all such utility functions. Precisely, a utility function f belongs to FAV if for every election (C, V ) where every vote in V is a singleton, it holds that f(c, V ) = AV(c, V ) = P v V |v {c}| for every c C. Clearly, all utility functions listed in Table 1 belong to FAV.

Theorem 1. The implication relationships among the properties USWO, ESWO, NSWO, EF, PEF, REF, and PO shown in Figure 1 hold. Moreover, if the two utility functions in the properties belong to FAV, the relationships are complete, in the sense that if it is not shown in the ﬁgure that a property X implies another property Y, then X does not imply Y.

One may wonder why we state the completeness only for utility functions in FAV. In fact, if this is not the case, certain implications won t be strict. Consider for instance the AV function and a constant function f such that f(w, V ) = 1 for all possible w and V . Then, it is easy to see that, with respect to these two utility functions, PO implies also USWO, ESWO, and NSWO. It is easy to ﬁnd a double election where EF winners allocations do not exist (e.g., C1 = C2 = {a, b}, all votes in V1 and V2 approve only a but not b, and k1 = k2 = 1). However, as there are always winners allocations with the maximum USW, Theorem 1 gives us the following result.

Corollary 1. Every double election admits nonempty PEF, REF, and PO (k1, k2)-winners allocations.

Complexity of Winners Allocations

Given the desirable properties deﬁned in the previous section, a natural question is then how efﬁciently can we compute a winners allocation that provides these properties. This is the focus of this section. In particular, we study the complexity of the following problem. Let X {USWO, ESWO, NSWO, EF, PEF, REF, PO}, and let f1 and f2 be two utility functions.

X WINNERS ALLOCATION W.R.T. (f1, f2) (X-WA-(f1, f2))

Given: A double election E = ((C1, V1), (C2, V2)) and two nonnegative integers k1, k2 such that k1 |C1|, k2 |C2|, and k1 + k2 |C1 C2|. Task: If X(E, (k1, k2), (f1, f2)) = , return a (k1, k2)- winners allocation from X(E, (k1, k2), (f1, f2)); otherwise, return ( , ).

As shown in the previous section, except for X = EF, it holds that X(E, (k1, k2), (f1, f2)) = .

Winners Allocations with Maximum Social Welfare For a utility function f, the COMMITTEE SELECTION problem is to compute a k-committee w C such that f(w, V ) f(w , V ) for all k-committees w C, where C is a given set of candidates, k |C| is a given nonnegative integer, and V is a given multiset of votes over C. COMMITTEE SELECTION is a special case of our problem USWO-WA-(f1, f2) where one of k1 and k2 is zero. It is known that if f is additive, then COMMITTEE SELECTION is polynomial-time solvable (see, e.g., (Yang and Wang 2019)): one ﬁrst ranks the candidates according to a nonincreasing order of their f scores, from the largest to the smallest, and then the ﬁrst k candidates constitute a solution. It is easy to see that this algorithm is extendable to weakly additive functions. In the following, we further extend the result to USWO-WA-(f1, f2).

Theorem 2. If both f1 and f2 are weakly additive, then USWO-WA-(f1, f2) is polynomial-time solvable.

Now we consider winners allocations that provide the maximum egalitarian/Nash social welfare w.r.t. utility functions that are weakly additive. Somewhat interestingly, in this setting the complexity varies. We ﬁrst show that if one of the utility functions is AV or CSAV, and the other is weakly additive, we still have polynomial-time solvability results. To this end, we ﬁrst show the polynomial-time solvability of an intermediate problem deﬁned below.

WINNERS COMPUTATION FOR f1 AND f2 (WC-(f1, f2))

Given: A double election E = ((C1, V1), (C2, V2)), two nonnegative integers k1 and k2 such that k1 |C1|, k2 |C2|, and k1 + k2 |C1 C2|, and one nonnegative rational number r1. Task: Return a (k1, k2)-winners allocation (w1, w2) of E with the maximum value of f2(w2, V2) under the restriction that f1(w1, V1) = r1, or return ( , ) if such a winners allocation does not exist.

We also study a decision version of WC-(f1, f2), where we have an additional rational number r2 in the input, and the question is whether E admits a (k1, k2)-winners allocation (w1, w2) such that f1(w1, V1) = r1 and f2(w2, V2) r2. We denote this problem by WD-(f1, f2).

Theorem 3. Let f be a weakly additive utility function. Then, WC-(AV, f) is polynomial-time solvable.

Proof (sketch). Let I = ((E1, E2), k1, k2, r) be an instance of WC-(AV, f) where E1 = (C1, V1) and E2 = (C2, V2). For ease of exposition, let f1 be the AV function and let f2

be an additive realization of f of order k2. We assume that r |V1| |C1| (otherwise we directly return ( , )). Our algorithm ﬁrst splits the given instance into polynomially many subinstances and then solves each subinstance in polynomial time via a dynamic programming algorithm. In particular, each subinstance is speciﬁed by three nonnegative integers k 1 min{k1, |C1 \ C2|}, k 2 min{k2, |C2 \ C1|}, and s1 r, and the goal is to compute a (k1, k2)-winners allocation (w1, w2) of (E1, E2) that has the maximum possible f2(w2, V2) under the restrictions that |w1 (C1 \ C2)| = k 1, |w2 (C2 \ C1)| = k 2, and f1(w1 (C1 \C2), V1) = s1, if it exists. We solve the subinstance as follows. To compute a k 1-committee of C1 \ C2 of AV score s1 from V1, we resort to pseudopolynomial-time algorithms for the classic κ-SUBSET SUM problem (see, e.g., (Koiliaris and Xu 2019)). Particularly, we solve a κ-SUBSET SUM instance (A = {f1(c, V1) : c C1 \ C2}, k 1, s1), where the goal is to ﬁnd k 1 integers in A whose sum is s1. As the input size of I is at least |C1| + |V1| and every number in A is at most |V1| |C1|, the algorithm in fact runs in polynomial time in the input size of I. If the κ-SUBSET SUM instance is a NOinstance, we discard this subinstance of I. Otherwise, Let w 1 be the set of the k 1 candidates corresponding to k 1 numbers returned by the κ-SUBSET SUM algorithm. Next, we order candidates in C2 \C1 according to their f2 scores received from V2, from the highest to the lowest. Let w 2 be the set of the ﬁrst k 2 candidates in the order and let s2 denote the f2 score of these k 2 candidates received from V2, i.e., s2 = f2(w 2, V2). The task now is to identify, for every i [2], ki k i candidates from C1 C2 so that putting them into w i provides us a solution. Obviously, if k1 k 1 + k2 k 2 > |C1 C2|, we can immediately discard the subinstance. So, we assume that this is not the case. The algorithm continues as follows. If C1 C2 = , we do the following: if k 1 = k1, k 2 = k2, and s1 = r, we return (w 1, w 2) for the subinstance of I; otherwise, we discard the subinstance. We may assume now that C1 C2 = . Let (c1, c2, . . . , ct) be a ﬁxed order of C1 C2. For each i [t], let C i = {cj : j [i]}. We maintain a 4-dimensional table T(ℓ1, ℓ2, i, r ) of four nonnegative integers such that i [t], ℓ1 min{i, k1 k 1}, ℓ2 min{i, k2 k 2}, and r r s1. The entry is supposed to store the maximum possible f2 score of an ℓ2-committee wi 2 C i from V2, under the restriction that there is an ℓ1committee of C i \ wi 2 of f1 score exactly r from V1 (if such an ℓ1-committee under this restriction does not exist, is stored in the entry). The values of base entries can be calculated in polynomial time based on the deﬁnition of the table. The remaining entries are computed via the following recursive formula. In particular, if f1(ci, V1) r , we deﬁne

T(ℓ1, ℓ2, i, r ) = max{T(ℓ1 1, ℓ2, i 1, r f1(ci, V1),

T(ℓ1, ℓ2 1, i 1, r ) + f2(ci, V2), T(ℓ1, ℓ2, i 1, r )}.

The three entries in the max function respectively correspond to that ci is allocated to the community V1, to the community V2, or none of the communities V1 and V2. If, however, f1(ci, V1) > r , ci cannot be allocated to V1, and

hence in this case we deﬁne T(ℓ1, ℓ2, i, r ) =

max{T(ℓ1, ℓ2 1, i 1, r ) + f2(ci, V2), T(ℓ1, ℓ2, i 1, r )}.

The output of the above dynamic programming algorithm is a 3-tuple whose components are, respectively, denoted by s(k 1, k 2, s1), w1(k 1, k 2, s1) and w2(k 1, k 2, s1). Precisely,

s(k 1, k 2, s1) = T(k1 k 1, k2 k 2, t, r s1) + s2.

If s(k 1, k 2, s1) 0, then using standard backtracking technique of dynamic programming algorithms, we can compute two disjoint subsets w 1, w 2 C1 C2 such that f2(w 2, V2) is maximized under the restrictions that |w 1| = k1 k 1, |w 2| = k2 k 2, and f1(w 1, V1) = r s1. In this case, we deﬁne w1(k 1, k 2, s1) = w 1 w 1 and w2(k 1, k 2, s1) = w 2 w 2. However, if s(k 1, k 2, s1) < 0, we discard this subinstance. For the original instance I, if all subinstances are discarded, we return ( , ). Otherwise, let ˆk1, ˆk2, and ˆs1 be such that s( ˆk1, ˆk2, ˆs1) = maxk 1,k 2,s1{s(k 1, k 2, s1)}, where k 1, k 2, and s1 run over all integers such that the subinstance speciﬁed by k 1, k 2, and s1 is not discarded. Then, we return (w1( ˆk1, ˆk2, ˆs1), w2( ˆk1, ˆk2, ˆs1)) for I.

The algorithm in the proof of Theorem 3 can be adapted for the case where f1 is CSAV. Furthermore, observe that for f1 {AV, CSAV} and f2 being weakly additive, NSWO/ESWO-WA-(f1, f2) is polynomial-time reducible to WC-(f1, f2). We then have the following result.

Theorem 4. Let f1 {AV, CSAV} and f2 be a weakly additive utility function. Then, ESWO/NSWO-WA-(f1, f2) is polynomial-time solvable.

One may wonder whether the polynomial-time solvability in Theorem 3 remains if we replace AV with some other additive functions like SAV. Somewhat surprisingly, this cannot be the case unless P=NP, as we can show that in this case the problem becomes NP-hard. More interestingly, our NPhardness result holds even in a very special case, namely, the case where the two elections in the given double election are both CI and VI. (see Introduction for the deﬁnitions of CI and VI, and related references) It should be noticed that the algorithm in the proof of Theorem 3 can be easily adapted to apply for all weakly additive functions f1 and f2, by changing the fourth component in the dynamic programming table into rational numbers which run over all possible scores of committees. However, for f1 being some other additive functions like SAV, we could not expect the size of the table to be polynomially bounded in the input size, because of the fourth component.

Theorem 5. WD-(SAV, SAV) is NP-hard even when C1 = C2 = C, V1 = V2 and, moreover, (C, V1) is both VI and CI.

Proof. We prove the theorem by a reduction from the κRATIONAL (0, 1)-SUBSET problem, where given a multiset A = { a1

b2 , . . . , an

bn } of n rational numbers, an integer k, and a rational number r, the question is whether there are k numbers in A whose sum is r. Very recently, Wojtczak (2018) proved that this problem is strongly NP-hard (note that if A contains only integers, the problem is weakly

NP-hard). We assume that 0 < ai

bi < 1 for all i [n]. 1 Let s = P i [n] ai bi . We construct a WD-(SAV, SAV) instance ((C, V1), (C, V2), k1, k2, r1, r2) as follows. For each ai

bi A, i [n], we create a set C(i) of bi candidates. For each i [n], we choose an arbitrary but ﬁxed candidate in C(i), and let c(i) C(i) denote this candidate. Let C = {c(i) : i [n]} denote the set of the n selected candidates. Let C = S i [n] C(i). Clearly, C consists of P i [n] bi candidates. This completes the construction of the candidates. The following votes are created in both V1 and V2. For each ai

bi A, i [n], we create ai votes each of which approves exactly the candidates in C(i). In addition, for every i [n] we create k + 1 votes each of which approves exactly the candidate c(i). In total, each of V1 and V2 consists of (k+1) n+P i [n] ai votes. We complete the reduction by setting k1 = k, k2 = n k, r1 = r + k (k + 1) and r2 = s r + (n k) (k + 1). Now we prove the correctness of the reduction. ( ) Let H [n] be a set of k integers such that P i H ai bi = r. Let w1 = {c(i) C : i H} and w2 = {c(i) C : i [n] \ H}. Due to the construction, each candidate c(i) C has SAV score ai

bi + k + 1 from both V1 and V2, i.e.,

f1(c(i), V1) = f2(c(i), V2) = ai

bi + k + 1. (1)

Then, f1(w1, V1) = P i H ai bi + k + 1 = r+k (k+1) =

r1 and f2(w2, V2) = P i [n]\H ai bi + k + 1 = s r + (n k) (k + 1) = r2. So, (w1, w2) is a desired winners allocation. ( ) Assume that the constructed WD-(SAV, SAV) instance is a YES-instance. We ﬁrst prove the following claim. Claim 1. For every k-committee w C such that f1(w, V1) = r1, it holds that w C . Proof of Claim 1. Assume for the sake of contradiction that there is a k-committee w C such that f1(w, V1) = r1 but w \ C = . W.l.o.g., let x = |w C |. Hence, we have x k 1. From the construction of the votes, for every i [n], it holds that every candidate in C(i) \ {c(i)} has SAV score exactly ai

bi , which is smaller than 1 as we assumed. In addition, as pointed out above, every c(i) where i [n] has SAV score exactly ai

bi + k + 1. It follows that

f1(w, V1) (k x) + X

c(i) w C ,i [n]

(k x) + x (k + 1) + x k2 + k 1 < r1.

a contradiction. This completes the proof of the claim. As k1 + k2 = n, and the SAV score of every candidate in S i [n] (C(i) \ {c(i)}) is strictly smaller than that of anyone in C , we know that if the WD-(SAV, SAV) instance

1In the strongly NP-hardness proof of k-RATIONAL (0, 1)- SUBSET in (Wojtczak 2018), each ai

bi is a positive rational number smaller than 2. We can transform this instance into an equivalent instance by replacing each ai

bi with ai 2bi and replacing r with r

is a YES-instance, it must admit a solution (w1, w2) such that w2 C . Furthermore, by Claim 1, we know that w1 w2 = C holds. According to the analysis for the other direction (see Equation (1)), the SAV score of the committee C from each of V1 and V2 is P i [n] ai bi + k + 1 = s + n (k + 1), which is exactly r1 + r2. It follows that the SAV score of w1 from V1 and the SAV score of w2 from V2 are r1 = r+k (k+1) and r2 = s r+(n k) (k+1), respectively, which further implies that P c(i) w1,i [n] ai bi = r. Finally, we show that (C1, V1) is both VI and CI. To this end, we deﬁne a linear order over C where, for every i [n], candidates in C(i) are consecutive. Analogously, we deﬁne a linear order over V1 where for every i [n], the ai votes approving C(i) and the k+1 votes approving only the candidate c(i) are consecutive, with the latter k + 1 votes ordered after the ai votes. It is easy to check that the candidates approved in every vote constructed above are consecutive in the candidates-order, and for every candidate c all votes approving c are consecutive in the votes-order.

Based on the hardness reduction in the proof of Theorem 5, we establish the NP-hardness of ESWO/NSWO-WA- (f1, f2) for f1 and f2 being SAV or MSAV.

Theorem 6. ESWO/NSWO-WA-(f1, f2) where f1, f2 {SAV, MSAV} are NP-hard. This holds even when the two elections in the given double election are both VI and CI.

Envy-Free Winners Allocations This section is devoted to the computation of envy-free winners allocations. The following corollary is a consequence of Theorems 1 and 2.

Corollary 2. Let X {PEF, REF, PO}, and let f1 and f2 be two utility functions that are weakly additive. Then, XWA-(f1, f2) is polynomial-time solvable.

As shown earlier, EF winners allocations do not always exist. Nevertheless, we show below that once they exist, we could compute in polynomial time an EF (k1, k2)-winners allocation with the maximum USW, when the utility functions used are weakly additive.

Theorem 7. If f1 and f2 are both weakly additive, determining if an EF (k1, k2)-winners allocation exists can be done in polynomial time. Moreover, if such an allocation exists, an EF (k1, k2)-winners allocation with the maximum USW can be computed in polynomial time.

Now we study utility functions f1 and f2 for at least one of which the COMMITTEE SELECTION problem is NP-hard.

Theorem 8. If for at least one of f1 and f2 COMMITTEE SELECTION is NP-hard, then REF-WA-(f1, f2) is NP-hard.

Theorems 1 and 8 bring to us the following corollary.

Corollary 3. If for at least one of f1 and f2 COMMITTEE SELECTION is NP-hard, then for each X {USWO, NSWO, EF, PEF, PO}, X-WA-(f1, f2) is NP-hard.

The above corollary, however, does not extend to computation of winners allocations of maximum ESW. To verify

USWO ESWO NSWO EF PEF/REF/PO

(AV/CSAV, wadd) P P (Thm. 4) P P (wadd, wadd) P (Thm. 2) NP-h (Thm. 6) P (Thm. 7) P FPT (|C1 C2|, k1 + k2 [Thms. 10, 12]) (PAV/CCAV, f) NP-h NP-h (Thm. 9) NP-h NP-h NP-h (Thm. 8) FPT (|V1 V2| [Thm. 11]) FPT: |V1 V2|

Table 2: In the table, wadd stands for weakly additive , and f can be any function in Table 1. Results in gray are implied by other results in the table. The NP-hardness holds even when the two elections in the given instance are both CI and VI.

this, consider the case where f1 is CCAV for which COMMITTEE SELECTION is NP-hard (Procaccia, Rosenschein, and Zohar 2008), and f2 is a constant utility function such that f2(w, V2) = 0 for all w and V2. Then, all winners allocations have the same ESW 0, implying that ESWO-WA- (f1, f2) for these speciﬁc functions f1 and f2 is polynomialtime solvable. Therefore, to derive an analogous result for ESWO, we need further restrictions. We say that a utility function f is a polynomial bound of another utility function f if for every multiset V of votes over a set C of candidates and every nonnegative integer k |C|, we can construct in polynomial time in |V | + |C| a multiset V of votes over C such that f (c, V ) f(w, V ) holds for all kcommittees w C and all candidates c C. It is not hard to see that every utility function shown in Table 1 is a polynomial bound of every function including itself in the table. For instance, SAV is a polynomial bound of PAV because for every C, V , and k as above, we can construct a multiset V of |C| |V | k votes each of which approves all candidates. Let m = |C| and n = |V |. Then, every candidate has SAV score m n k 1

m = n k from V , while every k-committee has PAV score at most n Pk i=1 1

i n k from V . With the above notion, we have the following theorem.

Theorem 9. Let f1 and f2 be two utility functions. If COMMITTEE SELECTION for f1 is NP-hard, and f2 is a polynomial bound of f1, then ESWO-WA-(f1, f2) is NP-hard.

Some Fixed-Parameter Tractability Results

Given the NP-hardness results established in previous sections, one could be interested in ﬁxed-parameter algorithms for these problems with respect to some natural parameters. The number of candidates and the number of votes are two natural parameters. It is trivial to check that with respect to the parameter |C1 C2|, all the NP-hardness results established in this paper are FPT. This motivates us to consider a generally smaller parameter |C1 C2|.

Theorem 10. For weakly additive utility functions f1 and f2, ESWO-WA-(f1, f2) and NSWO-WA-(f1, f2) are FPT with respect to the parameter |C1 C2|, where C1 and C2 are the two sets of candidates in the given double election. In particular, they can be solved in time O (4|C1 C2|).

Now we study the parameter the number of votes. We show that with respect to this parameter, computing winners allocations with the maximum USW is FPT for f1 and f2 being any functions listed in Table 1.

Theorem 11. If both f1 and f2 are utility functions in Table 1, then USWO-WA-(f1, f2) is FPT with respect to the number of total votes.

Finally, we discuss the parameterized complexity of winners allocation with respect to the number of candidates that are allocated in total, i.e., the parameter k1 + k2.

Theorem 12. Let f1 and f2 be two weakly additive utility functions. Then, ESWO-WA-(f1, f2) and NSWO-WA- (f1, f2) are FPT with respect to the number of allocated candidates.

Concluding Remarks

We proposed a model of winners allocation where given two elections whose candidate sets may intersect, the goal is to allocate k1 and k2 winners to two voting communities respectively. We studied several properties of this model, including three kinds of social welfare, three types of envyfreeness, and the Pareto optimality property. For these properties, we explored their implication relationships (Theorem 1 and Figure 1). Then, we investigated the complexity of calculating winners allocations that provide these properties (Theorems 2 9). If both utility functions used by the voting communities are weakly additive, we designed polynomialtime algorithms for almost all properties except for egalitarian/Nash social welfare, for which the complexity varies, depending on the utility functions. Particularly, when the utility functions are SAV or MSAV, computing a winners allocation with the maximum egalitarian/Nash social welfare is NP-hard and, moreover, this holds even when the two elections in the given double election are both VI and CI. When one of the utility functions is not additive, we often have hardness results for all properties. Finally, for hardness results, we also studied their parameterized complexity and derived several ﬁxed-parameter algorithms (Theorems 10 12). Table 2 summarizes these results. Recently, a set of axiomatic properties such as the justiﬁed representation (JR), extended JR, proportional JR have been advocated as desirable properties for approval-based multiwinner voting in certain circumstances. We refer to (Aziz et al. 2015, 2018; S anchez-Fern andez et al. 2017) for the deﬁnitions of these properties. It is easy to see that there are double elections where there are no (k1, k2)-winners allocations (w1, w2) such that w2 and w2 satisfy these properties for both elections simultaneously. In fact, the exemplary double election to show the nonexistence of EF winners allocations (after Theorem 1) directly works here.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2015. Justiﬁed Representation in Approval Based Committee Voting. AAAI, 784 790.

Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the Complexity of Extended and Proportional Justiﬁed Representation. AAAI, 902 909.

Aziz, H.; and Lee, B. E. 2020. The Expanding Approvals Rule: Improving Proportional Representation and Monotonicity. Soc. Choice Welfare 54(1): 1 45.

Boehmer, N.; Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2020. Line-Up Elections: Parallel Voting with Shared Candidate Pool. SAGT, 275 290.

Brandt, F.; Brill, M.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2015. Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates. J. Artif. Intell. Res. 53: 439 496.

Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds. 2016. Handbook of Computational Social Choice. Cambridge University Press.

Bredereck, R.; Faliszewski, P.; Igarashi, A.; Lackner, M.; and Skowron, P. 2018. Multiwinner Elections With Diversity Constraints. AAAI, 933 940.

Brezis, E. S.; and Birukou, A. 2020. Arbitrariness in the Peer Review Process. Scientometrics 123(1): 393 411.

Celis, L. E.; Huang, L.; and Vishnoi, N. K. 2018. Multiwinner Voting with Fairness Constraints. AAAI, 144 151.

Cygan, M.; Kowalik, L.; Socala, A.; and Sornat, K. 2017. Approximation and Parameterized Complexity of Minimax Approval Voting. AAAI, 459 465.

Downey, R. 2012. A Parameterized Complexity Tutorial. LATA, 38 56.

Elkind, E.; and Lackner, M. 2015. Structure in Dichotomous Preferences. IJCAI, 2019 2025.

Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; and Rothe, J. 2011. The Shield That Never Was: Societies with Single-Peaked Preferences Are More Open to Manipulation and Control. Inf. Comput. 209(2): 89 107.

Faliszewski, P.; Slinko, A.; and Talmon, N. 2020. Multiwinner Rules with Variable Number of Winners. ECAI, 67 74.

Kilgour, D. M. 2016. Approval Elections with a Variable Number of Winners. Theor. Decis. 81(2): 199 211.

Kocot, M.; Kolonko, A.; Elkind, E.; Faliszewski, P.; and Talmon, N. 2019. Multigoal Committee Selection. IJCAI, 385 391.

Koiliaris, K.; and Xu, C. 2019. Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Trans. Algorithms 15(3): 40:1 40:20.

Liu, H.; and Guo, J. 2016. Parameterized Complexity of Winner Determination in Minimax Committee Elections. AAMAS, 341 349.

Nguyen, N.; Nguyen, T. T.; Roos, M.; and Rothe, J. 2014. Computational Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation. Auton. Agent. Multi-AG. 28(2): 256 289. Nguyen, T. T.; Roos, M.; and Rothe, J. 2013. A Survey of Approximability and Inapproximability Results for Social Welfare Optimization in Multiagent Resource Allocation. Ann. Math. Artif. Intell. 68(1-3): 65 90. Peters, D. 2018a. Proportionality and Strategyproofness in Multiwinner Elections. AAMAS, 1549 1557. Peters, D. 2018b. Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-winner Elections. AAAI, 1169 1176. Procaccia, A. D.; Rosenschein, J. S.; and Zohar, A. 2008. On the Complexity of Achieving Proportional Representation. Soc. Choice Welfare 30(3): 353 362. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Val, P. B.; and Skowron, P. 2017. Proportional Justiﬁed Representation. AAAI, 670 676. Tovey, C. A. 2002. Tutorial on Computational Complexity. Interfaces 32(3): 30 61. Wojtczak, D. 2018. On Strong NP-Completeness of Rational Problems. CSR, 308 320. Yang, Y. 2020. On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting. AAMAS, 1584 1592. Yang, Y. 2019. Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting IJCAI, 637 643. Yang, Y.; and Wang, J. 2018. Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness. IJCAI, 576 582. Yang, Y.; and Wang, J. 2019. Complexity of Additive Committee Selection with Outliers. AAMAS, 2291 2293.