Justified Representation

Justified representation (JR) is a criterion for evaluating the fairness of electoral systems in multiwinner voting, particularly in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

Definitions

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, 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.

Mathematical definitions

Below are several possible mathematical definitions of "proportional representation" under the "justified representation" rubric:

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

The definitions below consider ''cohesive'' groups of voters, that is, who approve one or more candidates in common. Formally, given an integer ''L'' ≥ 1, we say that a group is ''L-cohesive'' if it contains at least ''L''*''n''/''k'' voters, and they approve at least ''L'' candidates in common. In other words, an ''L-cohesive'' group contains ''L'' quotas and agrees on ''L'' candidates. A group is called ''L-unanimous'' if it contains at least ''L''*''n''/''k'' voters, and they approve exactly the same ''L''.

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.

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. PJR and PER were introduced and analyzed by Sanchez-Fernandez, Elkind, Lackner, Fernandez, Fisteus, Val, and Skowron.

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.

Implications

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

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

Verification

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).

Existence and Computation

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

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. 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. Another rule that is both PJR and polytime computable is the ''maximin-support'' rule.

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.
* The Method of Equal Shares (previously called "Rule X") is a polynomially-time computable rule that satisfies EJR.
* 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.

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

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 , and the votes are: . The Hare quota is 9/3 = 3. For each candidate, there is a 1-cohesive group who approves this candidate: for a, for b, for c, 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.

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. PER is also satisfied by Phragmen's rule; therefore, this rule can be used to attain both PJR and PER.

Average satisfaction

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 guarantees an average satisfaction of at least 1 - 1/''L'' + 1/(''Ln''). The same is true for every PJR committee.
* Every EJR committee guarantees an average satisfaction of at least (''L''-1)/2.

So, EJR provides a much stronger worst-case satisfaction guarantee than PJR.

Price of justified representation

The price of justified representation is the loss in the average satisfaction due to the requirement to have a justified representation. It is analogous to the price of fairness.

Adaptation to party-approval voting

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.

A voter group is called ''L-cohesive'' if it contains at least ''L''*''n''/''k'' voters, and they 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 and agrees 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 illustrates the difference between CS and EJR. Suppose there are 5 parties , ''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, 9, 5, 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.

Extensions

* 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.
* The JR axioms have been extended to participatory budgeting.
* Proportionality can be extended to ''degressive proportionality'' - assigning more weight to minorities.

References

{{Reflist

Multi-winner electoral systems