Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting

1 Introduction

Investigating the complexity of various strategic voting problems has been an active topic in Computational Social Choice over the last three decades. Since the pioneering papers [Bartholdi et al., 1992; Bartholdi et al., 1989], many manipulation, control, and bribery problems have been proposed for single-winner voting rules. Recently, these problems have been extended to multiwinner voting systems. Enriching this line of research, we propose some natural manipulation and control problems for approval-based multiwinner voting rules, and investigate the complexity of these problems for approval voting (AV), satisfaction approval voting (SAV), net-satisfaction approval voting (NSAV), proportional approval voting (PAV), approval-based Chamberlin-Courant voting (ABCCV), and the Minimax approval voting (MAV).

A necessary notion in the study of manipulation is the preference of a voter over all possible outcomes. Unlike ranking-based single-winner voting rules where every voter has a linear preference over all candidates and the outcome is a single winner, in approval-based multiwinner voting it is even not clear how to deduce voters' preferences over committees based on their dichotomous preferences over candidates. A number of approaches for this purpose have been proposed recently (see, e.g., [Lackner and Skowron, 2018; Laslier and Van der Straeten, 2016; Peters, 2018]). For example, a voter may prefer a committee to another one if the former contains more of her truthful approved candidates. In a more conservative situation, a voter is more satisfied with the former one only if the former one contains not only more of her approved candidates but also all of her approved candidates included in the latter one. The two approaches lead to the concepts of cardinality-strategyproof and subset-strategyproof respectively when only one manipulator is considered (see, e.g., [Peters, 2018]). In contrast to the celebrated Gibbard-Satterthwaite theorem for singlewinner voting [Gibbard, 1973; Satterthwaite, 1975], there exist strategyproof multiwinner voting rules such as the AV rule (with respect to the above two concepts). However, many multiwinner voting rules are not strategy-proof. For example, Peters [2018] recently showed that any multiwinner voting rules which satisfy some proportional properties are not cardinality- and subset-strategyproof. In addition, Aziz et al. [2015] showed that SAV is not cardinalitystrategyproof. Motivated by these non-strategy-proofness results, many multiwinner manipulation problems have been proposed recently. Particularly, Aziz et al. [2015] studied the WINNER MANIPULATION and WINNER SET MANIPULATION problems. In the WINNER MANIPULATION problem we are given an election, a distinguished candidate, and an integer ℓ, and the question is whether we can add ℓ additional votes so that the distinguished candidate is included in the winning committee. In the WINNER SET MANIPULATION problem, there are multiple distinguished candidates, and the question is whether we can add ℓ additional votes so that the distinguished candidates are exactly the winners. In all of these problems, it is assumed that the manipulators have one clear target set of candidates/candidate whom they want to make the winners. However, in some cases, manipulators only want to improve the outcome, and there may be exponentially many outcomes which are preferred to the current outcome. In these cases, the above assumption seems not to be very natural, since asking the manipulators to enumerate all improved outcomes and solve the problem for each enumeration is not acceptable from the complexity point of view.

In this paper, we study two new versions of manipulation problems where some voters, referred to as manipulators, want to improve the election result by coordinately misreporting their truthful approved candidates. In particular, manipulators judge the results with respect to the two approaches discussed above. Notice that unlike the above manipulation problems, in our problems manipulators do not fix the candidates whom they want to make winners. In addition, we study some control problems called CONSTRUCTIVE CONTROL BY ADDING VOTERS/CANDIDATES (CCAV/CCAC) and CONSTRUCTIVE CONTROL BY DELETING VOTERS/CANDIDATES (CCDV/CCDC) for multiwinner voting. These problems are direct generalizations of the extensively studied control problems for single-winner voting rules [Faliszewski and Rothe, 2016].

We obtain many interesting results. For instance, we show that our manipulation problems are NP-hard even when there are more manipulators than non-manipulators, but become polynomial-time solvable if there are a constant number of manipulators. This stands in contrast to many other manipulation problems for both single-winner and multiwinner voting rules, where one usually has NP-hardness results when there is even one or two manipulators, but has polynomialtime solvability results when the number of manipulators is larger than the number of non-manipulators [Aziz et al., 2015; Bartholdi et al., 1989; Davies et al., 2014]. For control problems, we also reveal how the number of distinguished candidates, the committee size, and their relation shape the response of voting rules to the control problems.

2 Preliminaries

We assume the reader is familiar with the concepts of NPhardness, polynomial-time solvability, and fixed-parameter tractability (FPT).

In the approval model, an election is a tuple (C, V ) where C is a set of candidates and V a multiset of votes cast by a set of voters. Each vote v ∈ V is a non-empty subset of C, consisting of the candidates approved by the corresponding voter. So, two votes can approve exactly the same candidates and this explains why we use the notion of multiset for votes. For ease of exposition, we exchangeably use the terms vote and voter. For a subset C ′ ⊆ C and a submultiset V ′ ⊆ V , (C ′ , V ′ ) is (C, V ) restricted to C ′ and V ′ . Precisely, (C ′ , V ′ ) is obtained from (C, V ) by first removing all votes not in V ′ , and then removing all candidates not in C ′ from every remaining vote. For a candidate c ∈ C, we denote by V (c) the multiset of votes approving c, i.e., V (c) = {v ∈ V | c ∈ v}. For C ′ ⊆ C, let V (C ′ ) = ⋃c∈C′ V (c). Moreover, for a submultiset V ′ ⊆ V of votes, let C(V ′ ) denote the set of candidates approved in at least one vote in V ′ , i.e., C(V ′ ) = ⋃v∈V ′ v. For a submultiset V ′ ⊆ V and a multiset U of |V ′ | votes, let (V-V ′ ,U) be the multiset obtained from V by replacing V ′ with U. A multiwinner voting rule maps each election (C, V ) and an integer k to a class of k-subsets of C, called winning k-committees. In practice, when there are several winning k-committees, a tie-breaking scheme is used to select one from them.

We study some important approval-based multiwinner voting rules which can be categorized into two groups. With respect to each rule, each k-subset of candidates receives a score and the winning k-committees are those with the desired score. For the first group of rules the score of a committee is the sum of the scores of its members. These rules are referred to as additive rules in the literature.

Approval voting (AV) The score of a candidate c is the number of votes approving c. The winning k-committees are those with the highest score.

Satisfaction approval voting (SAV) Each candidate c receives 1 |v| points from each vote v approving c; hence, the score of c is ∑c∈v∈V 1 |v| . Similar to AV, winning kcommittees consist of those with the highest score, i.e., committees w ⊆ C with the maximum possible value of ∑v∈V |v∩w| |v| among all subsets of k candidates. SAV was proposed by Brams and Kilgour [2014].

Net-satisfaction approval voting (NSAV) This rule is a variant of SAV which captures the idea that if addition of approved candidates in the winning k-committee increases the satisfaction of a voter, then addition of disapproved candidates should decrease the satisfaction. Let m be the number of candidates. The satisfaction of a vote v derived from an approved candidate is measured as 1 |v| and from a disapproved candidate is 1 m-|v| . This rule aims to maximize voters' satisfaction and hence winning k-committees w are those with the maximum value of ∑v∈V ( |w∩v| |v| - |w\v| m-|v| ) among all subsets of k candidates 1 . Here, the score of each candidate c is ∑c∈v∈V 1 |v| - ∑c̸∈v∈V 1 m-|v| . NSAV was proposed by Kilgour and Marshall [2012].

Now we give the definitions of the second group of rules.

Approval-based Chamberlin-Courant voting (ABCCV)

A voter is satisfied by a committee if this committee includes at least one of her approved candidates. The score of a committee is the number of voters satisfied by it, and winning k-committees are those with the maximum score. ABCCV is a variant of the original rules proposed by Chamberlin and Courant [1983], and was suggested by Thiele [1895].

Proportional approval voting (PAV) The score of a committee w ⊆ C is ∑v∈V,v∩w̸=∅ (∑|v∩w| i=1 1i ). Winning k-committees are those with the maximum score. PAV seems to be first studied by Thiele [1895].

Minimax approval voting (MAV) The Hamming distance between w ⊆ C and v ⊆ C is |w\v|+|v\w|. The score of a committee w is the maximum Hamming distance between w and the votes, i.e., maxv∈V (|w\v|+|v\w|). Winning k-committees are those having the smallest score. This rule was proposed by Brams et al. [2007].

It should be pointed out that calculating a winning kcommittee for the second group of rules is NP-hard [Aziz et al., 2015; LeGrand, 2004; Procaccia et al., 2008], standing in contrast to the polynomial-time solvability for additive rules.

Now we formulate the problems studied in this paper. Let ϕ be a multiwinner voting rule.

CARDINALITY-BASED COALITION MANIPULATION (CBCM)

Given: An election (C, V ), the current winning kcommittee w ∈ ϕ(C, V, k) ⊆ C for some integer k, and a submultiset VM ⊆ V of votes cast by some voters called manipulators.

Question:

Is there a multiset U of |VM| votes such that for all winning k-committees w′ ∈ ϕ(C, (V-VM , U), k), it holds that |v ∩w′ | > |v ∩w| for all v ∈ VM?

1 By convention, if |v| =m, we take |w\v| m-|v| = 0.

We can replace |v ∩ w′ | > |v ∩ w| in the above definition with (v∩w) ⊂ (v∩w′ ) to obtain a variant of the CBCM problem which we call SUBSET-BASED COALITION MANIPULATION (SBCM).

Now we extend the definitions of four standard singlewinner voting control problems to multiwinner voting. These control problems model the scenario where some external agent (e.g., the election chair) aims to make some distinguished candidates the winners by modifying the election.

CONSTRUCTIVE CONTROL BY ADDING VOTERS (CCAV)

In the CCAV problem, the votes in V are referred to as registered votes and the ones in U are unregistered votes.

CONSTRUCTIVE CONTROL BY DELETING VOTERS (CCDV)

CONSTRUCTIVE CONTROL BY ADDING CANDIDATES (CCAC)

In the above definitions, we call C the registered set of candidates and D the unregistered set of candidates.

CONSTRUCTIVE CONTROL BY DELETING CANDIDATES (CCDC)

Notice that CCAV, CCDV, CCAC, and CCDC with the restriction |J| = k = 1 are exactly the extensively studied constructive control (by adding/deleting voters/candidates) problems for single-winner voting (precisely, the unique-winner model of the problems) [Faliszewski and Rothe, 2016].

A multiwinner voting rule ϕ is immune to a control type (adding/deleting voters/candidates) if it is impossible to make some J ⊆ C, which is not contained in the current winning kcommittee, be included in all winning k-committees, by performing the corresponding operation. Otherwise, we say ϕ is susceptible to this control type.

Remark. In the above control problems, the goal of the external agent is to make the distinguished candidates be included in all winning k-committees. This is natural in many situations. For example, when the external agent is not aware of the tie-breaking scheme, or when a randomized tie-breaking scheme is used, the external agent may want to make sure that her favorite candidates become winners with no risk at all. The above situation also motivates our requirement on w′ in the manipulation problem.

Additionally, we would like to point out that our hardness results also apply to multiwinner voting rules which always select exactly one winning k-committee by utilizing a specific tie-breaking scheme (see, e.g., [Bredereck et al., 2017] for descriptions of some tie-breaking schemes). In fact, our hardness reductions are established carefully to avoid ties. Moreover, our P- and FPT-algorithms for the additive rules can be adapted to solve these variants when ties are broken lexicographically.

3 RelatedWork

Meir et al. [2008] proposed some control and manipulation problems and considered ranking-based multiwinner voting rules where each voter holds a linear preference over all candidates. In their models, candidates have utilities to strategic agents who attempt to achieve a winning k-committee yielding as maximum total utilities as possible. In our control problems, the strategic agents have some fixed candidates whom they want to make winners. We remark that NPhardness proofs of our problems can be modified to show the NP-hardness of their utility-involved variants by assigning to some candidates very high utilities.

Aziz et al. [2015] and Bredereck et al. [2017] studied other manipulation problems where the manipulators have not cast their votes and want to make exactly one distinguished candidate be included in the winning k-committee. Aziz et al. [2015] also studied the WINNER SET MANIPULATION problem which seeks a given number of additional votes so that a given k-subset of candidates becomes the winning k-committee. A generalization of this problem has been studied in [Bredereck et al., 2017]. Recently, Faliszewski et al. [2017] studied bribery problems for approval-based multiwinner voting rules, where the goal is to ensure one distinguished candidate to be included in the winning k-committee by applying a limited number of modification operations.

Our paper is also related to the works of Laslier and Van der Straeten [2016], Peters [2018], and Yang and Wang [2018] who studied strategyproofness of approval-based multiwinner voting. However, they were concerned with mathematical properties of these rules and focused only on one manipulator.

In addition, our study is somewhat related to the control problems in group identification [Yang and Dimitrov, 2018]. Group identification models the scenario where voters and candidates (individuals) coincide and the goal is to select a subset of socially qualified candidates without the size constraint. The group control problems consist in making some given distinguished individuals socially qualified by adding/deleting/partitioning the individuals.

Finally, we would like to point out another line of research concerning manipulation in approval-based multiwinner voting. In particular, in this setting, it is assumed that voters have linear order preferences over candidates and the question is whether voters have incentive to submit non-sincere votes in order to improve the result. Recall that a vote is sincere with respect to a linear order over candidates if the approved candidates are exactly those ranked above some threshold candidate in the linear order. Moreover, voters compare different outcomes based on some preference extension principles such as the Kelly extension principle, G¨ardenfors extension principle, etc. We refer to [Barber`a et al., 2004; Endriss, 2013] and references therein for further discussions.

4 Manipulation

In this section, we consider the manipulation problems and show that in general these problems are NP-hard. Our reductions are from the classic VERTEX COVER problem. A vertex cover of a graph G is a subset of vertices whose removal results in a graph without any edge.

VERTEX COVER

Given: A graphG = (N,A) whereN is the set of vertices and A is the set of edges, and an integer κ.

Question: Does G have a vertex cover of size κ?

It is well-known that the VERTEX COVER problem remains NP-hard even in 3-regular graphs [Mohar, 2001].

Theorem 1. CBCM and SBCM for AV are NP-hard.

Proof. Let (G = (N,A), κ) be a VERTEX COVER instance where G is 3-regular. Let n = |N| and m = |A|. Without loss of generality, assume that m > 4. For each vertex b ∈ N, we create a candidate denoted still by b for simplicity. Additionally, we create κ candidates c1, c2, . . . , cκ disjoint from N. Therefore, there are in total n + κ candidates. We create the following votes. First, we create 4 non-manipulative votes each of which approves exactly c1, . . . , cκ. In addition, for each edge {b, b′ } ∈ A, there is a manipulator whose truthful approved candidates are exactly b and b′ . Let the vote cast by the manipulator be v(b, b′ ) = {b, b′ }. Therefore, there are m + 4 votes in total. Finally, we set k = κ. The current winning k-committee is w = {c1, . . . , cκ} regardless of tie-breaking schemes. Notice that w does not include any candidate approved by some manipulator. As a consequence, this instance has the same answer to CBCM and SBCM.

Now we prove the correctness of the reduction. Suppose that G has a vertex cover S ⊆ N of size κ. If all manipulators turn to approve exactly the candidates corresponding to S, the score of each candidate in S increases from 3 to m > 4, and hence candidates in S form the unique winning k-committee. For the opposite direction, if there exists no vertex cover of size κ, then no matter which κ′ ≤ κ candidates from N are in the final winning k-committee after the manipulators change their votes, there is at least one manipulative vote v(b, b′ ) such that none of b and b′ is in the final winning k-committee.

Similar to the reduction in the above proof, we can show the NP-hardness of CBCM and SBCM for SAV. Clearly, after all manipulators change to approve candidates corresponding to a vertex cover S of size κ, the SAV score of each candidate in S changes from 3/2 to m/κ. Given this, to prove the NP-hardness of CBCM and SBCM for SAV, we need only to create m - 5 further votes approving c1, . . . , cκ so that in the original election each ci has SAV score (m- 1)/κ 2 . Moreover, we can also show the NP-hardness of CBCM and SBCM for other rules studied in this paper.

Theorem 2. CBCM and SBCM for SAV, NSAV, PAV, ABCCV, and MAV are NP-hard.

In the NP-hardness proofs, the number of manipulators is even larger than the number of non-manipulators. The NPhardness in this case stands in contrast to the polynomialtime solvability of the classic coalition manipulation problem (see [Faliszewski and Rothe, 2016] for the definitions) for many ranking-based single-winner voting rules, where the manipulators can always make the distinguished candidate the winner by ranking the distinguished candidate in the top and ranking other candidates greedily. On the other hand, for a constant number t of manipulators, the classic coalition manipulation problem for many single-winner voting rules is already NP-hard even when t = 1, 2 [Bartholdi et al., 1989; Davies et al., 2014]. However, this is not the case for our problems. In particular, we show that CBCM and SBCM for AV, SAV, and NSAV are polynomial-time solvable when the number of manipulators is a constant.

Theorem 3. CBCM and SBCM for AV, SAV, and NSAV are polynomial-time solvable if there are a constant number of manipulators.

Proof for CBCM. Let ((C, V ),w ⊆ C, k = |w|, VM) be a given instance where w is the current winning k-committee. Observe that for AV, SAV, and NSAV, there are optimal solutions where all manipulators approve the same candidates in the final election and, moreover, these candidates are all from C(VM), the union of the candidates approved by the manipulators. Let t = |VM| be the number of manipulators which is a constant. The following algorithm is mainly for AV but can be modified easily to work for SAV and NSAV. For a subset U ⊆ V of votes, let C ∗ (U) be the set of candidates that are approved exactly by the votes in U, i.e., C ∗ (U) = {c ∈ C | V (c) = U}. For each non-empty subset S ⊆ VM, we guess a non-negative integer xS ≤ |C ∗ (S)| which indicates the number of candidates from C ∗ (S) that are expected to be included in the final winning k-committees. In addition, based on the above observation, we can guess the number k′ ≤ k of candidates approved by all manipulators in the final election. In effect, these guesses split the original instance into polynomially many subinstances each of which takes as input the original one together with a positive integer k′ ≤ k, and a nonnegative integer xS for every non-empty S ⊆ VM, and asks if there is a k′ -subset w′ ⊆ C(VM) so that (1) all manipulators prefer w′ to w; (2) for every non-empty S ⊆ VM, w′ includes exactly xS candidates from C ∗ (S); and (3) all winning k-committees contain w′ after all manipulators turn to approve exactly the candidates in w′ . We discard all subinstances except the ones satisfying the following conditions.

2 The correctness of the reduction also relies on the assumption that κ < 23 · (m-1) which does not change the NP-hardness of the VERTEX COVER problem in 3-regular graphs [Mohar, 2001].

First, as we pick k′ ≤ k winning candidates from C(VM), we require that ∑∅̸=S⊆VM xS = k′ . For each vote v ∈ VM, we require that ∑∅̸=S⊆VM,v∈S xS > |v ∩ w|. This is to ensure that after the manipulators change their votes, the final winning k-committee includes more approved candidates in every manipulative vote. For every combination of the guessed integers satisfying the above conditions, we further do the following. We let all manipulators approve xS certain candidates in each C ∗ (S) where ∅ ̸= S ⊆ VM and xS > 0. In particular, these xS candidates are those in C ∗ (S) that have the highest scores with respect to the non-manipulative votes V \ VM. Let C ′ be the set of all such candidates. Then, if C ′ belongs to all winning k-committees now (it suffices to check if there are at most k - k′ candidates not in C ′ that have at least the same score than that of the one in C ′ with the minimum score) the subinstance is a Yes-instance; otherwise, it is a No-instance.

Another important parameter that has been widely discussed in voting problems is the number of candidates. In many real world applications, this parameter is small [Fishburn and Brams, 2005; Mattei and Walsh, 2013]. In this case, we can enumerate all subsets of candidates in O(2m) time, where m is the number of candidates. Fixing some C ′ ⊆ C of at most k candidates such that every voter prefers every kcommittee containing C ′ to the current winning k-committee, for AV, SAV, and NSAV, the optimal strategy for the manipulators is that all of them approve exactly the candidates in C ′ . We have the following theorem.

Theorem 4. CBCM and SBCM for AV, SAV, and NSAV are FPT with respect to the number of candidates.

5 Control

When considering AV as a single-winner voting rule (i.e., when k = 1), it has been proved that CCAV and CCDV for AV are NP-hard [Baumeister et al., 2010; Lin, 2010]. Notably, when k = 1, PAV, ABCCV, and AV are identical. As a consequence, CCAV and CCDV for PAV and ABCCV are also NP-hard when k = 1. For CCAV and CCDV, it remains to consider SAV, NSAV, and MAV.

Theorem 5. CCAV and CCDV for SAV and NSAV are NPhard even when k = 1.

For MAV, we also prove that CCAV is NP-hard even when k = 1 via a reduction from the RX3C problem and based on the characterization of MAV single winners stated in the following lemma.

Lemma 1. Let (C, V ) be an election and A ⊆ V be the submultiset of votes approving the maximum number of candidates, i.e., A = argmaxv∈V {|v|}. Moreover, let C ′ be the set of candidates approved by all votes in A, i.e., C ′ = ⋂v∈A v. Then, if C ′ ̸= ∅, candidates in C ′ are tied as MAV single winners. Otherwise, all candidates are tied as MAV single winners.

Theorem 6. CCAV for MAV is NP-hard even when k = 1.

However, CCDV for MAV turns out to be polynomial-time solvable for k being a constant.

Theorem 7. CCDV for MAV is polynomial-time solvable if k is a constant.

The main idea of the algorithm is as follows. Let C(J) be the set of all k-committees containing J. As k is a constant, C(J) can be calculated in polynomial time. Then, we guess a non-negative integer x ≤ m and a k-committee w ∈ C(J), where x indicates the MAV score of the winning k-committees and w is supposed to be one of the winning k-committees in the final election. For each guessed pair (x, w), we delete all votes which have Hamming distance at least x + 1 from w and update ℓ accordingly. If ℓ < 0 after doing so, we discard this pair (x,w). Otherwise, we return "Yes" if and only if for every k-committee not in C(J), there is at least one vote which has Hamming distance at least x+1 from this k-committee.

Now we consider control by modifying the candidate set. Notice that for AV it is impossible to change the scores of registered candidates by adding unregistered candidates, as observed already in the single-winner voting case [Baumeister et al., 2010; Hemaspaandra and Hemaspaandra, 2007]. This implies that AV is immune to CCAC. However, this is not the case for SAV and NSAV, since in these two cases adding candidates may increase the number of approved candidates of some votes and hence affects the scores of these candidates. We show that CCAC for SAV and NSAV is NP-hard even in a special case, as summarized in the following theorem.

Theorem 8. CCAC for SAV and NSAV is NP-hard even when k = 1.

The immunity of single-winner AV to CCAC also implies that PAV and ABCCV are immune to CCAC when k = 1. More generally, one can observe that PAV and ABCCV are immune to CCAC when the number of distinguished candidates equals to k. The reason is that if some J ⊆ C is not the winning k-committee in the original election, then there is a committee w other than J which has at least the same score as that of J. As the scores of committees in the original election do not change by adding candidates, the committee w prevents J from being the unique winning k-committee no matter which candidates are added.

Theorem 9. PAV and ABCCV are immune to CCAC when the number of distinguished candidates is k.

However, when the number of distinguished candidates is strictly smaller than k, ABCCV and PAV are susceptible to CCAC as shown in the following example.

Example. Let C = {a, b, c}, D = {d}, J = {a}, and k = 2. For ABCCV, we create five votes v1 = {a}, v2 = v3 = {b, d}, and v4 = v5 = {c, d}. For PAV, we create eight votes v1 = v2 = {a}, v3 = v4 = v5 = {b, d}, and v6 = v7 = v8 = {c, d}. With respect to C, the only winning k-committee is {b, c}. However, if we add the candidate d, {a, d} becomes the unique winning k-committee.

Concerning the complexity, CCAC for ABCCV and PAV is co-NP-hard. In fact, we can show co-NP-hardness even for the special case where |J| = 1 and ℓ = 0. In this case, the question becomes whether a distinguished candidate p is included in all optimal k-committees in a given election. Note that this is also a special case of CCDC, CCAV, and CCDV. We denote this special case by p-CC.

Theorem 10. p-CC for ABCCV and PAV is co-NP-hard, and p-CC for MAV is NP-hard.

From the above theorem, we obtain the following corollary.

Corollary 1. CCAC and CCDC for ABCCV and PAV are coNP-hard, and for MAV are NP-hard. In addition, CCDV for MAV is NP-hard. These results hold even when |J| = 1.

Unlike the immunity of AV to CCAC, it is easy to see that AV is susceptible to CCDC. Concerning the complexity, we can show that CCDC for AV is polynomial-time solvable.

Theorem 11. CCDC for AV is polynomial-time solvable.

However, for SAV and NSAV, the complexity of CCDC is the same as CCAC.

Theorem 12. CCDC for SAV and NSAV is NP-hard even when k = 1.

The NP-hardness of the special case where k = 1 is not applicable to ABCCV and PAV. In fact, in this special case CCDC for ABCCV and PAV is polynomial-time solvable because CCDC for single-winner AV is polynomial-time solvable. For MAV, we can also show the polynomial-time solvability in this special case based on Lemma 1.

Theorem 13. CCDC for MAV is polynomial-time solvable when k = 1.

6 Some FPT Results for Control

In the previous section, we showed that many control problems are computationally hard. In this section, we consider these problems from the parameterized complexity point of view. First, it is easy to see that CCAC and CCDC for all rules studied in this paper are FPT with respect to the number of candidates, and CCAV and CCDV for AV, SAV, and NSAV are FPT with respect to the number of votes. Based on Lenstra's theorem on ILP [Lenstra, 1983], we can show the following FPT results.

Theorem 14. CCAV and CCDV for AV, SAV, and NSAV are FPT with respect to the number of candidates.

For the second group of voting rules, we can obtain similar results.

Theorem 15. CCAV and CCDV for ABCCV, PAV, and MAV are FPT with respect to the number of candidates.

Finally, we provide some FPT results for CCAC/CCDC with respect to the number of added/deleted candidates plus the number of voters.

Theorem 16. CCAC and CCDC for SAV, NSAV, PAV, ABCCV, and MAV are FPT with respect to the combined parameter ℓ+ n, where ℓ is the number of added/deleted candidates and n is the number of voters.

Recently, with respect to the number of voters, the parameterized complexity of control by adding/deleting candidates for single-winner voting rules has been studied, and it turned out that many problems are fixed-parameter intractable [Chen et al., 2017]. It is interesting to explore whether similar results hold for CCAC and CCDC for multiwinner voting rules, with respect to only the number of voters.

7 Concluding Remarks

In this paper, we have studied the complexity of several manipulation and control problems for numerous approval-based multiwinner voting rules. We showed that these rules generally resist these strategy behavior by giving many hardness results. However, it should be pointed out that our study is purely based on worst-case analysis. Whether these problems are difficult to solve in practice requests further investigations. In addition to the hardness results, we also derived several FPT-algorithms with respect to natural parameters and polynomial-time algorithms for some special cases of these problems. We refer to Table 1 for a summary of our results.

Finally, as winner determination for PAV, CCAV, and MAV is NP-hard, manipulation and control problems for these rules may belong to higher complexity classes. We leave this as open problems for future work.

Acknowledgements

The author thanks the anonymous reviewers of IJCAI 2019 for their insightful comments and suggestions.