# approvalbased_multiwinner_rules_and_strategic_voting__de8acf19.pdf

Approval-Based Multi-Winner Rules and Strategic Voting

Martin Lackner1 and Piotr Skowron2

1 Technische Universit at Wien, Austria 2 University of Warsaw, Poland lackner@dbai.tuwien.ac.at, p.skowron@mimuw.edu.pl

We investigate the possibility of strategic voting in approval-based multiwinner rules. In particular, we define three axiomatic properties that guarantee resilience to certain forms of strategic voting: independence of irrelevant alternatives (IIA), monotonicity, and SD-strategyproofness. In this paper, we systematically analyze multiwinner rules based on these axioms and provide a finegrained picture of their resilience to strategic voting. Both our axiomatic and experimental analysis show that approval-based multiwinner rules are generally very susceptible to strategic voting with one exception: Multiwinner Approval Voting.

1 Introduction In a multiwinner election, we are given a set of candidates, a set of voters with preferences over the candidates, and an integer k; the goal is to select a subset of exactly k candidates, called a committee. In this paper, we consider rules where the voters express their preferences by approving a subset of candidates. We refer to such rules as approval-based committee rules, in short: ABC rules. Our goal is to study strategic voting in this setting. In particular, we want to establish a model for strategic voting (i) that is applicable to arbitrary ABC rules, (ii) that does not require the assumption of voting rules being resolute (i.e., the assumption that tie-breaking mechanisms exist), and (iii) without the need of an auxiliary utility function determining the success of strategic voting. To the best of our knowledge, all previous studies on this topic failed at least one of these three principles (cf. Related Work). We begin our study by introducing three axiomatic properties which guarantee resilience to certain forms of strategic voting. The first axiom is independence of irrelevant alternatives (IIA), an adaptation of the Arrow s IIA axiom [1950] to the setting of ABC rules. IIA requires that the relative merit of two committees is not influenced by candidates outside of both committees. This axiom can be considered an incentive for voters to truthfully reveal preferences as it prevents a certain form of strategic voting, i.e., altering one s vote with respect to irrelevant candidates to manipulate the outcome. The second axiom is monotonicity, which guarantees that it is never disadvantageous to truthfully revealing one s ap-

proved candidates. However, it does not guarantee that approving of additional candidates, i.e., candidates that are actually disliked, is harmful. Consequently, monotonicity and IIA can be seen as complementary axioms. In Section 2.2, we provide two examples that further illustrate the connection between strategic voting, IIA and monotonicity. Finally and most importantly, we introduce SD-strategyproofness, which is an adaptation of the homonymous axiom from the literature on randomized social choice [Bogomolnaia and Moulin, 2001]. This axiom describes a strong form of resilience to strategic voting. Our further theoretical and experimental analysis is based on these three axioms. We obtain the following results:

We first consider the class of ABC counting rules, i.e., rules that generalize positional scoring rules to the ABC setting. Within this class we fully characterize all rules satisfying IIA and all satisfying monotonicity. We furthermore show that Multiwinner Approval Voting (AV) is the only ABC counting rule that satisfies both IIA and monotonicity. Finally, we show that AV is also the only ABC counting rule satisfying SD-strategyproofness.

Second, we perform an axiomatic analysis and examine popular ABC rules with respect to our three axioms. Our results show that while some of the commonly studied rules satisfy either IIA or monotonicity, AV is the only rule among those considered here that satisfies both axioms.

Finally, through a series of experiments, we quantify the level of resilience to strategic voting offered by different ABC rules (we measure it as a fraction of profiles where strategic voting is possible). Our conclusion is that rules which are more similar to AV (i.e., rules that follow the principle of individual excellence rather than diversity [Faliszewski et al., 2017]) are less manipulable. Our results reinforce the message of Barrot et al. [2017] that more egalitarian rules are more susceptible to manipulations (and such rules are, in some sense, diversity-oriented).

Related Work. For an overview on computational and axiomatic properties of multiwinner rules, we refer the reader to book chapters by Faliszewski et al. [2017] and Kilgour [2010]. Recently, Peters [2018] proved that there exist no resolute strategyproof ABC choice functions that are also proportional. Bredereck et al. [2017a] studied the impact of

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

(small) changes in the input profile on winning committees. Laslier and Van der Straeten [2016] analyzed strategic voting for AV in a probabilistic, game-theoretic model. Finally, we would like to mention several important works on computational aspects of strategic voting [Le Grand et al., 2007; Meir et al., 2008; Obraztsova et al., 2013; Baumeister et al., 2015; Barrot et al., 2017; Bredereck et al., 2017b].

2 Preliminaries

For each i, j N let [i, j] = {i, i+1, . . . , j}. Let [j] = [1, j]. For a set X and integer ℓ N we use Pℓ(X) to denote the set of all size-ℓsubsets of X. Let C = {c1, . . . , cm} be a set of candidates. We identify the universe of all possible voters with the set of natural numbers. For each finite subset V = {v1, . . . , vn} N, an approval profile over V , A = (A(v1), . . . , A(vn)), is an n-tuple of subsets of C; we call A(vi) the approval set of voter vi. Let A(C, V ) denote the set of all approval profiles over V . Let k, k < m, denote the required size of the committee. We call the elements of Pk(C) as committees. An approval-based committee ranking rule (ABC ranking rule) is a function F that maps approval profiles to weak orders over committees. We write W1 F(A) W2 if committee W1 is preferred to W2 according to the weak order F(A). Further, we define W1 F(A) W2 and W1 =F(A) W2 analogously. We say that a committee is winning if it is a maximal element in F(A). An approval-based committee choice rule (ABC choice rule) is a function R that takes approval profiles and returns sets of committees, again referred to as winning committees. Note that every ABC ranking rule F can naturally be translated to an ABC choice rule by returning all maximal elements in F(A). An ABC ranking rule F is trivial if for all profile A and committees W1, W2 Pk(C) it holds that W1 =F(A) W2. An ABC choice rule R is trivial if for all profiles A it holds that R(A) = Pk(C).

2.1 Hierarchy of ABC Rules In this section we recall the definitions of those ABC rules that are the focus of this paper.

ABC Counting Rules A counting function is a mapping f : [0, k] [0, m] R that is non-decreasing with respect to the first argument. Intuitively, f(x, y) is the score that a committee W obtains from a voter that approves x members of W and y candidates in total. Formally, the score of a committee W in A is

scf(W, A) = X

v V f(|A(v) W|, |A(v)|). (1)

An ABC ranking rule F is a counting rule if there exists a counting function f such that W1 F(A) W2 if and only if f(W1, A) > f(W2, A). Analogously, we say that an ABC choice rule R is a counting rule if there exists a counting function f such that for each profile A the set R(A) consists of those committees with the highest score. ABC counting rules have been introduced by Lackner and Skowron [2017]. This class is very broad, and contains, in particular, the following two important subclasses.

Thiele Methods This class of rules originated in the 19th century due to the works of Thiele [1895]. For a sequence of weights w = (w1, w2, . . .) we define the w-score of a committee W as P v V P|W A(v)| j=1 wj; the committees with highest w-score are the winners according to the w-Thiele method. One can easily observe that Thiele methods are ABC counting rules defined by counting functions that ignore the second argument. Formally, an ABC ranking rule F is a Thiele method if it is implemented by a counting function f(x, y) such that f(x, y) = f(x, y ) for all x [0, k] and y, y [0, m].

Dissatisfaction Counting Rules This class is defined analogously to Thiele methods, but the score that a voter assigns to a committee W depends on the number of approved candidates who are not contained in W. Formally, an ABC ranking rule F is a dissatisfaction counting rule if it is implemented by a counting function f(x, y) with the following property: there exists a function g: [m] R such that f(x, y) = g(y x) for all x [0, k] and y [0, m].

Concrete Examples of ABC Rules We list a few important examples of ABC ranking/choice rules. We will define ABC counting rules by giving their defining counting functions. For a more thorough discussion of multiwinner rules we refer the reader to the corresponding surveys [Faliszewski et al., 2017; Kilgour, 2010; Laslier and Sanver, 2010]. If not noted otherwise, rules below have first been discussed by Thiele [1895].

Multiwinner Approval Voting (AV) is a Thiele method implemented by the counting function f AV(x, y) = x. In fact, Multiwinner Approval Voting is also a dissatisfaction counting rule as it is implemented by f(x, y) = x y. We omit the proof of this statement. Proportional Approval Voting (PAV) is a Thiele method implemented by f PAV(x, y) = Px i=1 1/i. Approval Chamberlin Courant (CC) is also a Thiele method, implemented by f CC(x, y) = min(1, x). Satisfaction Approval Voting (SAV) is an ABC counting rule introduced by Brams and Kilgour [2014] which is neither a Thiele method nor a dissatisfaction counting rule. It is implemented by f SAV(x, y) = x

While all previous rules can be viewed both as ABC ranking rules and ABC choice rules, the following two do not fit well into the framework of ABC ranking rules because they do not allow to compare non-winning committees.

Sequential Thiele Methods. Let w = (w1, w2, . . .). The sequential w-Thiele method starts with an empty committee W = and works in k steps; in the i-th step it adds to the committee W a candidate c which maximizes the w-score of committee W {c}. Reverse-Sequential Thiele Methods. These rules are similar to sequential Thiele methods but start with the committee W = C and remove candidates iteratively until it has the desired size k. In each step the method removes a candidate c from the committee W whose removal reduces the w-score of W the least.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Note that AV, Sequential AV and Reverse-Sequential AV are the same rule; all three rules select k candidates with the largest number of approving votes. For all other Thiele methods this does not hold; their sequential and reverse-sequential variants are different from the respective original methods. Below we recall the definitions of three other voting methods which are not ABC counting rules.

Monroe s Approval-Based Rule [Monroe, 1995]. Given a committee W, a balanced assignment is a function φ: V W mapping n voters to the k committee members such that n

k |φ 1(c)| n

k for each c W. The score of an assignment φ is defined as |{v V | φ(v) A(v)}|. The Monroe score of a committee W is the maximum score of any balanced assignment φ: V W. The Monroe rule returns committees ordered by their Monroe score; committees with maximum score are winning.

Minimax Approval Voting (MAV) [Brams et al., 2007] is based on the Hamming distance of a committee W to the voters in V , defined as:

d H(W, V ) = X

v V (|A(v) \ W| + |W \ A(v)|).

For MAV, committees W win that minimize d H(W, V ).

Phragm en s sequential rule [Phragm en, 1894] is an ABC choice rule based on a load balancing mechanism. As understanding the definition of this rule is not essential for our paper, we omit details and refer the reader to a recent paper by Brill et al. [2017] and a survey by Janson [2016].

2.2 Axioms In this section, we introduce and discuss formal definitions of the axioms used in our further study. The first two axioms are formulated only for ABC ranking rules (we omit corresponding definitions for ABC choice rules). For A A(C, V ), v V , and c C, let Av,+c denote the profile that is identical to A except that voter v additionally approves c, i.e., Av,+c(v) = A(v) {c}.

Definition 1 (Independence of irrelevant alternatives). An ABC ranking rule F satisfies independence of irrelevant alternatives (IIA) if for all A A(C, V ), W1, W2 Pk(C), c C \ (W1 W2), and v V it holds that W1 F(A) W2 if and only if W1 F(Av,+c) W2.

Definition 2 (Monotonicity). An ABC ranking rule F is monotonic if for each W1, W2 Pk(C), A A(C, V ), v V , and c W1 it holds that (i) if W1 F(A) W2, then W1 F(Av,+c) W2, and (ii) if W1 F(A) W2, then W1 F(Av,+c) W2.

To see the relation of these two axioms and strategic voting, consider the following two examples.

Example 1 (monotonicity). Let A be a profile with A(1) = A(2) = A(3) = {a, b, c}, A(4) = A(5) = {a, b, d}, and A(6) = {a, d, e, f} and assume we intend to select a winning committee of size k = 3. In this case, committee {a, b, d} wins under PAV with a PAV-score of 9 + 2/3. In particular, {a, b, d} has a higher score than {a, b, c} (which is 9.5). If we assume that profile A reflects the voters true preferences,

voter 1 can benefit from approving only {c}. In this modified profile, the committee {a, b, c} has a PAV-score of 8+ 2/3 and is winning as {a, b, d} has a score of only 8 + 1/6. Hence, with this form of strategic voting, voter 1 would benefit by having all her approved candidates in the winning committee. This kind of strategic voting is ruled out by the monotonicity axiom, which as we just saw is not satisfied by PAV. Example 2 (IIA). Now, let us consider Satisfaction Approval Voting (SAV) and the profile A with A(1) = {a, b}, A(2) = {a, c, d}, and A(3) = {e}. For k = 1, committee {e} wins with a score of 1. The score of {a} is 5/6. If voter 1 would change its vote to {a}, then committee {a} would win with a score of 1 + 1/3; the score of {e} remains 1. We see that the situation of voter 1 improves: after changing his vote an approved candidate wins the election. Note that the change in the original profile concerned candidate b, but changed the relative order of the committees {a} and {e}. This type of strategic voting is ruled out by the independence of irrelevant alternatives axiom, which SAV does not satisfy. Thiele methods, however, do satisfy IIA. Let us now move to our last axiom concerning strategyproofness. To be able to speak about strategic voting, assumptions have to be made concerning the satisfaction of voters with committees. Our central assumption is that a voter v prefers a committee W to W if |W A(v)| > |W A(v)|, i.e., if voter v approves more candidates in W than in W . Based on this assumption, we define the following notion of strategyproofness, inspired by the idea of stochastic dominance (SD) [Bogomolnaia and Moulin, 2001]. Definition 3. Let S C be an approval set representing the true preferences of some specific voter. A set of committees X Pk(C) stochastically dominates a set of committees Y Pk(C) subject to S if the following two conditions hold: 1. For each ℓ N we have that the fraction of winning committees in X that contain at least ℓmembers of S is at least as large as the fraction for Y , i.e., |{W X : |W S| ℓ}|

|X| |{W Y : |W S| ℓ}|

2. There is ℓ N for which the above inequality is strict. Given a profile A A(C, V ) and v V , let (A v, T) denote the profile identical to A except that the approval set of voter v is changed to T. Definition 4. Given a profile A A(C, V ) and an ABC choice or ranking rule R, we say that a voter v V can SD-manipulate if there exists a set T C such that the set of committees R(A v, T) stochastically dominates R(A) subject to A(v). R is SD-strategyproof if for all profiles A A(C, V ) no voter v V can SD-manipulate. We note that for resolute rules SD-strategyproofness coincides with cardinality strategyproofness [Peters, 2018].

3 Characterization Results We first focus on ABC counting rules and present our main characterization results within this class. We will use the following useful lemma of Lackner and Skowron [2017].

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Lemma 1. Let Dm,k = {(x, y) [0, k] [0, m 1] : x y k x m y} and let f, h be counting functions. If there exist c R and d: [m] R such that f(x, y) = c h(x, y)+d(y) for all x, y Dm,k then f, h yield the same ABC counting rule, i.e., for all approval profiles A A(C, V ) and committees W1, W2 Pk(C) it holds that W1 f(A) W2 if and only if W1 h(A) W2. The following theorems establish that ABC ranking rules satisfying IIA correspond to the class of Thiele methods, whereas rules that satisfy monotonicity yield the class of dissatisfaction counting rules. Interestingly, the intersection of these two classes contains exactly one non-trivial rule: AV. Theorem 1. Thiele methods are the only ABC counting rules that satisfy independence of irrelevant alternatives.

Proof. To see that Thiele methods satisfy independence of irrelevant alternatives, let f implement a Thiele method and let A A(C, V ), W1, W2 Pk(C), c C \ (W1 W2), and v V . It holds that scf(W1, A) = scf(W1, Av,+c) and scf(W2, A) = scf(W2, Av,+c) and thus W1 F(A) W2 if and only if W1 F(Av,+c) W2. For the other direction, let F be an ABC counting rule satisfying IIA; let f be the corresponding counting function. Recall that by Lemma 1 we can focus on f restricted to the domain Dm,k = {(x, y) [0, k] [0, m 1] : x y k x m y}. We will show that for each y there exists a constant cy R such that for all x with (x, y) Dm,k and (x, y + 1) Dm,k we have

f(x, y + 1) = f(x, y) + cy. (2)

Assuming that (2) holds, we have that f(x, y ) f(x, y) = P y z<y cz for x, y, y with (x, y), (x, y ) Dm,k and y y. We can define a counting function h(x, y) = f(x, y) P 0 z<y cz. By Lemma 1, f and h implement F. Now,

h(x, y) = f(x, y) X

= f(x, y ) X

y z<y cz = h(x, y ),

and hence F is a Thiele method. In order to show that (2) holds, we will show that for each x, x , and y with (x, y), (x , y), (x, y+1), (x , y+1) Dm,k we have f(x, y + 1) f(x, y) = f(x , y + 1) f(x , y). Observe that it is sufficient to show the above relation for x = x + 1, i.e., we want to show that

f(x, y + 1) + f(x + 1, y) = f(x + 1, y + 1) + f(x, y).

Let W1, W2 Pk(C) be such that |W1 W2| = k 1, i.e., there exists a single candidate c1 with c1 W1 \ W2 and a single candidate c2 with c2 W2 \ W1. Furthermore, let us construct a profile A A(C, {1, 2}) with votes A(1) and A(2) that are defined as follows: The first vote A(1) satisfies |A(1)| = y + 1, c1 A(1), c2 / A(1), and |A(1) W1 W2| = x. Note that |A(1) W1 W2| = x, c1 A(1), and c2 / A(1) implies that |A(1) \ (W1 W2)| = y x. To see that a sufficient number of candidates exists for this construction, observe that |A(1) W1 W2| = (y x)+(k+

1). Since (x, y + 1) Dm,k it holds that k x m y 1 and hence (y x) + (k + 1) m. We obtain the second vote A(2) from A(1) by swapping c1 and c2 and removing one candidate d A(1) \ (W1 W2), i.e., A(2) = (A(1) {c2}) \ {c1, d} and |A(2)| = y. Such candidate d exists, because otherwise we would have A(1) W1 and hence x + 1 = y + 1, which contradicts the fact that (x + 1, y) Dm,k (and thus x + 1 y). Let us argue that W1 =F(A) W2. For that, let us now modify A so as to apply independence of irrelevant alternatives. Let A A(C, {1, 2}) with A (1) = A(1) and A (2) = A(2) {d}. Let us consider a bijection σ: C C with σ(c1) = c2, σ(c2) = c1, and which is the identity elsewhere. Note that σ(A (1)) = A (2) and vice versa; also σ(W1) = W2 and vice versa. Thus, by neutrality1 of F we infer that W1 =F(A ) W2, and by independence of irrelevant alternatives that W1 =F(A) W2. The score of W1 in A is equal to f(x + 1, y + 1) + f(x, y) and the score of W2 in A is equal to f(x, y + 1) + f(x + 1, y). Since W1 =F(A) W2, these scores need to be equal.

Theorem 2. Dissatisfaction counting rules are the only ABC counting rules that satisfy monotonicity.

Proof. To see that dissatisfaction counting rules satisfy monotonicity, let F be a dissatisfaction counting rule implemented by the counting function f, for which there exists a function g such that f(x, y) = g(y x) for each x, y. Observe that g is necessarily non-increasing because f(x, y) f(x , y) for x x . Now, consider a profile A and two committees W1 and W2 such that W1 F(A) W2, as well as the profile Av,+c with c W1. We calculate the difference between the scores of committee W1 in profiles Av,+c and A. It holds that scf(W1, Av,+c) scf(W1, A) = g(|A(v)| + 1 (|A(v) W1| + 1)) g(|A(v)| |A(v) W1|) = 0. For committee W2 we calculate this difference by considering two cases. If c W2 then just as before we have scf(W2, Av,+c) scf(W2, A) = 0. If c / W2 then scf(W2, Av,+c) scf(W2, A) = g(|A(v)| + 1 |A(v) W2|) g(|A(v)| |A(v) W2|) 0, since g is non-increasing. In both cases, the score of committee W1 in profile Av,+c remains at least as large as the score of committee W2, hence W1 F(Av,+c) W2. The same argument holds for W1 F(A) W2 and hence monotonicity holds. The proof for the other direction is more complex. We omit it due to space constraints.

We also have to omit the proof for the following theorem: Theorem 3. Multiwinner Approval Voting is the only nontrivial ABC counting rule that satisfies independence of irrelevant alternatives and monotonicity. We see that IIA and monotonicity allow us to identify AV within the class of ABC counting rules. As the following theorem shows, the same holds for SD-strategyproofness:

1An ABC ranking rule F is neutral if for each bijection σ : C C and A, A A(C, V ) with σ(A) = A it holds for W1, W2 Pk(C) that W1 F(A) W2 if and only if σ(W1) F(A ) σ(W2). Each ABC counting rule satisfies neutrality.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

Theorem 4. Multiwinner AV is the only non-trivial ABC counting rules that satisfies SD-strategyproofness.

Proof. In order to prove that Multiwinner Approval Voting satisfies SD-strategyproofness we will show an analogy between possible misreports of the voters and certain properties of the hypergeometric distribution. Consider an approval profile A and fix a voter v. For c C, let s(c) = |v V : c A(v)| denote the approval score of candidate c. Further let γ 0 such that |c C : s(c) γ| k and |c C : s(c) > γ| k. Let Weach = {c C : s(c) > γ} and Wtie = {c C : s(c) = γ}. Note that every winning committee W it holds that Weach W Weach Wtie. Finally, let xeach = |Weach A(v)| and xtie = |Wtie A(v)|. Now, we make the crucial observation. Let P(b, w, s, r) denote the (hypergeometric) probability that in the random process of sampling s balls without replacement from an urn containing b black balls and w white balls, we will get at least r black balls. We observe that the fraction of winning committees that contain at least ℓmembers approved by v is equal to P(b, w, s, r) with w = |Wtie| xtie, b = xtie, s = k |Weach|, and r = ℓ xeach. Hence, an SDmanipulation is successful if the parameters b, w, s, r can be changed in such a way that P(b, w, s, r) increases. We see:

If v approves an additional (previously disapproved) candidate, this results in one of the following possible changes of the parameters: (i) no change, (ii) moving a candidate from Wtie to Weach: wnew = w 1, bnew = b, snew = s 1, rnew = r, or (iii) moving a candidate from C \ (Wtie Weach) to Wtie: wnew = w + 1, bnew = b, snew = s, rnew = r. In each case it is easy to see that P(bnew, wnew, snew, rnew) P(b, w, s, r).

If v disapproves a previously approved candidate, then the following changes are possible: (i) no change, (ii) moving a candidate from Weach to Wtie: wnew = w, bnew = b + 1, snew = s + 1, rnew = r + 1, or (iii) moving a candidate from Wtie to C \(Wtie Weach): wnew = w, bnew = b 1, snew = s, rnew = r. Also here, in each of these cases, we have that P(bnew, wnew, snew, rnew) P(b, w, s, r).

Each misreport can be represented as a combination of a number of the above two types of actions. Since each action does not increase the probability, then the eventual probability after a misreport will not increase. Now we will prove the other implication. Let R be a nontrivial ABC counting rule implemented by a counting function f, and let us assume that R is SD-strategyproof. We omit the proof that R is a Thiele method, which uses the same reasoning (but a different construction) as in the proof of Theorem 1. Let g: [0, k] R such that f(x, y) = g(x). We will now prove that for each x, 0 x k 2, we have that g(x + 1) g(x) = g(x + 2) g(x + 1), and by that R is AV. Let us fix two committees, W1 and W2 such that |W1 W2| = k 1. Let v1 denote a vote where x + 1 members of W1 and x members of W2 are approved. Let v 1 be constructed from v1 by approving one additional candidate from W1 W2. Similarly, we construct v2 and v 2 by swapping the two candidates from W1\W2 and W2\W1 with each other in v1 and v 1, respectively.

In the following, we use sums to indicate the concatenation of approval profiles. For each candidate c C, we define E( c) to be a profile in which every subset of C \ {c} is approved by exactly one voter. Since R is nontrivial, it follows that all the committees that do not contain c are winning in E( c). Similarly, for each subset S C, we let E(S) = P c/ S E( c). In the profile EW1,W2 = E(W1 W2) + E(W1 W2) only W1 and W2 are winning. This can be seen either by a direct proof using the fact that R is a non-trivial ABC counting rule, or from the fact that ABC counting rules satisfy the consistency axiom [Lackner and Skowron, 2017], which yields this statement immediately. Further, assume that λ is a large number which ensures that in the profile λEW1,W2 (i.e., λ many copies) the difference between the scores of W1, W2 and other committees is sufficiently large. Let us now assume towards a contradiction that g(x+1) g(x) = g(x + 2) g(x + 1). We first consider the case when g(x + 1) g(x) > g(x + 2) g(x + 1). Take the (truthful) profile v 1 + v 2 + λEW1,W2. In this profile W1 and W2 are winning. However, if v 1 misreports v1, then the score of W1 decreases by g(x + 2) g(x + 1), while the score of W2 decreases by g(x + 1) g(x). Thus, W1 will become the only winner, which is preferred by v 1. Similarly, if g(x+1) g(x) < g(x+2) g(x+1), we can take the (truthful) profile v1+v2+λEW1,W2, and we can observe that v1 can misreport v 1, ensuring that W1 will be the only winning committee. This completes the proof.

Theorem 3 and Theorem 4 highlight the close relation between IIA, monotonicity and SD-strategyproofness within the class of ABC counting rules. However, outside of this class there exist voting rules that satisfy IIA and monotonicity, but are not SD-strategyproof. As an example consider the following rule: if there are fewer then k candidates who are approved by some voter, the rule works as the trivial rule, i.e., ranks all committees as equivalent. If there are at least k approved candidates, the rule returns a ranking with two equivalence classes: all size-k subsets of the union of approved candidates are ranked above all other committees. This rule sometimes allows voters to change the outcome from extreme indifference (all committees win) to a situation where only one committee wins that contains all her approved candidates, and thus is not SD-strategyproof. IIA and monotonicity are satisfied by this rule. Similarly, there are rules that are SD-strategyproof but fail IIA and monotonicity, since SDstrategyproofness only applies to winning committees. Finally, we note that if AV is used in conjunction with an unfortunate tie-breaking rule (to make AV resolute), strategic voting may again become possible.

Example 3. Let k = 3. Consider two votes A(v1) = {a, b} and A(v2) = {c, d}, and AV with the tie-breaking rule {a, b, e} {c, d, a} . . .. If v1 votes sincerely, {c, d, a} wins and, thus, v1 has an incentive to misreport {a, b, e}.

4 Comparing Properties of ABC Rules

As we have established earlier, AV is the only ABC counting rule that satisfies SD-strategyproofness and the only one

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

IIA mon. SD-str. simulations

Thiele Methods + Dissatis. counting rules + MW Appr. Voting (AV) + + + 0.0 0.0 Phragm en s sequ. rule + 0.659 0.848 Sequential PAV + 0.683 0.796 Proportional A.V. (PAV) + 0.708 0.811 Reverse-Sequ. PAV 0.711 0.814 Satisfaction A.V. (SAV) 0.861 0.955 Maximin A.V. (MAV) 0.861 1.0 Approval Monroe + 0.924 1.0 Sequential CC + 0.944 1.0 Chamberlin Cour. (CC) + 0.954 1.0 Reverse-Sequ. CC 0.957 1.0

Table 1: Approval-based multiwinner voting rules and axioms they satisfy (+) or fail (blank). Classes of rules (such as Thiele methods) satisfy an axiom if all rules in the class satisfy it; they fail an axiom if one rule in the class fails it. Some rules that are ABC choice rules by definition; these are marked with a star ( ). The simulations columns show the relative number of profiles where SD-manipulation was possible, based on 1000 instances with n = 24, m = 8, k = 4, and approval sets of size of 2 (left column) and 3 (right).

that satisfies IIA and monotonicity. However, AV is not the only ABC rule that satisfies SD-strategyproofness. For example, dictatorial rules trivially satisfy SD-strategyproofness, as well as rules where candidates and voters are divided into predefined districts and within each district a predefined number of representatives is selected via approval voting. The natural question arises whether any of the well-established ABC rules discussed in Section 2.1 (except for AV) satisfies SDstrategyproofness. We provide a negative answer with Table 1: AV holds indeed a special role among classic ABC rules. Furthermore, we list which rules satisfy IIA and monotonicity. Due to space constraints we have to omit the corresponding proofs and counterexamples. We complement this axiomatic analysis with an experimental evaluation. In randomly generated instances we investigated the possibility of voters to SD-manipulate, i.e., we computed the relative number of instances in which strategic voting allows voters to change the set of winning committees to one that stochastically dominates the original one. In Table 1 the results of two experiments are displayed. In the first experiment, it is assumed that voters approve of exactly two candidates, in the second that voters approve of exactly three candidates. For both experiments, approval sets were sampled uniformly at random to generate profiles with n = 24 voters, m = 8 candidates, and assuming a committee size of k = 4. Both experiments are based on 1,000 instances. We first note that a large percentage of the instances allowed for SD-manipulations. This is due to the strictness of SD-strategyproofness: even minor variations in the set of winning committees can yield a (minor) improvement for voters. Hence, SD-manipulations are often possible. Second, and more importantly, we note that the likelihood of SDmanipulations greatly varies for different ABC rule. We see that PAV and its derivatives as well as Phragm en s rule per-

p 1 2 3 4 5 6 0

appr. sets of size 2

appr. sets of size 3

Figure 1: The relative number of profiles where SD-manipulation is possible subject to p-geometric rules; via simulation with n = 24, m = 6, k = 3, and approval sets of a fixed size sampled from the uniform distribution.

form better than all other rules except for AV. On the other end, CC and its derivatives allow for SD-manipulations in nearly all profiles. This gives rise to the hypothesis that voting rules similar to AV are more resistant to SD-manipulation, rules similar to CC are more prone to SD-manipulation, and proportional rules are in between. Exception to this hypothesis can easily be identified: SAV is similar to AV but is SDmanipulable in a large number of profiles, and also Approval Monroe is very susceptible to SD-manipulation although it is a proportional rule. In both cases, this seems to be a consequence of their specific definitions allowing for specific SDmanipulations to succeed. We have therefore tested this hypothesis in a more controlled setting, i.e., in the (more uniform) class of p-geometric rules, p 1. These are Thiele methods defined by f(x, y) = Px i=1 1/pi. It is straightforward to see that the 1-geometric rule is AV and, for p , p-geometric rules approach CC. For this setting, we repeated our experiments (due to computational limitations with smaller profiles) and could clearly see that the number of SD-manipulable profiles increased with increasing p (cf. Figure 1). Two further observations can be made: Although these experiments are based on a large number of instances (1,000), there are some fluctuations in the likelihoods. It appears that if p is integer, then SD-manipulations are slightly more likely; this phenomenon asks for a more detailed analysis. Second, for approval sets of size 2 the likelihood values do not obviously approach the corresponding CC value (shown as p = ). This is due to the fact that CC treats all voters equally that have one or more approved candidates in the committee, whereas for p-geometric rules (even for large p) the score obtained from voters, e.g., with 2 and 3 approved candidates in the committee slightly varies. Hence, there are fewer tied winning committees and fewer SD-manipulations possible.

5 Conclusion

This work initiates the study of strategic voting for multiwinner rules (i) without the need of imposing tie-breaking mechanisms, and (ii) without auxiliary information in the form of utility functions. We have shown that Multiwinner Approval Voting enjoys a strong form of strategyproofness, which other popular rules do not satisfy. Furthermore, PAV, its

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

sequential versions, and Phragm en s rule all being proportional to some degree show a reduced susceptibility to SDmanipulation in our experiments. It would be interesting to study the impact of coalitional SD-manipulations and the algorithmic challenge of finding successful SD-manipulations.

Acknowledgements Martin Lackner was supported by the European Research Council (ERC) under grant number 639945 (ACCORD) and by the Austrian Science Foundation FWF, grant P25518 and Y698. Piotr Skowron was supported by a Humboldt Research Fellowship for Postdoctoral Researchers and by the Foundation for Polish Science within the Homing programme (Project title: Normative Comparison of Multiwinner Election Rules ).

References [Arrow, 1950] K. J. Arrow. A difficulty in the concept of social welfare. The Journal of Political Economy, pages 328 346, 1950. [Barrot et al., 2017] N. Barrot, J. Lang, and M. Yokoo. Manipulation of Hamming-based approval voting for multiple referenda and committee elections. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2017), pages 597 605, 2017. [Baumeister et al., 2015] D. Baumeister, S. Dennisen, and L. Rey. Winner determination and manipulation in minisum and minimax committee elections. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT-2015), pages 469 485, 2015. [Bogomolnaia and Moulin, 2001] A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295 328, 2001. [Brams and Kilgour, 2014] S. J. Brams and D. M. Kilgour. Satisfaction approval voting. In Voting Power and Procedures, Studies in Choice and Welfare, pages 323 346. Springer, 2014. [Brams et al., 2007] S. J. Brams, D. M. Kilgour, and M. R. Sanver. A minimax procedure for electing committees. Public Choice, 132(3 4):401 420, 2007. [Bredereck et al., 2017a] R. Bredereck, P. Faliszewski, A. Kaczmarczyk, R. Niedermeier, P. Skowron, and N. Talmon. Robustness among multiwinner voting rules. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT-2017), pages 80 92, 2017. [Bredereck et al., 2017b] R. Bredereck, A. Kaczmarczyk, and R. Niedermeier. On coalitional manipulation for multiwinner elections: Shortlisting. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2017), pages 887 893, 2017. [Brill et al., 2017] M. Brill, R. Freeman, S. Janson, and M. Lackner. Phragm en s voting methods and justified representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), pages 406 413, 2017.

[Faliszewski et al., 2017] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice. AI Access, 2017. To appear. [Janson, 2016] S. Janson. Phragm en s and Thiele s election methods. Technical Report ar Xiv:1611.08826 [math.HO], ar Xiv.org, 2016. [Kilgour, 2010] D. M. Kilgour. Approval balloting for multiwinner elections. In J.-F. Laslier and R. Sanver, editors, Handbook on Approval Voting, pages 105 124. Springer, 2010. [Lackner and Skowron, 2017] M. Lackner and P. Skowron. Consistent approval-based multi-winner rules. Technical Report ar Xiv:1704.02453v1 [cs.GT], ar Xiv.org, 2017. [Laslier and Sanver, 2010] J.-F. Laslier and R. Sanver, editors. Handbook on Approval Voting. Springer, 2010. [Laslier and Van der Straeten, 2016] J.-F. Laslier and K. Van der Straeten. Strategic voting in multi-winners elections with approval balloting: a theory for large electorates. Social Choice and Welfare, 47(3):559 587, 2016. [Le Grand et al., 2007] R. Le Grand, E. Markakis, and A. Mehta. Some results on approximating the minimax solution in approval voting. In Proceedings of the 3rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2007), pages 198:1 198:3, 2007. [Meir et al., 2008] R. Meir, A. Procaccia, J. Rosenschein, and A. Zohar. Complexity of strategic behavior in multiwinner elections. Journal of Artificial Intelligence Research, 33:149 178, 2008. [Monroe, 1995] B. Monroe. Fully proportional representation. American Political Science Review, 89(4):925 940, 1995. [Obraztsova et al., 2013] S. Obraztsova, Y. Zick, and E. Elkind. On manipulation in multi-winner elections based on scoring rules. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2013), pages 359 366, 2013. [Peters, 2018] D. Peters. Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2018), 2018. To appear. [Phragm en, 1894] E. Phragm en. Sur une m ethode nouvelle pour r ealiser, dans les elections, la repr esentation proportionnelle des partis. Ofversigt af Kongliga Vetenskaps Akademiens F orhandlingar, 51(3):133 137, 1894. [Thiele, 1895] T. N. Thiele. Om flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415 441. 1895.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)