 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(July 2021) (Learn how and when to remove this message) |
 | This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(March 2024) (Learn how and when to remove this message) |
| A jointPolitics andEconomics series |
| Social choice andelectoral systems |
|---|
 |
By results of combination By mechanism of combination By ballot type |
 Mathematics portal |
Justified representation (JR) is a criterion of fairness inmultiwinner approval voting. It can be seen as an adaptation of theproportional representation criterion to approval voting.
Proportional representation (PR) 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 theparty-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 variousapportionment methods.
In recent years, there is a growing dissatisfaction with the party system.[1] A viable alternative to party-list systems is letting citizens vote directly for candidates, usingapproval ballots. This raises a new challenge: how can we define proportional representation, when there are no pre-specified groups (parties) 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?[2] Several answers have been suggested; they are collectively known as justified representation.
Below, we denote the number of seats byk and the number of voters byn. TheHare quota isn/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 anL-cohesive group, defined as a group of voters with at least L quotas, who approve at least L candidates in common.
Ideally, we would like to require that, for every L-cohesive group, every member must have at least L representatives. This condition, calledStrong Justified Representation (SJR), might be unattainable, as shown by the following example.[3]
Example 1. Therek=3 seats and 4 candidates {a,b,c,d}. There aren=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 {ab,b,b,bc} 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 {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 committee satisfies strong JR.
There are several ways to relax the notion of strong-JR.
One way is to guarantee representation only to anL-unanimous group, defined as a voter group with at least L quotas, who approveexactly the same set of at least L candidates. This condition is calledUnanimous Justified Representation (UJR). However, L-unanimous groups are quite rare in approval voting systems, so Unanimous-JR would not be a very useful guarantee.
Remaining with L-cohesive groups, we can relax the representation guarantee as follows. Define thesatisfaction of a voter as the number of winners approved by that voter. Strong-JR requires that, in every L-cohesive group, theminimum satisfaction of a group member is at least L. Instead, we can require that theaverage satisfaction of the group members is at least L. This weaker condition is calledAverage Justified Representation (AJR).[4] 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.
We can weaken the requirement further by requiring that themaximum 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 calledExtended Justified Representation (EJR); it was introduced and analyzed by Aziz, Brill, Conitzer,Elkind, Freeman, andWalsh.[3] There is an even weaker condition, that requires EJR to hold only for L=1 (only for 1-cohesive groups); it is called Justified Representation.[3] Several known methods satisfy EJR:
A further weakening of EJR isproportional justified representation (PJR). It means that, for everyL ≥ 1, in everyL-cohesive voter group, theunion of their approval sets contains someL winners. It was introduced and analyzed by Sanchez-Fernandez,Elkind, Lackner, Fernandez, Fisteus, Val, andSkowron.[4]
The above conditions have bite only for L-cohesive groups. But L-cohesive groups may be quite rare in practice.[12] 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, iscore stability (CS).[3] It means that, for any voter group with L quotas (not necessarily cohesive), if this group deviates and constructs a smaller committee withL 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.
Peters, Pierczyński and Skowron[13] present a different weakening of cohesivity. Given two integers L andB≤L, a groupS of voters is called(L,B)-weak-cohesive if it contains at least L quotas, and there is a setC ofL candidates, such that each member of S approves at leastB candidates ofC. Note that (L,L)-weak-cohesive is equivalent to L-cohesive. A committee satisfiesFull Justified Representation (FJR) if in every (L,B)-weak-cohesive group, there is at least one members who approves some B winners. Clearly, FJR implies EJR.
Brill and Peters[14] present a different weakening of cohesivity. Given an elected committee, define a group asL-deprived if it contains at least L quotas, and in addition, at least one non-elected candidate is approved by all members. A committee satisfiesEJR+ if for every L-deprived voter group, the maximum satisfaction is at least L (at least one group member approves at least L winners); a committee satisfiesPJR+ if for every L-deprived group, the union of their approval sets contains someL winners. Clearly, EJR+ implies EJR and PJR+, and PJR+ implies PJR.
A different, unrelated property isPerfect representation (PER). It means that there is a mapping of each voter to a single winner approved by him, such that each winner represents exactlyn/k voters. While a perfect representation may not exist, we expect that, if it exists, then it will be elected by the voting rule.[4]
See also:Fully proportional representation.
The following diagram illustrates the implication relations between the various conditions: SJR implies AJR implies EJR; CS implies FJR implies EJR; and EJR+ implies EJR and PJR+. EJR implies PJR, which implies both UJR and JR. UJR and JR do not imply each other.
| SJR | → | AJR | → | EJR | → | PJR | → | UJR |
|---|---|---|---|---|---|---|---|---|
| ↑ | ↑ | → | JR | |||||
| CS | → | FJR | → | ↑ | ↑ | |||
| ↑ | ↑ | |||||||
| EJR+ | → | ↑ | → | PJR+ |
EJR+ is incomparable to CS and to FJR.[14]: Rem.2
PER considers only instances in which a perfect representation exists. Therefore, PER does not imply, nor implied by, any of the other axioms.
Given the voters' preferences and a specific committee, can we efficiently check whether it satisfies any of these axioms?[5]
Thesatisfaction of a voter, given a certain committee, is defined as the number of committee members approved by that voter. Theaverage satisfaction of a group of voters is the sum of their satisfaction levels, divided by the group size. If a voter-group isL-cohesive (that is, their size is at leastL*n/k and they approve at leastL candidates in common), then:
Proportional Approval Voting guarantees an average satisfaction larger thanL-1. It has a variant called Local-Search-PAV, that runs in polynomial time, and also guarantees average satisfaction larger thanL-1 (hence it is EJR).[5]: Thm.1,Prop.1 This guarantee is optimal: for every constantc>0, there is no rule that guarantees average satisfaction at leastL-1+c (see Example 1 above).[5]: Prop.2
Skowron[15] studies theproportionality degree of multiwinner voting rules - a lower bound on the average satisfaction of all groups of a certain size.
Freeman, Kahng and Pennock[16] adapt the average-satisfaction concept to multiwinner voting with a variable number of winners. They argue that the other JR axioms are not attractive with a variable number of winners, whereas average-satisfaction is a more robust notion. The adaptation involves the following changes:
Theprice of justified representation is the loss in the average satisfaction due to the requirement to have a justified representation. It is analogous to theprice of fairness.[8]
Bredereck, Faliszewski, Kaczmarczyk and Niedermeier[12] conducted an experimental study to check how many committees satisfy various justified representation axioms. They find that cohesive groups are rare, and therefore a large fraction of randomly selected JR committees, also satisfy PJR and EJR.
The justified-representation axioms have been adapted to various settings beyond simple committee voting.
Brill, Golz, Peters, Schmidt-Kraepelin and Wilker adapted the JR axioms toparty-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.[17]
A voter group is calledL-cohesive if it is L-large, and all group members approve at leastone party in common (in contrast to the previous setting, they need not approveL parties, since it is assumed that each party contains at leastL candidates, and all voters who approve the party, automatically approve all these candidates). In other words, anL-cohesive group containsL quotas of voters who agree on at least one party:
The following example[17] illustrates the difference between CS and EJR. Suppose there are 5 parties {a, b, c, d, e},k=16 seats, andn=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 anL-cohesive group exists isL=8 (the ab and ad voters), and this group is allocated 8 seats.
The concept of JR originates from an earlier concept, introduced byMichael Dummett for rank-based elections. His condition is that, for every integerL ≥ 1, for every group of size at leastL*n/k, if they rank the sameL candidates at the top, then these L candidates must be elected.[18]
Talmon and Page[19] extend some JR axioms from approval ballots to trichotomous (three-choice) ballots, allowing each voter to express positive, negative or neutral feelings towards each candidate. They present two classes of generalizations: stronger ("Class I") and weaker ("Class II").
They propose some voting rules tailored for trichotomous ballots, and show by simulations the extent to which their rules satisfy the adapted JR axioms.
Degressive proportionality (sometimes progressive proportionality) accords smaller groups more representatives than they areproportionally entitled to and is used by theEuropean Parliament. For example, Penrose has suggested that each group should be represented in proportion to thesquare root of its size.
The extreme of degressive proportionality isdiversity, which means that the committee should represent as many voters as possible. TheChamberlin-Courant (CC) voting rule aims to maximize diversity. These ideas are particularly appealing fordeliberative democracy, when it is important to hear as many diverse voices as possible.
On the other end,regressive proportionality means that large groups should be given above-proportional representation. The extreme of regressive proportionality isindividual excellence, which means that the committee should contain members supported by the largest number of voters.[9]: Sec.4.5 The blockapproval voting (AV) rule maximizes individual excellence.
Lackner and Skowron[20] show thatThiele's voting rules can be used to interpolate between regressive and degressive proportionality: PAV is proportional; rules in which the slope of the score function is above that of PAV satisfy regressive proportionality; and rules in which the slope of the score function is below that of PAV satisfy degressive proportionality. Moreover,[21] If the satisfaction-score of thei-th approved candidate is (1/p)i, for various values ofp, we get the entire spectrum between CC and AV.
Jaworski and Skowron[22] constructed a class of rules that generalize the sequentialPhragmén’s voting rule. Intuitively, a degressive variant is obtained by assuming that the voters who already have more representatives earn money at a slower rate than those that have fewer. Regressive proportionality is implemented by assuming that the candidates who are approved by more voters cost less than those that garnered fewer approvals.
Bei, Lu and Suksompong[23] extend the committee election model to a setting in which there is a continuum of candidates, represented by a real interval [0,c], as infair cake-cutting. The goal is to select a subset of this interval, with total length at mostk, where herek andc can be any real numbers with 0<k<c. To generalize the JR notions to this setting, they considerL-cohesive groups for any real numberL (not necessarily an integer):[23]: App.A
They consider two solutions: theleximin solution satisfies neither PJR nor EJR, but it istruthful. In contrast, the Nash rule, which maximizes the sum of log(ui), satisfies EJR and hence PJR. Note that the Nash rule can be seen as a continuous analog ofproportional approval voting, which maximizes the sum of Harmonic(ui). However, Nash is not truthful. The egalitarian ratio of both solutions isk/(n-nk+k).
Lu, Peters, Aziz, Bei and Suksompong[24] extend these definitions to settings with mixed divisible and indivisible candidates: there is a set ofm indivisible candidates, as well as a cake [0,c]. The extended definition of EJR, which allows L-cohesive groups with non-integer L, may be unattainable. They define two relaxations:
They prove that:
{{cite book}}: CS1 maint: multiple names: authors list (link)