Justified representation

One definition for "proportional representation" is that the candidates are partitioned into disjoint parties, and each voter approves all candidates in a single party. For example,[1] suppose we need to elect a committee of size 10. Suppose that exactly 50% of the voters approve all candidates in party A, exactly 30% approve all candidates in party B, and exactly 20% approve all candidates in party C. Then, proportional representation requires that the committee contains exactly 5 candidates from party A, exactly 3 candidates from party B, and exactly 2 candidates from party C. If the fractions are not exact, then some rounding method should be used, and this can be done by various apportionment methods. However, in approval voting there is a different challenge: the voters' approval sets might not be disjoint. For example, a voter might approve one candidate from party A, two candidates from B, and five from C. This raises the question of how proportional representation should be defined.

Several definitions have been suggested in the literature. To describe the definitions, we use the following notation and terminology:

• k is the number of seats (i.e., the required committee size).
• n is the number of voters (in the above example, k=10 and n=100).
• n/k is the Hare quota - the minimum number of supporters that justifies a single seat. For simplicity, we assume that k divides n, so n/k is an integer.

For every integer L ≥ 1, a group of voters is called:

• L-large -- if it contains at least L*n/k voters (at least L quotas);

• L-cohesive -- if it is L-large, and in addition, there are some L candidates that all voters in the group approve.
• L-unanimous -- if it is L-large, and in addition, all group members approve exactly the same candidates.

Using these definitions, we now define the justified representation properties.

Justified Representation (JR) means that, in every 1-cohesive voter group, at least one voter approves some winner.

Unanimous Justified Representation (UJR) means that, for every L ≥ 1, in every L-unanimous voter group, their L commonly-approved candidates are elected.

Proportional Justified Representation (PJR) means that, for every L ≥ 1, in every L-cohesive voter group, the union of their approval sets contains some L winners.

Extended Justified Representation (EJR) means that, for every integer L ≥ 1, in every L-cohesive voter group, at least one voter approves some L winners.

Average Justified Representation (AJR) means that, for every L ≥ 1, in every L-cohesive voter group, the average satisfaction is at least L (where the satisfaction of a voter is the number of winners he approves, and the average is over all members in the group).

Semi-strong Justified Representation (SSJR) means that, in every 1-cohesive group, every voter approves some winner.

Strong Justified Representation (SJR) means that, in every 1-cohesive group, some winner is approved by every voter.

Perfect representation (PER) means that there is a mapping of each voter to a single winner approved by him, such that each winner represents exactly n/k voters. While a perfect representation may not exist, we expect that, if it exists, then it will be elected by the voting rule.

JR, EJR, SSJR and SJR were introduced and analyzed by Aziz, Brill, Conitzer, Elkind, Freeman, and Walsh.[2] PJR and PER were introduced and analyzed by Sanchez-Fernandez, Elkind, Lackner, Fernandez, Fisteus, Val, and Skowron.[3]

A closely related concept is core stability (CS). It means that, for any voter group of size L*n/k voters (not necessarily cohesive), if this group deviates and constructs a smaller committee with L seats, then for at least one voter, the number of committee members he approves is not larger than in the original committee.

JR is the weakest condition. It is implied by PJR, which is implied by EJR, which is implied both by core-stability and by AJR. JR is also implied by SSJR, which is implied by SSJR. This is summarized in the following diagram:

SJR and EJR do not imply each other.[2] PER considers only instances in which a perfect representation exists. Therefore, PER does not imply, nor implied by, any of the previous axioms.

Given the voters' preferences and a specific committee, can we efficiently check whether it satisfies any of these axioms?

• JR can be verified in polynomial time;
• PJR and EJR are coNP-complete to verify;
• PER is NP-hard to verify (deciding whether a perfect representation exists is NP-complete).

JR is satisfied by many rules, including proportional approval voting (PAV), Monroe, and Greedy Monroe, which can be computed in polynomial time.[2] Sequential-PAV satisfies JR for k ≤ 5, but fails JR for k ≥ 6.[3]

PJR is a more demanding requirement.

• Sequential-PAV violates PJR.
• When k divides n, Monroe and Greedy Monroe satisfy PJR. However, when k does not divide n, both Monroe and Greedy Monroe might violate PJR.[3]
• PAV satisfies PJR, and it is also the only weight-based approval voting rule that satisfies PJR. However, PAV cannot be computed in polytime.
• The Phragmen and Sequential-Phragmen rules both satisfy PJR for all n and k; sequential-Phragmen can be computed in polynomial time.[4]
• Another rule that is both PJR and polytime computable is the maximin-support rule.[5]
• It is co-NP-complete to check whether a given committee satisfies PJR.[6]

EJR is even more demanding. Sequential-PAV and Monroe rule fail EJR. Several known methods that satisfy EJR are:

• PAV satisfies EJR. It is the only weight-based approval voting rule that satisfies EJR.[2]
• The Method of Equal Shares[7] (previously called "Rule X") is a polynomially-time computable rule that satisfies EJR. Two other polytime algorithms that guarantee EJR Local-Search-PAV and EJR-Exact.[6]
• A simple algorithm that finds an EJR allocation is called "Greedy EJR". Looping L from k downwards to 1, this algorithm checks whether there is an L-cohesive subset of voters. If so, it chooses a largest L-cohesive subset, and adds some L candidates that are approved by all of them.[8]^{: Algorithm 1}
• It is co-NP-complete to check whether a given committee satisfies EJR.[3]

CS is even more demanding: it is an open question whether any multiwinner voting rule satisfies it.

AJR cannot be guaranteed in all cases; see section Average Satisfaction below.

SSJR and SJR are too strong in general: there are instances in which even SSJR cannot satisfied. For example, suppose k=3 and n=9. The candidates are {a, b, c, d}, and the votes are: {1:a, 2:a, 3:ab, 4:b, 5:bc, 6:c, 7:cd, 8:d, 9:d}. The Hare quota is 9/3 = 3. For each candidate, there is a 1-cohesive group who approves this candidate: {1,2,3} for a, {3,4,5} for b, {5,6,7} for c, {7,8,9} for d. Moreover, in each such group, at least one voter approves only one candidate. Therefore, SSJR requires that this candidate will be elected. However, only 3 candidates can be elected.[2]

PER is compatible with PJR and JR: for every instance that admits perfect representation, there exists a committee that satisfies PJR. However, PER is not compatible with EJR: there are instances in which perfect representations exist, but none of them satisfies EJR. PER is satisfied by the Monroe rule, but violated by Greedy Monroe, Sequential PAV, and PAV.[3] PER is also satisfied by Phragmen's rule; therefore, this rule can be used to attain both PJR and PER.[4]

The satisfaction of a voter, given a certain committee, is defined as the number of committee members approved by that voter. The average satisfaction of a group of voters is the sum of their satisfaction levels, divided by the group size. If a voter-group is L-cohesive (that is, their size is at least L*n/k and they approve at least L candidates in common), then:

• Every JR committee has an average satisfaction of at least 1 - 1/L + 1/(Ln). The same is true for every PJR committee.
• Every EJR committee has an average satisfaction of at least (L-1)/2. So, EJR provides a much stronger worst-case satisfaction guarantee than PJR.[3]
• Every committee with an average satisfaction larger than L-1 is satisfies EJR.

Proportional Approval Voting guarantees an average satisfaction larger than L-1. It has a variant called Local-Search-PAV, that runs in polynomial time, and also guarantees average satisfaction larger than L-1 (hence it is EJR).[6]^{: Thm.1,Prop.1} This guarantee is optimal: for every constant c>0, there is no rule that guarantees average satisfaction at least L-1+c.[6]^: Prop.2

Here is an example showing that no rule can guarantee an average satisfaction of L to all L-cohesive groups. Suppose n=12 voters have to elect a committee of k=3 out of a set of 4 candidates {a,b,c,d}. The voters' approval votes are: ab, b, b, bc, c, c, cd, d, d, da, a, a. The group {ab,b,b,bc} is 1-cohesive. To give them an average satisfaction of 1, candidate b must be elected. Similarly, The group {bc,c c,cd} is 1-cohesive, which requires to elect candidate c. Similarly, the group {cd,d,d,da} requires to elect d, and the group {da,a,a,ab} requires to elect a. So we need to elect 4 candidates, but the committee size is only 3. Therefore, no rule can guarantee Average Justified Representation.

However, AJR can be satisfied by fractional committees - committees in which members can serve for a fraction of a term. In particular, the Nash rule satisfies AJR.[9] See also fractional social choice.

Recently, the justified-representation axioms were adapted to party-approval voting. In this setting, rather than approving individual candidates, the voters need to approve whole parties. This setting is a middle ground between party-list elections, in which voters must pick a single party, and standard approval voting, in which voters can pick any set of candidates. In party-approval voting, voters can pick any set of parties, but cannot pick individual candidates within a party. Some JR axioms are adapted to this setting as follows.[10]

A voter group is called L-cohesive if it is L-large, and all group members approve at least one party in common (in contrast to the previous setting, they need not approve L parties, since it is assumed that each party contains at least L candidates, and all voters who approve the party, automatically approve all these candidates). In other words, an L-cohesive group contains L quotas of voters who agree on at least one party.

Proportional Justified Representation (PJR) means that, for every L ≥ 1, in every L-cohesive voter group, the parties in the union of their approval sets are allocated at least L seats.

Extended Justified Representation (EJR) means that, for every integer L ≥ 1, in every L-cohesive voter group, the parties approved by at least one voter are allocated at least L seats.

Core stability (CS) means that, for any voter group of size L*n/k voters (not necessarily cohesive), if this group deviates and constructs a smaller committee with L seats, then for at least one voter, the number of committee members from parties he approves is not larger than in the original committee.

The following example[10] illustrates the difference between CS and EJR. Suppose there are 5 parties {a, b, c, d, e}, k=16 seats, and n=16 voters with the following preferences: 4*ab, 3*bc, 1*c, 4*ad, 3*de, 1*e. Consider the committee with 8 seats to party a, 4 to party c, and 4 to party e. The numbers of representatives the voters are: 8, 4, 4, 8, 4, 4. It is not CS: consider the group of 14 voters who approve ab, bc, ad, de. They can form a committee with 4 seats to party a, 5 seats to party b, and 5 seats to party d. Now, numbers of representatives are: 9, 5, [0], 9, 5, [0], so all members of the deviating coalition are strictly happier. However, the original committee satisfies EJR. Note that the quota is 1. The largest L for which an L-cohesive group exists is L=8 (the ab and ad voters), and this group is allocated 8 seats.

• JR in rank-based elections. The concept of JR originates from an earlier concept, introduced by Michael Dummett for rank-based elections. His condition is that, for every integer L ≥ 1, for every group of size at least L*n/k, if they rank the same L candidates at the top, then these L candidates must be elected.[11]
• The JR axioms have been extended to Sequential Decision Making. [12]
• The JR axioms have been extended to participatory budgeting.
• Proportionality can be extended to degressive proportionality - assigning more weight to minorities.[13]
• Mavrov, Munagala and Shen[14] study the core and the justified representation axioms when there are constraints on the committee.
• Munagala, Shen, Wang and Wang[15] study a multiplicative approximation of the core when agents may have non-additive satisfaction functions.