Stable winner set

From electowiki


In proportional representation, a stable winner set is a requirement on a winner set:

Given a winner set of winners, another winner set containing winners blocks iff , where is the number of voters who strictly prefer to , and is the number of voters. A winner set is stable if no other set blocks it.

There can be more than one stable winner set. The group of all stable winner sets is referred to as the core.[1][2]

There are a few points which are important to note:

  1. In most cases[vague] < . The stable winner set definition then formalizes 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.
  2. The function defines what is meant by "strictly prefers". Different definitions lead to different winner sets.
  3. 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 proportional representation

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 stricter definition of proportionality than Proportionality for Solid Coalitions, the common definition for nonpartisan ranked-choice systems. A clear compromise exists as the concept justified representation, which is implied by winner set stability.

"Strictly prefers" definitions

The definition of the function 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 who all won.

The term "strictly prefer" can have various meanings:

  1. Utilitarian: 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 utility for Y. However, this definition, while simple, is problematic, because it can hinge on comparisons between "utilities" for winner sets of different sizes. User:Jameson Quinn suggested the name "sum-stable winner set" for stable winner sets using this definition.[citation needed]
  2. Subset-proportional: Another possible model is to restrict direct comparison to winner sets of the same size. Thus, when comparing sets of different sizes, we use the rule: a voter strictly prefers set X of size x over a set Y of size y, where x≤y, iff: there is no set Z of size y, where X⊆Z⊆X∪Y, such that they strictly prefer Z over Y. Using cardinal utilities, this would be equivalent to: they strictly prefer X over Y iff they strictly prefer X over any size-x subset of Y. For instance, they'd prefer the two "Greek" winners {Γ, Δ} over the three "Latin" winners {A, B, C} iff they prefer the two Greeks over any two of the Latins. Quinn suggested the name ""proportionally-stable winner set" for this kind of stable winner set.[citation needed]
  3. Top-voting: Another possible variation is "voters strictly prefer a winner set iff they receive more of their preferred candidates, counting from the top."[clarification needed]

Example in which definition of "strictly prefers" matters

Consider the following example, where each candidate letter stands for an infinite number of clones:

61% vote A5 B4 C0
39% vote A0 B4 C5

Using the utilitarian definition, 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.

Using the subset-proportional definition 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}.

With the top-voting definition of V(S,S'), the situation is the same as for subset-proportionality. These definitions might still differ in more-complex situations.

Example

Let's look at a common example. Let's say we have two voting blocs: group A and B. A makes up 79% of the population and B 21%. In a five-winner election with max score of 5 and 100 voters, Group A will score all the A candidates 5 and the B candidates 0. Group B will do the opposite.

The best winner set for group A is {A1,A2,A3,A4,A5}. This is the bloc voting answer and is not the proportional answer. So let's prove it is not stable.

S = {A1,A2,A3,A4,A5}

A blocking set is S′ = {B1}

V(S,S′) = 21 since their total utility from S is 0 and S′ is 5.

V(S,S′)/n = 21/100 = 0.21

K′/K = 1/5 = 0.2

0.21≥ 0.2 so S′ blocks S. Therefore, S is not stable.

Notably, stable winner sets focus on a voters' total utility from all candidates in a winner set, rather than the number of highest-preferred candidates they have in the set. The latter definition is closer to the traditional approximate definition of PR (voters receive as many of their highest-preferred candidates in proportion to their coalition sizes) which was meant to be used in conjunction with ordinal methods. The former definition is more relevant for cardinal methods; the difference can be seen with the example

2 to elect, scores out of 10

10 voters: A=10, B=0 C=9, D=9

10 voters: A=0, B=10, C=9, D=9

S = {A,B}

S′ = {C,D}

K=K′=2

n=20

V(S,S′) = 20 since everybody has a Utility of 10 from S and 18 from S′

V(S,S′)/n=20/20=1

K′/K = 2/2 = 1

1≥ 1 so S′ block S. Since S′ is not also blocked by S then S′ is the better solution.

It can be argued that even though {C, D} doesn't include any voter's 1st choice candidate, whereas {A,B} includes a 1st choice candidate of every voter, {C,D} is a better solution because it maximizes all voters' satisfaction with the overall set of winners. In essence, 1 point of utility is lost when comparing a voter's favorite candidate in each set but 9 points are gained for their 2nd-favorite candidate in each set. This form of analysis has been done with Condorcet PR methods before, though not while also discussing cardinal utility:

Lifting preferences from candidates to committees is achieved through what we call f-preferences. A given voter has an f-preference for one possible committee A over another, B, if the voter prefers A to B when considering in each committee only the f candidates most preferred by that voter. For example, a voter has a 1-preference for committee A over committee B if the voter's favorite candidate in committee A is preferred by that voter over the voter's favorite candidate in committee B. The voter has a 2-preference for committee A over committee B if the two favorite candidates on committee 1 are preferred over the two favorite candidates on committee B.[3]

Note that under the "voter prefers the set with more of their highest-preferred candidates" definition, {A,B} would be the stable set here. This definition makes stable sets appear to become more analogous to a Smith-efficient Condorcet PR method, such as Schulze STV.

(It is possible to create various hybrids of the two definitions. One example is a voter being considered to prefer a set that offers them slightly less utility so long as it has a certain additional number of more-preferred candidates in it. So between one set where a voter gets their favorite candidate and 10 utility and another set where the voter gets their 2nd and 3rd favorite candidates and 11 utility, the former set could be considered preferred if the definition of "strictly prefer" added at least 1 or more points of utility to the voter's preference for the former set because it had a more-preferred candidate, the favorite, in it.)

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.:[4]

Let be some integer and consider a multi-winner election with voters and seats. Let the voters be split into factions voting the following way:

  • Voters approve candidates ... .
  • factions of voters each approve a candidate nobody else approves:
  • Finally, voters each approve a candidate nobody else approves: .

Then the set is in the core even though it denies representation to everybody but the first voters. One can argue that the set is a much fairer choice.

For instance, with k=3, L = 100:

100: c1=c2=c3
99: c4
99: c5
1: c6
1: c7

The set is in the core but would arguably be more fair (and is the one elected by e.g. proportional approval voting).

Droop version

If the formula V(S,S′)/n >= K′/K is modified to instead be V(S,S′)/n > K′/(K+1), then this makes stable sets' definition of proportionality become more similar to other definitions of PR that use Droop quotas rather than Hare quotas, and begins to resemble a Condorcet PR method.[5]

This definition must use a strict inequality or it may, even in very simple cases, judge every outcome as unstable. This parallels the disadvantages of using the Hagenbach-Bischoff quota in STV.

From a cardinal perspective, the Droop stability definition may be problematic because the Range winner is no longer stable in the single-winner case. Consider the following example:

49% vote A5 B3 C0
2%  vote A5 B3 C5
49% vote A0 B3 C5

B is the Range/Utilitarian winner and is stable under Hare but not Droop.

Also, stable sets can have this "quota" computed based solely on voters who have preferences between any pair of sets that are being compared, so that in a 2-winner Approval Voting election with 67 A 33 B 10 C, the quota when looking at matchups between sets including either or both A and B is only computed off of at most the 100 voters that have preferences between them, rather than all 110. This would fix some but not all of the issues with this definition.

Using Droop quotas and this "only voters with preferences between the relevant sets are used to compute the quota" trick makes stable sets become a Smith-efficient Condorcet method in the single-winner case and appear to become a Condorcet PR method in the multiwinner case (with the core being analogous to a Smith Set of winner sets). However, if the method supports equal-rank, then a cardinal variant can be implemented by using the KP transform. Such a method would take strength of preference into account even with a Droop-based stable set.[6][dead link]

The discussion on whether to use the Droop quota or the Hare quota in the formula has already been discussed for Condorcet PR methods:

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.

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.[3]

Further reading

References

  1. Jiang, Zhihao; Munagala, Kamesh; Wang, Kangning (2020-06-22). Approximately stable committee selection. New York, NY, USA: ACM. p. 463–472. doi:10.1145/3357713.3384238.
  2. Peters, Dominik; Skowron, Piotr (2019-11-26). "Proportionality and the Limits of Welfarism". arXiv:1911.11747 [cs.GT].
  3. a b https://civs.cs.cornell.edu/proportional.html
  4. Peters, Dominik; Pierczyński, Grzegorz; Shah, Nisarg; Skowron, Piotr (2021-05-18). "Market-Based Explanations of Collective Decisions" (PDF). Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5656–5663. ISSN 2374-3468. Retrieved 2022-06-15.
  5. Aziz, Haris; Elkind, Edith; Faliszewski, Piotr; Lackner, Martin; Skowron, Piotr (2017-01-27). "The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality". arXiv:1701.08023 [cs.GT]. 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.
  6. https://forum.electionscience.org/t/the-concept-of-a-stable-winner-set/553/26