Justified representation

[1] A viable alternative to party-list systems is letting citizens vote directly for candidates, using approval ballots.

This condition is called Extended Justified Representation (EJR); it was introduced and analyzed by Aziz, Brill, Conitzer, Elkind, Freeman, and Walsh.

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

It was introduced and analyzed by Sanchez-Fernandez, Elkind, Lackner, Fernandez, Fisteus, Val, and Skowron.

A committee satisfies Full Justified Representation (FJR) if in every (L,B)-weak-cohesive group, there is at least one members who approves some B winners.

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.

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

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

[5]: Prop.2 Skowron[15] studies the proportionality 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.

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

Brill, Golz, Peters, Schmidt-Kraepelin and Wilker adapted the JR axioms to party-approval voting.

In other words, an L-cohesive group contains L quotas of voters who agree on at least one party: The following example[17] illustrates the difference between CS and EJR.

It is not CS: consider the group of 14 voters who approve ab, bc, ad, de.

For example, Penrose has suggested that each group should be represented in proportion to the square root of its size.

The extreme of regressive proportionality is individual excellence, which means that the committee should contain members supported by the largest number of voters.

Moreover,[21] If the satisfaction-score of the i-th approved candidate is (1/p)i, for various values of p, we get the entire spectrum between CC and AV.

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.

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 in fair cake-cutting.

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 of proportional approval voting, which maximizes the sum of Harmonic(ui).

The extended definition of EJR, which allows L-cohesive groups with non-integer L, may be unattainable.