# participation_incentives_in_approvalbased_committee_elections__e7d78794.pdf

Participation Incentives in Approval-Based Committee Elections

Martin Bullinger1*, Chris Dong2, Patrick Lederer2, Clara Mehler2

1Department of Computer Science, University of Oxford 2School of Computation, Information and Technology, Technical University of Munich martin.bullinger@cs.ox.ac.uk, chris.dong@tum.de, ledererp@in.tum.de, mehler@in.tum.de

In approval-based committee (ABC) voting, the goal is to choose a subset of predefined size of the candidates based on the voters approval preferences over the candidates. While this problem has attracted significant attention in recent years, the incentives for voters to participate in an election for a given ABC voting rule have been neglected so far. This paper is thus the first to explicitly study this property, typically called participation, for ABC voting rules. In particular, we show that all ABC scoring rules even satisfy group participation, whereas most sequential rules severely fail participation. We furthermore explore several escape routes to the impossibility for sequential ABC voting rules: we prove for many sequential rules that (i) they satisfy participation on laminar profiles, (ii) voters who approve none of the elected candidates cannot benefit by abstaining, and (iii) it is NP-hard for a voter to decide whether she benefits from abstaining.

1 Introduction Many questions in multi-agent systems reduce to the problem of selecting a subset of the available candidates based on the preferences of a group of agents over these candidates. Maybe the most apparent example for this are elections of parliaments or city councils, but there are also numerous applications beyond classical voting. For instance, this model can also be used to describe automated recommender systems (Gawron and Faliszewski 2022) or the selection of validators in a block chain (Cevallos and Stewart 2021). In the field of computational social choice, such elections are known as approval-based committee (ABC) elections and they have recently attracted significant attention (Faliszewski et al. 2017; Lackner and Skowron 2023). In more detail, this research studies approval-based committee (ABC) voting rules, which choose a fixed-size subset of the candidates, typically called a committee, based on the voters approval ballots (i.e., voters express their preference about every candidate by either approving or disapproving her). One of the basic premises of ABC voting rules (and, more generally, of all types of elections) is that voters will participate in the election. However, this is not necessarily in the

*Most of this research was done when Martin Bullinger was a Ph D student at the Technical University of Munich. Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

interest of the voters: for example, for many single-winner voting rules, there are situations where voters prefer the outcome chosen when abstaining to the outcome chosen when voting (e.g., Moulin 1988; P erez 2001; Brandl et al. 2019). This undesirable phenomenon, which is known as the noshow paradox, entails that voting can be disadvantageous for a voter and hence disincentivizes participation. We are thus interested in voting rules that avoid this paradox, which are then said to satisfy participation. Note that while related concepts have been analyzed (e.g., S anchez-Fern andez and Fisteus 2019; Lackner and Skowron 2023, Prop. A.3), participation has not been studied for ABC voting rules and we thus initiate the study of this axiom for ABC elections.

Our contribution. In this paper, we study the participation incentives of ABC voting rules. In more detail, we first investigate which ABC voting rules satisfy participation and prove that all ABC scoring rules (including all Thiele rules) even satisfy group participation. This generalizes the observation that scoring rules satisfy participation for single-winner elections and gives a strong argument in favor of Thiele rules. By contrast, we prove a general impossibility theorem, which shows that most ABC voting rules that sequentially compute the winning committees fail participation. In particular, our result implies that all sequential Thiele rules (except for approval voting) as well as the sequential variant of Phragm en s rule and the method of equal shares severely fail participation: there are situations where a voter only approves one of the elected candidates when she votes but all except one of the elected candidates when she abstains. These theorems also subsume results by S anchez-Fern andez and Fisteus (2019) and Lackner and Skowron (2023) who study a monotonicity axiom that constitutes a special case of participation. We furthermore analyze several approaches to circumvent this negative result for sequential rules. Firstly, motivated by the notion of strategyproofness for unrepresented voters by Delemazure et al. (2023), we show that many sequential ABC voting rules ensure that voters who do not approve any of the elected candidates cannot benefit by abstaining (Proposition 1). This result complements our impossibility theorem, which shows that voters can significantly benefit from abstaining when they approve at least one candidate and, moreover, demonstrates that many sequential rules satisfy at least a minimal degree of participation. Next, we prove that

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

all sequential Thiele rules and the sequential Phragm en rule satisfy participation when restricting the domain to laminar profiles (Proposition 2). These profiles have been introduced by Peters and Skowron (2020) and require that for all candidates x and y, the respective sets of voters approving x and y are either disjoint or related by subset inclusion. Hence, this result shows that sequential ABC voting rules satisfy participation when focusing on an important special case. Finally, we show that it is NP-hard for a voter to decide whether she benefits from abstaining when using sequential Thiele rules, sequential Phragm en, or the method of equal shares (Section 3.3). Thus, even though a voter may benefit by abstaining, she may not be able to recognize it. Moreover, our technique for showing these hardness results is very universal and allows us to recover, strengthen, or complement existing hardness results by Faliszewski, Gawron, and Kusek (2022) and Janeczko and Faliszewski (2023). In addition, our results indicate that many basic problems (e.g., whether there is a winning committee for which a given voter approves ℓ candidates) are NP-hard for sequential rules.

Related Work. The topic of ABC voting currently attracts significant attention and we refer to Lackner and Skowron (2023) for a recent survey. While there is, to the best of our knowledge, no explicit work on participation in ABC voting, there are a few closely related papers. In particular, S anchez-Fern andez and Fisteus (2019) study an axiom called support monotonicity with population increase (SMWPI), which requires that the abstention of a voter cannot result in a committee that contains all of her approved candidates if such a committee is not chosen when voting. Clearly, SMWPI is a mild variant of participation and S anchez-Fern andez and Fisteus (2019) show that all ABC scoring rules satisfy this condition. Moreover, Lackner and Skowron (2023, Prop. A.3), Mora and Oliver (2015), and Janson (2016) consider various sequential rules and prove that they fail SMWPI, which implies that they also fail participation. Notably, the proof of Theorem 2 also works with SMWPI and our result thus strengthens the existing results by showing that essentially all sequential rules fail this property. Our paper is also related to the study of strategyproofness and robustness in ABC voting (e.g., Aziz et al. 2015; Peters 2018; Bredereck et al. 2021; Faliszewski, Gawron, and Kusek 2022). In particular, participation can be seen as a variant of strategyproofness that prohibits that voters manipulate by abstaining, or as a robustness axiom that measures how much impact an abstaining voter can have on the outcome. Many of these papers are conceptually similar to ours as they first study whether ABC voting rules satisfy an axiom and then explore escape routes. Finally, in the broader realm of social choice, there are numerous papers that study participation. In his seminal paper, Moulin (1988) showed that a large class of single-winner voting rules known as Condorcet extensions fail participation. This result caused a large amount of follow-up work, which either strengthens the negative result (e.g., Jimeno, P erez, and Garc ıa 2009; Duddy 2014; Brandt, Geist, and Peters 2017) or explores escape routes (e.g., Brandl, Brandt, and Hofbauer 2019; Brandl et al. 2019). A particularly noteworthy paper in

our context is by P erez, Jimeno, and Garc ıa (2010) who show that a large class of committee voting rules fail participation when voters report ranked ballots. We refer to Hofbauer (2019) for a survey on participation in social choice.

2 Preliminaries In this paper, we will use the standard ABC voting setting following the notation of Lackner and Skowron (2023). To formalize this model, let N denote an infinite set of voters and let C denote a set of m > 1 candidates. An electorate N is a non-empty and finite subset of N and we suppose that every voter i N reports an approval ballot Ai to express her preferences. Formally, an approval ballot is a non-empty subset of C. An approval profile A is the collection of the approval ballots of all voters i N, i.e., a function of the type N 2C \ { }. We denote by NA the set of voters that report a ballot in profile A and by NA(c) the set of voters who approve candidate c in A. Moreover, A i (resp. A I) is the profile derived from A when voter i NA (resp. a group of voters I NA) abstains. More formally, A = A i is defined by NA = NA \ {i} and A j = Aj for all j NA . Given an approval profile, our goal is to elect a committee, which is a subset of the candidates of predefined size. Following the literature, we define k {1, . . . , m 1} as the target committee size and Wk = {W C : |W| = k} as the set of size k committees. We collect all information associated with an election in an election instance E = (N, C, A, k), where we omit N and C whenever they are clear from the context. Given an election instance E, our goal is to determine the winning committee. To this end, we will use approval-based committee (ABC) voting rules which map every election instance E to a non-empty subset of Wk, i.e., ABC voting rules may return multiple committees that are tied for the win.

2.1 Classes of Voting Rules We now introduce several (classes of) ABC voting rules. We assume that all rules return all committees that can be obtained by some tie-breaking order.

ABC scoring rules. ABC scoring rules, which were introduced by Lackner and Skowron (2021), generalize scoring rules to ABC elections: each voter gives points to each committee and the winning committees are those with the maximal total score. Formally, these rules are defined by a scoring function s which maps all x, y N0 with x y to a rational number s(x, y) such that s(x, y) s(x , y) for all x x y. Without loss of generality, we suppose that s(0, y) = 0 for all y. Intuitively, s(x, y) is the score a voter gives to a committee W when she approves x members of W and y in total. Thus, the total score of a committee W in a profile A is ˆs(A, W) := P i NA s(|Ai W|, |Ai|). The ABC scoring rule defined by the scoring function s chooses the committees W that maximize the total score ˆs(A, W).

Thiele rules. Thiele rules, suggested by Thiele (1895), are scoring rules that are independent of the ballot size, i.e., s(x, y) = s(x, y ) for all x y y . Therefore, we drop the second argument of the scoring function. We impose the standard requirements that s(1) > 0 and s(x + 1) s(x)

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

s(x + 2) s(x + 1) for all x N0 (concavity). Important examples of Thiele rules are multiwinner approval voting (AV), defined by s(x) = x, proportional approval voting (PAV), defined by s(x) = Px y=1 1 y, and Chamberlin-Courant approval voting (CCAV), defined by s(x) = 1 for all x > 0.

Sequential query rules. Generalizing concepts of Brill et al. (2023) and Dong and Lederer (2023), we introduce the class of sequential query rules. The idea of this class is to encapsulate ABC voting rules that compute the winning committees by sequentially adding candidates. To formalize this, we let S(C) denote the set of all non-repeating sequences of candidates with length ℓ m 2. In particular, the empty set is the only sequence of length 0. The central concept for sequential query rules are query functions g which take a profile A, a target committee size k, and a sequence S = (c1, . . . , cℓ) S(C) as input and return a subset of C \ {c1, . . . , cℓ}. Intuitively, g(A, k, S) are the candidates that will be chosen next given that the candidates in S have been selected in this order. Moreover, we demand that g(A, k, S) is non-empty whenever S is generated by g. Formally, we say a sequence S = (c1, . . . , cℓ) is valid for g(A, k, ) if S = or ci g(A, k, (c1, . . . , ci 1)) for all 1 i ℓ. We require that g(A, k, S) = whenever S is valid and ℓ< k. Finally, an ABC voting rule f is a sequential query rule induced by the query function g if f(A, k) = {{c1, . . . , ck} Wk : (c1, . . . , ck) is valid for g(A, k, )} for all profiles A and committee sizes k. The class of sequential query rules as defined here is actually equivalent to the set of ABC voting rules as there are no restrictions on g. Hence, we will later introduce axioms for sequential query rules to pinpoint when a sequential query rule fails participation. In the following, we introduce several voting rules that can be easily described as sequential query rules.

Sequential Thiele rules. Sequential Thiele rules are greedy versions of Thiele rules and have also been suggested by Thiele (1895). Given some Thiele scoring function s, these rules extend in every step each committee W of the previous step with the candidates c that increase the score the most. More formally, sequential Thiele rules are sequential query rules defined by the query function g(A, k, (c1, . . . , cℓ)) = argmaxx C\{c1,...,cℓ}ˆs(A, {x, c1, . . . , cℓ}). Prominent examples of sequential Thiele rules are seq CCAV and seq PAV which are the sequential versions of CCAV and PAV. Note that the sequential version of AV is identical to AV.

Sequential Phragm en. This rule (seq Phragm en), which was suggested by Phragm en (1895) and rediscovered by Brill et al. (2017), relies on a cost-sharing mechanism. In more detail, seq Phragm en assumes that each candidate has a cost of 1 and each voter starts with a budget of 0. Over time, the budget of each voter increases uniformly and as soon as the voters that approve some candidate c have a total budget of 1, they buy c and add it to the winning committee. The budget of these (and only these) voters is then reset to 0. The process continues until k candidates have been bought. Clearly, seq Phragm en is a sequential query rule.

Method of equal shares. The method of equal shares (MES), which is due to Peters and Skowron (2020), works sim-

ilar to seq Phragm en. In particular, every candidate again costs 1, but every voter i starts with a budget of x0(i) = k

n instead of earning budget over time. MES then tries to buy candidates in sequential steps. In more detail, let xr(i) denote the budget of each voter i after r steps and let X = {c1, . . . , cr} denote the set of candidates that have already been bought. We define by Cr := {c C \ X : P i NA(c) xr(i) 1} the set of candidates that can still be afforded. If Cr = , we add the candidate c Cr to the winning committee that incurs the minimal cost to the voter paying the most when splitting the cost as equally as possible, i.e., c minimizes ρ(c) with P i NA(c) min(ρ(c), xr(i)) = 1. Next, we set xr+1(i) = xr(i) min(ρ(c), xr(i)) for i NA(c) and xr+1(i) = xr(i), otherwise. We then continue with the next round. This process, typically called Phase 1 of MES, iterates until Cr = . If at this point less than k candidates have been bought, Phase 2 of MES starts where we have to complete the committee. For this, a variant of seq Phragm en is used where voters keep their remaining budget from Phase 1.

2.2 Participation

We next turn to the central axiom of this paper, participation. The idea of this condition is that voters should not be worse off when voting instead of abstaining. To formalize this, we say that a voter i (weakly) prefers a committee W to committee W (denoted by W i W ) if |W Ai| |W Ai|, and strictly prefers W to W (denoted by W i W ) if |W Ai| > |W Ai|. This approach is the standard to extend voters preferences to preferences over committees (see, e.g., Aziz et al. 2015; Botan 2021; Delemazure et al. 2023). Since our ABC voting rules return sets of committees, we furthermore need to lift the voters preferences to sets of committees. Following the literature (Kluiving et al. 2020; Botan 2021), we use Kelly s extension. This extension states that a voter i prefers a set of committees X to another set of committees Y (denoted by X i Y ) if W i W for all W X and W Y (Kelly 1977). Moreover, this preference is strict (denoted by X i Y ) if there are W X, W Y with W i W . Kelly s extension guarantees that X i Y if and only if voter i weakly prefers the outcome chosen from X to the outcome chosen from Y regardless of the tie-breaking. We note, however, that all of our results except the complexity results in Section 3.3 are rather independent of the extension to sets of committees and, for instance, also hold under lexicographic tie-breaking or other extensions such as Fishburn s extension (Fishburn 1972), G ardenfors extension (G ardenfors 1976) or the leximax extension (Jimeno, P erez, and Garc ıa 2009). Now, an ABC voting rule f satisfies participation if f(A i, k) i f(A, k) for all profiles A, voters i NA, and committee sizes k {1, . . . , m 1}. Put differently, participation ensures that voters can never benefit by abstaining. To further strengthen the axiom, we say that a group of voters I NA benefits from abstaining for a profile A and committee size k if f(A I, k) i f(A, k) for all i I and f(A I, k) i f(A, k) for some i I. Then, an ABC voting rule f satisfies group participation if it is never possible for a group of voters to benefit by abstaining.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

3 Results We are now ready to formulate our results. In Section 3.1, we will show that ABC scoring rules satisfy group participation and that most sequential ABC voting rules fail participation. In Section 3.2, we thus explore two axiomatic escape routes to the impossibility for sequential rules. Finally, in Section 3.3, we show for our considered sequential ABC voting rules that it is NP-hard to decide for a voter whether she benefits by abstaining. Due to space restrictions, we defer all proofs not discussed here to the full version (Bullinger et al. 2023).

3.1 Participation for ABC Voting Rules The goal of this section is to understand which ABC voting rules satisfy participation. To this end, we first show that all ABC scoring rules even satisfy group participation.

Theorem 1. Every ABC scoring rule satisfies group participation.

Proof. Let f be an ABC scoring rule and let s denote its scoring function. We assume for contradiction that there is a profile A, a committee size k, and a group of voters I NA that benefits from abstaining, i.e., f(A I, k) i f(A, k) for all i I and f(A I, k) i f(A, k) for some i I. Next, we proceed with a case distinction with respect to f(A I, k) and first consider the case that there is W f(A I, k) \ f(A, k). By definition of Kelly s extension, this means that |W Ai| |W Ai| for all W f(A, k) and i I. Using the definition of ABC scoring rules, it hence follows that P i I s(|Ai W|, |Ai|) P i I s(|Ai W |, |Ai|). On the other hand, it holds that ˆs(A, W ) > ˆs(A, W) since W f(A, k) and W f(A, k). Combining these facts then implies that ˆs(A I, W) = ˆs(A, W) P i I s(|Ai W|, |Ai|) < ˆs(A, W ) P i I s(|Ai W |, |Ai|) = ˆs(A I, W ), which contradicts that W f(A I, k). As the second case, we suppose that f(A I, k) f(A, k) and let W f(A I, k), W f(A, k) \ f(A I, k). Using Kelly s extension, we infer again that |W Ai| |W Ai| for all i I, so P i I s(|Ai W|, |Ai|) P i I s(|Ai W |, |Ai|). Moreover, ˆs(A, W) = ˆs(A, W ) because W, W f(A, k). We conclude that ˆs(A I, W) ˆs(A I, W ), which contradicts our assumption because W f(A I, k) is then only possible if W f(A I, k). Since we have a contradiction in both cases, f satisfies group participation.

Next, we turn to sequential ABC voting rules. As discussed before, for some of these rules (e.g., seq PAV, seq Phragm en, and MES), earlier results in the literature imply that they fail participation (Janson 2016; Lackner and Skowron 2023, Prop. A.3). We will next show that the incompatibility is much more far-reaching as essentially all sequential rules other than AV fail participation. In more detail, we introduce three mild axioms for query functions and prove that every sequential query rule whose query function satisfies these conditions fails participation.

Continuity. Continuity has been introduced by Young (1975) for single-winner voting rules and requires that large groups of voters can enforce that some of their desired outcomes are chosen. Formally, we say that a query function g

satisfies continuity if for all A, A , k and S S(C), it holds that g(λA + A , k, S) g(A, k, S) for every sufficiently large λ N. The sum of approval profiles means that a copy for each voter in each profile is present, and the multiplication by a non-negative integer λ that λ copies of each voter are present.

Standardness. A condition that almost all commonly considered sequential ABC voting rules satisfy is that they typically choose the approval winner as first candidate. We formalize this as standardness: a query function g is standard if g(A, k, ) = AV(A, 1).

Concurrence. While the previous two axioms are necessary for Theorem 2, they do not capture its essence as AV and other sequential rules satisfy continuity, standardness, and participation. The crucial observation is that sequential query rules only optimize the voter satisfaction myopically, which causes a dependence on the history of previous choices. For instance, consider the following profile with 4 ballots, let k = 2, and suppose that candidate c is chosen first.

1 {a, b} 1 {b, c} 1 {a} 1 {c}

Essentially all commonly considered sequential ABC voting rules but AV will choose a and not b as next candidate because the voter who approves b and c is already partially satisfied. More generally, let S S(C) be a sequence of already chosen candidates and consider a, b C with |NA(a)| |NA(b)| such that in each step of S the voters approving b are at least as satisfied as the voters approving a. Concurrence captures the idea that sequential rules prefer to choose a over b in such a situation. To formalize this in a fashion that encompasses all commonly considered sequential rules, we add technical restrictions which weaken the axiom. In more detail, we call a query function g concurring if the following holds: Consider a profile A such that |Ai| 2 for all i NA and |NA(c)| = |NA(d)| n

k for all c, d C, and a sequence of already chosen candidates (c1, . . . , cℓ) S(C). Then, for all candidates c, d C \ {c1, . . . , cℓ} such that |{i NA : Ai = {cj, d}}| |{i NA : Ai = {cj, c}}| for all j {1, . . . , ℓ}, where one of these inequalities is strict, it holds that d g(A, k, (c1, . . . , cℓ)). As we show next, myopic efficiency (in the form of concurrence) is the main culprit for the no-show paradox of sequential query rules.

Theorem 2. Every sequential query rule fails participation if k 3 and its query function is standard, concurring, and continuous. Even more, a voter can obtain only 1 approved candidate when participating while obtaining k 1 approved candidates when abstaining.

Proof. Let f denote a sequential query rule and suppose its query function g is standard, concurring, and continuous. Moreover, we let k 3 denote the target committee size and set C = {a1, . . . , ar, b1, . . . , br} for r = k 1. Next, consider the following profile A: first, we add for every two element subset B C except for {a1, b1} and {ar, br} a voter who approves B; second, we add for each i {2, . . . , r} two voters who approve {ai, b1} and for each j {2, . . . , r 1} two voters who approve {bj, ar}; third, we add a voter who

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Figure 1: Visualization of the profile A for the proof of Theorem 2. A black, orange, or blue edge between two alternatives means that there is (are) exactly one, two, or three voter(s) who approve(s) the connected candidates, respectively.

approves {b1, br} and a voter who approves {a1, ar}; finally, we add voters who approve only a single candidate such that all candidates have the same approval score. Moreover, if k = 3, we add another candidate d before the last step that shares three ballots {b, x} with each x C to ensure that |NA(x)| n

k for all x C. This candidate will be ignored from now on as it does not affect our analysis. Figure 1 visualizes this profile by depicting ballots of size 2 as edges.

We next determine the winning committees for A and first note that g(A, k, ) = C by standardness. Hence, (a1) is a valid sequence. Our first goal is to show that all ways of extending (a1) lead to the committee {a1, b1, . . . , br}. First, concurrence implies that g(A, (a1)) = {b1}, as all other candidates share some ballot with a1. Hence, the only valid continuation is (a1, b1). We next suppose inductively that (a1, b1, . . . , bℓ 1) is a valid sequence with ℓ< r. We now check the requirements for concurrence and consider to this end the candidate bℓ. First, we note that there is one voter who reports {bℓ, x} for each alternative x {a1, b1, . . . , bℓ 1}. By contrast, for each candidate ai with i 2, there is at least one voter who reports {ai, x} for each x {a1, b2, . . . , bℓ 1} and three voters who report {b1, ai}. So, concurrence implies that ai g(A, k, (a1, b1, . . . , bℓ 1)). Similarly, we can check that br is not in this set because two voters report {b1, br} but only a single voter reports {b1, bℓ}. Hence, g(A, k, (a1, b1, . . . , bℓ 1)) {bℓ, . . . , br 1} and due to the symmetry of these candidates in A, we can suppose that bℓ g(A, k, (a1, b1, . . . , bℓ 1)). For the final step, we need to compare br with ai with i > 1. Since b1 only shares two ballots with br and three with each candidate ai for i 2, and each other candidate x {a1, b2, . . . , br 1} shares one ballot with br and at least one ballot with ai, concurrence necessitates g(A, (a1, b1, . . . , br 1)) = {br}. Finally, we conclude that {a1, b1, . . . , bk} is the only chosen committee of size k when electing a1 in the first round. Moreover, an analogous argument shows that g can only extend the sequence (br) to the committee {br, a1, . . . , ar}.

As the next step, we let A denote a profile which consists of four voters who report {a1, . . . , ar}, {b1, . . . , br}, {a1}, and {br} respectively. Furthermore, let A = λA + A for some λ N. By standardness, we obtain that g(A , ) = {a1, br} regardless of the choice of λ. Next, by continuity, we can choose λ large enough such that g(A , s) g(A, s) for all sequences s S(C). By combining this with our previous analysis, it is now easy to infer that f(A , k) = {{a1, b1, . . . , br}, {br, a1, . . . , ar}}. Finally, to show that f fails participation, we consider the profile A i where the voter i with ballot {a1, . . . , ar} abstains. By standardness, it follows that g(A i, ) = {br}. Furthermore, for large enough λ, we get again that g(λA + A i, k, s) g(A, k, s) for all s S(C). This means that f(A i, k) = {{br, ar, . . . , a1}}, so voter i can benefit by abstaining and f fails participation.

As a corollary of Theorem 2, it follows immediately that seq Phragm en, MES, and all sequential Thiele rules but AV fail participation because the query functions of these rules satisfy all conditions of Theorem 2.

Corollary 1. Every sequential Thiele rule except AV, as well as seq Phragm en and MES fail participation.

Remark 1. The axioms of Theorem 2 are independent. All Thiele rules but AV satisfy all properties but standardness and AV only violates concurrence. Moreover, if we adapt AV to break ties whenever concurrence requires it, the resulting rule only fails continuity. By contrast, Theorem 2 turns into a possibility if k 2 or if requiring that a voter needs to approve all of the elected candidates after abstaining as sequential Thiele rules then satisfy participation.

Remark 2. We note that the proof of Theorem 2 can be adapted to show that also reverse sequential ABC voting rules, which start with a full committee and then iteratively delete candidates, and sequential Thiele rules with increasing marginal contribution fail participation. While such rules are only rarely considered in the literature, this shows that Theorem 2 is rather robust. Moreover, Example 7 by S anchez Fern andez and Fisteus (2019) entails that also the optimizing variants of seq Phragm en fail participation. By contrast, there are sequential rules other than AV that satisfy participation. In particular, Dong and Lederer (2024) introduce the class of ballot size weighted approval voting (BSWAV) rules. Since these rules are ABC scoring rules, they satisfy group participation by Theorem 1. However, all these rules coincide with their sequential version, thus giving a class of sequential ABC voting rules that satisfy participation. Notably, the proof of Theorem 2 can be modified to show that every sequential ABC scoring rule that satisfies participation and s(x, y) > 0 for all x, y > 0 belongs to this class.

3.2 Axiomatic Escape Routes to Theorem 2

We next consider two escape routes to Theorem 2: we first show that at least voters who do not approve any of the elected candidates cannot benefit by abstaining for most sequential ABC voting rules, and then that these rules satisfy participation on the important special case of laminar profiles.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Unrepresented Voters. The proof of Theorem 2 shows that voters who only approve a single elected candidate can significantly gain by abstaining and it is easy to extend this result to voters who approve more than one elected candidate. Hence, the only open case is whether voters who approve none of the elected candidates can benefit by abstaining. In analogy to the notion of strategyproofness for unrepresented voters by Delemazure et al. (2023), we thus require that a voter who approves none of the elected candidates cannot benefit by abstaining. More formally, we say an ABC voting rule f satisfies participation for unrepresented voters if f(A i, k) i f(A, k) for all approval profiles A, committee sizes k, and voters i NA for which there is a committee W f(A, k) with W Ai = . As we show next, all sequential Thiele rules and seq Phragm en satisfy this condition, whereas MES even fails this minimal notion of participation. We note that these results complement Theorem 2 by showing that the violation of participation observed in this result is maximal and, moreover, strengthen insights by Lackner and Skowron (2023, Prop. A.3) on a mild monotonicity axiom.

Proposition 1. Sequential Thiele rules and seq Phragm en satisfy participation for unrepresented voters. MES violates participation for unrepresented voters.

Proof sketch. The key insight why seq Phragm en and sequential Thiele rules satisfy participation for unrepresented voters is that an abstaining voter who does not approve any of the elected candidates cannot affect the picking sequence of the candidates. Indeed, the scores of her approved candidates are always too low to be picked and the voter only further reduces these scores by abstaining. By contrast, for MES, we construct a counterexample by using that an abstaining voter influences the budgets of other voters.

Laminar Profiles. As our second escape route to Theorem 2, we consider the effect of restricting the domain of feasible profiles. In particular, we will show that sequential Thiele rules, seq Phragm en, and MES satisfy participation on laminar profiles. To this end, we say that a profile A is laminar if for all candidates c, d C, it holds that NA(c) NA(d), NA(d) NA(c), or NA(c) NA(d) = . These profiles have been introduced by Peters and Skowron (2020) who additionally require size constraints on the sets NA(c) which make no sense in our context. Laminar profiles generalize the concept of party-list profiles (e.g., Brill, Laslier, and Skowron 2018; Botan 2021) and thus constitute an important special case of approval profiles.

Proposition 2. Sequential Thiele rules, seq Phragm en, and MES satisfy participation on laminar profiles.

Proof Sketch. The central idea for this proposition is that for laminar profiles A, the sets NA(c) can be represented by a forest F on the candidates where c is a child of d if NA(c) NA(d). For all considered rules, it then follows that it is always valid to add a candidate to the winning committee before any of her children. This structure on the picking order can be used to show that a voter cannot increase the number of her approved candidates by abstaining as the picking order imposed by the profile does not change.

3.3 Hardness of Abstention In this section, we investigate the following decision problem: given an election instance and a voter, can this voter benefit by abstaining from the election when a specific rule (e.g., MES or seq PAV) is used. This offers yet another perspective on Theorem 2: while many sequential rules fail participation, it can still be the case that the voters even when knowing the preferences of all other participants are unlikely to be able to efficiently decide whether they can benefit from abstention. The general proof idea for our reductions is as follows: the reduced instances consist of a part of the election mimicking an NP-hard problem together with a gadget that is a small election where it is beneficial to abstain for a voter. The elections then consist of essentially two stages. First, we select candidates associated with a proposed solution to the NP-hard source problem, e.g., a set of vertices of a given target size. Then, certain gadget candidates are selected. If the proposed solution to the NP-hard problem is not of the desired form, e.g., if the vertex set is not an independent set, then the selection of gadget candidates cannot be influenced by abstention. However, if the source instance is a Yes-instance, then some voter approving gadget candidates can benefit from abstention. As a first result in this section, we find that participation leads to a computational intractability for sequential Thiele rules. The proof is inspired by Janeczko and Faliszewski (2023). We showcase the proof and the general proof technique of this section by considering the special case of seq PAV. Theorem 3. For every sequential Thiele rule except AV, it is NP-hard to decide whether a voter can benefit from abstention.

Proof sketch for seq PAV. We perform a reduction from INDEPENDENTSET for cubic graphs (Garey and Johnson 1979). Given an instance (G, t) of INDEPENDENTSET, where G = (V, E) is a cubic graph and t N is the target size of the independent set, we construct the following reduced instance. Without loss of generality, we assume that we only consider instances where |V | 3, |E| > 0, |V |3 is divisible by 8, and t is divisible by 2. Since the independent set needs to be of size t and the graph is cubic, we assume |E| 3t. The set of candidates is C = {gi : i {1, . . . , 4}} CV , where CV = {cv : v V }. The candidates gi, called gadget candidates, form a gadget in which abstention might be performed and candidates cv, called vertex candidates, represent vertices v of the source instance. Let x = |V | and y = 1

4 . This is an integer by assumption. The approval profile is given as follows:

For each vertex v V , there exist x3 voters approving {cv}. For each pair of vertices {v, w} V , there exist x3 voters with approval set {cv, cw}. For each edge {v, w} E, there exists one voter with approval set {cv, cw, g1}. Moreover, there are voters approving only the gadget candidates. These are y voters for each of the approval sets {g1, g2}, {g1, g3}, {g2, g4}, {g3, g4}, |E| 3

2t N>0 voters approving {g2} (recall that t is divisible by 2, |E| > 0, and |E| 3t), and one voter approving {g1}.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

As usual, A denotes the approval profile. The target committee size is k = x + 3. Eventually, we will select all candidates in CV as well as 3 gadget candidates. We claim that a voter with approval set {g1, g3} can benefit from abstention if and only if the source instance is a Yes-instance. We qualitatively describe the election by seq PAV in the reduced instance. Initially, the score of vertex candidates is larger than the score of gadget candidates. By design of the scores, the first t candidates to be selected are vertex candidates. Now, the marginal gain to the score by gadget candidates overtakes the gain by vertex candidates, and we select two gadget candidates. The reduced instance is designed in a way such that without abstention, g1 always has the highest score among gadget candidates and is selected first. Then, the candidate g4 is selected. Afterwards, the committee is filled with the remaining vertex candidates and then a third gadget candidate. Since g2 contributes more than g3, we select g2 as the final candidate in the committee. Together, the choice set contains exactly the committee CV {g1, g2, g4}. If, however, a voter with approval set {g1, g3} abstains from the election, the election is similar but the committee CV {g1, g2, g3} may be selected additionally if the source instance was a Yes-instance. In summary, if the source instance is a No-instance, then the choice set is identical after abstention, and there is no incentive to abstain. Otherwise, the choice set additionally contains CV {g1, g2, g3} and is preferred by a voter with approval set {g1, g3} (due to Kelly s extension).

As a next result, we want to consider the method of equal shares. Importantly, an execution of MES may heavily rely on the completion method applied in Phase 2. We thus provide a reduction where a voter benefits from abstention both after Phase 1 and Phase 2 of MES. The same reduction also yields a result for seq Phragm en.

Theorem 4. Consider voting by MES. Then,

1. it is NP-hard to decide whether a voter can benefit from abstention after Phase 1. 2. it is NP-hard to decide whether a voter can benefit from abstention after Phase 2, even if none of her approved candidates are elected in Phase 2. Moreover, for seq Phragm en, it is NP-hard to decide whether a voter can benefit from abstention.

The proofs of our hardness results are quite universal and allow for a number of interesting consequences. First, if we omit the abstaining voter from the reduced instance, then there is exactly one possibly selected committee if the source instance is a No-instance, and two possible committees if the source instance is a Yes-instance. Hence, we recover the hardness of deciding whether the election contains more than one possible committee (Janeczko and Faliszewski 2023). Second, it is interesting to see why we formulate our theorems as NP-hardness, but not NP-completeness, i.e., we do not know whether membership in NP holds. In fact, it is unclear whether this actually is true. In particular, we cannot use the outcomes of elections as polynomial-size certificates for verifying whether a voter benefits from abstention because we cannot check this in polynomial time.

Corollary 2. For every sequential Thiele rule except AV, as well as for Phase 1 or complete MES, and seq Phragm en, the following statements are true. 1. Given a set of committees C, it is co NP-complete to decide whether C is the outcome of the election. 2. Given a positive integer s, it is NP-complete to decide whether a given voter approves at least s candidates in some winning committee. Finally, our reductions give novel insights into the robustness of sequential ABC voting rules. Faliszewski, Gawron, and Kusek (2022) consider the question whether the outcome of an election can change if a given number of approvals of candidates can be added or removed. They find that this problem is NP-hard for seq CCAV, seq PAV, and seq Phragm en. However, they operate in a setting, where the election of a single committee is enforced by lexicographic tie-breaking and they need an unbounded budget of approvals to be added or deleted (but of linear magnitude with respect to the size of the source instance). As a third corollary from our reductions, we complement their results in the set-valued setting and obtain hardness even if we only add or delete a single approval. The result holds because for a tied second committee, only the approval of g1 by the abstaining voter is relevant. So, if the source instance is a Yes-instance, then this approval can be added or deleted to create or prevent a second outcome of the election. The reductions can be modified so that the addition or deletion of other candidates does not matter for its outcome. Corollary 3. For every sequential Thiele rule except AV, as well as for Phase 1 or complete MES, and seq Phragm en, it is NP-complete to decide if the outcome of the election can change if a single approval is added or deleted.

4 Conclusion In this paper, we initiate the study of participation for ABC voting rules. This axiom states that it can never be beneficial for voters to abstain and thus describes an incentive for active participation in elections. In more detail, we prove that all ABC scoring rules even satisfy group participation, thus generalizing a prominent phenomenon from single-winner voting to ABC elections. Moreover, we give a strong impossibility theorem demonstrating that most sequential rules (e.g., all sequential Thiele rules but AV, sequential Phragm en, and the method of equal shares) severely fail participation. In light of this strong negative result for sequential rules, we then explore various escape routes. In particular, we show that sequential Thiele rules and sequential Phragm en satisfy participation for voters who do not approve any candidate in the winning committee as well as participation on laminar profiles. These results demonstrate that sequential rules satisfy participation at least in important special cases. Finally, we also show that for all commonly studied sequential ABC voting rules, it is NP-hard to decide for a voter whether she can benefit by abstaining. This indicates that, while voters can in general benefit by abstaining, they may not be able to recognize this. Our approach for deriving these results is very universal and allows us to recover, strengthen, and extend existing hardness results.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgements We thank Felix Brandt, the participants of the Summer School on Computational Social Choice (University of Amsterdam, 2023), and the anonymous reviewers for helpful feedback. This work was supported by the Deutsche Forschungsgemeinschaft under grants BR 2312/11-2 and BR 2312/12-1, as well as by the AI Programme of The Alan Turing Institute.

References Aziz, H.; Gaspers, S.; Gudmundsson, J.; Mackenzie, S.; Mattei, N.; and Walsh, T. 2015. Computational Aspects of Multi Winner Approval Voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 107 115. Botan, S. 2021. Manipulability of Thiele Methods on Party List Profiles. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 223 231. Brandl, F.; Brandt, F.; Geist, C.; and Hofbauer, J. 2019. Strategic Abstention based on Preference Extensions: Positive Results and Computer-Generated Impossibilities. Journal of Artificial Intelligence Research, 66: 1031 1056. Brandl, F.; Brandt, F.; and Hofbauer, J. 2019. Welfare Maximization Entices Participation. Games and Economic Behavior, 14: 308 314. Brandt, F.; Geist, C.; and Peters, D. 2017. Optimal Bounds for the No-Show Paradox via SAT Solving. Mathematical Social Sciences, 90: 18 27. Special Issue in Honor of Herv e Moulin. Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Niedermeier, R.; Skowron, P.; and Talmon, N. 2021. Roubstness among multiwinner voting rules. Artificial Intelligence, 290: 103403. Brill, M.; Dindar, H.; Israel, J.; Lang, J.; Peters, J.; and Schmidt-Kraepelin, U. 2023. Multiwinner Voting with Possibly Unavailable Candidates. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI). Forthcoming. Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017. Phragm en s Voting Methods and Justified Representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 406 413. Brill, M.; Laslier, J.-F.; and Skowron, P. 2018. Multiwinner Approval Rules as Apportionment Methods. Journal of Theoretical Politics, 30(3): 358 382. Bullinger, M.; Dong, C.; Lederer, P.; and Mehler, C. 2023. Participation Incentives in Approval-Based Committee Elections. Technical report, https://arxiv.org/abs/2312.08798. Cevallos, A.; and Stewart, A. 2021. A verifiably secure and proportional committee election rule. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, 29 42. Delemazure, T.; Demeulemeester, T.; Eberl, M.; Israel, J.; and Lederer, P. 2023. Strategyproofness and Proportionality in Party-approval Multiwinner Elections. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), 5591 5599.

Dong, C.; and Lederer, P. 2023. Characterizations of Sequential Valuation Rules. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1697 1705. Dong, C.; and Lederer, P. 2024. Refined Characterizations of Approval-Based Committee Scoring Rules. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI). Forthcoming. Duddy, C. 2014. Condorcet s principle and the strong noshow paradoxes. Theory and Decision, 77(2): 275 285. Faliszewski, P.; Gawron, G.; and Kusek, B. 2022. Using Multiwinner Voting to Search for Movies. In Proceedings of the 19th European Conference on Multi-Agent Systems (EUMAS), Lecture Notes in Computer Science (LNCS), 116 133. Springer-Verlag. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner Voting: A New Challenge for Social Choice Theory. In Endriss, U., ed., Trends in Computational Social Choice, chapter 2. Fishburn, P. C. 1972. Even-chance lotteries in social choice theory. Theory and Decision, 3(1): 18 40. G ardenfors, P. 1976. Manipulation of Social Choice Functions. Journal of Economic Theory, 13(2): 217 228. Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Gawron, G.; and Faliszewski, P. 2022. Using Multiwinner Voting to Search for Movies. In Proceedings of the 19th European Conference on Multi-Agent Systems (EUMAS), Lecture Notes in Computer Science (LNCS), 134 151. Springer Verlag. Hofbauer, J. 2019. Should I Stay or Should I Go? The No Show Paradox in Voting and Assignment. Ph.D. thesis, Technische Universit at M unchen. Janeczko, L.; and Faliszewski, P. 2023. Ties in Multiwinner Approval Voting. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2765 2773. Janson, S. 2016. Phragm en s and Thiele s election methods. Technical Report ar Xiv:1611.08826 [math.HO], ar Xiv.org. Jimeno, J. L.; P erez, J.; and Garc ıa, E. 2009. An extension of the Moulin No Show Paradox for voting correspondences. Social Choice and Welfare, 33(3): 343 459. Kelly, J. S. 1977. Strategy-Proofness and Social Choice Functions Without Single-Valuedness. Econometrica, 45(2): 439 446. Kluiving, B.; de Vries, A.; Vrijbergen, P.; Boixel, A.; and Endriss, U. 2020. Analysing Irresolute Multiwinner Voting Rules with Approval Ballots via SAT Solving. In Proceedings of the 24th European Conference on Artificial Intelligence (ECAI). Lackner, M.; and Skowron, P. 2021. Consistent Approval Based Multi-Winner Rules. Journal of Economic Theory, 192: 105173. Lackner, M.; and Skowron, P. 2023. Multi-Winner Voting with Approval Preferences. Springer-Verlag.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Mora, X.; and Oliver, M. 2015. Eleccions mitjanc ant el vot d aprovaci o. El m etode de Phragm en i algunes variants. Butllet ı de la Societat Catalana de Matem atiques, 30(1): 57 101. Moulin, H. 1988. Condorcet s Principle implies the No Show Paradox. Journal of Economic Theory, 45(1): 53 64. P erez, J. 2001. The Strong No Show Paradoxes are a common flaw in Condorcet voting correspondences. Social Choice and Welfare, 18(3): 601 616. P erez, J.; Jimeno, J. L.; and Garc ıa, E. 2010. No Show Paradox in Condorcet k-voting Procedure. Group Decision and Negotiation, 21(3): 291 303. Peters, D. 2018. Proportionality and Strategyproofness in Multiwinner Elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), volume 1549 1557. Peters, D.; and Skowron, P. 2020. Proportionality and the Limits of Welfarism. In Proceedings of the 21nd ACM Conference on Economics and Computation (ACM-EC), 793 794. Phragm en, E. 1895. Proportionella val. En valteknisk studie. Svenska sp orsm al 25. Lars H okersbergs f orlag, Stockholm. S anchez-Fern andez, L.; and Fisteus, J. A. 2019. Monotonicity axioms in approval-based multi-winner voting rules. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 485 493. Thiele, T. N. 1895. Om Flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 415 441. Young, H. P. 1975. Social Choice Scoring Functions. SIAM Journal on Applied Mathematics, 28(4): 824 838.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)