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.

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 (SJR), might be unattainable, as shown by the following example.

Example 1. There k=3 seats and 4 candidates {a,b,c,d}. 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 {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.

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 (UJR). 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 (AJR) or average fair share (AFS). 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 (note that in that paper AJR is called AFS).

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 (EJR); 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 (only for 1-cohesive groups); it is called justified representation. Several known methods satisfy EJR:

• Every committee with average-satisfaction larger than L-1 satisfies EJR (by the pigeonhole principle). 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 (PJR). 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 (CS). It means that, for any voter group with L quotas (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. 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 (L,B)-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 (L,L)-weak-cohesive is equivalent to L-cohesive. A committee satisfies full justified representation (FJR) if in every (L,B)-weak-cohesive group, there is at least one member who approves some B winners. Clearly, FJR implies EJR.

• FJR can always be satisfied by the greedy cohesive rule (which is not polytime); 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 (at least one group member approves at least L winners); 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. PJR+ is the approval-based specialisation of a more general concept called Inclusion Proportionality for Solid Coalitions (IPSC) that was introduced by Aziz and Lee.

• 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 (of size k+1).

Perfect representation

A different, unrelated property is perfect representation (PER). It 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.

• 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, and by the leximax-Phragmen's rule; but it is violated by greedy Monroe, sequential PAV, and PAV.

Implications

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.

EJR+ is incomparable to CS and to FJR.

PER considers only instances in which a perfect representation exists. Therefore, PER does not imply, nor implied by, any of the other 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).

Average satisfaction – proportionality degree

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. Proof sketch: EJR guarantees at least one member in an L-cohesive group, a satisfaction of at least L. Once this member is removed, the remaining group is at least (L-1)-cohesive, so at least one remaining member is guaranteed a satisfaction of least L-1. Proceeding this way gives an average satisfaction of L+(L-1)+..., which is larger than (L-1)/2.
• So, EJR provides a much stronger worst-case satisfaction guarantee than PJR.
• 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). This guarantee is optimal: for every constant c>0, there is no rule that guarantees average satisfaction at least L-1+c (see example 1 above).

Skowron studies the proportionality degree of multiwinner voting rules - a lower bound on the average satisfaction of all groups of a certain size:

• Sequential (min-max) Phragmen: (L-1)/2;
• Global optimization (min-max) Phragmen: 1;
• Sequential PAV: ~0.7L-1 for k<=200;
• PAV: L-1+o(1/k)

Variable number of winners

Freeman, Kahng and Pennock 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:

• Each voter gains satisfaction, not only from an elected candidate that he approves, but also from a non-elected candidate that he does not approve (this makes the problem similar to multi-issue voting, where each candidate is a binary issue).
• A group is L-large if it contains at least L*n/m voters (where m is the total number of candidates), and L-cohesive if in addition the group members agree on the placement of at least L candidates (that is: the intersection of A_i plus the intersection of C\A_i is at least L).
• A committee is r-AS (r-average-satisfaction) if for every L-cohesive group, the average of the members' satisfaction is at least r*L. The JR, PJR and EJR conditions are generalized in a similar way.
• The PAV rule chooses a committee that maximizes the sum of harmonic(sat_i), where sat_i is the satisfaction of voter i. The sequential Phragmen rule and the method of equal shares divide the load of each elected candidate among the voters who approve it, and the load of each unelected candidate among the voters who do not approve it. All these rules satisfy PJR. MES violates EJR; it is not known whether the other two satisfy it.
• A deterministic rule cannot guarantee r-AS for r = (m-1)/m+epsilon, for any epsilon>0. PAV, Phragmen and MES cannot guarantee r-AS for r = 1/2+epsilon. But there is a randomized rule that satisfies (29/32)-AS.

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.

JR in temporal voting

Temporal voting, also called sequential voting, is a setting in which the same set of n voters conducts several consecutive single-winner votes. In PV, the number of rounds, as well as the candidates in each round, are not known in advance; in TV, they are known in advance. In both cases, the satisfaction of a voter is the number of rounds in which the winner is approved by them. The role played by the committee size in multiwinner voting is played here by the number of rounds, so that after every T rounds, the quota is n/T. A rule is called offline if all ballots are known in advance, semi-online if only the number of rounds is known in advance, and fully-online if even the number of rounds is not known in advance; the latter setting is also called Perpetual voting (PV).

Bulteau, Hazon, Page, Rosenfeld and Talmon adapted JR and PJR to this setting. They distinguish two settings.

• A static setting, in which each voter submits the same ballot in every round. This setting is similar but not identical to committee voting. The differences are (a) the number of rounds is not fixed in advance, whereas the committee size is. (b) It is possible to select the same candidate in different rounds, whereas in a committee it is not. The static setting is equivalent to approval based apportionment, where voters submit approval ballots to parties rather than to individual candidates; in this setting, it is known that an EJR and committee-monotone rule exists.
• A dynamic setting, in which ballots may change over time. For the dynamic setting, they propose two adaptations of cohesiveness: all-periods-intersection means that a group is considered cohesive only if all group members agree on some alternative in all rounds; some-periods-intersection means that a group is considered cohesive if all group members agree on some alternative in some of the rounds. Accordingly, they present two adaptations of JR and PJR.

Here are the definitions for PJR:

• All-periods-intersection PJR: for every L, for every group of at least Ln/T voters who agree in all T rounds, there are at least L rounds in which some voter in the group approves the outcome.
• Some-periods-intersection PJR: for every L and t, for every group of at least Ln/t voters who agree in some t rounds, there are at least L rounds in which some voter in the group approves the outcome.

The former condition is a special case of the latter condition for t=T. They show that the JR variants can be satisfied in polynomial time by greedy adaptations of Greedy Chamberlin–Courant, and that the PJR variants are always satisfiable by algorithms that are fixed-parameter tractable with respect to the number of voters; they conjecture that no polynomial-time algorithm satisfies the dynamic PJR variants unless P = NP. They also report an experiment with 190 participants, in which more than half of the participants' choices agreed with one of the fairness notions captured by their framework, while the majority also expressed a preference for outcomes maximizing social welfare.

Chandak, Goel and Peters renamed the all-periods-intersection axiom as weak PJR and the some-periods-intersection axioms as PJR, and introduced corresponding adaptations of EJR and weak EJR. Their results include:

• The sequential Phragmén rule, which is fully-online, satisfies PJR (hence also weak PJR); this refutes the conjecture. However, it fails weak EJR (hence also EJR).
• The method of equal shares, run in a semi-online fashion in which each round costs n/T, satisfies weak EJR (hence also weak PJR and weak JR), but fails JR (hence also PJR and EJR); when it does not run out of budget before the last round, its outcome does satisfy PJR.
• PAV and its polynomial-time local-search variant, which are offline, satisfy EJR and hence all the other axioms.
• An online rule satisfying weak EJR would yield a multiwinner rule satisfying both EJR and committee monotonicity, which is a known open problem.
• No semi-online rule (hence also no online rule) satisfies EJR.
• Several natural strengthenings are unattainable: if the size required of a deserving group is lowered by any constant, or if a group is required to agree in only L rounds rather than in all rounds in order to deserve L rounds, then no outcome satisfies the resulting axiom on some instances.

Lackner and Maly study weaker proportionality requirements that are meaningful for online (perpetual) rules. They call a group closed if its members submit identical ballots in every round and no voter outside the group approves any alternative that they approve, and they require the satisfaction of each member of a closed group to be at least (lower quota) or at most (upper quota) its proportional share, in every prefix of the decision sequence. They prove that no rule whose voter weights depend only on the number of rounds a voter has won can satisfy either axiom; that a perpetual adaptation of Phragmén's rule satisfies lower quota, via a perpetual version of priceability; that perpetual consensus satisfies upper quota; and that perpetual priceability and upper quota are mutually incompatible. Lower quota for closed groups is implied by weak PJR.

Phillips, Elkind, Teh and Wąs organize these notions into a hierarchy with three levels:

• Weak axioms, which constrain only groups agreeing in all rounds (like weak JR, weak PJR and weak EJR);
• Intermediate axioms (like JR, PJR and EJR);
• Strong axioms, which grant a group agreeing in t rounds the guarantee it would receive if it agreed throughout.

They add temporal analogues of EJR+, FJR, FPJR and the core. They show that:

• Every strong axiom, including the weakest of them strong JR, fails on some instances in which each voter approves exactly one alternative per round; this is because a group may deserve representation on the strength of agreement in a few heavily contested rounds.
• A temporal EJR+ defined in terms of the number of voters of a group that agree in a given round, rather than the size of the group, retains the three attractive features of its multiwinner counterpart: it implies EJR, it can be verified in polynomial time, and an outcome satisfying it can be computed in polynomial time by the local-search variant of PAV.
• An outcome satisfying temporal FJR always exists and can be found by a modification of the Greedy Cohesive Rule, although no polynomial-time algorithm is known.
• Strong FPJR can be attained by serial dictatorship when every voter approves at least one alternative in every round and the number of voters divides the number of rounds; it is incomparable with EJR.
• Whether an outcome in the temporal core always exists is open, as it is in the multiwinner setting.

Approximate justified representation

Justified representation might be incompatible with other desirable properties. Hence, it can be relaxed as follows.

An A-L-cohesive group is as a group of voters with at least A*L quotas, who approve at least L candidates in common. A committee satisfies A-EJR if in every A-L-cohesive group, the maximum satisfaction is at least L.

Empirical study

Bredereck, Faliszewski, Kaczmarczyk and Niedermeier 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.

JR in participatory budgeting

Combinatorial participatory budgeting (PB) is a generalization of multiwinner voting in which each candidate project c may have a different cost cost(c), and the goal is to choose a subset of candidates with a total cost at most a fixed budget B. Each group S deserves a fraction of the total budget proportional to its size, that is, B*|S|/n. Some adaptations of the JR axioms were developed by Aziz, Lee and Talmon. Peters, Pierczyński and Skowron presented the following adaptations.

• For PB with approval preferences: given a set of projects T, a group S of voters is called T-cohesive if [a] their budget share B*|S|/n is at least cost(T), and [b] all members of S approve all projects in T. EJR requires that in each T-cohesive group, at least one member approves at least |T| winning projects (for cardinality utilities), or at least one member approves winning projects with total cost at least cost(T) (for cost utilities).
• For the more general setting of additive preferences: given a set of projects T and a threshold function U on the set of projects, a group S of voters is called (U,T)-cohesive if [a] their budget share B*|S|/n is at least cost(T), and [b] all members i in S agree that all projects c in T are valuable, u_i(c) >= U(c). EJR requires that in each (U,T)-cohesive group, at least one member derives from the winning budget a utility of at least U(T). An EJR budget allocation always exists, and can be found by an exponential algorithm they call greedy cohesive rule. However, it cannot be computed in polynomial time, by reduction from the knapsack problem.
• EJR up to one project (EJR1) requires that, in each (U,T)-cohesive group, there is a voter for whom the winning budget satisfies one of the following: either [a] the utility is at least U(T), or [b] there is a project c in T such that, if c is added to the winning committee, the utility is strictly larger than U(T). Due to the strict inequality, EJR1 reduces to EJR in for approval preferences. An appropriate adaptation of the method of equal shares, that runs in polynomial time,satisfies EJR1 in the general PB model with additive utilities (hence it satisfies EJR in the special case of approval preferences).

Papasotiropoulos, Pishbin, Skibski, Skowron and Was define a fractional variant of EJR, which they call fractional EJR. Given a set T of projects, a fraction function f from the projects to [0,1], and a utility threshold function U on the projects, a group S of voters is called (T,f,U)-cohesive if [a] their budget share B*|S|/n is at least the total cost of the given fractions, ${\displaystyle B\cdot (|S|/n)\ge \sum _{c\in T}f(c)\cdot cost(c)}$, and [b] all members i in S agree that all fractions of projects c in T are valuable, ${\displaystyle f(c)\cdot u_i(p)\ge U(c)}$. Fractional EJR requires that, in every (T,f,U)-cohesive group, at least one voter derives from the (possibly fractional) budget allocation, a utility of at least U(T).

Adaptations

The justified-representation axioms have been adapted to various settings beyond simple committee voting.

Party-approval voting

Brill, Golz, Peters, Schmidt-Kraepelin and Wilker adapted the JR axioms 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 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:

• 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.
• 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.
• 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 {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.

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.

Trichotomous ballots

Talmon and Page 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 and regressive proportionality

Degressive proportionality (sometimes progressive proportionality) accords smaller groups more representatives than they are proportionally entitled to and is used by the European Parliament. For example, Penrose has suggested that each group should be represented in proportion to the square root of its size.

The extreme of degressive proportionality is diversity, which means that the committee should represent as many voters as possible. The Chamberlin–Courant (CC) voting rule aims to maximize diversity. These ideas are particularly appealing for deliberative 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 is individual excellence, which means that the committee should contain members supported by the largest number of voters. The block approval voting (AV) rule maximizes individual excellence.

Lackner and Skowron show that Thiele'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, If the satisfaction-score of the i-th approved candidate is (1/p)ⁱ, for various values of p, we get the entire spectrum between CC and AV.

Jaworski and Skowron constructed a class of rules that generalize the sequential Phragmé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.

Divisible candidates

The committee election model has been extended to a setting in which, instead of a finite set of candidates, there is a continuumof candidates, represented by a real interval [0,c]. The goal is to select a subset of this interval, with total length at most k, where here k and c can be any real numbers with 0<k<c. The PJR, EJR and AJR axioms can be extended to this setting by considering L-cohesive groups for any real number L>0. The max Nash welfare rule (which can be seen as the continuous analogue of proportional approval voting) satisfies AJR, hence also EJR and PJR.

Lu, Peters, Aziz, Bei and Suksompong extend these definitions to settings with mixed divisible and indivisible candidates: there is a set of m 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:

• EJR-M guarantees to any L-cohesive group, when there is a set of resources of total size exactly L, that at least one group member receives utility at least L. EJR-M reduces to EJR both in settings with only indivisible candidates and in settings with only a divisible candidate.
• EJR-β (for any real number β) guarantees to any L-cohesive group, that at least one group member receives utility larger than L-β.

They prove that:

• For any β<1, EJR-β may be unattainable.
• The Nash rule does not satisfy EJR-β for any β.
• A rule called greedy-EJR satisfies EJR-M, but runs in exponential time, and has proportionality degree ~L/2.
• A generalization of equal shares satisfies EJR-1 but not EJR-M, but satisfies EJR for divisible-only instances, and has proportionality degree ~L/2.
• A generalization of PAV, using an analytic extension to the harmonic series, satisfies EJR-1 but not EJR-M, does not satisfy EJR for divisible-only instances, and has proportionality degree larger than L-1.

Other adaptations

• Brill, Laslier and Skowron adapted JR to degressive proportionality - assigning more weight to minorities.
• Mavrov, Munagala and Shen study the core and the JR axioms when there are constraints on the committee.
• Munagala, Shen, Wang and Wang study a multiplicative approximation of the core when agents may have non-additive satisfaction functions.