# phragmnõs_voting_methods_and_justified_representation__1c2d39ee.pdf

Phragm en s Voting Methods and Justified Representation

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

Rupert Freeman Duke University rupert@cs.duke.edu

Svante Janson Uppsala University svante.janson@math.uu.se

Martin Lackner University of Oxford martin.lackner@cs.ox.ac.uk

In the late 19th century, Lars Edvard Phragm en proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants one minimizing the maximal load and one minimizing the variance of loads and a sequential variant. We study Phragm en s methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and S anchez-Fern andez et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragm en s methods and provide mixed-integer programming based algorithms for computing them.

1 Introduction

An important part of multiagent systems research concerns the study of preference aggregation mechanisms (e.g., Conitzer 2010). Recent years have witnessed an increasing interest in committee voting rules (e.g., Elkind et al. 2014; Skowron, Faliszewski, and Lang 2015; Aziz et al. 2015a; Caragiannis et al. 2016). In this setting, a fixed-size subset of alternatives has to be selected based on the preferences of a group of agents. In this paper, we assume that the preferences of individual agents are given by approval ballots, specifying which alternatives are approved by the agents. An important issue in group decision making is (proportional) representation. Informally, an outcome of a decision making process is representative if it reflects the preferences of the members of the group. In the context of approvalbased committee elections, reasoning about representation is non-trivial. Since approval sets may overlap arbitrarily, there are many different ways in which the set of agents can be split into more or less cohesive subgroups. Whether a given subgroup has a justified claim to be represented in the committee depends on the size of the subgroup as well as on its level of cohesiveness.

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

Aziz et al. (2015a) and S anchez-Fern andez et al. (2016; 2017) have identified axiomatic properties capturing the intuitive notion that subgroups that are large enough and cohesive enough deserve to be represented in the committee: justified representation (JR), proportional justified representation (PJR), and extended justified representation (EJR). While a number of standard committee voting rules have been shown to satisfy the basic requirement of JR, it turns out that the more demanding properties PJR and EJR are much harder to satisfy. Essentially, the only rule that is known to satisfy PJR and EJR is Proportional Approval Voting (PAV), which was proposed by Danish polymath Thorvald N. Thiele in the late 19th century (Thiele 1895; Janson 2016). Unfortunately, PAV is NP-hard to compute. It has therefore remained an open question whether computationally tractable rules satisfying the more demanding representation properties exist. In this paper, we consider committee voting rules that are due to Swedish mathematician Lars Edvard Phragm en (1894; 1895; 1896; 1899). Although Phragm en s methods were proposed in the same era as PAV, they have received considerably less attention. Variants of both Phragm en s methods and PAV have been used in Swedish parliamentary elections (for distribution of seats within parties), and a version of one of Phragm en s methods is still part of the election law, although in a minor role (Janson 2016). Phragm en phrases committee elections as load balancing problems: Adding a candidate to the committee incurs some load, and this load should be shared among the agents approving this candidate. Phragm en suggests choosing committees in such a way that the corresponding load distributions are as balanced as possible, and different ways of measuring balancedness result in different optimization objectives. This approach yields two optimization variants, one minimizing the maximal load and one minimizing the variance of loads, and one sequential variant, which proceeds by greedily selecting candidates so as to keep the maximal load as small as possible. After briefly reviewing related work in Section 2 and introducing some basic notation in Section 3, we formally define Phragm en s rules in Section 4. In Section 5, we analyze the computational complexity of Phragm en s rules and we provide algorithms for computing them. The algorithms for the optimization variants are based on mixed-

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

integer linear and quadratic programming. In Section 6, we consider the representation axioms mentioned above. We show that the sequential variant satisfies PJR, making it the first known polynomial-time computable method with this property.1 Moreover, we show that the optimization variants satisfy perfect representation (PR), a further representation axiom introduced by S anchez-Fern andez et al. (2017). The latter result provides a contrast to PAV, which is known to violate PR. Omitted proofs can be found in the full version of this paper.

2 Related Work

Proportional representation is an important issue in committee voting (see the influential paper by Monroe, 1995, and the references therein) and methods ensuring representation often lead to interesting computational problems (Potthof and Brams 1998; Procaccia, Rosenschein, and Zohar 2008; Lu and Boutilier 2011; Betzler, Slinko, and Uhlmann 2013). In the setting of approval-based committee voting (Kilgour 2010), Aziz et al. (2015a) proposed two representation axioms: justified representation (JR) and its strengthening extended justified representation (EJR). Later, S anchez Fern andez et al. (2017) observed that EJR is not compatible with what they call perfect representation (PR) and proposed an axiomatic property, proportional justified representation (PJR), that is. EJR implies PJR, which in turn implies JR. Aziz et al. (2015a) and S anchez-Fern andez et al. (2017) showed that most common committee voting rules fail EJR and PJR. A notable exception is Thiele s PAV, which satsfies EJR (and thus PJR). Interestingly, variants of PAV based on different weight vectors fail both EJR and PJR. The same is true for a greedy approximation algorithm for PAV known as sequential PAV or reweighted approval voting. Computing the outcome of PAV is NP-hard (Skowron, Faliszewski, and Lang 2015; Aziz et al. 2015b) and thus not feasible in polynomial time unless P = NP. Therefore, it has remained an open question whether there exist polynomialtime computable rules satisfying EJR or PJR. S anchez Fern andez et al. (2017) have shown that the polynomial-time computable Greedy Monroe rule satisfies PJR in the special case where the committee size divides the number of voters (but fails PJR in the general case).

3 Preliminaries

We consider a social choice setting with a finite set N = {1, . . . , n} of voters and a finite set C of candidates. Throughout the paper we let m = |C| denote the number of candidates and n = |N| the number of voters. The preferences of each voter i N are given by a subset Ai C, representing the subset of candidates that the voter approves of. We refer to the list A = (A1, . . . , An) as the preference profile. For a candidate c C, we let Nc denote the set of voters approving c, i.e., Nc = {i N : c Ai}. To avoid trivialities, we assume that Nc = for all c C.

1In simultaneous and independent work, S anchez-Fern andez, Fern andez, and Fisteus (2016) have introduced another method that satisfies PJR and is computable in polynomial time.

We want to select a subset consisting of exactly k candidates, for a given natural number k m. An approvalbased multi-winner voting rule (henceforth simply rule) maps an instance (A, k) to a subset S C of size k, the committee. In general, there may be ties, and we then allow the rule to yield several choices, so formally the rule is a map from instances to non-empty sets of committees. Finally, for a tuple of real numbers z = (z1, . . . , zn), we let z(ℓ) denote the ℓ-th largest element in z.

4 Phragm en s Methods

The main idea behind Phragm en s methods is to identify committees whose support is distributed as evenly as possible among the electorate. Phragm en used different formulations for explaining his methods; we refer the reader to the survey by Janson (2016) for an overview and more details. In this paper, we adopt the formulation from the 1899 paper (Phragm en 1899). In this formulation, every candidate in the committee is thought of as incurring one unit of load, and the load incurred by candidate c needs to be distributed among the voters in Nc. The goal is to find a committee of size k for which the corresponding load distribution is as balanced as possible. Formally, a load distribution is a two-dimensional array x = (xi,c)i N,c C satisfying the following four conditions:

0 xi,c 1 for all i N and c C (1) xi,c = 0 if c / Ai (2)

c C xi,c = k (3)

i N xi,c {0, 1} for all c C (4)

Here, xi,c corresponds to the load that voter i receives from candidate c. Condition (2) ensures that the load incurred by candidate c is distributed among voters in Nc only, and Conditions (3) and (4) ensure that x corresponds to a size-k committee {c C :

i N xi,c = 1}. For a load distribution x, we let xi denote the total load of voter i N, i.e., xi =

c C xi,c, and we refer to ( x1, . . . , xn) as the vector of voter loads. Using this notation, Condition (3) reads i N xi = k. Note that Condition (3) implies that the average voter load is k

n. There are different ways to measure how balanced a given load distribution is, each giving rise to a different optimization objective. One such objective is to minimize the maximal load assigned to a voter, i.e., minx maxi N xi. (This is equivalent to minimizing the maximal difference between a voter load and the average voter load.) Obviously, the average voter load k

n is a lower bound on the maximal voter load, and we call a load distribution x perfect if xi = k

n for all i N. Another objective is to minimize the variance of voter loads, i.e., the sum of squared distances from the average voter load. Again, a perfect load distribution is optimal for this objective. We further distinguish between optimization methods, where we solve a global optimization problem to find a load

distribution optimizing the objective, and sequential methods, where we iteratively construct a load distribution, in each round greedily choosing a candidate optimizing the objective at that iteration. In this paper, we consider three rules: the optimization methods max-Phragm en and var-Phragm en minimizing the maximal voter load and the variance of voter loads, respectively and the sequential method seq-Phragm en, which greedily minimizes the maximal voter load. The method seq-Phragm en was introduced by Phragm en (1894; 1895; 1896; 1899), and it is the variant that he proposed to be used in actual elections. Phragm en defined this method as a generalization of D Hondt s apportionment method to the case without party lists: for every instance of the partylist setting, seq-Phragm en and D Hondt s method coincide (Phragm en 1895; Janson 2016; Brill, Laslier, and Skowron 2017). Optimization variants and the objective of minimizing the variance are discussed in the 1896 paper (Phragm en 1896). Despite their intuitive appeal, Phragm en s methods have received little attention in the social choice literature.2

4.1 Optimization Variants We first define the optimization variants. max-Phragm en: The rule max-Phragm en selects committees minimizing the maximal voter load. In case that two or more committees have the same (minimal) maximal load, we employ a specific tie-breaking. This is because it might be the case that for two load distributions x and y, although maxi N xi = maxi N yi, one load distribution is clearly preferable to the other.

Example 1. Consider A = ({a}, {a}, {b}, {c}) and k = 2. Any committee of size 2 contains either b or c, which are approved by only one voter each, so the maximum load is 1 for all committees. Thus, all subsets of size 2 minimize the maximal voter load, although arguably the committees containing a are preferable to the committee {b, c}.

Thus, to refine the set of winning committees, we compare two committees in the following way.

Definition 1. For y = (y1, . . . , yn) and z = (z1, . . . , zn), y is leximax-smaller than z, denoted y < z, if there exists j n such that y(j) < z(j) and y(i) = z(i) for all i j 1.

max-Phragm en selects all committees corresponding to load distributions ( x1, . . . , xn) that are leximax-optimal, i.e., minimal with respect to <. As we will see in Section 6.3, this tie-breaking is necessary in order to guarantee strong representation properties. Rather than minimizing the maximum load, one could also aim to (lexicographically) maximize the minimal voter load. This variant of Phragm en s method would select committees minimizing the number of unrepresented voters, even in the face of large cohesive groups of voters. Therefore, this method will not do well in terms of the representation axioms considered in Section 6. For this reason, we do not consider it further in this paper.

2Notable exceptions are a survey by Janson (2012) (in Swedish) and a paper by Mora and Oliver (2015) (in Catalan).

var-Phragm en: The rule var-Phragm en selects committees corresponding to load distributions minimizing i N x 2 i . Minimizing the sum of squares of ( x1, . . . , xn) indeed minimizes the variance of ( x1, . . . , xn), as is well-known. The following example demonstrates that the maximal voter load under var-Phragm en may indeed be greater than under max-Phragm en. Example 2. Let C = {a, b, c, d}, k = 3, and consider the profile A = ({a}, {b}, {b, c}, {a, b, c}, {d}). For this instance, max-Phragm en selects the committee {a, b, c} and var-Phragm en selects the committee {a, b, d}. Optimal load distributions corresponding to these committees are illustrated in Figure 1. Load distributions minimizing the maximal voter load (like the one illustrated by the first diagram in Figure 1) satisfy maxi N xi = 3

4 and i N x2 i = 4( 3

4)2 = 9 4, and the load distribution minimizing the variance of voter loads (illustrated by the second diagram in Figure 1) satisfies maxi N xi = 1 and

i N x2 i = 4( 1

2)2 + 12 = 2.

4.2 Sequential Method We now introduce the sequential method. seq-Phragm en: The rule seq-Phragm en starts with an empty committee and iteratively adds candidates, always choosing the candidate that minimizes the (new) maximal voter load. Let x(j) i denote the voter loads after round j. At first, all voters have a load of 0, i.e., x(0) i = 0 for all i N. As a first candidate we select one that is supported by most voters as it is the one that increases the maximal load the least. In the next round, we again choose a candidate that induces a (new) maximal voter load that is as small as possible, but now we have to take into account that some voters already have a non-zero load. The new maximal load if c is chosen as the (j + 1)-st committee member is calculated as

s(j+1) c = 1 +

i Nc x(j) i |Nc| . (5)

This is because we distribute the load of 1 among all voters in Nc in such a way that all these voters have the same voter load afterwards. Let c be the candidate that minimizes s(j+1) c among those that are not yet in the committee.3 Then we add c to the committee and set

s(j+1) c if i Nc x(j) i otherwise. (6)

It follows that i N x(j+1) i = j + 1. After k iterations, we have obtained a load distribution and a committee. The definitions ensure that voter loads never decrease, i.e., x(j+1) i x(j) i for all i N and all j < k. This is because a candidate minimizing the new maximal load is selected in each round. If the selection of candidate c in round j +1 led to a load distribution x(j+1) with s(j+1) c = x(j+1) i < x(j) i for some i Nc, then candidate c would have been selected in an earlier round, a contradiction. (See also Lemma 5(i).)

3If there are several candidates minimizing s(j+1) c , we use a fixed tie-breaking rule to decide which candidate to add.

a b c a b c

A2 = {b} A3 = {b, c} A4 = {a, b, c}

a b b c b a c

a b b b a d

Figure 1: Illustration of Examples 2 and 3. From left to right: The first diagram illustrates a load distribution minimizing the maximal voter load maxi N xi; the second diagram illustrates the unique load distribution minimizing

i N x2 i ; the third and fourth diagrams illustrate the load distributions obtained by seq-Phragm en with ties broken in favor of c or d, respectively.

Phragm en (1899) illustrates his sequential method by imagining the different groups of ballots as represented by cylindrical vessels, with base area proportional to the number of ballots in each group. The already elected candidates are represented by a liquid that is fixed in the vessels, and the additional unit of load incurred by adding another candidate to the committee is represented by pouring 1 unit of a liquid into the vessels representing voters approving this candidate. The liquid then distributes among these vessels such that the height of the liquid is the same in all vessels. This is to be tried for each candidate; the candidate that requires the smallest height is elected, and the corresponding amounts of liquid are added to the vessels and fixed there. The sequential method seq-Phragm en can be seen as a (polynomial-time computable) heuristic to approximate the optimization method max-Phragm en. Unsurprisingly, the load distribution constructed by seq-Phragm en might not be optimally balanced. Example 3. Consider again the instance from Example 2. We have s(1) b = 1

3, s(1) a = s(1) c = 1

2, and s(1) d = 1. Therefore, candidate b is chosen in the first round. In the second round, we have s(2) a = 2

3, s(2) c = 5

6 and s(2) d = 1, so candidate a is chosen. In the third round, there is a tie between c and d because s(3) c = s(3) d = 1. Thus, the final committee is either {a, b, c} or {a, b, d}, depending on which tie-breaking method is used. Figure 1 illustrates the resulting load distributions, both of which are suboptimal for the optimization problems corresponding to max-Phragm en and var-Phragm en. One can also define a sequential version of var-Phragm en, by in each iteration selecting a candidate minimizing the variance of the resulting load distribution (Mora 2016). This variant does not fare well in terms of the representation axioms considered in Section 6, and we therefore do not consider it any further.

5 Computational Aspects In this section, we study the computational complexity of Phragm en s methods, and we provide algorithms for finding winning committees. S anchez-Fern andez et al. (2017) have shown that every rule satisfying perfect representation (see Section 6) is NP-hard; this essentially follows from earlier work by Procaccia, Rosenschein, and Zohar (2008). Since we show that max-Phragm en and var-Phragm en both satisfy

this condition (Theorems 8 and 11), it follows that there do not exist polynomial-time algorithms for computing a committee for either of these rules, unless P = NP. We complement these hardness results by considering two basic decision problems. MAX-PHRAGM EN asks whether an instance allows a load distribution x such that ( x1, . . . , xn) < (y1, . . . , yn) for some given n-tuple (y1, . . . , yn). And VAR-PHRAGM EN asks whether an instance allows a load distribution x such that i N x 2 i < α for some given threshold value α > 0. Both problems can be interpreted as asking whether a given load distribution is optimal. We show that both problems are NP-complete even for rather restricted instances. For a preference profile A, let s(A) denote the maximum number of candidates a voter approves, and let d(A) denote the maximum number of voters that approve a candidate.

Theorem 1. MAX-PHRAGM EN, and VAR-PHRAGM EN are NP-complete, even restricted to instances with s(A) = 2 and d(A) = 3.

We now turn to algorithms for computing Phragm en s rules. First, we show how the outcome of max-Phragm en can be computed with the help of mixed-integer linear programs (MILPs). We start by formulating an MILP that solves the decision problem MAX-PHRAGM EN. We use the variables xi,c (for i N, c C), ei,j (for i, j N), si (for i N), tj (for j N), and ϵ. For a given n-tuple y = (y1, . . . , yn) of real numbers, let P(y) be the MILP that maximizes ϵ under the constraints (1) (4) and (7) (14).

ei,j {0, 1} for all i, j N (7) si {0, 1} for all i N (8) tj {0, 1} for all j N (9)

j N ei,j = 1 for all i N (10)

i N ei,j 1 for all j N (11)

j N tj = 1 for all i N (12)

xi k(1 ei,j) yj for all i, j N (13) xi k(2 si tj) yj ϵ for all i, j N (14)

The main idea of this MILP is as follows: The variables ei,j encode a partial bijection π from a subset of N to a subset of N; the variables si encode the subset S N where π is not defined; and the variables tj encode t N, an index of an element in {yj : j / range(π)}. Constraint (10) encodes the relation between π and S: for every i N, either si = 1 or ei,j = 1 for some j N. In a similar fashion, constraint (11) encodes the relation between π and t: for every i N, ti = 1 only if ei,j = 0 for all j N. Together with constraint (12), we enforce that there exists exactly one j N such that tj = 1. Hence at least one voter has a load strictly smaller than yt and ( x1, . . . , xn) < (y1, . . . , yn). The final two constraints ensure that indeed ( x1, . . . , xn) < (y1, . . . , yn). From constraint (13) it follows that xi yj whenever π(i) = j. This is because if ei,j = 0 (i.e., π(i) = j), constraint (13) reduces to xi k yj, which is trivially satisfied because every load distribution x satisfies xi k for all i N. If ei,j = 1 (i.e., π(i) = j), however, constraint (13) reads xi yj. Similarly, constraint (14) enforces that xi yt ϵ maxj N\range(π) yj ϵ for i S. As we maximize ϵ, we look for a solution where xi < maxj N\range(π) yj. We conclude that a feasible solution with objective function value ϵ > 0 encodes a load distribution x with ( x1, . . . , xn) < (y1, . . . , yn). Observe that P(y) solves the MAX-PHRAGM EN decision problem: given voter loads y, P(y) returns ϵ > 0 if and only if MAX-PHRAGM EN with input y is a Yes-instance. We now present an MILP-based algorithm that computes the outcome of max-Phragm en. Our algorithm solves a sequence of at most 2n instantiations of the MILP P, using the optimal solutions of previously solved instances as constraints for subsequent calls. We assume that P returns the load distribution x and the objective function value ϵ. For an overview of the procedure, see Algorithm 1.

Algorithm 1: Computing max-Phragm en

y (k, 0, . . . , 0) for ℓ= 1 . . . n do

x, ϵ P(y) x ( x1, . . . , xn) // x(1), . . . , x(ℓ) optimal if ϵ = 0 then // no improvement x , ϵ P( x) if ϵ = 0 then // x optimal return {c C :

i N xi,c = 1}

y ( x(1), . . . , x(ℓ+1), 0, . . . , 0)

return {c C :

i N xi,c = 1}

We start with y = (k, 0, . . . , 0), an n-tuple consisting of one k and n 1 zeroes. We employ P to find a strictly better solution. The only entry of y that can be improved is y(1) = k and hence the solution x returned by P minimizes the largest load; let x(1) be the largest load and x(2) the second-largest. We repeat this procedure with

y = ( x(1), x(2), 0, . . . , 0). We already know that x(1) is optimal and cannot be further decreased (and 0 cannot be improved), hence the next P instance minimizes the secondlargest load. We iterate this process and in step ℓguarantee that the ℓ-th largest load is optimal. If at some point P returns ϵ = 0, we verify whether the current solution is optimal: if P( x) also returns ϵ = 0, the load distribution x is indeed optimal and the algorithm terminates. In any case Algorithm 1 returns {c C :

i N xi,c = 1}, the committee corresponding to the load distribution x. We have therefore proven the following result.

Theorem 2. max-Phragm en can be computed by solving at most 2n mixed-integer linear programs with O(nm + n2) variables.

To compute var-Phragm en, we solve a mixed-integer quadratic program, i.e., a program consisting of linear constraints and a quadratic optimization statement.

Theorem 3. var-Phragm en can be computed by solving one mixed-integer quadratic program with O(nm) variables.

Finally, we study the runtime for computing seq Phragm en. A naive estimate is that seq-Phragm en can be computed in O(kmn) time. This estimate ignores the cost of computing the quantities s(j) c , i.e., numerical operations are assumed to require constant time. While this is a sensible assumption in many cases, here it is questionable since computing s(j) c exactly requires fractions with large numerators and denominators. Indeed, the denominator of s(j) c can grow exponentially with j. Hence, the following theorem also takes the complexity of these operations into account.

Theorem 4. The output of seq-Phragm en can be computed in O(k3mn(log n)2) time.

6 Phragm en s Methods and Representation

In this section, we study which representation axioms are satisfied by Phragm en s methods. Our results are summarized in Table 1. Particularly noteworthy are the results that seq-Phragm en satisfies PJR and that max-Phragm en and var Phragm en satisfy PR.

6.1 Justified Representation Axioms

We start by restating the definitions of Aziz et al. (2015a) and S anchez-Fern andez et al. (2017).

Definition 2. A committee S C with |S| = k provides

justified representation (JR) if there does not exist a set N N of voters with |N | n

i N Ai| 1 and |S Ai| = 0 for all i N . proportional justified representation (PJR) if there does not exist an integer ℓ> 0 and a set N N of voters with |N | ℓn

i N Ai| ℓand |S (

i N Ai)| < ℓ. extended justified representation (EJR) if there does not exist an integer ℓ> 0 and a set N N of voters with |N | ℓn

i N Ai| ℓand |S Ai| < ℓfor all i N .

JR PJR EJR PR

seq-Phr. (Cor. 7) (Th. 6) (Ex. 5) (Ex. 4) max-Phr. (Cor. 10) (Th. 9) (Ex. 4) (Th. 8) var-Phr. (Th. 12) (Ex. 6) (Ex. 4) (Th. 11)

Table 1: Phragm en s methods and representation axioms

A rule f satisfies JR (respectively, PJR or EJR) if, for every instance (A, k), every committee S f(A, k) provides JR (respectively, PJR or EJR). It follows immediately from the definitions that a rule satisfying EJR also satisfies PJR, and that a rule satisfying PJR also satisfies JR. The following definition is due to S anchez-Fern andez et al. (2017). Definition 3. Consider an instance (A, k) so that k divides n = |N|. A committee S = {c1, . . . , ck} C provides perfect representation if there exists a partition of the set N of voters into k pairwise disjoint subsets N1, . . . , Nk such that, for all j {1, . . . , k}, |Nj| = n

i Nj Ai. Let PR(A, k) denote the set of all committees providing perfect representation for the instance (A, k). A rule f satisfies perfect representation (PR) if, for every instance (A, k) where k divides n and PR(A, k) = , we have f(A, k) PR(A, k). The following example, which also appears in the papers by Aziz et al. (2015a) and S anchez-Fern andez et al. (2017), illustrates the requirements of the different axioms. Example 4. Let C = {a, b, c, d, e, f} and consider the 8voter preference profile given by A1 = {a}, A2 = {b}, A3 = {c}, A4 = {d}, A5 = {a, e, f}, A6 = {b, e, f}, A7 = {c, e, f}, A8 = {d, e, f}. Let k = 4 and assume that ties are broken alphabetically. Then, seq-Phragm en chooses e, f, a, and b (in this order). The final loads are ( x1, . . . , x8) = ( 3

2). This is indeed not optimal as there is a perfect load distribution y with yi = 1

2 for all i N. The corresponding committee {a, b, c, d} is selected by both max-Phragm en and var-Phragm en. Consider the group of voters N = {5, 6, 7, 8}, of size ℓn

4 = 4, where ℓ= 2. Since the voters all approve candidates e and f, a set of size ℓ= 2, the conditions for JR, PJR, and EJR all bind. JR requires that at least one candidate approved by at least one voter in N is chosen. PJR requires that at least 2 candidates are chosen that are each supported by at least one voter from N , while EJR requires that some voter from N is represented twice. Thus, EJR dictates that either e or f is chosen. On the other hand, the only committee providing PR is {a, b, c, d}. As a consequence, no rule can satisfy both PR and EJR. Note that max-Phragm en and var-Phragm en both violate EJR in this example, and that seq-Phragm en violates PR. The incompatibility of PR and EJR was first observed by S anchez-Fern andez et al. (2017).

6.2 Results for seq-Phragm en In this section we establish our main result: seq-Phragm en satisfies proportional justified representation.

We need the following notation. For the committee S that is selected by seq-Phragm en (using a fixed tiebreaking rule), we can relabel the candidates such that S = {c1 . . . , ck} and candidate cj was chosen in round j. Then, we have cj = arg minc C\{c1,...,cj 1} s(j) c . Using this con-

vention, we define s(j) = s(j) cj . That is, s(j) is the new load of all voters in Ncj after candidate cj is added to the committee in round j. We call (s(1), . . . , s(k)) the max-load sequence. (Note that different tie-breaking rules can lead to different max-load sequences.) The following lemma has two parts. The first part states that the max-load sequence is monotonically increasing. The second part states that, when computing the optimal distribution of the load of a candidate c among its voters, it never helps to restrict attention to a subset N Nc.

Lemma 5. Fix an instance (A, k).

(i) The max-load sequence satisfies s(1) . . . s(k). (ii) For a candidate c C, a subset N Nc, and j k, let s(j) c [N ] denote the maximal voter load after optimally distributing the load of c among all voters in N . Then, s(j) c [Nc] s(j) c [N ] for all N Nc.

We are now ready to prove our main theorem.

Theorem 6. seq-Phragm en satisfies PJR.

Proof. PJR requires that |S (

i N Ai)| ℓfor all groups N N of voters satisfying |N | ℓn

i N Ai| ℓfor some integer ℓ> 0. We show that seq-Phragm en satisfies a strictly stronger property by weakening the constraint |N | ℓn

k to |N | > ℓ n k+1. Consider an instance (A, k) and let S be the committee selected by seq-Phragm en. Assume for contradiction that there exists a group N N of voters and an integer ℓ> 0 with |N | > ℓ n k+1 such that |

i N Ai| ℓand |S (

i N Ai)| ℓ 1. Let c (

i N Ai) \ S and consider round k (the last round) of the seq-Phragm en procedure. Adding candidate c to the committee would have caused a maximal voter load of

s(k) c = 1 + i Nc x(k 1) i |Nc| 1 +

i N x(k 1) i |N |

|N | = ℓ |N | < k + 1

Here, the first inequality follows from part (ii) of Lemma 5 (observe that N Nc), the second inequality follows from |S ( i N Ai)| ℓ 1, and the strict inequality follows from |N | > ℓ n k+1. Let ck be the candidate that was chosen in round k. Since candidate c was not chosen, we have c = ck and s(k) ck s(k) c . Using part (i) of Lemma 5, we have s(1) . . . s(k) = s(k) ck s(k) c < k+1

n . In particular, this implies that at the end of round k, every voter i N has a load x(k) i that is strictly

less than k+1

n . Summing the loads over all voters, we get

i N x(k) i =

i N x(k) i +

i N\N x(k) i

(ℓ 1) + |N \ N | s(k)

< ℓ 1 + n k + 1(k + 1 ℓ)k + 1

where we have used the fact that |N \N | n k+1(k+1 ℓ).

But i N x(k) i < k is a contradiction, because the sum of all voter loads (at the end of the seq-Phragm en procedure) must equal k. This completes the proof.

A consequence of Theorem 6 is that a committee providing PJR can be computed in polynomial time. We note that the proof of Theorem 6 shows that seq-Phragm en satisfies a property that is strictly stronger than PJR, because the constraint on the size of group N has been relaxed. As an immediate corollary of Theorem 6, we obtain that seq-Phragm en satisfies JR.

Corollary 7. seq-Phragm en satisfies JR.

However, seq-Phragm en violates EJR, as the following example demonstrates.

Example 5. Consider the following instance with n = 24, k = 12, and C = {a, b, c1, c2, . . . , c12}.

2 {a, b, c1} 6 {c1, c2, . . . , c12} 2 {a, b, c2} 5 {c2, c3, . . . , c12} 9 {c3, c4, . . . , c12}

seq-Phragm en selects S = {c1, c2, . . . , c12}. To see that S does not provide EJR, consider the group N consisting of the four voters on the left. We have |N | = 4 = 2 n

k and | i N Ai| = |{a, b}| = 2. Therefore, EJR requires that at least one voter in N approves at least 2 candidates in S, which is not the case.

Therefore, it remains an open problem whether an committee providing EJR can be computed in polynomial time. Note that seq-Phragm en also fails PR (see Example 4). This is not surprising, considering that PR is computationally intractable (S anchez-Fern andez et al. 2017).

6.3 Results for max-Phragm en In Example 4, max-Phragm en selects the committee providing perfect representation. We now show that max Phragm en satisfies PR in general.

Theorem 8. max-Phragm en satisfies PR.

The proof consists of (1) observing that the existence of a committee providing PR implies the existence of a perfect load distribution, and (2) showing that every perfect load distribution corresponds to a committee providing PR. For the latter, we invoke the Birkhoff von-Neumann theorem. Since EJR is incompatible with PR (see Example 4), max Phragm en fails EJR. However, it satisfies property PJR.

Theorem 9. max-Phragm en satisfies PJR.

The proof is by contradiction. Assuming that there is a cohesive group N such that not enough candidates approved by voters in N are in the committee, the corresponding load distribution can be improved upon (with respect to leximax comparisons) by shifting load from N \ N to N . Corollary 10. max-Phragm en satisfies JR. We note that Example 1 shows that simply minimizing the maximal voter load (without leximax tie-breaking; see Definition 1) does not even yield committees satisfying JR.

6.4 Results for var-Phragm en The proof of Theorem 8 directly applies to var-Phragm en. Theorem 11. var-Phragm en satisfies PR. Unlike max-Phragm en, var-Phragm en fails PJR. Example 6. Consider the following example with 100 voters, C = {a, b, c, d, e, f, g}, and k = 6. 67 voters approve {a, b, c, d}, 12 voters approve {e}, 11 voters approve {f}, and 10 voters approve {g}. Let N be the set of voters approving {a, b, c, d}. We have |N | = 67 4 n

i N Ai| = 4. Thus, PJR requires that all four candidates in

i N Ai = {a, b, c, d} are selected. However, var-Phragm en selects {a, b, c, e, f, g}. Example 6 also shows that the sequential version of var Phragm en violates PJR. Example 6 is an instance of the party-list setting (with four disjoint parties). An alternative proof that var-Phragm en violates PJR consists in noting that in the party-list setting, var-Phragm en reduces to Sainte-Lagu e s apportionment method (Sainte-Lagu e 1910), and PJR is equivalent to lower quota (Brill, Laslier, and Skowron 2017; S anchez-Fern andez, Fern andez, and Fisteus 2016). It is well known that Sainte-Lagu e s method violates lower quota (Balinski and Young 1982). Finally, we prove that var-Phragm en satisfies JR. Theorem 12. var-Phragm en satisfies JR.

7 Conclusion We have shown that Phragm en s load-balancing methods satisfy interesting representation axioms. In particular, the polynomial-time computable variant seq-Phragm en satisfies PJR. Moreover, we have shown that both max-Phragm en and var-Phragm en satisfy PR and that max-Phragm en additionally satisfies PJR. Arguably, max-Phragm en is the first known example of a natural rule satisfying both PR and PJR the only other rule known to satisfy these two properties is an artificial construct that returns a PR committee if one exists and otherwise runs PAV (S anchez-Fern andez et al. 2017). The Monroe rule (i.e., the optimization variant of Greedy Monroe) satisfies PR by definition, but fails PJR if the committee size does not divide the number of voters (S anchez-Fern andez et al. 2017). Since seq-Phragm en violates EJR, it remains an open problem whether committees providing EJR can be computed efficiently. The intricate nature of Example 5 seems to suggest that instances on which seq-Phragm en violates EJR are rare. It would be interesting to see whether seq Phragm en satisfies EJR for realistic distributions of preferences and/or for reasonable domain restrictions.

Acknowledgments We would like to thank Xavier Mora for many fruitful discussions and for providing us with copies of the original papers by Phragm en. We also thank Marie-Louise Lackner for pointing out essential literature and providing us with translations. Furthermore, we thank Vincent Conitzer, Edith Elkind, Dominik Peters, and Piotr Skowron for helpful comments. This material is based on work supported by ERCSt G 639945, NSF IIS-1527434 and ARO W911NF-12-10550, by a Feodor Lynen return fellowship of the Alexander von Humboldt Foundation, by COST Action IC1205 on Computational Social Choice, by a grant from the Knut and Alice Wallenberg Foundation, by the Isaac Newton Institute for Mathematical Sciences (EPSRC Grant Number EP/K032208/1) and by a grant from the Simons foundation.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2015a. Justified representation in approval-based committee voting. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 784 790. AAAI Press. Aziz, H.; Gaspers, S.; Gudmundsson, J.; Mackenzie, S.; Mattei, N.; and Walsh, T. 2015b. Computational aspects of multi-winner approval voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 107 115. IFAAMAS. Balinski, M., and Young, H. P. 1982. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press. Betzler, N.; Slinko, A.; and Uhlmann, J. 2013. On the computation of fully proportional representation. Journal of Artificial Intelligence Research 47:475 519. Brill, M.; Laslier, J.-F.; and Skowron, P. 2017. Multiwinner approval rules as apportionment methods. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI). AAAI Press. Forthcoming. Caragiannis, I.; Nath, S.; Procaccia, A. D.; and Shah, N. 2016. Subset selection via implicit utilitarian voting. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 151 157. AAAI Press. 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. Janson, S. 2012. Proportionella valmetoder. Available at http://www2.math.uu.se/ svante/papers/sj V6.pdf. 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 Handbook on Approval Voting. Springer. Chapter 6.

Lu, T., and Boutilier, C. 2011. Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 280 286. AAAI Press. Monroe, B. L. 1995. Fully proportional representation. The 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. Mora, X. 2016. Phragm en s sequential method with a variance criterion. Technical Report ar Xiv:1611.06833 [math.OC], 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. Phragm en, E. 1895. Proportionella val. En valteknisk studie. Svenska sp orsm al 25. Lars H okersbergs f orlag, Stockholm. Phragm en, E. 1896. Sur la th eorie des elections multiples. Ofversigt af Kongliga Vetenskaps-Akademiens F orhandlingar 53:181 191. Phragm en, E. 1899. Till fr agan om en proportionell valmetod. Statsvetenskaplig Tidskrift 2(2):297 305. Potthof, R. F., and Brams, S. J. 1998. Proportional representation: Broadening the options. Journal of Theoretical Politics 10(2):147 178. Procaccia, A. D.; Rosenschein, J. S.; and Zohar, A. 2008. On the complexity of achieving proportional representation. Social Choice and Welfare 30:353 362. Sainte-Lagu e, A. 1910. La repr esentation proportionnelle et la m ethode des moindres carr es. In Annales scientifiques de l Ecole Normale Sup erieure, volume 27, 529 542. S anchez-Fern andez, L.; Fern andez, N.; Fisteus, J. A.; and Basanta Val, P. 2016. Some notes on justified representation. In Proceedings of the 10th Multidisciplinary Workshop on Advances in Preference Handling (MPREF). S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial 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 29th AAAI Conference on Artificial Intelligence (AAAI), 2131 2137. AAAI Press. Thiele, T. N. 1895. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 415 441.