Justified representation


Justified representation is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

Background

is an important consideration in designing electoral systems. It means that the various groups and sectors in the population should be represented in the parliament in proportion to their size. The most common system for ensuring proportional representation is the party-list system. In this system, the candidates are partitioned into parties, and each citizen votes for a single party. Each party receives a number of seats proportional to the number of citizens who voted for it. For example, for a parliament with 10 seats, if exactly 50% of the citizens vote for party A, exactly 30% vote for party B, and exactly 20% vote for party C, then proportional representation requires that the parliament contains exactly 5 candidates from party A, exactly 3 candidates from party B, and exactly 2 candidates from party C. In reality, the fractions are usually not exact, so some rounding method should be used, and this can be done by various apportionment methods.
In recent years, there is a growing dissatisfaction with the party system. A viable alternative to party-list systems is letting citizens vote directly for candidates, using approval ballots. This raises a new challenge: how can we define proportional representation, when there are no pre-specified groups that can deserve proportional representation? For example, suppose one voter approves candidate 1,2,3; another voter approves candidates 2,4,5; a third voter approves candidates 1,4. What is a reasonable definition of "proportional representation" in this case? Several answers have been suggested; they are collectively known as justified representation.

Basic concepts

Below, we denote the number of seats by k and the number of voters by n. The Hare quota is n/''k'' - the minimum number of supporters that justifies a single seat. In PR party-list systems, each voter-group of at least L quotas, who vote for the same party, is entitled to L representatives of that party.
A natural generalization of this idea is an L-cohesive group, defined as a group of voters with at least L quotas, who approve at least L candidates in common.

Justified representation properties

Ideally, we would like to require that, for every L-cohesive group, every member must have at least L representatives. This condition, called Strong Justified Representation , might be unattainable, as shown by the following example.
Example 1. There k=3 seats and 4 candidates. There are n=12 voters with approval sets: ab, b, b, bc, c, c, cd, d, d, da, a, a. Note that the Hare quota is 4. The group is 1-cohesive, as it contains 1 quota and all members approve candidate b. Strong-JR implies that candidate b must be elected. Similarly, The group is 1-cohesive, which requires to elect candidate c. Similarly, the group requires to elect d, and the group requires to elect a. So we need to elect 4 candidates, but the committee size is only 3. Therefore, no committee satisfies strong JR.

There are several ways to relax the notion of strong-JR.

Unanimous groups

One way is to guarantee representation only to an L-unanimous group, defined as a voter group with at least L quotas, who approve exactly the same set of at least L candidates. This condition is called Unanimous Justified Representation . However, L-unanimous groups are quite rare in approval voting systems, so Unanimous-JR would not be a very useful guarantee.

Cohesive groups

Remaining with L-cohesive groups, we can relax the representation guarantee as follows. Define the satisfaction of a voter as the number of winners approved by that voter. Strong-JR requires that, in every L-cohesive group, the minimum satisfaction of a group member is at least L. Instead, we can require that the average satisfaction of the group members is at least L. This weaker condition is called Average Justified Representation . Unfortunately, this condition may still be unattainable. In Example 1 above, just like Strong-JR, Average-JR requires to elect all 4 candidates, but there are only 3 seats. In every committee of size 3, the average satisfaction of some 1-cohesive group is only 1/2.
  • Proportional Approval Voting guarantees each L-cohesive group, 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. This guarantee is optimal: for every constant c>0, there is no rule that guarantees average satisfaction at least L-1+c.
  • AJR can be satisfied by fractional committees—committees in which members can serve for a fraction of a term, or receive weighted votes. In particular, the Nash rule satisfies AJR.
We can weaken the requirement further by requiring that the maximum satisfaction of a group member is at least L. In other words, in every L-cohesive group, at least one member must have L approved representatives. This condition is called Extended Justified Representation ; it was introduced and analyzed by Aziz, Brill, Conitzer, Elkind, Freeman, and Walsh. There is an even weaker condition, that requires EJR to hold only for L=1 ; it is called Justified Representation. Several known methods satisfy EJR:
  • Every committee with average-satisfaction larger than L-1 satisfies EJR. Hence, PAV and Local-Search-PAV satisfy EJR. PAV is the only one of Thiele's voting rules that satisfies EJR.
  • The method of equal shares is another polynomial-time computable rule that satisfies EJR.
  • Another polytime algorithm that guarantees EJR is EJR-Exact.
  • 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.
  • Sequential-PAV satisfies EJR only for 1-cohesive groups, and only for k ≤ 5. For k ≥ 6, it fails EJR even for 1-cohesive groups.
  • Monroe's rule satisfies EJR only for 1-cohesive groups.
  • It is co-NP-complete to check whether a given committee satisfies EJR.
A further weakening of EJR is proportional justified representation . It means that, for every L ≥ 1, in every L-cohesive voter group, the union of their approval sets contains some L winners. It was introduced and analyzed by Sanchez-Fernandez, Elkind, Lackner, Fernandez, Fisteus, Val, and Skowron.
  • EJR implies PJR, but not vice-versa. For example, consider a setting with 2k candidates and k voters. Voter i approves candidate i, as well as candidates k+1,...,2k. Note that the quota is one voter, and every L voters are an L-cohesive group. The committee 1,...,k satisfies PJR, since for every L voters, the union of their approval sets contains L winners. But it does not satisfy EJR, since every voter has only 1 approved winner. In contrast, the committee k+1,...,2k satisfies EJR.
  • PAV satisfies EJR, so it satisfies PJR too; and it is also the only weight-based approval voting rule that satisfies PJR. However, Sequential-PAV violates PJR.
  • Some of Phragmen's voting rules satisfy PJR, namely: the Leximax Phragmen - which is NP-hard to compute, and the Sequential Phragmen - which is polytime computable, and in addition, satisfies committee monotonicity.
  • 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, except when L=1.
  • Another rule that is both PJR and polytime computable is the maximin-support rule.
  • It is co-NP-complete to check whether a given committee satisfies PJR.

    Partially cohesive groups

The above conditions have bite only for L-cohesive groups. But L-cohesive groups may be quite rare in practice. The above conditions guarantee nothing at all to groups that are "almost" cohesive. This motivates the search for more robust notions of JR, that guarantee something also for partially-cohesive group.
One such notion, which is very common in cooperative game theory, is core stability. It means that, for any voter group with L quotas, 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. EJR can be seen as a weak variant of CS, in which only L-cohesive groups are allowed to deviate. EJR requires that, for any L-cohesive group, at least one member does not want to deviate, as his current satisfaction is already L, which is the maximum satisfaction possible with L representatives.
  • As of 2023, it is an open question whether a CS committee always exists.
Peters, Pierczyński and Skowron present a different weakening of cohesivity. Given two integers L and B≤''L, a group S'' of voters is called -weak-cohesive if it contains at least L quotas, and there is a set C of L candidates, such that each member of S approves at least B candidates of C. Note that -weak-cohesive is equivalent to L-cohesive. A committee satisfies Full Justified Representation if in every -weak-cohesive group, there is at least one members who approves some B winners. Clearly, FJR implies EJR.
  • FJR can always be satisfied by the Greedy Cohesive Rule ; it is open whether there are polytime algorithms satisfying FJR.
Brill and Peters present a different weakening of cohesivity. Given an elected committee, define a group as L-deprived if it contains at least L quotas, and in addition, at least one non-elected candidate is approved by all members. A committee satisfies EJR+ if for every L-deprived voter group, the maximum satisfaction is at least L ; a committee satisfies PJR+ if for every L-deprived group, the union of their approval sets contains some L winners. Clearly, EJR+ implies EJR and PJR+, and PJR+ implies PJR.
  • PAV, local-search-PAV and MES satisfy EJR+; the proofs are the same as the original proofs, as the original proofs do not use cohesivity - they only use the fact that one candidate approved by all group members is not elected.
  • There is also a polytime greedy algorithm that finds an EJR+ committee: the Greedy Justified Candidate Rule.
  • PJR+ can be verified in polynomial time by reduction to submodular optimization - in contrast to PJR which is coNP-hard to verify.
  • EJR+ can be verified in polynomial time by the following simple algorithm: For every L between 1 and k, and for every unelected candidate c: count the number of voters who approve c, and approve fewer than L winners. If the number of such voters is at least L quotas, then the committee violates EJR+.
  • EJR+ satisfies a weak form of Committee monotonicity: for all k, there is an EJR+ committee W of size k, and an unelected candidate c, such that adding c to W yields an EJR+ committee.