Justified representation: Difference between revisions
Content added Content deleted
(Add strategy susceptibility paper, replace another reference with a more direct link) |
m (Replace Skowron ref with more detailed reference, change some initial capitalized section titles) |
||
Line 12: | 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 |
==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 |
==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 |
== 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"> |
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 50: | Line 50: | ||
While [[approval voting]] is strategy-proof for voters with dichotomous preferences, 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> |
While [[approval voting]] is strategy-proof for voters with dichotomous preferences, 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== |
||
Line 56: | Line 57: | ||
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 |
==Extension to score systems== |
||
Simply applying the [[Kotze-Pereira transformation]] will allow for a generalization to |
Simply applying the [[Kotze-Pereira transformation]] will allow for a generalization to [[cardinal voting systems]] with greater than 2 gradations. |
||
==References== |
==References== |