Stable winner set: Difference between revisions
no edit summary
(→Example: add section, will finish it later) |
No edit summary |
||
| (17 intermediate revisions by 4 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:
▲ A winner set is stable if no replacement set blocks it.
There are a few points which are important to note:
# In most cases K′ < K. This means that the definition of a stable winner set is that a subgroup of the population cannot be more happy with fewer winners given the relevant size comparison of the Ks and the group. This relates to how PR methods attempt to maximize voters' representation by electing those who sizeable subgroups each strictly prefer, rather than only those who only majorities or pluralities can agree on.
# There can be more than one stable winner set. The group of all stable winner sets is referred to as ''the core''.
#The definition of V(X,Y) must be such that, if Y is a subset of X, V(X, Y) must be 0. That is to say: it does not make sense for voters to want to "block" a winner set because of how much they like a set of candidates
#The term "strictly prefer" can have various meanings:
##In the simplest model, voters have a certain quantity of "utility" for each candidate, and they strictly prefer set X over Y iff the sum of their utility for X is greater than the sum of their utilty for Y. However, this definition, while simple, is problematic, because it can hinge on comparisons between "utilities" for winner sets of different sizes.
Line 16 ⟶ 15:
#The formula V(S,S′)/n >= K′/K is analogous to a (Hare) quota; formulas analogous to other quotas may be used instead.
==Relation to
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 70 ⟶ 69:
=== Example in which definition of "strictly prefers" matters===
In the above example, all the definitions of "strictly prefers" lead to the same winner sets being stable. But consider the following example (as above, each candidate letter stands for an unlimited group of clones):
61% vote A5 B4 C0
== Droop Version==▼
39% vote A0 B4 C5
Under the above definition 4.1. of V(S,S'), the winner set {B, B, B, B, B} is strictly preferred by all voters over any other set of size 5 or less, so it is the unique stable winner set.
Under the above definition 4.2. of V(S,S'), the winner set {B, B, B, B, B} is not stable. For instance, the set {A, A, A} blocks it (or any other set without at least three As), because the first group of voters — over 3/5 of all voters — prefers {A, A, A} over any 3 candidates from {B, B, B, B, B}. Similarly, any set without at least one C is blocked by {C} because of the second group of voters. Thus, the only stable sets under this definition are {A, A, A, A, C}, {A, A, A, B, C}, and {A, A, A, C, C}.
Under the above definition 4.3. of V(S,S'), the situation is the same as for definition 4.2. (These definitions might still differ in more-complex situations. Since definition 4.3. has stronger criteria for "strictly prefer", the set of stable winner sets under 4.2. will be a non-strict subset of that for 4.3.)
[[User:Jameson Quinn|Jameson Quinn]] has suggested the terms "sum-stable winner set" and "proportionally-stable winner set" for the stable winner sets under definitions 4.1 and 4.2 respectively.
==Limitations==
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]]).
If the formula V(S,S′)/n >= K′/K is modified to instead be V(S,S′)/n >= K′/'''(K+1),''' (it may be appropriate to make it only a > rather than an >=, for reasons to be explained below), then this makes stable sets' definition of proportionality become more similar to other definitions of PR that use Droop [[Quota]]s (or more specifically, Hagenbach-Bischoff Quotas) rather than Hare [[Quota]]s, and begins to resemble a Condorcet PR method. <ref>{{Cite web|url=https://arxiv.org/abs/1701.08023|title=The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=|quote=A size-k committee is locally stable in an election with n voters if there is no candidate c and no group of more than n/(k+1) voters such that each voter in this group prefers c to each committee member.}}</ref>
Line 91 ⟶ 123:
Interestingly, the two varying modes of deciding which set a voter prefers in each pairwise matchup (evaluate a voter's preference between sets as based either on either: first whether they have a more-preferred candidate in one set, and then second more of their more-preferred candidates in that set, or: which set gives them more utility), as well as the discussion over whether to use Droop Quotas vs. Hare Quotas within the formula, has already been discussed before for Condorcet PR methods:<blockquote>We deferred the question of how to decide whether a voter prefers one set of ''f'' candidates over another, where a set of candidates is a subset of a committee. In [[Proportional representation]] mode, there is only one difference from the voter's perspective. The voting algorithm decides which of two committees would be preferred by a candidate using one of two criteria, ''combined weights'' or ''best candidate''.</blockquote><blockquote>The factor (''k''+1) may be surprising in the condition for proportional validity, but it actually agrees with proportional representation election methods developed elsewhere; it is analogous to the Droop quota used by many STV election methods.<ref name=":0" /></blockquote>
==Further
* [https://arxiv.org/abs/1910.14008 Approximately Stable Committee Selection]
| |||