--- title: "Proportionality in Approval-Based Elections With a Variable Number of Winners" authors: - "Rupert Freeman" - "Anson Kahng" - "David M. Pennock" doi: "10.24963/ijcai.2020/19" url: "https://ijcai.org/proceedings/2020/19" pdf: "https://ijcai.org/proceedings/2020/0019.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "132-138" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" - "Agent-based and Multi-agent Systems: Computational Social Choice" - "Agent-based and Multi-agent Systems: Voting" --- # Proportionality in Approval-Based Elections With a Variable Number of Winners Rupert Freeman, Anson Kahng, David M. Pennock *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 132-138. DOI: [10.24963/ijcai.2020/19](https://doi.org/10.24963/ijcai.2020/19) ## Abstract We study proportionality in approval-based multiwinner elections with a variable number of winners, where both the size and identity of the winning committee are informed by voters' opinions. While proportionality has been studied in multiwinner elections with a fixed number of winners, it has not been considered in the variable number of winners setting. The measure of proportionality we consider is average satisfaction (AS), which intuitively measures the number of agreements on average between sufficiently large and cohesive groups of voters and the output of the voting rule. First, we show an upper bound on AS that any deterministic rule can provide, and that straightforward adaptations of deterministic rules from the fixed number of winners setting do not achieve better than a 1/2 approximation to AS even for large numbers of candidates. We then prove that a natural randomized rule achieves a 29/32 approximation to AS. ## Full text ## 1 Introduction We study multiwinner approval-based elections, where a group of agents, or voters, selects a committee from a set of candidates based on the agents' preferences. Each agent expresses her preferences through an approval vote, where she designates a subset of candidates she approves for the committee, and all votes are then aggregated to select a winning committee from the pool of candidates. Some multiwinner elections include a fixed committee size: the outcome must fill exactly k seats on a committee. This is known as the fixed number of winners (FNW) setting, and there is a large body of work on the complexity and proportionality of various voting rules in the FNW setting [Aziz et al., 2017; S´anchez-Fern´andez et al., 2017; Aziz et al., 2018; Brill et al., 2017; Peters and Skowron, 2019; Skowron et al., 2017b]. In contrast, we are interested in the setting in which there is no a priori fixed committee size, also known as the variable number of winners (VNW) setting. In this case, both the size of the committee and the candidates chosen to sit on the committee are informed by agents' votes. ∗Contact Author We present a setting where VNW elections are a natural fit; Faliszewski et al. [2017] discuss others. Consider an election that consists of a series of ballot measures, where each ballot question can easily be reversed such that "Yes" becomes "No" and "No" becomes "Yes". This is a practical concern, as ballots are often deliberately constructed such that a "Yes" on one question represents a vote in favor of upholding a current statute, while a "Yes" on another question down the ballot represents a vote in favor of repealing a current statute [Mueller, 1969]. In this case, voters derive utility from every decision they agree with, whether it is an approval vote or a disapproval vote. Note that, because there is no set number of measures that must be "elected" (i.e., passed), this constitutes a VNW election. It can be important to ensure that the selected alternatives are chosen in a proportional manner. For instance, in the case of ballot measures, we may want to ensure that all groups in the electorate are satisfied with at least some of the outcomes. In other words, a small majority of the electorate should not be able to overrule a sizable minority on every ballot measure. In order to study proportionality in FNW elections, researchers have proposed the axioms of justified representation (JR), proportional justified representation (PJR), extended justified representation (EJR), and average satisfaction (AS) [Aziz et al., 2017; S´anchez-Fern´andez et al., 2017], which capture the intuition that all sufficiently large groups that agree on sufficiently many candidates should achieve some measure of satisfaction. However, to our knowledge, we are the first to study representation in VNW elections. Our Contributions. Our main research goal is to study proportionality in multiwinner elections with a variable number of winners. In particular, we study the proportionality measure of average satisfaction (AS) and show that there is a separation between the performance of deterministic and randomized voting rules. As our first contribution, we develop a framework for thinking about proportionality in VNW elections. Previous work on proportionality in FNW elections is largely based on the concept of justified representation (and extensions thereof). However, as we discuss in Section 3, JR-based notions of proportionality are less compelling in VNW elections than in FNW elections. Therefore, we instead base our approach on the concept of average satisfaction, which is arguably a more robust version of justified representation. Second, in Section 4, we consider the proportionality guarantees of deterministic rules in the VNW setting. We extend three existing deterministic rules for the FNW setting to the VNW setting, and show that these rules do not guarantee good approximations to average satisfaction. We also prove upper bounds on the level of average satisfaction that any deterministic rule can provide. Finally, in Section 5, motivated by the shortcomings of deterministic rules, we turn our attention to randomized rules and show that a natural randomized rule provides a good approximation to average satisfaction. ## 1.1 RelatedWork There is a significant body of work studying proportionality in FNW elections. As mentioned above, Aziz et al. [2017] put forward the compelling axiom of justified representation (JR), as well as a stronger version of this axiom, extended justified representation (EJR) to capture the notion that any sufficiently large and cohesive group of voters deserves some measure of representation in the elected committee. S´anchezFern´andez et al. [2017] build on this idea by introducing the intermediate axiom of proportional justified representation (PJR), a relaxation of EJR that is more stringent than JR. Average satisfaction (AS) was first defined by S´anchezFern´andez et al. [2017], who study the average satisfaction guaranteed by extended justified representation (EJR). Further work by Aziz et al. [2018] shows that Proportional Approval Voting (PAV) guarantees a level of average satisfaction that implies EJR. Additionally, Skowron et al. [2017a] extend the notion of average satisfaction to the context of complete rankings as opposed to committee selection. Further work by Skowron [2018] studies the proportionality degree of various multiwinner rules by considering the average satisfaction of all groups of a certain size. There is also a significant body of work studying VNW elections; however, to the best of our knowledge, none of the proposed rules satisfy proportionality (and, in general, that is not their goal). Kilgour [2016] proposes a multitude of rules for VNW elections, including satisfaction approval voting and variants thereof. In a related vein, Kilgour et al. [2006] and Brams et al. [2007] study the minimax and minisum rules for selecting a committee in the VNW setting. Fishburn and Pekeˇc [2004] study threshold approaches to committee selection, which are VNW rules in the sense that the size of the selected committee depends on the approval votes. Additionally, the Mean Rule [Duddy et al., 2016] and Borda Mean Rule [Brandl and Peters, 2019] can be seen as VNW rules when given approval votes. Finally, Faliszewski et al. [2017] study the computational complexity of various VNW rules, but do not consider proportionality in their analysis. ## 2 Preliminaries Let N = {v1, . . . , vn} be a set of n voters and C = {c1, . . . , cm} be a set of m candidates. For every voter vi, denote by Ai ⊆ C the set of candidates that are approved by vi. A preference profile A = {A1, . . . ,An} is the set of all voter preferences Ai. A variable number of winners (VNW) voting rule f takes as input a preference profile A and outputs some set of candidates f(A) ⊆ C. Note that we allow f(A) = ∅ or f(A) = C. We will also consider randomized VNW voting rules that output a distribution over sets of candidates. Throughout this paper, we will denote by W the set of candidates included in the committee, and we will denote by C \ W the set of candidates excluded from the committee. We say that a group of voters V ⊆ N is ℓ-large if |V | ≥ ℓ · nm , and ℓ-cohesive if | ∩i∈V Ai| + | ∩i∈V C \ Ai| ≥ ℓ. We will also say that a group of voters V agrees on a candidate cj if cj ∈ Ai for all i ∈ V or cj ̸∈ Ai for all i ∈ V . Otherwise, we say that V disagrees on cj. Intuitively, a group of voters is ℓ-large and ℓ-cohesive if they constitute an ℓ/m fraction of all voters who agree on ℓ out of m candidates. In our work, we consider a different measure of representation than in the FNW setting. In the FNW setting, voters derive utility from the number of their approved candidates elected to the committee. However, this definition cannot be easily adapted to the VNW setting because then a rule could maximally satisfy all voters by including all candidates on the committee. Therefore, we assume that voters derive utility from agreeing with the placement of candidates either on the committee or not on the committee. For instance, in an election with two candidates, c1 and c2, if a voter i has approval set Ai = {c1} (i.e., she approves c1 and disapproves c2), then she receives one unit of utility for the output committee {c1, c2} because she agrees with the inclusion of c1 but disagrees with the inclusion of c2. With this in mind, the following definition of average satisfaction is adapted from the definition of S´anchez-Fern´andez et al. [2017] in the FNW setting. Definition 1. Given a set of candidates W ⊆ C, the average satisfaction of a group of voters V ⊆ N is We can now define AS in the VNW setting. 1 The intuition behind the following definition is that any sufficiently large and cohesive group of voters deserves to be adequately represented on average, which is a departure from justified representation-based axioms that have been studied in the FNW setting. Intuitively, JR-like notions of proportionality only require that some member of each cohesive group is represented to some extent, whereas average satisfaction requires all members of each cohesive group to be represented (at least on average). Definition 2. A set of candidates W ⊆ C satisfies α-AS if, for all ℓ-large and ℓ-cohesive groups of voters V ⊆ N, avsW(V ) ≥ α · ℓ for all ℓ ∈ [m]. For brevity, we refer to the special case of 1-AS as AS. The following example demonstrates cohesiveness and average satisfaction. 1 Note that we overload the use of the term "average satisfaction" to refer to both the numerical quantity from Definition 1 (average satisfaction) as well as the axiomatic property in Definition 2 (AS). Example 1. Consider the following profile with n = 8 voters, v1, . . . , v8, and m = 4 candidates, c1, . . . , c4, with pref- Now, consider the output W = {c4}. Note that each voter agrees with the output on the placement of at least one candidate, so for any 1-large and 1-cohesive group V(1) (i.e., a group of 1 · nm = 2 voters who agrees on the placement of 1 candidate), avsW(V(1)) ≥ 1. Furthermore, note that there is only one 2-large and 2-cohesive group of voters: v1, v2, v3, and v4 agree on the placement of c1 and c2, but disagree on the placement of c3 and c4, so they constitute a 2-large group of voters who agree on 2 candidates. Let V(2) = {v1, v2, v3, v4}. Note that avsW(V(2)) = 1 because each v ∈ V agrees with W on exactly one placement, but because this group of voters is 2-large and 2-cohesive, we see that W only satisfies 1/2-AS in this scenario. Given our definition of voter satisfaction, we can straightforwardly extend the following deterministic multiwinner rules from the FNW setting to the VNW setting. Proportional Approval Voting (PAV). Under the PAV rule [Thiele, 1895], voter i derives utility Hk = 1 + 1/2 + · · · + 1/k from a committee W , where k = |Ai ∩W | + |(C \ Ai) ∩ (C \ W)| is the number of candidate placements that i agrees with. The goal of PAV is to maximize the sum of all voters' utilities, and thus PAV outputs the subset W ⊆ C with highest PAV-score. Sequential Phragm´en (seq-Phragm´en). The seqPhragm´en rule [Phragm´en, 1899; Janson, 2016; Brill et al., 2017] is defined as follows. Each candidate carries a load of one unit, and this load is distributed among voters who agree with the placement of this candidate in either the included set or excluded set. The seq-Phragm´en rule proceeds iteratively by, in each round, placing the candidate that results in the smallest increase in the maximal load of any voter. Let x(t) i denote the load of voter i, and s(t) the maximal load, after t candidates have been placed. All voters start out with no load, x(0) i = 0. Furthermore, let Nj = {i ∈ N : cj ∈ Ai} represent the set of voters that approve of candidate cj . The maximal voter load if, on the tth placement, candidate cj is included in the committee is and the maximal voter load if candidate cj is excluded from the committee is because the load is distributed so as to equalize the loads of all voters who agree with the placement of cj. At each step t, seq-Phragm´en places the candidate cj that minimizes min(s(t) (cj), s(t) (cj)) and updates voter loads accordingly: in the case that cj is included in the committee, and in the case that cj is excluded from the committee, This rule proceeds until all candidates have been placed, and then returns the included and excluded candidates. Rule X. Rule X [Peters and Skowron, 2019] allocates each voter a budget of one dollar, which they then spend on placing candidates either in the included set or excluded set. Placing a candidate costs n/m dollars, and the set of voters who agree on the placement of this candidate must be able to collectively afford the placement. The rule starts with an empty included set W and an empty excluded set W, and it iteratively places candidates in the committee or its complement as follows. Let bi(t) be the amount of money that voter i has remaining after the tth candidate is placed; i.e., bi(0) = 1 for all voters vi ∈ N. At the tth step, we say that a candidate c ̸∈ W ∪W is q-affordable for some q ≥ 0 if In other words, candidate c is q-affordable if it can be placed in either the included or excluded set while voters who approve or disapprove of c each pay a maximum of q dollars. If no candidate is q-affordable for any q ≥ 0, then the rule stops, placing the current set of included candidates into W, the current set of excluded candidates into C \ W, and placing arbitrarily any candidates not already put into W or into C \ W. Else, the rule places the candidate which is qaffordable for the minimum value q in the approved or disapproved committee, according to voter preferences. Each voter who agrees with this placement has their budget updated to bi(t) = bi(t-1)-min(q, bi(t-1)), and the process continues. ## 3 Justified Representation in VNWElections In order to build intuition about why we focus on AS instead of (E/P)JR, we begin by defining JR, PJR, and EJR for VNW elections. In each case, the definition is a straightforward adaptation of the corresponding definition for the FNW setting, where we intuitively replace "agreement with members on the committee" with "agreement on the placement of each candidate." We slightly overload notation-namely, JR, PJR, and E JR-from the FNW setting in the following definitions. Definition 3 (JR). Consider a ballot profile A. A set of candidates W ⊆ C satisfies justified representation (JR) with respect to A if, for all sets of 1-large and 1-cohesive voters N ∗ , there exists an i ∈ N ∗ such that |Ai ∩W| + |(C \Ai) ∩ (C \ W)| ≥ 1. Definition 4 (PJR). Consider a ballot profile A. A set of candidates W ⊆ C satisfies proportional justified representation (PJR) with respect to A if, for all ℓ-large and ℓ-cohesive groups of voters N ∗ , | ⋃i∈N ∗ Ai ∩W|+|(⋃i∈N ∗(C \Ai))∩ (C \W)| ≥ ℓ for all ℓ ∈ [m]. Definition 5 (EJR). Consider a ballot profile A. A set of candidates W ⊆ C satisfies extended justified representation (EJR) with respect to A if, for all ℓ-large and ℓ-cohesive groups of voters N ∗ , there exists an i ∈ N ∗ such that |Ai ∩ W| + |(C \ Ai) ∩ (C \ W)| ≥ ℓ for all ℓ ∈ [m]. The following example illustrates these definitions. Example 2. Consider the same profile as in Example 1 with n = 8 voters, v1, . . . , v8, and m = 4 candidates, c1, . . . , c4. Again, consider the output W = {c4}. W satisfies JR because each voter agrees with the output on the placement of at least one candidate. Furthermore, W satisfies PJR because, on the only 2-large and 2-cohesive group of voters, {v1, v2, v3, v4}, two of them agree with the placement of c3 and two of them agree with the placement of c4. However, W does not satisfy EJR because no voter in the coalition agrees with two placements of W-they all agree with exactly one placement. We also study the relationship between the extensions of PAV, seq-Phragm´en, and Rule X, and different notions of justified representation in the VNW setting. The proofs of the following propositions are omitted due to space constraints. 2 Proposition 1. PAV satisfies PJR. Proposition 2. Seq-Phragm´en satisfies PJR. Proposition 3. Rule X satisfies PJR but not EJR. Notably, in the VNW setting, JR and PJR are less compelling notions of representation than in the FNW setting. In particular, whenever an ℓ-cohesive group of voters does not agree on the placement of a particular candidate, PJR automatically counts that candidate toward the group's representation quota, since at least one member of the group agrees with the candidate's placement. In other words, any disagreement within an ℓ-cohesive group results in partial representation, no matter the outcome of the election. This is particularly problematic for JR: any 1-large, 1-cohesive group of voters that disagrees on even a single candidate will never be witness to a violation of JR. Proposition 3 is also notable because Rule X satisfies EJR for FNW elections, but the straightforward extension of this rule does not satisfy EJR for VNW elections, demonstrating a qualitative difference between proportionality properties in the FNW and VNW settings. It is still an open question whether or not PAV and seq-Phragm´en satisfy EJR for VNW elections. ## 4 Deterministic Rules We begin by showing an upper bound on the level of average satisfaction that deterministic rules can provide. 2 All omitted proofs can be found in the full version of the paper on the authors' websites. Theorem 1. No deterministic rule satisfies ( m-1 m +ϵ)-AS for any m and any ϵ > 0. Proof. First, suppose that m is odd. Then set n = 2, with A1 = {c1, . . . , cm} and A2 = ∅. Without loss of generality, suppose that the output W is such that |W| > m2 . But then voter v2 is an m2 -large, m2 -cohesive group with average satisfaction at most m-1 2 , which yields an ( m-1 m )-AS approximation. Next, suppose m is even, and set n = 4m. Consider the profile Again, without loss of generality, suppose that the output W is such that |W| ≥ m2 . We consider two cases. In the first case, suppose that the output W has |W| ≥ m2 +1. Consider the m2 -large, m2 -cohesive group of voters V = {v3, v4}. We have which yields at most an ( m-1 m )-AS approximation. In the second case, suppose that the output W has |W| = m2 . Suppose that cm ̸∈ W (the case of cm ∈ W follows symmetrically). Then again consider V = {v3, v4}. We have again yielding an ( m-1 m )-AS approximation. This completes the proof. Theorem 1 leaves open the possibility that there exists a deterministic rule that provides quite good average satisfaction guarantees when the number of candidates is large. Finding such a rule or lowering the upper bound is an interesting open question. However, we show that none of the natural adaptations of FNW rules that we consider is able to guarantee better than a 0.5 approximation to AS even when m is large. Proof. Consider a profile with n = 2m voters with preferences This profile is symmetric in cm, so without loss of generality suppose that cm is included. Suppose that some k - 1 < m - 1 of the candidates c1, . . . , cm-1 are included. Then, the change in PAV score that would result from including an additional candidate is where the first inequality holds because k < m. Therefore, the maximum PAV score is achieved when all candidates c1, . . . , cm-1 are included. But then the group N ∗ = {v2m-1, v2m} is 1-large and 1-cohesive but is only satisfied 0.5 times on average. Theorem 3. seq-Phragm´en does not satisfy (0.5+ϵ)-AS, for any ϵ > 0 for m ≥ 2. Proof. Consider the same profile as in the proof of Theorem 2. It is easy to check that seq-Phragm´en begins by including candidates c1, . . . , cm-2, after which each voter of the first and second type has load m-2 2(m-1) . In the (m- 1)-th round, the algorithm has four choices: to include or exclude cm-1, or to include or exclude cm. Including cm-1 results in a load of m-1 2(m-1) = 12 on voters v1, . . . , v2m-2. Excluding cm-1 results in a load of 1 2 to voters v2m-1 and v2m. Including cm (which is symmetric to excluding cm) results in a load x to voters v1, . . . , vm-1, v2m-1, where x is the solution to mx- (m- 1) m-2 2(m-1) = 1, which yields a solution of x = 12 . The algorithm is therefore indifferent between all possible actions; breaking ties adversarially yields the inclusion of cm-1. Regardless of the inclusion or exclusion of candidate cm, the group N ∗ = {v2m-1, v2m} is 1-large and 1-cohesive but is only satisfied 0.5 times on average. We note that the dependence on tiebreaking in the proof of Theorem 3 can be removed by taking multiple copies of the profile used in the proof and changing the preference of a single voter. Theorem 4. Rule X does not satisfy (0.5 + ϵ)-AS, for any ϵ > 0 for m ≥ 3. 3 Proof. Consider the same profile used in the proof of Theorem 2. Rule X begins by including each of candidates c1, . . . , cm-1. Each of these candidates costs n m(2m-2) = 1 m-1 for each voter v1, . . . , v2m-2. In comparison, placing the last candidate at any point costs n/2 voters n/m n/2 = 2m , which is a greater cost than 1 m-1 when m ≥ 3. Including each of c1, . . . , cm-1 therefore costs v1, . . . , v2m-2 one dollar each. Regardless of the placement of cm, the 1-large and 1-cohesive group of voters N ∗ = {v2m-1, v2m} is satisfied only 0.5 times on average. ## 5 Randomized Rules We now turn our attention to randomized rules in order to achieve better average satisfaction guarantees. A randomized rule is one that outputs a distribution over committees rather than a single committee, and our approximation guarantee will hold in expectation over the possible committees. 4 We consider a simple and natural randomized rule that, for each candidate cj, includes cj in the set of winners W with probability equal to the fraction 5 of the voters who approve cj . 3 When m = 2, we know from Theorem 1 that no deterministic rule, including Rule X, can achieve better than a 0.5 approximation. 4 Recent work by Cheng et al. [2019] has applied randomization to proportionality in the FNW setting as well. Definition 6. Given a preference profile A, the Proportional Random Rule (PRR) independently includes each cj ∈ C in the winning committee W with probability Theorem 5. PRR satisfies 29/32-AS in expectation for any m. In the proof of Theorem 5, it will be helpful to think about the effect that an individual candidate has on the satisfaction of a group G. For an outcome W, a group of voters G, and a candidate cj, we say that the contribution from cj to the average satisfaction of G is avscj (G) = |{i : cj ∈ Ai}|/|G| if cj ∈ W or avscj (G) = |{i : cj ̸∈ Ai}|/|G| if cj ̸∈ W. Note that avsW (G) = ∑mj=1 avscj (G). Proof. We prove the result in two steps. First, we show that when ℓ ≤ m/3, PRR achieves an average satisfaction of ℓ; second, we show that when ℓ > m/3, PRR achieves an average satisfaction of (29/32)ℓ. Case 1: ℓ ≤ m/3. Consider an ℓ-cohesive group, G, of size ℓn/m, and a candidate cj. Note that it is sufficient to consider groups of size exactly ℓn/m because if there exists an ℓ-cohesive larger group that violates the desired guarantee, there must exist a subset of size ℓn/m that also violates the guarantee. Let kA = |{vi ∈ G : cj ∈ Ai}| denote the number of voters in G who approve cj , and kD = ℓn/m- kA denote the number of voters in G who disapprove cj . Without loss of generality, let kA ≤ kD. Further, suppose that x of the voters in N \ G approve cj and y = n - ℓn/m - x voters in N \ G disapprove cj . The expected contribution from cj to the average satisfaction of G is Because kA ≤ kD and x + y is fixed, this expression is minimized when y = 0. We therefore have where the inequality holds because kD ≤ ℓn/m by definition, and we can assume m ≥ 3 because ℓ must be at least 1. Summed over all candidates, the average satisfaction of G is at least ℓ, as required. 5 The marginal probabilities for each candidate being included in the committee are the same under this rule as the random dictatorship rule. The distribution over committees induced by the two rules is different, however. Case 2: ℓ > m/3. Consider an ℓ-cohesive group, G, of size ℓn/m, and a candidate cj. Let kA = |{vi ∈ G : cj ∈ Ai}| denote the number of voters in G who approve cj, and kD = ℓn/m- kA denote the number of voters in G who disapprove cj. Without loss of generality, let kA ≤ kD. As in the previous case, it is easy to show that the expected contribution from cj to G's average satisfaction is minimized when all voters in N \ G approve cj . We therefore have that Substituting kD = ℓn/m- kA, taking the derivative with respect to kA, and setting to 0 yields where the inequality follows from the assumption that ℓ > m/3. Furthermore, the second derivative with respect to kA is 4/n > 0, and therefore kA = (3ℓn/m- n)/4 is a local minimum. The expected contribution from cj to G's average satisfaction can therefore be as low as We also note that, because G is ℓ-cohesive, there exist at least ℓ candidates that G agrees on. Each of these candidates has where the first inequality follows from G being ℓ-cohesive and the second from G being ℓ-large. Summing over the contributions of all candidates, the average satisfaction of G is at least Our goal is to lower bound the term in parentheses by 29 32 , thus providing the desired approximation guarantee. Setting ℓ = αm, where α ∈ ( 13 , 1), and differentiating with respect to α yields Setting equal to 0 yields so the only critical point in the interval α ∈ (1/3, 1] is α = 2/3. It is easy to check that the second derivative is positive at α = 2/3, so average satisfaction is minimized at this point. Plugging ℓ = 2m/3 into Equation 1 yields a 29/32 approximation to AS, as desired. Guided by Theorem 5, we show that the bound is tight. Theorem 6. PRR does not satisfy (29/32 + ϵ)-AS for any ϵ > 0. Proof. Let m = 3 and n = 12. Consider the profile In particular, note that the first 8 voters form a 2-large and 2-cohesive group. Then the expected satisfaction of the first five voters is 2 3 + 23 + 5 12 = 21 12 and the expected satisfaction of the next three voters is 23 + 23 + 7 12 = 23 12 . Taking the average yields 18 (5 21 12 + 3 23 12 ) = 29 16 = 29 32 ℓ for ℓ = 2. Whether there exists a randomized rule that achieves better than a 29/32-AS approximation remains an open problem. Before concluding this section, we note a final interesting and desirable property of PRR: strategyproofness. Since decisions are made on each candidate independently, voters maximize their expected satisfaction by reporting their true approval preferences. ## 6 Conclusion We have initiated the study of representation in approval elections with a variable number of winners. We believe that this topic, and the study of VNW elections more generally, deserves further research. Many open problems remain. In particular, we do not have matching upper and lower bounds for the average satisfaction guarantees that can be provided by deterministic and randomized rules. Determining the existence of rules that satisfy EJR is also an interesting question; while we have argued that natural extensions of JR and PJR make less sense for VNW elections than for FNW, EJR remains a compelling property. More broadly, we have assumed that voters gain utility whenever they agree with the placement of a candidate, either included or excluded. This is a natural model when the notions of inclusion and exclusion are symmetric, as in the ballot measure example. In other settings it makes sense to consider other utility models. For instance, a natural extension of our model would consider voters who derive different levels of utility for an approved candidate being selected and a disapproved candidate being excluded, or even negative utility from an approved candidate not being selected or a disapproved candidate being included. The latter utility model is reminiscent of rules such as net satisfaction approval voting (NSAV) [Kilgour and Marshall, 2012], and precision and recall metrics in information retrieval. Extending our results to this setting appears nontrivial. ## Acknowledgments The majority of this work was done while David M. Pennock was at Microsoft Research New York City, and Anson Kahng was a research intern at Microsoft Research New York City. We also thank our anonymous IJCAI and workshop reviewers for their thorough and insightful feedback. ## References 1. [Aziz et al., 2017] Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2):461-485, 2017. 2. [Aziz et al., 2018] Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis Sánchez-Fernández, and Pi- otr Skowron. On the complexity of extended and propor- tional justified representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 902- 909, 2018. 3. [Brams et al., 2007] Steven J Brams, D Marc Kilgour, and M Remzi Sanver. A minimax procedure for electing com- mittees. Public Choice, 132(3-4):401-420, 2007. 4. [Brandl and Peters, 2019] Florian Brandl and Dominik Pe- ters. An axiomatic characterization of the Borda mean rule. Social Choice and Welfare, 52(4):685-707, 2019. 5. [Brill et al., 2017] Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. Phragmén's voting methods and justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 406- 413, 2017. 6. [Cheng et al., 2019] Yu Cheng, Zhihao Jiang, Kamesh Mu- nagala, and Kangning Wang. Group fairness in committee selection. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 263-279, 2019. 7. [Duddy et al., 2016] Conal Duddy, Ashley Piggins, and William S Zwicker. Aggregation of binary evaluations: a Borda-like approach. Social Choice and Welfare, 46(2):301-333, 2016. 8. [Faliszewski et al., 2017] Piotr Faliszewski, Arkadii Slinko, and Nimrod Talmon. The complexity of multiwinner vot- ing rules with variable number of winners. arXiv preprint arXiv:1711.06641, 2017. 9. [Fishburn and Pekeč, 2004] Peter C Fishburn and Aleksan- dar Pekeč. Approval voting for committees: Threshold approaches. Technical Report, 2004. 10. [Janson, 2016] Svante Janson. Phragmén's and Thiele's elec- tion methods. arXiv preprint arXiv:1611.08826, 2016. 11. [Kilgour and Marshall, 2012] D Marc Kilgour and Erica Marshall. Approval balloting for fixed-size committees. In Electoral Systems, pages 305-326. 2012. 12. [Kilgour et al., 2006] D Marc Kilgour, Steven J Brams, and M Remzi Sanver. How to elect a representative committee using approval balloting. In Mathematics and Democracy, pages 83-95. Springer, 2006. 13. [Kilgour, 2016] D Marc Kilgour. Approval elections with a variable number of winners. Theory and Decision, 81(2):199-211, 2016. 14. [Mueller, 1969] John E Mueller. Voting on the propositions: Ballot patterns and historical trends in california. Ameri- can Political Science Review, 63(4):1197-1212, 1969. 15. [Peters and Skowron, 2019] Dominik Peters and Piotr Skowron. Proportionality and the limits of welfarism. arXiv preprint arXiv:1911.11747, 2019. 16. [Phragmén, 1899] Edvard Phragmén. Till frågan om en pro- portionell valmetod. Statsvetenskaplig Tidskrift, 2(2):297- 305, 1899. 17. [Sánchez-Fernández et al., 2017] Luis Sánchez-Fernández, Edith Elkind, Martin Lackner, Norberto Fernández, Jesús A Fisteus, Pablo Basanta Val, and Piotr Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 670-676, 2017. 18. [Skowron et al., 2017a] Piotr Skowron, Martin Lackner, Markus Brill, Dominik Peters, and Edith Elkind. Propor- tional rankings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pages 409-415, 2017. 19. [Skowron et al., 2017b] Piotr Skowron, Martin Lackner, Edith Elkind, and Luis Sánchez-Fernández. Optimal av- erage satisfaction and extended justified representation in polynomial time. arXiv preprint arXiv:1704.00293, 2017. 20. [Skowron, 2018] Piotr Skowron. Proportionality degree of multiwinner rules. arXiv preprint arXiv:1810.08799, 2018. 21. [Thiele, 1895] Thorvald N Thiele. Om flerfoldsvalg. Over- sigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 1895:415-441, 1895.