Justified representation

From Electowiki
Jump to navigation Jump to search

Justified representation is an an extension to the Hare Quota rule for multi-member approval voting systems. There are three variants: Justified representation, Extended Justified representation and Proportional Justified representation. They can be thought of as an alternative to the definition of Proportional representation for dealing with a representative systems and not a Partisan system.

Justified representation establishes requirements on when a large enough group of voters is justified to have at least one of the candidates they approve elected. Similarly, Extended Justified representation establishes requirements on when a large enough group of agents justified to have to have several of the candidates approved by them elected. Proportional Justified representation is a fix to the earlier definition of Extended Justified representation to be consistent with Perfect representation in the limiting case. The formal definitions can be found in the image. and will be reviewed later in this paper. These definitions are interesting are interesting, because voting rules that satisfy them guarantee that a large enough group of agents (even if it is a minority of the total agents) will receive at least one (for JR) or at least x (for EJR and PJR) representatives that they approve regardless of any strategic vote followed by the reminder voters.

Justified Representation.png

Justified representation[edit | edit source]

Given a matrix of approval votes A where each column represents a candidate c ∈ C and each row represents a voter v ∈ V. A winner set of candidates, W, of size |W| = k provides justified representation for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ n/k such that the voter all approve of a the same candidate not in the winner set and none of the candidates in the winner set. We say that an approval-based voting system satisfies justified representation (JR) if for every profile A = (A1, . . . , An) and every target committee size k it outputs a winning set that provides justified representation for (A, k).

Extended Justified Representation[edit | edit source]

Given a matrix of approval votes A where each column represents a candidate c ∈ C and each row represents a voter v ∈ V. A winner set of candidates, W, of size |W| = k provides provides -justified representation for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ n/k for a positive integer such that the number of approvals for the same candidate not in the winner set is greater than ℓ, but approvals for the all candidates in the winner set is less than ℓ. W provides extended justified representation (EJR) for (A, k) if it provides -JR for (A, k) for all , 1 ≤ ≤ k. We say that an approval-based voting rule satisfies -justified representation (-JR) if for every matrix A and every target committee size k it outputs a committee that provides -JR for (A, k). Finally, we say that a voting system satisfies extended justified representation (EJR) if it satisfies -JR for all ℓ, 1 ≤ ℓ ≤ k.

Proportional Justified Representation[edit | edit source]

In linked papers. Need to sort out how to do formatting

Compliant systems[edit | edit source]

System JR EJR PJR Coplexity
Proportional approval voting Yes Yes ?? NP-hard
Sequential Proportional Approval Voting Yes if seats < 6 No No in P
Ebert's Method Yes No No NP-hard
Max Phragmen Yes No Yes NP-hard
Sequential Phragmen Yes No Yes in P

Comparison[edit | edit source]

Every winner set that provides Perfect representation also provides Proportional Justified Representation [1]. In contrast, Extended Justified Representation may rule out all winner sets that provide perfect representation. [2] It is easily seen that PJR is a weaker requirement than EJR, and a stronger one than JR. A method satisfying EJR also satisfies PJR, and that a method satisfying PJR also satisfies JR.

Even though Justified representation may appear to be similar to core stability, it is, in fact, a strictly weaker condition. Indeed, the core stability condition appears to be too demanding, as no known voting system is guaranteed to produce a core stable outcome, even when the core is known to be non-empty.

Extension to Score systems[edit | edit source]

Simply applying the Kotze-Pereira transformation will allow for a generalization to Kotze-Pereira transformation Cardinal voting systems with greater than 2 gradations.

References[edit | edit source]