# approvalbased_apportionment__cbe2cfd3.pdf

The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)

Approval-Based Apportionment

Markus Brill,1 Paul G olz,2 Dominik Peters,2 Ulrike Schmidt-Kraepelin,1 Kai Wilker1

1Technische Universit at Berlin, Chair of Efficient Algorithms 2Carnegie Mellon University, Computer Science Department {brill, u.schmidt-kraepelin}@tu-berlin.de, {pgoelz, dominikp}@cs.cmu.edu, wilker@campus.tu-berlin.de

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.

1 Introduction The fundamental fairness principle of proportional representation is relevant in a variety of applications ranging from recommender systems to digital democracy (Skowron et al. 2017). It features most explicitly in the context of political elections, which is the language we adopt for this paper. In this context, proportional representation prescribes that the number of representatives championing a particular opinion in a legislature be proportional to the number of voters who favor that opinion. In most democratic institutions, proportional representation is implemented via party-list elections: Candidates are members of political parties and voters are asked to indicate their favorite party; each party is then allocated a number of seats that is (approximately) proportional to the number of votes it received. The problem of transforming a voting outcome into a distribution of seats is known as apportionment. Analyzing the advantages and disadvantages of different apportionment methods has a long and illustrious political history and has given rise to a deep and elegant mathematical theory (Balinski and Young 1982; Pukelsheim 2014). Unfortunately, forcing voters to choose a single party prevents them from communicating any preferences beyond their most preferred alternative. For example, if a voter feels

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

equally well represented by several political parties, there is no way to express this preference within the voting system. In the context of single-winner elections, approval voting has been put forward as a solution to this problem as it strikes an attractive compromise between simplicity and expressivity (Brams and Fishburn 2007; Laslier and Sanver 2010). Under approval voting, each voter is asked to specify a set of candidates she approves of, i.e., voters can arbitrarily partition the set of candidates into approved candidates and disapproved ones. Proponents of approval voting argue that its introduction could increase voter turnout, help elect the strongest candidate, and add legitimacy to the outcome of an election (Brams and Fishburn 2007, pp. 4 8). Due to the practical and theoretical appeal of approval voting in single-winner elections, a number of scholars have suggested to also use approval voting for multiwinner elections, in which a fixed number of candidates needs to be elected (Kilgour and Marshall 2012). In contrast to the single-winner setting, where the straightforward voting rule choose the candidate approved by the highest number of voters enjoys a strong axiomatic foundation (Fishburn 1978), several ways of aggregating approval ballots have been proposed in the multiwinner setting (e.g., Aziz et al. 2017; Janson 2016). Most studies of approval-based multiwinner elections assume that voters directly express their preference over individual candidates; we refer to this setting as candidate-approval elections. This assumption runs counter to widespread democratic practice, in which candidates belong to political parties and voters indicate preferences over these parties (which induce implicit preferences over candidates). In this paper, we therefore study party-approval elections, in which voters express approval votes over parties and a given number of seats must be distributed among the parties. We refer to the process of allocating these seats as approval-based apportionment. We believe that party-approval elections are a promising framework for legislative elections in the real world. Allowing voters to express approval votes over parties enables the aggregation mechanism to coordinate like-minded voters. For example, two blocks of voters might currently vote for parties that they mutually disapprove of. Using approval ballots could reveal that the blocks jointly approve a party of more general appeal; allocating more seats to this party leads to mutual gain. This cooperation is particularly necessary for small minority opinions that are not centrally coordinated. In

such cases, finding a commonly approved party can make the difference between being represented or votes being wasted because the individual parties receive insufficient support. In contrast to approval voting over individual candidates, party-approval voting does not require a break with the current role of political parties it can be combined with both open list and closed list approaches to filling the seats allocated to a party.

1.1 Related Work

To the best of our knowledge, this paper is the first to formally develop and systematically study approval-based apportionment. That is not to say that the idea of expressing and aggregating approval votes over parties has not been considered before. Indeed, several scholars have explored possible generalizations of existing aggregation procedures. For instance, Brams, Kilgour, and Potthoff (2019) study multiwinner approval rules that are inspired by classical apportionment methods. Besides the setting of candidate approval, they explicitly consider the case where voters cast party-approval votes. They conclude that these rules could encourage coalitions across party or factional lines, thereby diminishing gridlock and promoting consensus. Such desire for compromise is only one motivation for considering party-approval elections, as exemplified by recent work by Speroni di Fenizio and Gewurz (2019). To allow for more efficient governing, they aim to concentrate the power of a legislature in the hands of few big parties, while nonetheless preserving the principle of proportional representation. To this end, they let voters cast party-approval votes and transform these votes into a party-list election by assigning each voter to one of her approved parties. One method for doing this (referred to as majoritarian portioning later in this paper) assigns voters to parties in such a way that the strongest party has as many votes as possible. Several other papers consider extensions of approval-based voting rules to accommodate party-approval elections (Brams and Kilgour 2014; Mora and Oliver 2015; Janson 2016; Janson and Oberg 2019). All of these papers have in common that they study specific rules or classes of rules, rather than exploring the party-approval setting in its own right.

1.2 Relation to Other Settings

Party-approval elections can be positioned between two wellstudied voting settings (see Figure 1). First, approval-based apportionment generalizes standard apportionment, which corresponds to party-approval elections in which all approval sets are singletons. This relation (depicted as arrow (i) in Figure 1) provides a generic two-step approach to define aggregation rules for approval-based apportionment problems: transform a party-approval instance to an apportionment instance, and then apply an apportionment method. In Section 3, we employ this approach to construct approval-based apportionment methods satisfying desirable properties. Second, our setting can be viewed as a special case of approval-based multiwinner voting, in which voters cast candidate-approval votes. A party-approval election can be

Candidate-approval elections (Kilgour and Marshall 2012; Aziz et al. 2017)

Party-approval elections [approval-based apportionment]

Party-list elections [apportionment] (Balinski and Young 1982; Pukelsheim 2014)

Figure 1: Relations between the different settings of multiwinner elections. An arrow from X to Y signifies that X is a generalization of Y . The relationship corresponding to arrow (iii) has been explored by Brill, Laslier, and Skowron (2018). We establish and explore the relationship (i) in Section 3 and the relationship (ii) in Section 4.

embedded in this setting by replacing each party by multiple candidates belonging to this party, and by interpreting a voter s approval of a party as approval of all of its candidates. This embedding establishes party-approval elections as a subdomain of candidate-approval elections (see arrow (ii) in Figure 1). In Section 4, we explore the axiomatic and computational ramifications of this domain restriction.

1.3 Contributions In this paper, we formally introduce the setting of approvalbased apportionment and explore different possibilities of constructing axiomatically desirable aggregation methods for this setting. Besides its conceptual appeal, this setting is also interesting from a technical perspective. Exploiting the relations described in Section 1.2, we resolve problems that remain open in the more general setting of approval-based multiwinner voting. First, we prove that committee monotonicity is compatible with extended justified representation (a representation axiom proposed by Aziz et al. 2017) by providing a rule that satisfies both properties. Second, we show that the core of an approval-based apportionment problem is always nonempty and that core-stable committees can be found in polynomial time. Besides these positive results, we verify for a wide range of multiwinner voting rules that their axiomatic guarantees do not improve in the party-approval setting, and that some rules remain NP-hard to evaluate. On the other hand, we show that it becomes tractable to check whether a committee provides extended justified representation or the weaker axiom of proportional justified representation. Omitted proofs as well as further definitions and results can be found in the full version of the paper (Brill et al. 2019).

2 The Model A party-approval election is a tuple (N, P, A, k) consisting of a set of voters N = {1, . . . , n}, a finite set of parties P, a ballot profile A = (A1, . . . , An) where each ballot Ai P is the set of parties approved by voter i, and the committee

size k N. We assume that Ai = for all i N. When considering computational problems, we assume that k is encoded in unary (see Footnote 5). A committee in this setting is a multiset W : P N over parties, which determines the number of seats W(p) assigned to each party p P. The size of a committee W is given by |W| =

p P W(p), and we denote multiset addition and subtraction by + and , respectively. A party-approval rule is a function that takes a party-approval election (N, P, A, k) as input and returns a committee W of valid size |W| = k.1 In our axiomatic study of party-approval rules, we focus on two axioms capturing proportional representation: extended justified representation and core stability (Aziz et al. 2017).2 Both axioms are derived from their analogs in multiwinner elections (see Section 4.2) and can be defined in terms of quota requirements. For a party-approval election (N, P, A, k) and a subset S N of voters, define the quota of S as q(S) = k |S|/n . Intuitively, q(S) corresponds to the number of seats that the group S deserves to be represented by (rounded down).

Definition 1. A committee W : P N provides extended justified representation (EJR) for a party-approval election (N, P, A, k) if there is no subset S N of voters such that i S Ai = and p Ai W(p) < q(S) for all i S.

In words, EJR requires that for every voter group S with a commonly approved party, at least one voter of the group should be represented by q(S) many candidates. A partyapproval rule is said to satisfy EJR if it only produces committees providing EJR. We can obtain a stronger representation axiom by removing the requirement of a commonly approved party.

Definition 2. A committee W : P N is core stable for a party-approval election (N, P, A, k) if there is no nonempty subset S N and committee T : P N of size |T| q(S) such that

p Ai T(p) >

p Ai W(p) for all i S. The core of a party-approval election is defined as the set of all core-stable committees.

Core stability requires adequate representation even for voter groups that cannot agree on a common party, by ruling out the possibility that the group can deviate to a smaller committee that represents all voters in the group strictly better. It follows from the definitions that core stability is a stronger requirement than EJR: If a committee violates EJR, there is a group S that would prefer any committee of size q(S) that assigns all seats to the commonly approved party. A final, non-representational axiom that we will discuss is committee monotonicity. A party-approval rule f satisfies this axiom if, for all party-approval elections (N, P, A, k),

1This definition implies that rules are resolute, that is, only a single committee is returned. In the case of a tie between multiple committees, a tiebreaking mechanism is necessary. Our results hold independently of the choice of a specific tiebreaking mechanism. 2Some results in the full version refer to the weaker representation axioms of justified representation (JR) (Aziz et al. 2017) and proportional justified representation (PJR) (S anchez-Fern andez et al. 2017). It is well known that EJR implies PJR and that PJR implies JR.

it holds that f(N, P, A, k) f(N, P, A, k + 1). Committee monotonic rules avoid the so-called Alabama paradox, in which a party loses a seat when the committee size increases. Besides, committee monotonic rules can be used to construct proportional rankings (Skowron et al. 2017).

3 Constructing Party-Approval Rules via Portioning and Apportionment

Party-approval elections are a generalization of party-list elections, which can be thought of as party-approval elections in which all approval sets are singletons. Since there is a rich body of research on apportionment methods, it is natural to examine whether we can employ these methods for our setting as well. To use them, we will need to translate party-approval elections into the party-list domain on which apportionment methods operate. This translation thus needs to transform a collection of approval votes over parties into vote shares for each party. Motivated by time sharing, Bogomolnaia, Moulin, and Stong (2005) have developed a theory of such transformation rules, further studied by Duddy (2015) and Aziz, Bogomolnaia, and Moulin (2019). We will refer to this framework as portioning. The approach explored in this section, then, divides the construction of a party-approval rule into two independent steps: (1) portioning, which maps a party-approval election to a vector of parties shares; followed by (2) apportionment, which transforms the shares into a seat distribution. Both the portioning and the apportionment literature have discussed representation axioms similar in spirit to EJR and core stability. For both settings, several rules have been found to satisfy these properties. One might hope that by composing two rules that are each representative, we obtain a partyapproval rule that is also representative (and satisfies, say, EJR). If we succeed in finding such a combination, it is likely that the resulting voting rule will automatically satisfy committee monotonicity since most apportionment methods satisfy this property. In the general candidate-approval setting (considered in Section 4), the existence of a rule satisfying both EJR and committee monotonicity is an open problem.

3.1 Preliminaries

We start by introducing relevant notions from the literature of portioning (Bogomolnaia, Moulin, and Stong 2005; Aziz, Bogomolnaia, and Moulin 2019) and apportionment (Balinski and Young 1982; Pukelsheim 2014), with notations and interpretations suitably adjusted to our setting.

Portioning A portioning problem is a triple (N, P, A), just as in party-approval voting but without a committee size. A portioning is a function r : P [0, 1] with

p P r(p) = 1. We interpret r(p) as the vote share of party p. A portioning method maps each triple (N, P, A) to a portioning. Our minimum requirement on portioning methods will be that they uphold proportionality if all approval sets are singletons, i.e., if we are already in the party-list domain. Formally, we say that a portioning method is faithful if for all (N, P, A) with |Ai| = 1 for all i N, the resulting portioning r satisfies r(p) = |{i N | Ai = {p}}|/n for all

p P. Among the portioning methods considered by Aziz, Bogomolnaia, and Moulin (2019), only three are faithful. They are defined as follows.

Conditional utilitarian portioning selects, for each voter i, pi as a party in Ai approved by the highest number of voters. Then, r(p) = |{i N | pi = p}|/n for all p P.

Random priority computes n! portionings, one for each permutation σ of N, and returns their average. The portioning for σ = (i1, . . . , in) maximizes

p Ai1 r(p), breaking ties by maximizing

p Ai2 r(p), and so forth.

Nash portioning selects the portioning r maximizing the Nash welfare

The last method seems particularly promising because it satisfies portioning versions of core stability and EJR (Aziz, Bogomolnaia, and Moulin 2019). We will also make use of a more recent portioning approach, which was proposed by Speroni di Fenizio and Gewurz (2019) in the context of party-approval voting.

Majoritarian portioning proceeds in rounds j = 1, 2, . . . . Initially, all parties and voters are active. In iteration j, we select the active party pj that is approved by the highest number of active voters. Let Nj be the set of active voters who approve pj. Then, set r(pj) to |Nj|/n, and mark pj and all voters in Nj as inactive. If active voters remain, the next iteration is started; else, r is returned.

Under majoritarian portioning, the approval preferences of voters who have been assigned to a party are ignored in further iterations. Note that conditional utilitarian portioning can similarly be seen as a sequential method, in which the preferences of inactive voters are not ignored.

Apportionment An apportionment problem is a tuple (P, r, k), which consists of a finite set of parties P, a portioning r : P [0, 1] specifying the vote shares of parties, and a committee size k N. Committees are defined as for party-approval elections, and an apportionment method maps apportionment problems to committees W of size k. An apportionment method satisfies lower quota if each party p is always allocated at least k r(p) seats in the committee. Furthermore, an apportionment method f is committee monotonic if f(P, r, k) f(P, r, k + 1) for every apportionment problem (P, r, k). Among the standard apportionment methods, only one satisfies both lower quota and committee monotonicity: the D Hondt method (aka Jefferson method).3 The method assigns the k seats iteratively, each time giving the next seat to the party p with the largest quotient r(p)/(s(p) + 1), where s(p) denotes the number of seats already assigned to p. Another apportionment method satisfying lower quota and committee monotonicity is the quota method, due to Balinski and Young (1975). It is identical to the D Hondt method, except that, in the jth iteration, only parties p satisfying s(p)/j < r(p) are eligible for the allocation of the next seat.

3All other divisor methods fail lower quota, and the Hamilton method is not committee monotonic (Balinski and Young 1982).

Composition If we take any portioning method and any apportionment method, we can compose them to obtain a party-approval rule. Note that if the apportionment method is committee monotonic then so is the composed rule, since the portioning is independent of k.

3.2 Composed Rules That Fail EJR Perhaps surprisingly, many pairs of portioning and apportionment methods fail EJR. This is certainly true if the individual parts are not representative themselves. For example, if an apportionment method M properly fails lower quota (in the sense that there is a rational-valued input r on which lower quota is violated), then one can construct an example profile on which any composed rule using M fails EJR: Construct a party-approval election with singleton approval sets in which the voter counts are proportional to the shares in the counterexample r. Then any faithful portioning method, applied to this election, must return r. Since M fails lower quota on r, the resulting committee will violate EJR. By a similar argument, an apportionment method that violates committee monotonicity on some rational portioning will, when composed with a faithful portioning method, give rise to a party-approval rule that fails committee monotonicity. To our knowledge, among the named and studied apportionment methods, only two satisfy both lower quota and committee monotonicity: D Hondt and the quota method. However, it turns out that the composition of either option with the conditional-utilitarian, random-priority, or Nash portioning methods fails EJR, as the following examples show. Example 1. Let n = k = 6, P = {p0, p1, p2, p3}, A = ({p0}, {p0}, {p0, p1, p2}, {p0, p1, p2}, {p1, p3}, {p2, p3}). Then, the conditional utilitarian solution sets r(p0) = 4/6, r(p1) = r(p2) = 1/6, and r(p3) = 0. Any apportionment method satisfying lower quota allocates four seats to p0, one each to p1 and p2, and none to p3. The resulting committee does not provide EJR since the last two voters, who jointly approve p3, have a quota of q({5, 6}) = 2 that is not met. Example 2. Let n = k = 6, P = {p0, p1, p2, p3}, and A = ({p0}, {p0}, {p0, p1, p2}, {p0, p1, p3}, {p1}, {p2, p3}). Random priority chooses the portioning r(p0) = 23/45, r(p1) = 23/90, and r(p2) = r(p3) = 7/60. Both D Hondt and the quota method allocate four seats to p0, two seats to p1, and none to the other two parties. This clearly violates the claim to representation of the sixth voter (with q({6}) = 1). Nash portioning produces a fairly similar portioning, with r(p0) 0.5302, r(p1) 0.2651, and r(p2) = r(p3) 0.1023. D Hondt and the quota method produce the same committee as above, leading to the same EJR violation. At first glance, it might be surprising that Nash portioning combined with a lower-quota apportionment method violates EJR (and even the weaker axiom JR). Indeed, Nash portioning satisfies core stability in the portioning setting, which is a strong notion of proportionality, and the lower-quota property limits the rounding losses when moving from the portioning to a committee. As expected, in the election of Example 2, the Nash solution itself gives sufficient representation to the sixth voter since r(p2) + r(p3) 0.2047 > 1/6. However, since both r(p2) and r(p3) are below 1/6 on their own, lower

quota does not apply to either of the two parties, and the sixth voter loses all representation in the apportionment step.

3.3 Composed Rules That Satisfy EJR

As we have seen, several initially promising portioning methods fail to compose to a rule that satisfies EJR. One reason is that these portioning methods are happy to assign small shares to several parties. The apportionment method may round several of those small shares down to zero seats. This can lead to a failure of EJR when not enough parties obtain a seat. It is difficult for an apportionment method to avoid this behavior since the portioning step obscures the relationships between different parties that are apparent from the approval ballots of the voters. Majoritarian portioning is designed to maximize the seat allocations to the largest parties. Thus, it tends to avoid the problem we have identified. While it fails the strong representation axioms that Nash portioning satisfies, this turns out not to be crucial: Composing majoritarian portioning with any apportionment method satisfying lower quota yields an EJR rule. If we use an apportionment method that is also committee monotonic, such as D Hondt or the quota method, we obtain a party-approval rule that satisfies both EJR and committee monotonicity.4

Theorem 1. Let M be a committee monotonic apportionment method satisfying lower quota. Then, the party-approval rule composing majoritarian portioning and M satisfies EJR and committee monotonicity.

Proof. Consider a party-approval election (N, P, A, k) and let r be the outcome of majoritarian portioning applied to (N, P, A). Let N1, N2, . . . and p1, p2, . . . be the voter groups and parties in the construction of majoritarian portioning, so that r(pj) = |Nj|/n for all j. Consider the committee W = M(P, r, k) and suppose that EJR is violated, i.e., that there exists a group S N with

i S Ai = and

p Ai W(p) < q(S) for all i S. Let j be minimal such that S Nj = . We now show that |S| |Nj|. By the definition of j, no voter in S approves of any of the parties p1, p2, . . . pj 1; thus, all those voters remain active in round j. Consider a party p i S Ai. In the jth iteration of majoritarian portioning, this party had an approval score of at least |S|. Therefore, the party pj that is chosen in the jth iteration has an approval score that is at least |S| (of course, p = pj is possible). The approval score of party pj equals |Nj|. Therefore, |Nj| |S|. Since |Nj| |S|, we have q(Nj) q(S). Since M satisfies lower quota, it assigns at least k r(pj) = k(|Nj|/n) = q(Nj) seats to party pj. Now consider a voter i S Nj. Since this voter approves party pj, we have

p Ai W(p) W(pj) q(Nj) q(S), a contradiction. This shows that EJR is indeed satisfied; committee monotonicity follows from the committee monotonicity of M.

4As long as the apportionment method is computable in polynomial time (which is the case for D Hondt and the quota method), the same holds for the resulting party-approval rule.

While the party-approval rules identified by Theorem 1 satisfy EJR and committee monotonicity, they do not quite reach our gold standard of representation, i.e., core stability. Example 3. Let n = k = 16, let P = {p0, . . . , p4}, with the following approval sets: 4 times {p0, p1}, 3 times {p1, p2}, once {p2}, 4 times {p0, p3}, 3 times {p3, p4}, and once {p4}. Note the symmetry between p1 and p3, and between p2 and p4. Majoritarian portioning allocates 1/2 to p0 and 1/4 each to p2 and p4. Any lower-quota apportionment method must translate this into 8 seats for p0 and 4 seats each for p2 and p4. This committee is not in the core: Let S be the coalition of all 14 voters who approve multiple parties, and let T allocate 4 seats to p0 and 5 seats each to p1 and p3. This gives strictly higher representation to all members of the coalition. The example makes it obvious why majoritarian portioning cannot satisfy the core: All voters approving of p0 get deactivated after the first round, which makes p2 seem universally preferable to p1. However, p1 is a useful vehicle for cooperation between the group approving {p0, p1} and the group approving {p1, p2}. Since majoritarian portioning is blind to this opportunity, it cannot guarantee core stability. The example also illustrates the power of core stability: The deviating coalition does not agree on any single party they support, but would nonetheless benefit from the deviation. There is room for collaboration, and core stability is sensitive to this demand for better representation.

4 Constructing Party-Approval Rules via Multiwinner Voting Rules In the previous section, we applied tools from apportionment, a more restrictive setting, to our party-approval setting. Now, we go in the other direction, and apply tools from a more general setting: As mentioned in Section 1.2, party-approval elections can be viewed as a special case of candidate-approval elections, i.e., multiwinner elections in which approvals are expressed over individual candidates rather than parties. After introducing relevant candidate-approval notions, we show how party-approval elections can be translated into candidateapproval elections. This embedding allows us to apply established candidate-approval rules to our setting. Exploiting this fact, we will prove the existence of core-stable committees for party-approval elections.

4.1 Preliminaries A candidate-approval election is a tuple (N, C, A, k). Just as for party-approval elections, N = {1, . . . , n} is a set of voters, C is a finite set, A is an n-tuple of nonempty subsets of C, and k N is the committee size. The conceptual difference is that C is a set of individual candidates rather than parties. This difference manifests itself in the definition of a committee because a single candidate cannot receive multiple seats. That is, a candidate committee W is now simply a subset of C with cardinality k. (Therefore, it is usually assumed that |C| k.) A candidate-approval rule is a function that maps each candidate-approval election to a candidate committee. A diverse set of such voting rules has been proposed since the late 19th century (Kilgour and Marshall 2012;

Janson 2016; Aziz et al. 2017), out of which we will only introduce the one which we use for our main positive result. Let Hj denote the jth harmonic number, i.e., Hj = j t=1 1/t. Given (N, C, A, k), the candidate-approval rule proportional approval voting (PAV), introduced by Thiele (1895), chooses a candidate committee W maximizing the PAV score PAV(W) =

i N H|W Ai|. We now describe EJR and core stability in the candidateapproval setting, from which our versions of these axioms are derived. Recall that q(S) = k |S|/n . A candidate committee W provides EJR if there is no subset S N and no integer ℓ> 0 such that q(S) ℓ, |

i S Ai| ℓ, and |Ai W| < ℓfor all i S. (The requirement |

i S Ai| ℓ is often referred to as cohesiveness.) A candidate-approval rule satisfies EJR if it always produces EJR committees. The definition of core stability is even closer to the version in party-approval: A candidate committee W is core stable if there is no nonempty group S N and no set T C of size |T| q(S) such that |Ai T| > |Ai W| for all i S. The core consists of all core-stable candidate committees.

4.2 Embedding Party-Approval Elections

We have informally argued in Section 1.2 that party-approval elections constitute a subdomain of candidate-approval elections. We formalize this notion by providing an embedding of party-approval elections into the candidate-approval domain. For a given party-approval election (N, P, A, k), we define a corresponding candidate-approval election with the same set of voters N and the same committee size k. The set of candidates contains k many clone candidates p(1), . . . , p(k)

for each party p P, and a voter approves a candidate p(j) in the candidate-approval election iff she approves the corresponding party p in the party-approval election. This embedding establishes party-approval elections as a subdomain of candidate-approval elections. As a consequence, we can apply rules and axioms from the more general candidateapproval setting also in the party-approval setting. In particular, the generic way to apply a candidate-approval rule for a party-approval election consists in (1) translating the party-approval election into a candidate-approval election, (2) applying the candidate-approval rule, and (3) counting the number of chosen clones per party to construct a committee over parties. Note that, since k is encoded in unary, the running time is blown up by at most a polynomial factor.5

Having established party-approval elections as a subdomain of candidate-approval elections, our variants of EJR and core stability (Definitions 1 and 2) are immediately induced by their candidate-approval counterparts. In particular, any candidate-approval rule satisfying an axiom in the candidate-

5For candidate-approval elections, it does not make sense to have more seats than candidates, whereas for party-approval elections it is natural to have more seats than parties. If k was encoded in binary, even greedy candidate-approval algorithms would suddenly have exponential running time. This would complicate running-time comparisons between the candidate-approval and party-approval setting and would blur the intuitive distinction between simple and complex algorithms. Encoding k in unary sidesteps this technical complication.

approval setting will satisfy the corresponding axiom in the party-approval setting as well. Note that, by restricting our view to party approval, the cohesiveness requirement of EJR is reduced to requiring a single commonly approved party.

4.3 PAV Guarantees Core Stability A powerful stability concept in economics, core stability is a natural extension of EJR. It is particularly attractive because blocking coalitions are not required to be coherent at all, just to be able to coordinate for mutual gain. Our earlier Example 3 illustrates how a coalition might deviate in spite of not agreeing on any approved party. Unfortunately, it is still unknown whether core-stable candidate committees exist for all candidate-approval elections. Fain, Munagala, and Shah (2018) give positive approximate results for a variant of core stability in which blocking coalitions S N get to provide sets of candidates T of size k but have to increase their utilities by at least a factor of n/|S| to be counterexamples to their notion of core stability. They provide a nonconstant approximation to the core in our sense, but nonemptyness remains open. Recently, Cheng et al. (2019) showed that there always exist randomized committees providing core stability (over expected representation), but it is not clear how their approach based on two-player zero-sum game duality would extend to deterministic committees. All standard candidate-approval rules either already fail weaker representation axioms such as EJR or fail core stability. In particular, Aziz et al. (2017) have shown that PAV satisfies EJR, but may produce non-core-stable candidate committees even for candidate-approval elections for which core-stable candidate committees are known to exist. By contrast, we show that PAV guarantees core stability in the party-approval setting. We follow the structure of the aforementioned proof showing that PAV satisfies EJR for candidate-approval elections (Aziz et al. 2017).

Theorem 2. For every party-approval election, PAV chooses a core-stable committee.

Proof. Consider a party-approval election (N, P, A, k) and let W : P N be the committee selected by PAV. Assume for contradiction that W is not core stable. Then, there is a nonempty coalition S and a committee T : P N such that |T| k |S|/n and p Ai T(p) > p Ai W(p) for every voter i S. Let ui(W) denote the number of seats in W that are allocated to parties approved by voter i, i.e., ui(W) =

p Ai W(p). Furthermore, for a party p with W(p) > 0, we let MC(p, W) denote the marginal contribution to the PAV score of allocating a seat to p, i.e., MC(p, W) = PAV(W) PAV(W {p}). Observe that MC(p, W) = i Np 1/ui(W), where Np = {i N | p Ai}. The sum of all marginal contributions satisfies

p P W(p) MC(p, W) =

W(p) ui(W) = |{i N | ui(W) > 0}| n.

Note that terms MC(p, W) for W(p) = 0 and quotients 1/ui(W) for ui(W) = 0 are undefined in the calculation above, but that they only appear with factor 0. It follows that the average marginal contribution of all k seats in W is at most n/k, and consequently, that there has to be a party p1 with a seat in W such that MC(p1, W) n/k. Using a similar argument, we show that there is also a party p2 with T(p2) > 0 which would increase the PAV score by at least n/k if it received an additional seat in W:

p P T(p) MC(p, W + {p}) =

T(p) ui(W + {p})

T(p) ui(W + {p}) =

T(p) ui(W) + 1

T(p) ui(T) = |{i S | ui(T) > 0}| = |S|.

The second inequality holds because every voter in S strictly increases their utility when deviating from W to T; the last equality holds because every voter in S must get some representation in T to deviate. As desired, it follows that there has to be a party p2 in the support of T with MC(p2, W + {p2}) |S|/|T| n/k. If any of these inequalities would be strict, that is, if MC(p1, W) < n/k or MC(p2, W + {p2}) > n/k, then the committee W {p1} + {p2} would have a PAV-score of

PAV(W) MC(p1, W) + MC(p2, W {p1}+{p2}) PAV(W) MC(p1, W) + MC(p2, W + {p2}) (1) > PAV(W),

which would contradict the choice of W. Else, suppose that MC(p, W) = n/k for all parties p in the support of W and MC(p, W +{p}) = n/k for all parties p in the support of T. If there is a party p1 in W that is approved by some voter i S, we can choose an arbitrary party p2 from the support of T that i approves as well. Then, for voter i, the marginal contribution of p2 in W {p1} + {p2} is 1 ui(W {p1}+{p2}) = 1 ui(W ), but the marginal contribution of p2 in W +{p2} for i is only 1 ui(W +{p2}) = 1 ui(W )+1. This implies MC(p2, W {p1} + {p2}) > MC(p2, W + {p2}), which makes inequality (1) strict and again contradicts the optimality of W. Thus, one has to assume that no voter in S approves any party in the support of W. Pick an arbitrary p in the support of T, and recall that MC(p , W + {p }) = n/k for all p in the support of T. Thus, all inequalities in the derivation of

p P T(p) MC(p, W + {p}) |S| above must be equalities, which implies that this increase in PAV score must solely come from voters in S. Thus, there are at least n/k voters in S who are not represented at all in W, but commonly approve p. This would be a violation of EJR, contradicting the fact that PAV satisfies this axiom.

Corollary 3. The core of a party-approval election is nonempty.

An immediate follow-up question is whether core-stable committees can be computed efficiently. PAV committees are known to be NP-hard to compute in the candidate-approval setting, and we confirm in the full version of the paper that hardness still holds in the party-approval subdomain. Equally confronted with the computational complexity of PAV, Aziz et al. (2018) proposed a local-search variant of PAV, which runs in polynomial time and guarantees EJR in the candidate-approval setting. Using the same approach, we can find a core-stable committee in the party-approval setting. We defer the proof to the full version of the paper. Theorem 4. Given a party-approval election, a core-stable committee can be computed in polynomial time. Theorem 2 motivates the question of whether other candidate-approval rules satisfy stronger representation axioms when restricted to the party-approval subdomain. We have studied this question for various rules besides PAV, and the answer was always negative.6 While the party-approval setting does not reduce the complexity of computing PAV, it allows us to efficiently check whether a given committee provides EJR or PJR; both problems are co NP-hard in the candidate-approval setting (Aziz et al. 2017; 2018). For EJR, this follows from coherence becoming simpler for party-approval elections. Our algorithm for checking PJR employs submodular minimization. Again, details can be found in the full version.

5 Discussion In this paper, we have initiated the axiomatic analysis of approval-based apportionment. On a technical level, it would be interesting to see whether the party-approval domain allows us to satisfy other combinations of axioms that are not known to be attainable in candidate-approval elections. For instance, the compatibility between strong representation axioms and certain notions of support monotonicity is an open problem (S anchez-Fern andez and Fisteus 2019). We have presented our setting guided by the application of apportioning parliamentary seats to political parties. We believe that this is an attractive application worthy of practical experimentation. Our formal setting has other interesting applications. An example would be participatory budgeting settings in which the provision of items of equal cost is decided, where the items come in different types. For instance, a university department could decide how to allocate Ph.D. scholarships across different research projects, in a way that respects the preferences of funding organizations. As another example, the literature on multiwinner elections suggests many applications to recommendation problems (Skowron, Faliszewski, and Lang 2016). For instance, one might want to display a limited number of news articles, movies, or advertisements in a way that fairly represents

6We consider the candidate-approval rules Seq PAV, Rev Seq PAV, Approval Voting (AV), Satisfaction AV, Minimax AV, Seq Phragm en, Max Phragm en, Var Phragm en, Phragm en-STV, Monroe AV, Greedy Monroe AV, Greedy AV, Hare AV, and Chamberlin Courant AV. Besides EJR and core stability, we consider JR and PJR (see Footnote 2). Definitions and results can be found in the full version of the paper.

the preferences of the audience. These preferences might be expressed not over individual pieces of content, but over content producers (such as newspapers, studios, or advertising companies), in which case our setting provides rules that decide how many items should be contributed by each source. Expressing preferences on the level of content producers is natural in repeated settings, where the relevant pieces of content change too frequently to elicit voter preferences on each occasion. Besides, content producers might reserve the right to choose which of their content should be displayed. In the general candidate-approval setting, the search continues for rules that satisfy EJR and committee monotonicity, or core stability. But for the applications mentioned above, these guarantees are already achievable today.

Acknowledgements This work was partially supported by the Deutsche Forschungsgemeinschaft under Grant BR 4744/2-1. We thank Steven Brams and Piotr Skowron for suggesting the setting of party approval to us, and we thank Anne-Marie George, Ayumi Igarashi, Svante Janson, J erˆome Lang, and Ariel Procaccia for helpful comments and discussions.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified representation in approval-based committee voting. Social Choice and Welfare 48(2):461 485. Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the complexity of extended and proportional justified representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 902 909. Aziz, H.; Bogomolnaia, A.; and Moulin, H. 2019. Fair mixing: The case of dichotomous preferences. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), 753 781. Balinski, M. L., and Young, H. P. 1975. The quota method of apportionment. The American Mathematical Monthly 82(7):701 730. Balinski, M., and Young, H. P. 1982. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press. Bogomolnaia, A.; Moulin, H.; and Stong, R. 2005. Collective choice under dichotomous preferences. Journal of Economic Theory 122(2):165 184. Brams, S. J., and Fishburn, P. C. 2007. Approval Voting. Springer, 2nd edition. 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 Potthoff, R. F. 2019. Multiwinner approval voting: an apportionment approach. Public Choice 178(1 2):67 93. Brill, M.; G olz, P.; Peters, D.; Schmidt-Kraepelin, U.; and Wilker, K. 2019. Approval-based apportionment. Technical report, arxiv:1911.08365.

Brill, M.; Laslier, J.-F.; and Skowron, P. 2018. Multiwinner approval rules as apportionment methods. Journal of Theoretical Politics 30(3):358 382. Cheng, Y.; Jiang, Z.; Munagala, K.; and Wang, K. 2019. Group Fairness in Committee Selection. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), 263 279. Duddy, C. 2015. Fair sharing under dichotomous preferences. Mathematical Social Sciences 73:1 5. Fain, B.; Munagala, K.; and Shah, N. 2018. Fair allocation of indivisible public goods. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), 575 592. Fishburn, P. C. 1978. Axioms for approval voting: Direct proof. Journal of Economic Theory 19(1):180 185. Janson, S., and Oberg, A. 2019. A piecewise contractive dynamical system and Phragm en s election method. Bulletin de la Soci et e Math ematique de France 147(3):395 441. Janson, S. 2016. Phragm en s and Thiele s election methods. Technical report, arxiv:1611.08826. Kilgour, D. M., and Marshall, E. 2012. Approval balloting for fixed-size committees. In Electoral Systems, Studies in Choice and Welfare. Springer. 305 326. Laslier, J.-F., and Sanver, M. R., eds. 2010. Handbook on Approval Voting. Studies in Choice and Welfare. Springer. 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. Pukelsheim, F. 2014. Proportional Representation: Apportionment Methods and Their Applications. Springer. S anchez-Fern andez, L., and Fisteus, J. A. 2019. Monotonicity axioms in approval-based multi-winner voting rules. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 485 493. 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), 670 676. Skowron, P.; Lackner, M.; Brill, M.; Peters, D.; and Elkind, E. 2017. Proportional rankings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 409 415. Skowron, P. K.; Faliszewski, P.; and Lang, J. 2016. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence 241:191 216. Speroni di Fenizio, P., and Gewurz, D. A. 2019. The space of all proportional voting systems and the most majoritarian among them. Social Choice and Welfare 52(4):663 683. Thiele, T. N. 1895. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 415 441.