Stable winner set: Difference between revisions
no edit summary
(<math>-ify definition, clean up section headings) |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
Line 1:
In proportional representation, a '''stable winner set''' (called the '''core''' in game theory parlance<ref>{{Cite journal|title=|url=https://dl.acm.org/doi/abs/10.1145/3357713.3384238|journal=}}</ref><ref>{{Cite journal|title=|url=https://arxiv.org/pdf/1911.11747.pdf|journal=}}</ref>) is a requirement on a winner set:
{{Definition| Given a winner set <math>S</math> of <math>k</math> winners, another winner set <math>S^\prime</math> containing <math>k^\prime</math> winners blocks <math>S</math> iff <math>\frac{V(S,S^\prime)}{n} \geq \frac{K^\prime}{K}</math>, where <math>V(S,S^\prime)</math> is the number of voters who strictly prefer <math>S^\prime</math> to <math>S</math>, and <math>n</math> is the number of voters.
Line 19:
Each group of voters should feel that their preferences are sufficiently respected, so that they are not incentivized to deviate and choose an alternative winner set of smaller weight. In the common scenario that we do not know beforehand the exact nature of the demographic coalitions, we adopt the robust solution concept which requires the winner set to be agnostic to any potential subset of voters deviating. This means that the requirement of a stable winner set is equivalent to but more robust than the concept of [[Proportional representation]].
This is a more strict definition than the Hare Quota Criterion which is typically what is used as a stand-in for Proportional Representation in non-partisan systems since there is no universally accepted definition. The existing definitions of [[Proportional Representation]] are unclear and conflicting. A clear
==Example==
Line 85:
A set being in the core is not sufficient for "fairness", in the sense that core sets may exist where a quota of the voters gets all its approved candidates elected, even though nobody outside of that group of voters approved of them. This can be seen in the following example by Peters ''et al.'':<ref name="Peters Pierczyński Shah Skowron 2021 pp. 5656–5663">{{cite journal | last=Peters | first=Dominik | last2=Pierczyński | first2=Grzegorz | last3=Shah | first3=Nisarg | last4=Skowron | first4=Piotr | title=Market-Based Explanations of Collective Decisions | journal=Proceedings of the AAAI Conference on Artificial Intelligence | volume=35 | issue=6 | date=2021-05-18 | issn=2374-3468 | pages=5656–5663 | url=https://www.cs.toronto.edu/~nisarg/papers/priceability.pdf | access-date=2022-06-15}}</ref>
Let L be some integer and consider a multi-winner election with <math>n=kL</math> voters and <math>k</math> seats, and let the voters be split into factions who vote the following way:
* Voters 1 ... L approve candidates <math>c_1</math> ... <math>c_k</math>.
* <math>k-1</math> factions of <math>L-1</math> voters each approve a candidate nobody else approves: <math>c_{k+1},\ldots,c_{2k-1}</math>
* finally, <math>k-1</math> voters each approve a candidate nobody else approves: <math>c_{2k},\ldots,c_{3k-2}</math>.
Then the set <math>W_1 = \{c_1,\ldots,c_k\}</math> is in the core even though it denies representation to everybody but the first <math>L</math> voters. One can argue that the set <math>W_2 = \{c_1,c_{k+1},\ldots,c_{2k-1}\}</math> is a much fairer choice.
For instance, with k=3, L = 100:
{{ballots|1=
100: c1=c2=c3
99: c4
99: c5
1: c6
1: c7}}
The set <math>c_1, c_2, c_3</math> is in the core but <math>c_1, c_4, c_5</math> would arguably be more fair (and is the one elected by e.g [[proportional approval voting]]).
== Droop version==
| |||