Justified representation: Difference between revisions

From electowiki
Content added Content deleted
VisualWikitext
m (→‎Full Justified Representation: the equation bugged so I got rid of it.)
No edit summary
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Wikipedia}}
⚫
Justified representation is an an extension to the [[Quota | 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''' is a term advocated by people applying [[approval voting]] to [[proportional representation]].
⚫
'''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 is an an extension to the [[Quota | Hare]] [[Quota rule]] for multi-member approval voting systems. There are at least three variants: "justified representation", "extended justified representation" and "proportional justified representation" (though it seems more can be found on the English Wikipedia article: [[w:Justified representation]]). These alternative definitions 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 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.


[[File:Justified Representation.png|thumb]]
[[File:Justified Representation.png|thumb]]
Line 8: Line 12:
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 voters all approve of 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).
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 voters all approve of 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==
==Extended justified representation==


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 '''<math> \ell</math> -justified representation''' for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k for a positive integer <math> \ell</math> such that there are at least <math> \ell</math> candidates they all approve and they all approve fewer than <math> \ell</math> winners. W provides '''extended justified representation''' (EJR) for (A, k) if it provides <math> \ell</math>-JR for (A, k) for all <math> \ell</math>, 1 ≤ <math> \ell</math> ≤ k. We say that an approval-based voting rule satisfies '''<math> \ell</math>-justified representation''' (<math> \ell</math>-JR) if for every matrix A and every target committee size k it outputs a committee that provides <math> \ell</math>-JR for (A, k). Finally, we say that a voting system satisfies '''extended justified representation''' (EJR) if it satisfies <math> \ell</math>-JR for all ℓ, 1 ≤ ℓ ≤ k.
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 '''<math> \ell</math> -justified representation''' for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k for a positive integer <math> \ell</math> such that there are at least <math> \ell</math> candidates they all approve and they all approve fewer than <math> \ell</math> winners. W provides '''extended justified representation''' (EJR) for (A, k) if it provides <math> \ell</math>-JR for (A, k) for all <math> \ell</math>, 1 ≤ <math> \ell</math> ≤ k. We say that an approval-based voting rule satisfies '''<math> \ell</math>-justified representation''' (<math> \ell</math>-JR) if for every matrix A and every target committee size k it outputs a committee that provides <math> \ell</math>-JR for (A, k). Finally, we say that a voting system satisfies '''extended justified representation''' (EJR) if it satisfies <math> \ell</math>-JR for all ℓ, 1 ≤ ℓ ≤ k.


==Proportional Justified Representation==
==Proportional justified representation==


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 '''proportional''' '''justified representation''' for (A, k) if there does not exist a positive integer <math> \ell</math> and a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k such that there are at least <math> \ell</math> candidates they all approve and ''fewer than <math> \ell</math> winners any of them approve'' (emphasis to distinguish from extended justified representation).
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 '''proportional''' '''justified representation''' for (A, k) if there does not exist a positive integer <math> \ell</math> and a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k such that there are at least <math> \ell</math> candidates they all approve and ''fewer than <math> \ell</math> winners any of them approve'' (emphasis to distinguish from extended justified representation).


== Full Justified Representation ==
== Full justified representation ==
In approval elections, 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 '''full justified representation''' for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k for a positive integer <math> \ell</math> such that there is a subset T ⊆ C of no more than <math> \ell</math> candidates such that for some '''β''' ≤ <math> \ell</math>, each voter in N∗ approves at least '''β''' candidates in T and they all approve fewer than '''β''' winners.<ref name=":0">https://arxiv.org/abs/1911.11747</ref>
In approval elections, 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 '''full justified representation''' for (A, k) if there does not exist a subset of voters N∗ ⊆ N with |N∗| ≥ <math> \ell</math>n/k for a positive integer <math> \ell</math> such that there is a subset T ⊆ C of no more than <math> \ell</math> candidates such that for some '''β''' ≤ <math> \ell</math>, each voter in N∗ approves at least '''β''' candidates in T and they all approve fewer than '''β''' winners.<ref name=":0">{{cite arXiv | last=Peters | first=Dominik | last2=Skowron | first2=Piotr | title=Proportionality and the Limits of Welfarism | date=2019-11-26 | eprint=1911.11747 | class=cs.GT}}</ref>


In score elections, "each voter in N∗ approves at least '''β''' candidates in T" is replaced by "each voter in N∗ gives the candidates in T a total of at least '''β''' points (with scores normalized to [0,1])." <ref name=":0" />
In score elections, "each voter in N∗ approves at least '''β''' candidates in T" is replaced by "each voter in N∗ gives the candidates in T a total of at least '''β''' points (with scores normalized to [0,1])." <ref name=":0" />
Line 27: Line 31:
{| class="wikitable"
{| class="wikitable"
|-
|-
! System !! JR !! EJR !! PJR !! Coplexity
! System !! JR !! EJR !! PJR !! FJR !! Complexity
|-
|-
| [[Proportional approval voting]] || Yes|| Yes || Yes || NP-hard
| [[Proportional approval voting]] || Yes|| Yes || Yes || No || NP-hard
|-
|-
| [[w:Sequential_proportional_approval_voting|Sequential Proportional Approval Voting]] || Yes if seats < 6|| No || No || in P
| [[Sequential proportional approval voting]] || Yes if seats < 6|| No || No || No || in P
|-
|-
| [[Ebert's Method]] || Yes|| No || No || NP-hard
| [[Method of Equal Shares]] || Yes || Yes || Yes || No || in P
|-
|-
| [[Max Phragmen]] || Yes|| No || Yes || NP-hard
| [[Ebert's Method]] || Yes|| No || No || No || NP-hard
|-
|-
| [[Sequential Phragmen]] || Yes|| No || Yes|| in P
| [[Phragmen's voting rules#max-Phragmén|"max-Phragmén"]] || Yes|| No || Yes || No || NP-hard
|-
| [[Phragmen's voting rules#seq-Phragmén|Sequential Phragmen ("seq-Phragmén")]] || Yes|| No || Yes|| No || in P


|}
|}

==Implications==

While [[approval voting]] is strategyproof for voters with dichotomous preferences,{{Cn}} every method passing justified representation is susceptible to strategic voting, even in this setting.<ref>{{cite arXiv | last=Peters | first=Dominik | title=Proportionality and Strategyproofness in Multiwinner Elections|eprint=2104.08594|class=cs.GT| date=2021-04-17}}</ref>


==Comparison==
==Comparison==


Every winner set that provides [[Perfect representation]] also provides [[Justified representation | Proportional Justified Representation ]]<ref> {{Cite|authors=Luis Sánchez Fernández, University Carlos III de Madrid; Norberto Fernandez, Defense University Center at the Spanish Naval Academy; Jesus Arias Fisteus, University Carlos III de Madrid; Pablo Basanta-Val, University Carlos III de Madrid|date=|year=2016|title=Some Notes on Justified Representation|url=https://www.researchgate.net/publication/308022665_Some_Notes_on_Justified_Representation|conference=10th Multidisciplinary Workshop on Advances in Preference Handling|location=New York, USA|volume=|pages=|via=[[ResearchGate]]}} </ref>. In contrast, [[Justified representation | Extended Justified Representation ]] may rule out all winner sets that provide perfect representation. <ref>{{Cite journal|last=Aziz|first=Haris|last2=Brill|first2=Markus|last3=Conitzer|first3=Vincent|last4=Elkind|first4=Edith|last5=Freeman|first5=Rupert|last6=Walsh|first6=Toby|date=2016-09-11|title=Justified Representation in Approval-Based Committee Voting|url=http://arxiv.org/abs/1407.8269|journal=arXiv:1407.8269 [cs]}}</ref> 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.
Every winner set that provides [[Perfect representation]] also provides [[Justified representation | Proportional Justified Representation]]<ref>{{cite web | last=Fernández | first=Sánchez | last2=García | first2=Fernández | last3=Fisteus | first3=Arias | last4=Val | first4=Basanta | title=Some notes on justified representation | website=e-Archivo Principal | date=2016-06-14 | url=https://e-archivo.uc3m.es/handle/10016/25680 | access-date=2022-04-30}}</ref>. In contrast, [[Justified representation | Extended Justified Representation ]] may rule out all winner sets that provide perfect representation. <ref>{{Cite arXiv|last=Aziz|first=Haris|last2=Brill|first2=Markus|last3=Conitzer|first3=Vincent|last4=Elkind|first4=Edith|last5=Freeman|first5=Rupert|last6=Walsh|first6=Toby|date=2016-09-11|title=Justified Representation in Approval-Based Committee Voting|eprint=1407.8269|class=cs.MA}}</ref> 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 [[Stable Winner Set | 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.
Even though Justified representation may appear to be similar to [[Stable Winner Set | 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==
==Extension to score systems==


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


==References==
==References==

Latest revision as of 18:51, 28 April 2024

Wikipedia has an article on:

Justified representation is a term advocated by people applying approval voting to proportional representation.

Justified representation is an an extension to the Hare Quota rule for multi-member approval voting systems. There are at least three variants: "justified representation", "extended justified representation" and "proportional justified representation" (though it seems more can be found on the English Wikipedia article: w:Justified representation). These alternative definitions 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 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

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 voters all approve of 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

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 for a positive integer such that there are at least candidates they all approve and they all approve fewer than winners. 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

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 proportional justified representation for (A, k) if there does not exist a positive integer and a subset of voters N∗ ⊆ N with |N∗| ≥ n/k such that there are at least candidates they all approve and fewer than winners any of them approve (emphasis to distinguish from extended justified representation).

Full justified representation

In approval elections, 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 full 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 there is a subset T ⊆ C of no more than candidates such that for some β ≤ , each voter in N∗ approves at least β candidates in T and they all approve fewer than β winners.[1]

In score elections, "each voter in N∗ approves at least β candidates in T" is replaced by "each voter in N∗ gives the candidates in T a total of at least β points (with scores normalized to [0,1])." [1]

Full Justified Representation implies Extended Justified Representation since the requirements are the same for β = . [1]

Compliant systems

System JR EJR PJR FJR Complexity
Proportional approval voting Yes Yes Yes No NP-hard
Sequential proportional approval voting Yes if seats < 6 No No No in P
Method of Equal Shares Yes Yes Yes No in P
Ebert's Method Yes No No No NP-hard
"max-Phragmén" Yes No Yes No NP-hard
Sequential Phragmen ("seq-Phragmén") Yes No Yes No in P

Implications

While approval voting is strategyproof for voters with dichotomous preferences,[citation needed] every method passing justified representation is susceptible to strategic voting, even in this setting.[2]

Comparison

Every winner set that provides Perfect representation also provides Proportional Justified Representation[3]. In contrast, Extended Justified Representation may rule out all winner sets that provide perfect representation. [4] 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

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

References

  1. ↑ a b c Peters, Dominik; Skowron, Piotr (2019-11-26). "Proportionality and the Limits of Welfarism". arXiv:1911.11747 [cs.GT].
  2. ↑ Peters, Dominik (2021-04-17). "Proportionality and Strategyproofness in Multiwinner Elections". arXiv:2104.08594 [cs.GT].
  3. ↑ Fernández, Sánchez; García, Fernández; Fisteus, Arias; Val, Basanta (2016-06-14). "Some notes on justified representation". e-Archivo Principal. Retrieved 2022-04-30.
  4. ↑ Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2016-09-11). "Justified Representation in Approval-Based Committee Voting". arXiv:1407.8269 [cs.MA].
Retrieved from "https://electowiki.org/wiki/Justified_representation?oldid=18420"