Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness

1 Introduction

Approval based multiwinner voting aims to select a subset of candidates, often called committee (or winners), from a class of admissible sets (subsets of candidates) based on the approval ballots of voters. It has found applications in a wide range of areas such as recommendation systems, political elections, etc. Most of the previous work is mainly concerned with the specific setting where admissible sets are those of cardinality exactly k [Aziz et al., 2017; Faliszewski et al., 2017a; Brill et al., 2017a; 2017b; Faliszewski et al., 2017b; S´anchez-Fern´andez et al., 2017; Lackner and Skowron, 2017; Yang and Wang, 2018]. The multiwinner rules in this setting are often referred to as k-committee selection rules in the literature. This specific setting is relevant to many real-world applications such as parliamentary elections where the number of winners is predefined. However, in this setting, the relations among the candidates which may be crucial to the decision-making procedure are completely ignored. Imagine for example that a famous band plans to tour several cities in a far away country in the next month. As the members are only able to take 5 days out of their busy schedules for the tour, it is very important for the members to take into account the distances between the cities when making their decision. In this paper, we study multiwinner rules with admissible sets being represented with respect to a graph where candidates are considered as vertices, and edges indicate the relations between candidates (e.g., whether there is an irreconcilable conflict between them, whether the two candidates can work together efficiently, etc.).

Let C be a set of candidates. In our setting, we are additionally given a graph G = (C,A). The goal is to find a committee that has some combinatorial property, e.g., the subgraph induced by the committee is connected, is an independent set, etc. When the combinatorial property is "the subgraph induced by the committee includes exactly k vertices", we have the k-committee selection rules. We first investigate the question of how efficiently an optimal committee can be calculated in this setting, i.e., the complexity of the winner determination problem. Whether winners with respect to a voting rule can be calculated efficiently is an important factor to evaluate the quality of the rule. We particularly focus on approval voting (AV), net-approval voting (NAV), proportional approval voting (PAV), Chamberlin-Courant approval voting (CCAV), satisfaction approval voting (SAV), and netSAV (NSAV) in our setting 1 , aiming to reveal how different combinatorial restrictions on admissible sets shape the complexity of winner determination for these rules. Previously, the complexity of winner determination for admissible sets of size exactly k has been investigated. In particular, Aziz et al. [2015] gave polynomial-time algorithms for SAV and AV, and established an NP-hardness reduction for PAV. The NP-hardness for CCAV was also proved by researchers (see, e.g., [Betzler et al., 2013]).

First, we consider the universal admissible sets, i.e., every subset of candidates is an admissible set. We show that in this case winner determination for all aforementioned rules is polynomial-time solvable. Then, we study connected admissible sets, i.e., subsets that induce connected graphs, and bounded radius admissible sets, i.e., subsets that induce graphs of bounded radius. In this two cases, we show NPhardness for NSAV and NAV, and polynomial-time solvability for other rules. We further show that winner determination for NSAV and NAV is fixed-parameter tractable (FPT) with respect to the treewidth of the associated graph G = (C,A).

1 These rules are initially mainly designed as k-committee selection rules, but they can be extended to our setting naturally.

Moreover, we consider independent admissible sets, i.e., the selected committee should induce an independent set in the associated graph G = (C,A). In contrast to the general polynomial-time solvability in other cases, we show that winner determination for all aforementioned rules with independent admissible sets is NP-hard, even when there is only one vote. For PAV and CCAV, the NP-hardness even holds when the associated graph is a path (in this case there is more than one vote). However, for other rules (AV, SAV, NAV, NSAV), the problem becomes polynomial-time solvable when the associated graph is a tree. In fact, we show FPT results with respect to the treewidth of the associated graph. Our results are summarized in Table 2.

Strategyproofness is another important factor to evaluate the quality of voting rules. We explore the strategyproofness of multiwinner rules with different classes of admissible sets, and obtain some interesting results. For instance, for admissible sets of size exactly k, AV is known to be strategyproof (see [Aziz et al., 2015] for the details), in the sense that changing one's vote does not result in a committee which includes more approved candidates of this voter to be selected. However, we show that this is no more the case with respect to independent admissible sets. Our results concerning strategyproofness are summarized in Table 3.

To the best of our knowledge, except the universal and fixed-sized admissible sets (k-committee selection rules), other classes of admissible sets have not been studied in the literature so far. Recently, Kilgour [2016] studied several multiwinner rules where the number of winners is not fixed. These rules can be considered as multiwinner rules with the universal admissible sets. Later, Faliszewski, Slinko, and Talmon [2017c] studied the complexity of winner determination for several multiwinner rules considered in [Kilgour, 2016], including particularly AV and NAV.

Finally, we would like to point out that multiwinner voting with other kinds of restricted committees has also been considered recently (see, e.g., [Bredereck et al., 2018; Celis et al., 2017]). In addition, our paper is related to the work of Talmon [2018] who studies a generalization of CCAV by taking into account the relations between voters. In particular, the relations between voters are indicated by a graph whose vertices one-to-one correspond to the voters.

2 Preliminaries

An election is a tuple E = (C, V ) where C is a set of candidates and V is a multiset of votes, each of which is a subset of C. For a vote v ∈ V and a candidate c ∈ C, we say v approves c if and only if c ∈ v. We assume that every voter approves at least one candidate (one may consider an empty vote as an abstained vote) 2 . Let 2C be the power set of C.

A multiwinner rule ϕ is a function that assigns to each election (C, V ) a subset ϕ(C, V ) ∈ AC, where AC ⊆ 2C is the codomain and each element of AC is called an admissible set. The elements in ϕ(C, V ) are called the winners of (C, V ) with respect to ϕ. One of the most widely studied codomains is arguably the one consisting of all subsets of C of cardinality k. In this case, the multiwinner rule is often referred to as a k-committee selection rule.

2 We make this assumption purely for ease of exposition. All our results hold without this assumption.

In this paper, we mainly consider multiwinner rules defined based on scoring functions f : 2C × 2C → R. For a subset C ′ ⊆ C, the score of C ′ in (C, V ) with respect to f is ∑v∈V f(v,C ′ ). The multiwinner rule ϕf selects an admissible set C ′ ∈ AC maximizing ∑v∈V f(v,C ′ ) 3 . Table 1 summarizes some well-studied scoring functions.

Obviously, the number of admissible sets can be exponential in the number of candidates. To overcome this drawback, we propose a compact representation scheme based on graph properties. A graph property G is a class of graphs. In this scheme, we are given a graph G = (C,A). Fixing a graph property G, the class of admissible sets AGC consists of all C ′ ⊆ C such that G[C ′ ] ∈ G, where G[C ′ ] is the subgraph induced by C ′ . We consider the following graph properties.

Universal This property consists of all graphs, i.e., every subset of C is an admissible set.

Fixed-sized This is so far the most widely studied property. Particularly, it consists of all graphs of exactly k vertices.

Independent The property consists of all graphs without edges. In some cases, there may exist irreconcilable conflicts between two candidates (e.g., two politicians may possess completely different political opinions). In this case, an edge between such two candidates indicates the existence of an irreconcilable conflict between them.

Connected This property consists of all connected graphs. Different from the independent property, in some setting, the edge between two candidates can be a positive indication (e.g., an edge means that they can cooperate efficiently, or they can communicate directly). In this case, a committee which induces a connected subgraph is of particular interesting.

3 If several admissible sets have the same highest score, a tiebreaking method is used to break the tie.

Bounded radius This property consists of all graphs with radius at most d, where d is a constant. The radius of a graph is the minimum integer d′ such that there exists a vertex which is of distance at most d′ from every other vertex. The distance between two vertices is the length of a shortest path between them.

For a graph property G and a multiwinner rule ϕf , we study the following problem.

We assume familiarity with basic concepts of complexity, parameterized complexity, and graph theory, such as NPhard, FPT, and treewidth. We refer to [Tovey, 2002] for the concept of NP-hard, and Chapters 1 and 7 of [Cygan et al., 2015] for FPT and treewidth.

3 Universal and Connected Admissible Sets

It is known that for fixed-sized admissible sets, winner determination for PAV and CCAV is NP-hard [Aziz et al., 2015; Betzler et al., 2013]. In contrast, we show that winner determination for PAV, CCAV, SAV, and NSAV is polynomial-time solvable for the universal admissible sets. Winner determination for AV and NAV with universal admissible sets is known to be polynomial-time solvable [Faliszewski et al., 2017c].

Theorem 1. For G being the universal property and ϕf ∈ {CCAV, PAV, SAV, NSAV}, WD-(G, ϕf ) is polynomial-time solvable.

Proof. Observe that for CCAV, PAV, and SAV, the set C of all candidates is always an optimal committee. So, for these rules we need only to check if the score of C is at least r. Now we consider NSAV. For each candidate c, we define

Let C ′ = {c ∈ C | g(c) > 0}. If C ′ ̸= ∅, we return Yes if and only if the score of C ′ is at least r. Otherwise, we return Yes if and only if there is a candidate c such that g(c) ≥ r.

For connected admissible sets, we also obtain polynomialtime solvability results for CCAV, PAV, AV, and SAV, but obtain NP-hardness results for NAV and NSAV even if there is only one vote. This is because that for the first four rules, adding a candidate to a committee never decreases the score of the committee. Hence, there must be an optimal committee which induces a connected component. However, this is not the case for NAV and NSAV. Generally speaking, the NP-hardness arises because in some cases we need to carefully select a limited number of candidates of negative scores whose role is only to connect candidates of positive scores.

Theorem 2. WD-(G, ϕf ) is polynomial-time solvable for ϕf ∈ {CCAV, PAV, AV, SAV} and G being the connected property.

Our NP-hardness results are based on reductions from the following NP-hard problem [Gonzalez, 1985].

RESTRICTED EXACT COVER BY 3-SETS (RX3C) Input: A finite set U = {u1, . . . , u3κ} and a collection S = {s1, . . . , s3κ} of 3-subsets of U s.t. every

u ∈ U occurs in exactly three subsets of S. Question: ∃S′ ⊆ S such that |S′ | = κ and every

u ∈ U occurs in exactly one subset of S′ ?

Theorem 3. For G being the connected property and ϕf ∈ {NAV, NSAV}, WD-(G, ϕf ) is NP-hard, even if there is only one vote.

Proof for NAV. Given an RX3C instance (U, S) where |U| = |S| = 3κ, we create an instance of WD-(G, ϕf ) as follows. Without loss of generality, assume that κ ≥ 4. For each u ∈ U, we create a candidate c(u). For each s ∈ S, we create a candidate c(s). Let C(U) = {c(u) | u ∈ U} and C(S) = {c(s) | s ∈ S}. In addition, we create a candidate b. Hence, C = C(U)∪C(S)∪{b}. In the graph G = (C, A), we create an edge between b and every c(s), where s ∈ S. Additionally, for every c(s), s ∈ S, and every c(u), u ∈ U, we create one edge between them if and only if u ∈ s. Moreover, we create one vote v which approves all candidates in C(U) and disapproves all other candidates, i.e., v = C(U). Finally, we set r = 2κ - 1. Clearly, the construction can be done in polynomial time.

Assume that there is an exact 3-set cover S′ ⊆ S. Let w = {c(s) | s ∈ S′ }∪C(U)∪{b}. Clearly, |w| = 4κ+1 and w induces a connected graph in G. Due to the construction, all the 3κ approved candidates of the vote v are in w. Hence, |v ∩w| = 3κ and |w \ v| = κ+1. It follows that the score of w is |v∩w|-|w\v| = 3κ-(κ+1) = r. Nowwe prove the correctness for the opposite direction. Let w be a committee with score at least 2κ-1. Moreover, let x = |w∩C(U)| and y = |w ∩ C(S)|. We claim first that b ∈ w. Assume for the sake of contradiction that this is not the case. Notice that the subgraph induced by C(U) ∪C(S) is a bipartite graph where every vertex is of degree 3. From the fact that w induces a connected subgraph, we know that y ≥ x-1 2 . Hence, the score of w is |w ∩ v| - |w \ v| = x - y ≤ x+1 2 ≤ 3κ+1 2 < r (due to x ≤ 3κ and κ ≥ 4), a contradiction. Hence, from now on assume that b ∈ w. In this case, to make the candidates in (w∩C(U))∪{b} connected, w contains at least x3 candidates in C(S), i.e., y ≥ x3 . Hence, the score of w is x - y - 1 ≤ 23 x-1. If the score of w is at least 2κ-1, it must be that x = 3κ and y = κ. So, C(U) ⊆ w. As w induces a connected subgraph, every c(u), where u ∈ U, is adjacent to at least one c(s) ∈ w, where s ∈ S, such that u ∈ s (due to the construction). As y = κ, the set {s ∈ S | c(s) ∈ w} must be an exact 3-set cover.

In the following, we show that if the associated graph has bounded treewidth, then winner determination for both NAV and NSAV with connected admissible sets becomes FPT. Our algorithm is based on standard dynamic programming technique to deal with the parameter treewidth (see, e.g., Chapter 7 in [Cygan et al., 2015]). Generally, we define for each candidate c ∈ C a score g(c) = ∑v∈V f(v, {c}), and consider g(c) as the weight of c in the associated graph. Then, the question is to find a connected subgraph with maximum total weight in the associated graph.

Theorem 4. For G being the connected property and ϕf ∈ {NAV, NSAV}, WD-(G, ϕf ) is FPT with respect to the treewidth of the associated graph.

4 Bounded Radius

In this section, we study bounded radius admissible sets. In the WD-(G, ϕf ) instance constructed in the proof of Theorem 3, every optimal committee includes b and κ candidates in C(S) to connect the candidates in C(U). The induced subgraph has radius 2. This directly gives us the following result.

Corollary 1. WD-(G, ϕf ) is NP-hard where ϕf ∈ {NAV, NSAV} and G is the class of graphs with radius at most 2, even if there is only one vote.

Moreover, similar to the connected property, we can show the following FPT results.

Theorem 5. WD-(G, ϕf ) is FPT with respect to the treewidth of the associated graph, where ϕf ∈ {NAV, NSAV} and G is the class of graphs with radius d for some constant d.

In contrast to the NP-hardness results in Corollary 1, we have polynomial-time solvability results for other rules.

Theorem 6. WD-(G, ϕf ) is polynomial-time solvable, where G is the class of graphs of radius at most d and ϕf ∈ {PAV, CCAV, SAV, AV}.

5 Independent Admissible Sets

Now we study independent admissible sets. Unlike the connected and bounded radius properties for which one can find in polynomial time a largest admissible set, in this case finding a largest admissible set is equivalent to the MAXIMUM

INDEPENDENT SET problem (MIS) which is NP-hard [Garey and Johnson, 1979]. In an election with only one vote which approves all candidates, an optimal committee corresponds to a maximum independent set in the associated graph, and vice versa. Based on this, we have the following result.

Theorem 7. For G being the independent property and ϕf ∈ {AV, PAV, CCAV, SAV, NAV, NSAV}, WD-(G, ϕf ) is NP-hard, even when there is only one vote.

It is well-known that MIS is polynomial-time solvable in trees (see, e.g., [Gavril, 1972]). Hence, one may expect that winner determination with independent admissible sets becomes polynomial-time solvable if the associated graph is a tree. However, the following theorem refutes such expectation for CCAV and PAV.

ALMOST 2-SAT

Input: A set X = {x1, . . . , xm} of Boolean variables, a set CL = {cl1, . . . , cln} of clauses each of which consists of exactly two literals of variables in X, and a positive integer ℓ.

Question: Is there a truth-assignment δ : X → {0, 1} which satisfies at least ℓ clauses in CL? Here, a clause cl ∈ CL is satisfied by δ if there exists a literal x ∈ cl such that δ(x) = 1 or a literal x ∈ cl such that δ(x) = 0.

It is known that the ALMOST 2-SAT problem is NP-hard (see, e.g., [Alon et al., 2011; Garey et al., 1976]).

Theorem 8. For G being the independent property and ϕf ∈ {CCAV, PAV}, WD-(G, ϕf ) is NP-hard, even if the associated graph is a path and every voter approves only two candidates.

Proof for PAV. Let (X = {x1, . . . , xm},CL = {cl1, . . . , cln}, ℓ) be an instance of the ALMOST 2-SAT problem. We create an instance of WD-(G, ϕf ) as follows. For each variable x ∈ X, we create two candidates c(x) and c(x). In addition, we create m-1 dummy candidates c1, . . . , cm-1. The edges in the associated graph are as follows. For every xi ∈ X, 1 ≤ i ≤ m, there is an edge between c(xi) and c(xi). Therefore, any admissible set includes at most one of c(xi) and c(xi). In addition, for every ci, 1 ≤ i ≤ m- 1, there is an edge between ci and c(xi), and an edge between ci and c(xi+1). The votes are created according to CL. Concretely, for each cl ∈ CL, we create three votes v(cl, 1), v(cl, 2), and v(cl, 3) such that (1) v(cl, 1) and v(cl, 2) are the same, and they approve c(y) for every literal y ∈ cl; and (2) v(cl, 3) approves c(y) for every literal y ∈ cl. Hence, every voter approves two candidates, and dummy candidates are not approved by any vote. Finally, we set r = 32 · (ℓ + n). Clearly, the construction can be done in polynomial time.

Assume that there is a truth-assignment δ : X → {0, 1} that satisfies at least ℓ clauses. Let CL′ be the set of all clauses in CL that are satisfied by δ. So, |CL′ | ≥ ℓ. Let

We shall show that the score of w is at least r. Observe that for every clause cl ∈ CL′ , either both literals in cl are true or exactly one of them is true with respect to δ. Due to the construction, in the former case, both approved candidates of v(cl, 1) and v(cl, 2) are in w, and none of the approved candidates of v(cl, 3) is in w. Hence, we have that f(v(cl, 1), w) = f(v(cl, 2), w) = 32 and f(v(cl, 3), w) = 0. In the latter case, exactly one of the approved candidates of each v(cl, i), 1 ≤ i ≤ 3, is in w, which implies that f(v(cl, 1),w) = f(v(cl, 2),w) = f(v(cl, 3),w) = 1. In both cases, we have that ∑3i=1 f(v(cl, i), w) = 3. Consider now a clause cl ∈ CL\CL′ , i.e., a clause that is not satisfied by the truth-assignment δ. Due to the construction, none of the approved candidates of v(cl, 1) and v(cl, 2) is in w, and both approved candidates of v(cl, 3) are in w. It then follows that ∑3i=1 f (v(cl, i), w) = 0 + 0 + 32 . Therefore, we have

We prove the other direction now. Observe that there is an optimal committee which does not include any dummy candidate and, moreover, for every x ∈ X it includes exactly one of c(x) and c(x). Let w be such an optimal committee. Consider the truth-assignment δ : X → {0, 1} such that δ(x) = 1 if and only if c(x) ∈ w. Let ℓ′ be the number of satisfied clauses by δ. Similar to the above discussion, we can conclude that for each satisfied clause cl it holds that ∑1≤i≤3 f(v(cl, i),w) = 3, and for each unsatisfied clause cl′ it holds that ∑1≤i≤3 f(v(cl′ , i),w) = 32 . So, the score of w is 3ℓ′ + 3 2 (n-ℓ′ ) = 32 (ℓ′ +n). If theWD-(G, ϕf ) instance is a Yes-instance, then 3 2 (ℓ′ + n) ≥ r, implying that ℓ′ ≥ ℓ and the ALMOST 2-SAT instance is a Yes-instance.

Now we study the complexity of winner determination for other rules for independent admissible sets, when the associated graph has bounded treewidth. A scoring function f : 2C ×2C → R is additive if for every vote v ⊆ C and every committee w ⊆ C it holds that f(v, w) = ∑c∈w f(v, {c}). Amultiwinner rule ϕf is additive if f is additive. It is known that AV, SAV, NAV, and NSAV are additive [Kilgour, 2010]. Note that PAV and CCAV are not additive.

Theorem 9. Let G be the independent property and ϕf an additive multiwinner rule. Then, WD-(G, ϕf ) is FPT with respect to the parameter treewidth of the associated graph.

6 Strategyproofness

In this section, we consider the strategyproofness of multiwinner rules in Table 1 with respect to different classes of admissible sets. Unlike single-winner voting, the strategyproofness of (approval based) multiwinner voting had not received sufficient attention until very recently. The reason is that for multiwinner voting, one is first faced with the question of how to extract voters' preferences over committees from voters' approval ballots. Two natural solutions which have been considered recently are based on the size of the intersection of a vote and a committee (cardinality-strategyproofness), and the Hamming distance between a vote and a committee (Hamming-strategyproofness) [Aziz et al., 2015; Peters, 2018]. For a multiset V of votes, a vote v ∈ V , and a nonempty subset v′ ⊆ C, we use (V-v, v′ ) to denote the multiset obtained from V by replacing v with v′ .

A multiwinner rule ϕf is cardinality-strategyproof (resp. Hamming-strategyproof) if for every election (C, V ), no voter can make himself/herself better off by misreporting his/her vote, i.e., there do not exist v ∈ V and nonempty v′ ⊆ C such that |v ∩ w′ | > |v ∩ w| (resp. |v \ w′ | + |w′ \ v| < |v \ w| + |w \ v|), where w = ϕf(C, V ) and w′ = ϕf (C, (V-v, v′ )).

In this paper, we use a different approach. In particular, we use f(v,w) to infer the preferences of voters over committees. We believe that this approach makes sense because the voting rule simply selects the committee based on f(v,w). Somewhat surprisingly, it has not been studied previously.

We say a multiwinner rule ϕf is f-strategyproof if for every election (C, V ), there do not exist v ∈ V and nonempty v′ ⊆ C such that f(v,w′ ) > f(v,w), where w = ϕf(C, V ) and w′ = ϕf(C, (V-v, v′ )). We mainly study f-strategyproofness. However, we point out that almost all of our results hold for the cardinality- and Hammingstrategyproofness too (see the detailed discussion later). We refer to Table 3 for an overview of our results.

First, we show that for universal admissible sets, many rules in Table 1 are f-strategyproof.

Theorem 10. For universal admissible sets, PAV, AV, SAV, NAV, and NSAV are f-strategyproof, if the lexicographic tiebreaking method is used.

Proof (Sketch). The theorem for PAV, AV, and SAV follows from the fact that each optimal committee contains every candidate approved by at least one vote. The proof for NAV and NSAV is based on the fact that both rules are additive.

In fact, the f-strategyproofness for PAV, SAV, and AV in Theorem 10 holds regardless of which tie-breaking method is used. Observe that for PAV, AV, and SAV, f-strategyproof is equivalent to cardinality-strategyproof. So, Theorem 10 also shows that these rules are cardinality-strategyproof, assuming the lexicographic tie-breaking method is used.

Now, we show the f-strategyproofness for CCAV in all classes of admissible sets studied in this paper. Notice that according to the definition of f-strategyproofness, only someone who has no representative in the current committee has an incentive to manipulate.

Theorem 11. For all classes of admissible sets in Table 2, CCAV is f-strategyproof, if the lexicographic tie-breaking method is used.

Proof. Let ϕf be CCAV. Assume for the sake of contradiction that there is an election E = (C, V ), a vote v ∈ V , and a nonempty v′ ⊆ C such that f(v,w′ ) > f(v,w), where w = ϕf(C, V ) and w′ = ϕf(C, (V-v, v′ )). This implies that v ∩ w = ∅ and v ∩ w′ ̸= ∅. For ease of exposition, let V ′ = (V-v, v′ ) and E′ = (C, V ′ ) be the election after v is changed to v′ . The fact that v ∩ w = ∅ implies that w in E′ has at least the same score as that in E, i.e., f(V ′ ,w) ≥ f(V,w). In addition, v ∩ w′ ̸= ∅ implies that the score of w′ in E and E′ are the same, i.e., f(V,w′ ) = f(V ′ ,w′ ). As w = ϕf (C, V ) and w′ = ϕf (C, V ′ ), it holds that f(V, w) ≥ f(V, w′ ) and f(V ′ , w′ ) ≥ f(V ′ , w). Summarizing all above, we have that f(V,w) = f(V,w′ ) = f(V ′ ,w) = f(V ′ ,w′ ). In other words, w and w′ are tied in both E and E′ . From ϕf (C, V ) = w, it follows that w is lexicographically smaller than w′ . However, from ϕf(C, V ′ ) = w′ , it follows that w′ is lexicographically smaller than w, a contradiction.

It is easy to verify that for fixed-sized admissible sets, AV and NAV are equivalent and, moreover, they are fstrategyproof if the lexicographic tie-breaking method is used. Aziz et al. [2015] showed the non-strategyproofness of PAV and SAV with fixed-sized admissible sets, if the lexicographic tie-breaking method is used. In the following we give examples to show the non-f-strategyproofness for all the remaining cases. We remark that our examples are robust to all deterministic tie-breaking methods. Moreover, except the examples for AV, all examples below also apply to cardinalitystrategyproofness and Hamming-strategyproofness.

Fixed-sized admissible sets

NSAV Consider an election with ten candidates and five votes v1 = {a, b}, v2 = v3 = v4 = {a, c, d}, and v5 = {a, b, e, f}. Candidates not shown are not approved by any vote. Let k = 2. The optimal 2-committees are {a, c} and {a, d}. After v1 drops a, the only optimal 2-committee is {a, b}.

Independent admissible sets

AV Consider four candidates a, b, c, d, and three votes v1 = {a, b, c}, v2 = v3 = {a}. The associated graph is a star with a being the center. Then, {a} and {b, c, d} are the optimal committees before and after the first vote is changed to {b, c, d}, respectively. This example also applies to the cardinality-strategyproofness.

PAV Consider five candidates a, b, c, d, e, and four votes v1 = {a, b, c}, v2 = v3 = {a, c, d}, v4 = {d, e}. In the associated graph, a is adjacent to e, and d is adjacent to b

• and c, and there are no other edges. The only optimal committee is {a, d}. However if v1 drops a, the only two optimal committees are {a, b, c} and {b, c, e}.

SAV Consider five candidates a, b, c, d, e and three votes v1 = {a, d, e}, v2 = v3 = {a, b, c}. The associated graph is a clique without the edge between d and e, i.e., there is an edge between every two candidates, except the one between d and e. Before and after v1 is changed to {d, e} the optimal committees are {a} and {d, e}, respectively.

NSAV/NAV Consider three candidates a, b, c and three votes v1 = v2 = {a, b, c}, v3 = {a}. The associated graph is a star with a being the center. Before and after v1 is changed to {b, c} the optimal committees are {a} and {b, c}, respectively.

Examples for connected and bounded radius admissible sets are obtained from the above ones by only changing the associated graphs.

Finally, we remark that Peters [2018] recently studied an impossibility theorem which in general says that proportionality and strategyproofness are incompatible. The impossibility theorem tells us the non-strategyproofness of PAV with fixed-sized admissible sets, but does not tell us any other results obtained in this section. The reasons are as follows. First, Peters only considered k-committee selection rules, and hence the impossibility theorem only applies to the fixedsized admissible sets. Second, AV, SAV, NSAV, and NAV do not satisfy the proportionality properties used in Peters' impossibility theorem. Third, Peters' theorem was established based on a different concept of strategyproofness.

7 Conclusion

We have studied multiwinner voting with different classes of admissible sets that are represented by graph properties. We mainly focused on the complexity of the winner determination problem for six concrete multiwinner rules (Table 1). Our results reveal that the complexity of the problem depends closely on the admissible sets. In addition, we discussed strategyproofness of multiwinner rules with different classes of admissible sets. Our results concerning the complexity of winner determination and strategyproofness are summarized in Tables 2 and 3, respectively. According to our study, CCAV has the most f-strategyproofness results in Table 3, and AV has the most polynomial-time solvability results in Table 2. Winner determination for SAV and AV has the same complexity in Table 2, but AV is strategyproof with respect to fixed-sized admissible sets, while SAV is not.

There remain many intriguing problems to study in the future. For instance, what kinds of axiomatic properties can we study for different classes of admissible sets? For fixedsized admissible sets, several proportionality properties have been proposed, including the justified representation, proportional justified representation, extended justified representation, etc. [Aziz et al., 2017; S´anchez-Fern´andez et al., 2017]. In general, such properties say that large group of voters who have common approved candidates deserve a corresponding number of representatives in the k-committee. In the precise definitions of these properties, the committee size k plays a significant role. However, in other classes of admissible sets studied in this paper, we do not fix the size of the committee. Hence, it is interesting to see how to carry over these proportionality properties to other classes of admissible sets. In addition, apart from graph properties, one could consider other compact representations of admissible sets. For instance, one could use propositional logic for this purpose by considering each candidate as a variable in a set of CNFs, and admissible sets are those which satisfy one or some of the given CNFs. Similar ideas have been used in the study of hedonic games [Elkind and Wooldridge, 2009]. Finally, investigating the complexity of strategic voting problems such as manipulation, bribery for multiwinner rules with different classes of admissible sets is also a prominent research direction.

Acknowledgments

The work is supported by the National Natural Science Foundation of China (Grant No. 61702557) and the China Postdoctoral Science Foundation (Grant No. 2017M612584).