# multiwinner_approval_rules_as_apportionment_methods__f2ded25a.pdf

Multiwinner Approval Rules as Apportionment Methods

Markus Brill University of Oxford mbrill@cs.ox.ac.uk

Jean-Franc ois Laslier CNRS and Paris School of Economics jean-francois.laslier@ens.fr

Piotr Skowron University of Oxford piotr.skowron@cs.ox.ac.uk

We establish a link between multiwinner elections and apportionment problems by showing how approval-based multiwinner election rules can be interpreted as methods of apportionment. We consider several multi-winner rules and observe that some, but not all, of them induce apportionment methods that are well established in the literature and in the actual practice of proportional representation. For instance, we show that Proportional Approval Voting induces the D Hondt method and that Monroe s rule induces the largest remainder method. We also consider properties of apportionment methods and exhibit multiwinner rules that induce apportionment methods satisfying these properties.

1 Introduction The study of preference aggregation mechanisms in particular, voting rules is an important part of multiagent systems research (e.g., Conitzer 2010). Recent years have witnessed an increasing interest in multiwinner elections. In this setting, there is a set of agents who entertain preferences over a set of alternatives. Based on these preferences, the goal is to select a committee, i.e., a (ﬁxed-size) subset of the alternatives. Preferences are usually speciﬁed either as rankings, i.e., complete linear orders over the set of all alternatives (e.g., Elkind et al. 2014), or as approval votes, i.e., yes/no assessments of all the alternatives (e.g., Kilgour 2010). We are particularly interested in the latter variant, in which each agent can be thought of as specifying a subset of alternatives that are acceptable for that agent. The decision scenario modeled by multiwinner elections selecting a subset of objects from a potentially much larger pool of available objects is ubiquitous: consider, e.g., picking players to form a sports team, selecting items to display in an online shop, choosing the board of directors of a company, etc. Many of these scenarios are reminiscent of parliamentary elections, a topic that has been studied in great detail by political scientists. In a parliamentary election, the candidates are traditionally organized in political parties and the election determines how many parliamentary seats a party is allocated. Under so-called proportional representation systems with closed party lists, a voter is allowed to give her vote to one

Copyright c 2017, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

and only one party.1 In a sense, this forces the voter to approve all candidates from one party and no candidates from any other party. Counting such ballots, and deciding how many candidates are elected from each list, is an apportionment problem. Any apportionment problem can thus be seen as a very simple approval voting instance: all voters approve all the candidates from their chosen party, and only those. The present paper formally establishes and explores this analogy between multiwinner elections and apportionment problems. We show how an apportionment problem can be phrased as an instance of an approval-based multiwinner election, thereby rendering multiwinner rules applicable to the apportionment setting. As a result, every approval-based multiwinner rule induces a method of apportionment. Exploring this link between multiwinner rules and apportionment methods is interesting for at least two reasons. First, observing what kind of apportionment method a given multiwinner rule induces yields new insights into the nature of the rule. Second, every multiwinner rule inducing a given apportionment method can be seen as an extension of the apportionment method to a more general setting where candidates have no party afﬁliations (or party afﬁliations are ignored in the election process). After formally establishing the link between approvalbased multiwinner rules and apportionment methods, we consider several multiwinner rules and observe that they induce (and extend) apportionment methods that are wellestablished in the apportionment literature. For instance, Proportional Approval Voting induces the D Hondt method (aka Jefferson method) and Monroe s rule induces the largest remainder method (aka Hamilton method). We also consider properties of apportionment methods (such as lower quota or the Penrose condition) and exhibit multiwinner rules that induce apportionment methods satisfying these properties. The paper is organized as follows. Section 2 introduces both the apportionment problem and the multiwinner election setting. Section 3 shows how approval-based multiwin-

1Some countries use open-list systems, leaving some ﬂexibility to the voters by allowing them to vote for speciﬁc candidates inside the chosen party list. In some (rare) cases, voters are given even more freedom. Under so-called panachage systems, sometimes used in Luxembourg and in France, voters can vote for candidates from different parties.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

ner rules can be employed as apportionment methods, and contains several results related to proportional representation. Section 4 is devoted to non-proportional representation in the form of degressive proportionality and thresholds, and Section 5 concludes. All proofs can be found in the full version of this paper (Brill, Laslier, and Skowron 2016).

2 The Apportionment Problem and Approval-Based Multiwinner Elections In this section we provide the formal setting of the apportionment problem and of approval-based multiwinner elections, and we deﬁne several apportionment methods and multiwinner rules. (Examples illustrating these methods can be found in the full version of this paper.) For a natural number t N = {1, 2, . . .}, let [t] denote the set {1, 2, . . . , t}.

2.1 Apportionment Methods In the apportionment setting, there is a ﬁnite set of voters and a ﬁnite set of p parties P1, . . . , Pp. Every voter votes for exactly one party, and for each i [p], we let vi denote the number of votes that party Pi receives, i.e., the number of voters who voted for Pi. The goal is to allocate h (parliamentary) seats among the parties. Formally, an instance of the apportionment problem is given by a tuple (v, h), where v = (v1, . . . , vp) Np is the vote distribution and h is the number of seats to distribute. We use v+ to denote the total number of votes, v+ = p i=1 vi. Throughout this paper, we assume that vi > 0 for all i [p] and h > 0. An apportionment method M maps every instance (v, h) to a nonempty set2 M(v, h) of seat distributions. A seat distribution is a vector (x1, . . . , xp) Np 0 with p i=1 xi = h. Here, xi corresponds to the number of seats allocated to party Pi.

Divisor Methods A rich and very well-studied class of apportionment methods is deﬁned via divisor sequences.

Deﬁnition 1. Let d = (d(0), d(1), d(2), . . .) be a sequence with 0 < d(j) d(j + 1) for all j N0. The divisor method based on d is the apportionment method that maps a given instance (v, h) to the set of all seat allocations that can result from the following procedure: Start with the empty seat allocation (0, . . . , 0) and iteratively assign a seat to a party Pi maximizing vi d(si) where si is the number of seats that have already been allocated to party Pi.

Divisor methods are often deﬁned in a procedurally different, but mathematically equivalent way (see Balinski and Young 1982, Proposition 3.3).3 Two prominent divisor methods are due to D Hondt and Sainte-Lagu e.

Deﬁnition 2 (D Hondt method). The D Hondt method (aka Jefferson method or Hagenbach-Bischoff method) is the divisor method based on d = (1, 2, 3, . . .). Therefore, in each

2In order to accomodate for symmetric instances, apportionment methods are allowed to output several seat distributions. 3Divisor methods with d(0) = 0 can also be deﬁned. For such methods, which Pukelsheim (2014) calls impervious, the conventions vi

0 vi vj are used. Examples of impervious divisor methods are the methods due to Huntington and Hill, Adams, and Dean (see Balinski and Young 1982).

round, a seat is allocated to a party Pi maximizing vi si+1, where si is the number of seats that have already been allocated to party Pi. Deﬁnition 3 (Sainte-Lagu e method). The Sainte-Lagu e method (aka Webster method, Schepers method, or method of major fractions) is the divisor method based on d = (1, 3, 5, . . .). Therefore, in each round, a seat is allocated to a party Pi maximizing vi 2si+1, where si is the number of seats that have already been allocated to party Pi.

Largest Remainder Method The largest remainder method is the most well-known apportionment method that is not a divisor method. Recall that v+ = p i=1 vi denotes the total number of votes. Deﬁnition 4 (Largest remainder method). The largest remainder method (aka Hamilton method or Hare-Niemeyer method) is deﬁned via two steps. In the ﬁrst step, each party Pi is allocated vih

v+ seats. In the second step, the remaining seats are distributed among the parties so that each party gets at most one of them. The parties are sorted according to the remainders vih

v+ and the remaining seats are allocated to the parties with the largest remainders.

Properties of Apportionment Methods The literature on fair representation has identiﬁed a number of desirable properties of apportionment methods (Balinski and Young 1982; Pukelsheim 2014). In this paper, we focus on properties requiring that the proportion of seats in the resulting apportionment should reﬂect, as close as possible, the proportion of the votes cast for respective parties. Deﬁnition 5. An apportionment method respects lower quota if, for every instance (v, h), each party Pi gets at least vih

v+ seats. An apportionment method respects quota

if each party Pi gets either vih

Clearly, any apportionment method respecting quota also respects lower quota. It is well known that the largest remainder method respects quota, but no divisor method does. Moreover, the D Hondt method is the only divisor method respecting lower quota (Balinski and Young 1982).

2.2 Approval-Based Multiwinner Election Rules We now introduce the setting of approval-based multiwinner elections. We have a ﬁnite set N = {1, 2, . . . , n} of voters and a ﬁnite set C = {c1, c2, . . . , cm} of candidates. Each voter expresses their preferences by approving a subset of candidates, and we want to select a committee consisting of exactly k candidates. We will refer to k-element subsets of C as size-k committees, and we let Ai C denote the set of candidates approved by voter i N. Formally, an instance of the approval-based multiwinner election problem is given by a tuple (A, k), where A = (A1, A2, . . . , An) is a preference proﬁle and k is the desired committee size. An approval-based multiwinner election rule (henceforth multiwinner rule) R is a function that maps every instance (A, k) to a nonempty set4 R(A, k) of size-k committees. Every

4In order to accomodate for symmetric instances, multiwinner rules are allowed to output multiple committees.

element of R(A, k) is referred to as a winning committee.

OWA-Based Rules A remarkably general class of multiwinner election rules is deﬁned via ordered weighted averaging (OWA) operators (Thiele 1895; Yager 1988; Skowron, Faliszewski, and Lang 2015). A weight sequence is an inﬁnite sequence of real numbers w = (w1, w2, . . .).

Deﬁnition 6 (OWA-based rules). Consider a weight sequence w = (w1, w2, . . .), a subset S C of candidates, and a voter i. The satisfaction of i from S given w is deﬁned as uw i (S) = |Ai S| j=1 wj. Given an instance (A, k) of the multiwinner election problem, the w-based OWA rule selects all size-k committees S maximizing the total satisfaction i N uw i (S).

Note that multiplying a weight sequence w by a positive constant does not change the way in which a rule operates. Several established multiwinner election rules can be described as OWA-based rules.

Deﬁnition 7. The Chamberlin Courant rule is the OWAbased rule with weight sequence w CC = (1, 0, 0, . . .).

The Chamberlin Courant rule is usually deﬁned in the context of elections where voter preferences are given by ranked ballots (Chamberlin and Courant 1983); our deﬁnition is a straightforward adaption to the approval setting.

Deﬁnition 8. Proportional Approval Voting (PAV) is the OWA-based rule with weight sequence w PAV = (1, 1

Though sometimes attributed to Forest Simmons, PAV was already proposed and discussed by the Danish polymath Thorvald N. Thiele in the 19th century (Thiele 1895; Janson 2016). According to PAV, each voter cares about the whole committee, but the marginal gain of satisfaction of an already satisﬁed voter from an additional approved committee member is lower than the gain of a less satisﬁed voter. The reason for using the particular weight sequence w PAV is not obvious. Aziz et al. (2017) and S anchez-Fern andez et al. (2017) provide compelling arguments by showing that w PAV is the unique weight sequence w such that the w-based OWA rule satisﬁes certain axiomatic properties. Theorem 2 in the present paper can be viewed as an additional though related argument in favor of the weight sequence w PAV.

Deﬁnition 9. The top-k rule is the OWA-based rule with weight sequence wtop-k = (1, 1, 1, . . .).

According to the top-k rule, the winning committee contains the k candidates that have been approved by the greatest number of voters.

Sequential OWA-Based Rules Another interesting class of multiwinner election systems consists of sequential variants of OWA-based rules.

Deﬁnition 10. The sequential w-based OWA rule selects all committees that can result from the following procedure. Starting with the empty committee (S = ), in k consecutive steps add to the committee S a candidate c that maximizes

i N uw i (S {c}) uw i (S).

Just like OWA-based rules, sequential OWA-based rules have already been considered by Thiele (1895).

Monroe s Rule The optimization problem underlying the Chamberlin Courant rule can be thought of in terms of maximizing representation: every voter is assigned to a single candidate in the committee and this representative completely determines the satisfaction that the voter derives from the committee. The rule proposed by Monroe (1995) is based on the same idea; however, Monroe requires each candidate to represent the same number of voters. For the sake of simplicity, when considering the Monroe rule we assume that the number of voters n is divisible by the size of the committee k.

Deﬁnition 11. Consider an instance (A, k) such that k divides n and let S be a size-k committee. A balanced allocation of the voters to the candidates in S is a function τS : N S such that |τ 1 S (c)| = n k for all c S. The satisfaction ui(τS) of a voter i from τS is equal to one if i approves of τS(i), and zero otherwise. The total satisfaction of voters provided by S, denoted u(S), is deﬁned as the satisfaction from the best balanced allocation, i.e., u(S) = maxτS

i N ui(τS). The Monroe rule selects all size-k committees S maximizing u(S).

s Rules In the late 19th century, Swedish mathematician Lars Edvard Phragm en proposed a load-balancing approach for selecting committees (Phragm en 1894; Janson 2016). Here, we formulate two particularly interesting variants (see Brill et al. 2017). The motivation behind Phragm en s rules is to ﬁnd a committee whose support is distributed as evenly as possible among the electorate. For every candidate in the committee, one unit of load needs to be distributed among the voters approving this candidate. The goal is to ﬁnd a committee of size k for which the maximal load of a voter (or the variance of the load distribution) is as small as possible.

Deﬁnition 12. Consider an instance (A, k) of the multiwinner election problem. A load distribution for (A, k) is a matrix L = (ℓi,c)i N,c C R|N| |C| such that (i) i N

c C ℓi,c = k, (ii)

i N ℓi,c {0, 1} for all c C, and (iii) ℓi,c = 0 if c / Ai. Every load distribution L corresponds to a size-k committee {c C :

i N ℓi,c = 1}.

The multiwinner election rules max-Phragm en and var Phragm en are deﬁned as optimization problems over the set of all load distributions.

Deﬁnition 13. The rule max-Phragm en selects all size-k committees corresponding to load distributions L minimizing maxi N

c C ℓi,c. The rule var-Phragm en selects all size-k committees corresponding to load distributions L minimizing i N( c C ℓi,c)2.

3 Apportionment Via Multiwinner Rules In this section we demonstrate how approval-based multiwinner rules can be employed as apportionment methods. For a given instance (v, h) of the apportionment problem and a multiwinner rule R, this procedure involves three steps:

1. Translate (v, h) into an instance (A, k) of the multiwinner election problem.

2. Apply the multiwinner rule R to (A, k).

3. Translate committee(s) in R(A, k) into seat distribution(s) for (v, h).

We now describe each step in detail.

Step 1. Given an instance (v, h) of the apportionment problem, we construct an instance (A, k) of the multiwinner election problem as follows. For each i [p], we introduce a set Ci consisting of h candidates, and a set Ni consisting of vi voters. Each voter in Ni approves of all candidates in Ci (and of no other candidates). Furthermore, we deﬁne C = p i=1 Ci, N = p i=1 Ni, and k = h. Intuitively, Ci is the set of members of party Pi and Ni is the set of voters who voted for party Pi.

Step 2. We can now apply multiwinner rule R to (A, k) in order to ﬁnd the set R(A, k) of winning committees.

Step 3. For every winning committee S R(A, k), we can extract a seat distribution x for the instance (v, h) in the following way: the number xi of seats of a party Pi is given by the number of candidates from Ci in the committee S, i.e., xi = |Ci S|.

The next example illustrates this three-step procedure.

Example 1 (Sequential PAV as an apportionment method). Consider the instance (v, h) = ((20, 40, 30, 10), 10) of the apportionment problem. We construct an instance of the multiwinner election setting with 40 candidates; each party Pi has a set Ci consisting of 10 candidates. Further, there are 4 i=1 vi = 100 voters: 20 voters approve the ten candidates in C1, 40 voters approve the ten candidates in C2, 30 voters the ten candidates in C3, and 10 voters the ten candidates in C4. The Sequential PAV method selects the winning committee by selecting in 10 consecutive steps candidates from C2, C3, C1, C2, C3, C2, C1, C2, C3, C4. Thus, the corresponding seat allocation is (x1, x2, x3, x4) = (2, 4, 3, 1).

For a given multiwinner rule R, we let MR denote the apportionment method deﬁned by steps 1 to 3. We say that a multiwinner election rule R satisﬁes (lower) quota if the corresponding apportionment method MR satisﬁes the respective property.

3.1 OWA-Based Apportionment Methods

In this section, we consider apportionment methods induced by OWA-based rules. Fix a weight sequence w and let R denote the w-based OWA rule. For every instance (v, h) of the apportionment setting, MR(v, h) contains all seat distributions x maximizing the total voter satisfaction u(x), which is given by

i [p] viuw i (x) =

Here, uw i (x) = xi j=1 wj denotes the satisfaction of a voter voting for party Pi.

Whenever the weight vector w is non-increasing, the wbased OWA rule induces the same apportionment method as its sequential variant.5

Proposition 1. Let w be a weight sequence with wj wj+1 0 for all j N. The apportionment method induced by the w-based OWA rule coincides with the apportionment method induced by the sequential w-based OWA rule.

An immediate corollary is that OWA-based rules with a non-increasing weight sequence can be computed efﬁciently in the apportionment setting. Further, we can use Proposition 1 to show that every OWA-based rule with a non-increasing positive weight sequence induces a divisor method. For a weight sequence w = (w1, w2, . . .), let dw = (dw(0), dw(1), . . .) be the sequence deﬁned by dw(s) = 1 ws+1 for all s N0. For example, w PAV = (1, 1

3, . . .) yields dw PAV = (1, 2, 3, . . .).

Theorem 1. Let w be a weight sequence such that wj wj+1 > 0 for all j N. The apportionment method induced by the w-based OWA rule coincides with the divisor method based on dw = ( 1

w1 , 1 w2 , 1 w3 , . . .).

The proof consists in comparing the divisor method based on dw with the sequential w-based OWA rule (which by Proposition 1 coincides with the w-based OWA in the apportionment setting). In each iteration, the former assigns a seat to a party Pi maximizing vi dw(si), and the latter assigns a seat to a party maximizing the marginal increase i N uw i (S {c}) uw i (S) = viwsi+1. Setting dw(s) = 1 ws+1 exactly aligns the two maximization problems.

3.2 PAV and the D Hondt Method A particularly interesting consequence of Theorem 1 is that Proportional Approval Voting, the OWA rule with w PAV = (1, 1

3, . . .), induces the D Hondt method.

Corollary 2. The apportionment method induced by PAV coincides with the D Hondt method.

The observation that PAV reduces to the D Hondt method in the party-list setting occasionally occurs (without proof) in the literature (e.g., see Plaza 2004, Pereira 2016, S anchez Fern andez, Fern andez, and Fisteus 2016).6 Theorem 1 shows that this is just one special case of the general relationship between OWA-based multiwinner rules and divisor methods. Since the D Hondt method satisﬁes lower quota, the same holds for PAV and Sequential PAV.

Corollary 3. PAV and Sequential PAV satisfy lower quota.

5OWA-based rules with non-increasing weight sequences are very natural, especially when viewed in the context of apportionment. OWA-based rules with increasing sequences induce apportionment methods that allocate all seats to the single party that receives the most votes. The same seat distribution can be also obtained by using the OWA-based rule with a constant weight vector (see Proposition 5). 6In fact, already Thiele (1895) stated this equivalence, but only in the special case when perfect proportionality is possible; see the survey by Janson (2016).

The fact that PAV satisﬁes lower quota can also be established by observing that every multiwinner rule satisfying extended justiﬁed representation (Aziz et al. 2017) or proportional justiﬁed representation (S anchez-Fern andez et al. 2017) also satisﬁes lower quota; see the full version of this paper for details. Further, we show that PAV is the only OWA-based rule satisfying lower quota.7

Theorem 2. PAV is the only OWA-based rule satisfying lower quota.

Theorem 2 characterizes PAV as the only OWA-based rule respecting lower quota. Since PAV does not respect (exact) quota, it follows that no OWA-based rule respects quota.

The load-balancing rule max-Phragm en also induces the D Hondt method. Indeed, Phragm en formulated his rule as a generalization of the D Hondt method (Mora and Oliver 2015; Janson 2016).

Theorem 3. The apportionment method induced by max Phragm en coincides with the D Hondt method.

There is also a sequential variant of Phragm en s rule (Phragm en 1894).8 It is straightforward to verify that, in the apportionment setting, this variant coincides with max Phragm en and thus also induces the D Hondt method.

3.3 Phragm en s Variance-Minimizing Rule and the Sainte-Lagu e method Since the Sainte-Lagu e method is the divisor method based on (1, 3, 5, . . .), Theorem 1 implies that it is induced by the w-based OWA rule with weight sequence (1, 1/3, 1/5, . . .).9 However, this is not the only multiwinner rule inducing the Sainte-Lagu e method. Recall that var-Phragm en is the variant of Phragm en s load-balancing methods that minimizes the variance of the loads.

Theorem 4. The apportionment method induced by var Phragm en coincides with the Sainte-Lagu e method.

The proof consists in observing that, as already Sainte Lagu e (1910) and Owens (1921) have shown, the Sainte Lagu e method selects exactly those seat distributions x minimizing

(see also Balinski and Young 1982, pages 103 104). It is not hard to check that the apportionment method induced by var-Phragm en minimizes the same function.

7This result also follows from Theorem 1 together with the characterization of the D Hondt method as the only divisor method satisfying lower quota (Balinski and Young 1982, Proposition 6.4). In the full version of this paper, we give a direct proof. 8In fact, the sequential variant is the main method that Phragm en proposed to be used in actual elections; see the survey by Janson (2016) for details. 9The fact that the variant of PAV based on weight sequence (1, 1/3, 1/5, . . .) reduces to the Sainte-Lagu e method in the partylist setting is also stated (without proof) by Pereira (2016).

3.4 Monroe s Rule and the Largest Remainder Method We now turn to Monroe s multiwinner rule. It turns out that it induces the largest remainder method.

Theorem 5. Assume that the number of seats divides the total number of voters. Then, Monroe s rule induces the largest remainder method.

An immediate consequence of Theorem 5 is that Monroe s rule respects quota.

3.5 Other Multiwinner Rules in the Context of Apportionment In this section we examine two further OWA-based rules, the Chamberlin Courant rule and the top-k rule, in the context of apportionment. Since w CC = (1, 0, 0, . . .) and wtop-k = (1, . . . , 1, 0, 0, . . .), Proposition 1 applies to both rules. The Chamberlin Courant apportionment method produces lots of ties, because it does not strive to give more than one seat even to parties with a large support. In the special case where the number p of parties exceeds the number h of seats, the Chamberlin Courant rules assigns one seat to each of the h largest parties.10

Proposition 4. Consider an instance (v, h) of the apportionment problem. If p > h, the apportionment method induced by the Chamberlin Courant rule assigns one seat to each of the h parties with the greatest number of votes.

Proposition 4 gives an interesting insight into the nature of the Chamberlin Courant apportionment method: it selects an assembly having one representative from each of the h largest groups of a given society. The top-k rule is on the other end of the spectrum of apportionment methods.

Proposition 5. The apportionment method induced by the top-k rule assigns all seats to the party (or parties) receiving the highest number of votes.

Thus, the top-k rule induces the apportionment method M in Proposition 4.5 of Balinski and Young (1982). We conclude this section by mentioning two further rules that are often studied in the context of multiwinner elections. Satisfaction Approval Voting (Brams and Kilgour 2014) induces the same apportionment methods as the top-k rule. And Minimax Approval Voting (Brams, Kilgour, and Sanver 2007) induces the apportionment method that assigns the seats in a way that maximizes the number of seats of the party with the fewest seats.

4 Degressive Proportionality and Election Thresholds In this section, we show that OWA-based multiwinner rules can also be used to induce apportionment methods with appealing properties other than lower quota. We do this by exploring degressive proportionality, the concept suggesting

10In this special case, the apportionment method induced by the Chamberlin Courant rule coincides with impervious divisor methods (see Footnote 3).

that smaller populations should be allocated more representatives in comparison to the divisor methods, and election thresholds, the concept saying that a party should only be represented in parliament if it receives at least a certain numbers of votes. To the best of our knowledge, the OWA-based rules considered in this section have not been studied before.

4.1 Degressive Proportionality Despite its mathematical elegance and apparent simplicity, the proportionality principle is not always desirable. For instance, in an assembly where decisions are taken under simple majority rule, a cohesive group of 51% has obviously more than a fair share. Principles of justice indicate that, for decisions bodies governed by majority rule, fair apportionment should follow a norm of degressive proportionality (Laslier 2012; Koriyama et al. 2013). In fact, degressive proportional apportionments can often be observed in parliaments that gather districts, regions, or states of very different sizes, such as the European Parliament.11 The Penrose apportionment method (aka square-root method and devised by Penrose, 1946; see also the work of Słomczy nski and Zyczkowski 2006) allocates seats in such a way that the number of seats allocated to a party is proportional to the square root of the votes for that party. It has been proposed for the United Nations Parliamentary Assembly and for allocating voting weights in the Council of the European Union.12 Let us say that an apportionment method M satisﬁes the Penrose condition if, for every instance (v, h) and for every x M(v, h), it holds that xi h vi

ℓ vℓ for all i [p]. Interestingly, the Penrose condition can be satisﬁed by using an OWA-based rule. The weight sequence w achieving this is given by wj = 1 j2 for all j N.

Theorem 6. The apportionment method induced by the OWA-based rule with weight sequence w = (1, 1/4, 1/9, . . .) satisﬁes the Penrose condition. Degressive proportionality is also an important feature of the so-called Cambridge Compromise, which proposes an apportionment method for the European Parliament based on an afﬁne formula: each member state should be endowed with a ﬁxed number (5) of delegates plus a variable number, proportional to the population of the state (Grimmett et al. 2011). We show that such an apportionment method can be implemented via an OWA-based multiwinner rule. Proposition 6. Consider an instance (v, h) of the apportionment setting with h 5p and let Z be a constant with Z > 5v+. Let R denote the w-based OWA rule with weight sequence w = (0, 0, 0, 0, Z, 1, 1/2, 1/3, . . .). Then, for every x MR(v, h) and for every i [p],

xi 5 + vi(h 5p)

11Even though the composition of the European Parliament is not the result of the application of a well-deﬁned rule, it is interesting to note that the history of successive negotiations produced such a result (see Rose 2013). 12The problem of allocating voting weights to representatives is formally equivalent to the apportionment problem.

4.2 Election Thresholds OWA-based multiwinner rules also provide an interesting way for implementing election thresholds. Thresholds in the form of percentage hurdles are often encountered in parliamentary elections (see Pukelsheim 2014, Section 7.6). For a weight sequence w = (w1, w2, . . .), let w[t] be the weight sequence obtained from w by replacing the ﬁrst t elements of w with zeros. The w[t]-based OWA rule induces an apportionment method that allocates seats to a party only if the number of votes the party receives exceeds a certain fraction of the total number of votes received by parties with allocated seats.13 Proposition 7 formalizes this behavior for the weight sequence w PAV. Proposition 7. Consider an instance (v, h) of the apportionment problem and ﬁx an integer t with 1 t < h. Let R denote the OWA-based rule with weight sequence w PAV[t]. Then, for all seat distributions x MR(v, h),

xi > 0 only if vi

ℓ [p]:xℓ>0 vℓ > t

5 Conclusion In legislative procedures, proportional representation is typically achieved by employing party-list apportionment methods such as the D Hondt method or the largest remainder method. These methods impose proportionality by assuring that each party in a representative body is allocated a number of representatives that is proportional to the number of received votes. Nevertheless, party-list systems have many drawbacks for instance, they provide very weak links between elected legislators and their constituents. In this paper we have proposed a simple and natural formal framework that allows us to view approval-based multiwinner election rules as apportionment methods. Some multiwinner rules (such as PAV, Monroe s rule, Phragm en s rules, and the rules considered in Section 4) induce apportionment methods that are used or have been proposed for parliamentary apportionment. The apportionment methods that are induced by other multiwinner rules (such as the Chamberlin Courant rule, the top-k rule, Satisfaction Approval Voting, and Minimax Approval Voting) are, however, less appealing. These results give interesting insights into the nature of the analyzed multiwinner rules, and they show how traditional apportionment methods can be extended to settings where voters can vote for individual candidates. Further, our methodology allowed us to discover a new interesting multiwinner election rule which, if applied to the apportionment setting, satisﬁes Penrose s (square root proportionality) condition.

13The thresholds implemented by OWA-based apportionment methods differ from real-world election thresholds in one important aspect: Rather than requiring a certain fraction (say, 5%) of all votes, the thresholds we consider here require a certain fraction of those votes that are received by parties with allocated seats. An advantage of the latter kind of threshold requirement is that it can always be satisﬁed. By contrast, requiring a certain fraction of all votes can lead to situations in which no party reaches the required number of votes and, therefore, no seat allocation satisﬁes the threshold requirement.

Acknowledgments We thank Bernard Grofman, Svante Janson, and Friedrich Pukelsheim for helpful discussions. This material is based on work supported by ERC-St G 639945 (ACCORD), by a Feodor Lynen return fellowship of the Alexander von Humboldt Foundation, and by the ANR project ANR13-BSH10010 Dyna MITE.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justiﬁed representation in approvalbased committee voting. Social Choice and Welfare. Forthcoming. Balinski, M., and Young, H. P. 1982. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press. (2nd Edition [with identical pagination], Brookings Institution Press, 2001). Brams, S. J., and Kilgour, D. M. 2014. Satisfaction approval voting. In Voting Power and Procedures, Studies in Choice and Welfare. Springer. 323 346. Brams, S. J.; Kilgour, D. M.; and Sanver, M. R. 2007. A minimax procedure for electing committees. Public Choice 132:401 420. Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017. Phragm en s voting methods and justiﬁed representation. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI). AAAI Press. Forthcoming. Brill, M.; Laslier, J.-F.; and Skowron, P. 2016. Multiwinner approval rules as apportionment methods. Technical Report ar Xiv:1611.08691 [cs.GT], ar Xiv.org. Chamberlin, J. R., and Courant, P. N. 1983. Representative deliberations and representative decisions: Proportional representation and the Borda rule. The American Political Science Review 77(3):718 733. Conitzer, V. 2010. Making decisions based on the preferences of multiple agents. Communications of the ACM 53(3):84 94. Elkind, E.; Faliszewski, P.; Skowron, P.; and Slinko, A. 2014. Properties of multiwinner voting rules. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 53 60. IFAAMAS. Grimmett, G.; Pukelsheim, F.; Laslier, J. F.; Gonz alez, V. R.; Rose, R.; Słomczy nski, W.; Zachariasen, M.; and Zyczkowski, K. 2011. The allocation between the EU Member States of the seats in the European Parliament: The Cambridge Compromise. Technical report, European Parliament, Policy Department, Constitutional Affairs. Janson, S. 2016. Phragm en s and Thiele s election methods. Technical Report ar Xiv:1611.08826 [math.HO], ar Xiv.org. Kilgour, D. M. 2010. Approval balloting for multi-winner elections. In Laslier, J.-F., and Remzi, M. R., Handbook on Approval Voting, chapter 6, pages 105 124. Springer. Koriyama, Y.; Laslier, J.-F.; Mac e, A.; and Treibich, R. 2013. Optimal apportionment. Journal of Political Economy 121(3):584 608.

Laslier, J. F. 2012. Why not proportional? Mathematical Social Sciences 63(2):90 93. Monroe, B. 1995. Fully proportional representation. American Political Science Review 89(4):925 940. 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. Owens, F. W. 1921. On the apportionment of representatives. Quarterly Publications of the American Statistical Association 17(136):958 968. Penrose, L. S. 1946. The elementary statistics of majority voting. Journal of the Royal Statistical Society 109(1):53 57. Pereira, T. 2016. Proportional approval method using squared loads, approval removal and coin-ﬂip approval transformation (PAMSAC) A new system of proportional representation using approval voting. Technical Report ar Xiv:1602.05248 [cs.GT], ar Xiv.org. Phragm en, E. 1894. 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. Plaza, E. 2004. Technologies for political representation and accountability. In EU-LAT Workshop on e-Government and e-Deomocracy, 99 107. Pukelsheim, F. 2014. Proportional Representation: Apportionment Methods and Their Applications. Springer. Rose, R. 2013. Representing Europeans: a pragmatic approach. Oxford: Oxford University Press. Sainte-Lagu e, A. 1910. La repr esentation proportionnelle et la m ethode des moindres carr es. Annales scientiﬁques de l Ecole Normale Sup erieure 27:529 542. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional justiﬁed representation. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI). AAAI Press. Forthcoming. S anchez-Fern andez, L.; Fern andez, N.; and Fisteus, J. A. 2016. Fully open extensions to the D Hondt method. Technical Report ar Xiv:1609.05370 [cs.GT], ar Xiv.org. Skowron, P. K.; Faliszewski, P.; and Lang, J. 2015. Finding a collective set of items: From proportional multirepresentation to group recommendation. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2131 2137. AAAI Press. Słomczy nski, W., and Zyczkowski, K. 2006. Penrose voting system and optimal quota. Acta Physica Polonica B 37:3133 3143. Thiele, T. N. 1895. Om ﬂerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 415 441. Yager, R. 1988. On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Transactions on Systems, Man and Cybernetics 18(1):183 190.