The concept of a stable winner set

I have been doing some reading from the adjacent field of participatory budgeting. I found this paper which defines something like Proportional Representation. Their semantics are a little different so I will translate the definition into something more similar to what we use.

Given a winner set S of K winners, a smaller winner set S containing K’ < K winners blocks the stability of S iff V(S,S’)/n >= K’/K. Where V(S,S’) is the number of voters who strictly prefer S’ to S and n is the number of voters. A winner set is stable if no replacement set blocks it.

The important thing is that S’ is a smaller set than S (ie K’<K) so the members of the group that prefers S’ each individually would have higher sum(score) with fewer winners.

This implies the Hare Quota Criterion which is basically what we use as a stand in for Proportional Representation since there is no universally accepted definition. The existing definitions of Proportional Representation are unclear and conflicting. Please don’t debate that in this thread. Instead read the wiki page and update it.

What I would like to discuss is if this concept of “stable winner set” is useful. Can we use winner set stability to get rid of the concept of Proportional Representation? There can be situations where there is no stable winner set. There can also be cases where there are many stable winner sets. All the stable winner sets make up what is called the “core”. It is somewhat like a Condorcet cycle were there are multiple “equally good winners”.

Also, can this be used to build a election method? ie the method that always finds the stable winner set if one exists and does something reasonable when there is no or multiple stable winner sets.

Could you make an example demonstrating this? I figure that at any point, if you took S’ and added in one of the members not in S’ but in S, then the modified S’ can only increase or maintain the voters’ sum(score).

If what you’re discussing relates to the idea of voters iteratively attempting to maximize their own satisfaction leading to some kind of equilibria or set of outcomes superior to all others (like a Smith Set), I’d suggest looking into Asset Voting or Condorcet PR methods. Specifically, in Asset, the negotiators attempt to strategically place their (vote unitary-satisfying) assets on candidates in such a way as to maximize their satisfaction with the outcome (the satisfaction can be thought of ordinally i.e. I’ll take my 1st choice above all others or cardinally i.e. I’ll instead take both my 2nd and 3rd choice); such a thing can be thought of algorithmically, and you can reach certain outcomes that dominate others. One obvious 1-winner example is:
11 A>B>C
5 B
9 C>B>A
Candidate A has the most 1st choices and presumably assets to start off with, but C and B would want to pool their assets together to instead elect B.

This can be generalized to PR as well; just identify the k candidates with the most assets at any point in negotiation and predict where the assets might pool next because of negotiators who prefer a different outcome. Making this work in a cardinal framework (i.e. negotiators score the candidates and some PR method is run on that, the outcomes and votes shifting at each point in the negotiations) seems very computationally complex.

The main reason to look at Asset as compared to other methods is that Asset inherently looks at “weight” (i.e. a negotiator can give fractions of their assets to other candidates); the assets themselves are the voting weight.

Sure, lets look at a common example lets say we have two voting blocks group A and B. B makes up 79% of the population and A 21%. In 5 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 lets 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.

The annoying thing about this definition is that that you prove things to be unstable via a counter example so it is hard to prove stability. Can we prove that {A1,A2,A3,A4,B1} does not have a set which blocks it.

This is a more restrictive definition than the Hare Quota Criterion. In the hare quota criterion it is assumed that the group who wants representation bullet voted for the blocker. In this they do not need to have bullet voted. There might be some interesting examples where K’ =4 and the set is better for greater than 4/5 due to the sum across all 4.

It is worth noting that this all assumes that score is additive or more so that Utility obeys Cauchy’s functional equation for mapping of score to utility. That is f(x+y) = F(x) +f(y). More clearly, if s_a, s_b and s_c are the score given to three candidates then s_a + s_b = s_c implies U(s_a) + U(s_b) = U(s_c). Where U() is the mapping of score to utility. This is only satisfied by linear mappings which sort of implies vote unitarity. The reweighting methods have things like U(x) = 1/x which is clearly not going to obeys Cauchy’s functional equation.

Would you want it to? I’m not sure it’s the single thing we’re after. It sounds very analogous to the Condorcet winner for single-winner methods, which I’ve read is the Nash Equilibrium for score voting. This isn’t necessarily entirely a bad thing, but on the other hand Condorcet single-winner methods aren’t exactly universally accepted as the best.

Let’s look at the example I gave here:

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

I think it’s clear that the most stable outcome would be to elect A and B, but it’s not necessarily the “best”.

The concept of PR is poorly defined in the sense that it is not really defined for systems without vote splitting. It really only makes sense for partisan voting anyway. This tends to lock people into a move towards either partisan voting and/or keeping choose one voting.

This is a good example

S = {A,B}
S’ = {C,D}
V(S,S’) = 20 since everybody has a Utility of 10 from S and 18 from S’

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.

Seeing as Condorcet (maximally strategic equilibrium) and utilitarianism (honest “altruistic” voting) are the major competing philosophies to consider, it seems worth considering some hybrids of the two i.e. if the result a Condorcet PR method would give you is ~70% as good as the result a utilitarian PR method would give you (as judged using the utilitarian method itself), then go with the Condorcet result, otherwise the utilitarian result. Or maybe if the Condorcet PR method can grade the utilitarian method’s results, then vice versa.

A conjecture is that if a set can be improved upon, it can be improved upon one member at a time. If that’s the case, then it’s almost like you can do pairwise comparisons of sets like a Condorcet PR method.

If this stable set idea works well, making a sequential version of it would be good. Something to point out - if we define a voter’s preference between sets as being based on how many of their favorite candidates they elect, rather than total utility, then this would appear to become like the traditional definition of PR.

Actually, I’d like to ask whether the stable set idea becomes Condorcet in the single-winner case under your definition? I don’t believe it does, since unless every voter prefers S’ to S, K’/K is 1 and V(S, S’)/n is less than one. Actually, every candidate is a stable winner so long as no Hare Quota prefers someone to be in the set over them, right? So the tiebreaker when multiple candidates are in the set has to be “highest utility” to make this become Score.

Sadly this is false. Suppose there are two voters and we want 4 winners. Voter 1 likes a and b, voter 2 likes c and d, and there are two candidates e and f that nobody likes. The set {a,c,e,f} has no blocking set of size 1, but there are blocking sets of size 2 ({a,b} and {c,d}) and 4 ({a,b,c,d}).

Another interesting thing is that the candidate with the maximum utility (the sum of score) is NOT always in one of the stable winner sets. This is bad news for all these Utility based sequential systems.

Wouldn’t (a,c,d,f) be a blocking set as well? 1 voter, 1/2 of all voters, prefers this to (a,c,e,f) and that’s more than 1/4th of all winners, the fraction of winners that were changed. (a,c,e,f) can’t block (acdf) back because nobody prefers e over d (unless the ab voters have a weak preference).
Perhaps we ought to address the issue of sets simultaneously blocking each other by defining the winner of a matchup as the one that gives greater utility to the voters that prefer it. That forms a nice similarity to how Condorcet methods define the strength of a candidate in a matchup as how many voters prefer them. Then, interestingly enough, you might be able to do a Condorcet method to test and resolve which stable set should win, or just to see logical properties.

Edit: One issue from a utilitarian perspective with the above proposal is that a candidate 100% would be satisfied with would be defeated by a majority’s favorite. To prevent that, I think maybe the winner sets should be ranked by “greatest average Hare Quota utility”, as this reduces to Score in the single-winner case.

No, its the size of the total set. That has size, K’=4

This concept seems rather interesting then. But aren’t there a lot of potential complications that can be fixed by forcing the final winner set to be of a certain size? It seems odd to even consider the blocking sets of size 2 when 4 winners are desired.

Yes, this is a very interesting concept. I think it can replace Proportional Representation. It is more of a generalization of the Hare Quota Criterion.

The blocking set is not a an alternative winner set. Most blocking sets are smaller than the whole winner set. For a blocking set to be of full size it needs to make everybody happier. Blocking sets prove somebody is getting less than their fair share. If somebody can be happier with a set of smaller size then they should be able to be accommodated with the larger set.

Read the paper from the original post.

1 Like

Can this be proven? It’d help a great deal with computation; you’re basically saying that if in pairwise comparisons between k-sized subsets of a winner set-size set and other k-sized sets, the k-sized set “wins”, then the members of that k-sized set beat the members of the subset of the winner set-size set. That isn’t enough to prove stability though, since all other sets may beat the k-sized set, right?

No, that is not what I am saying. That is too loose. The requirement is in the original definition. What I was saying is that if somebody is happier with a smaller set then it does not matter what what other candidates win since they can only make it better.

So this becomes Droop-proportional for K’/(K+1)?

Should “S’ = {C<D}” be “S’ = {C,D}”? I’m just checking I get the notation.

So you’re saying that CD blocks AB? That’s interesting but I also think just changing one winner from CD would block it. Say we have AC. Half the voters would be happier with the change of this one candidate. And then after that AB could block AC. So we would get a blocking cycle.

I think this case is a little bit like the Prisoner’s Dilemma where both factions could co-operate and get CD (18 points for everyone), or one could defect giving AC (19 points for one faction, 9 for the other) or both could defect giving AB (10 points for everyone). Although I’m not using the metric of stability defined here, I see AB as more intrinsically stable, with CD requiring active co-operation from factions.

Edit - Actually I think I might have got confused about how this works. For AC to block CD, half the voters would have to prefer A alone to CD, which they wouldn’t.

Take this example (approval voting, 2 to elect):

1 voter: ABC
99 voters: BC

BC is clearly the best set here. But if you have AB as the winner set, no-one actually prefers C to AB so AB’s stability isn’t blocked.

Edit - Let’s say you needed a Droop quota instead of Hare. Over 2/3 prefer the entire set BC to AB so it could then block it. But changing the numbers still messes that up:

34 voters: ABC
66 voters BC

You don’t then get the 2/3 required for BC to block AB, and you certainly don’t get 1/3 preferring B to AB (since no-one does).

Edit 2 - I think it would be better to look at the fraction that prefer one set to the other out of those voters who have any preference at all between them. That way you solve at least some of the above problems and you deal with irrelevant ballots as well.

I’d like to note the implication of this in the single-winner case, which is that the Score winner may no longer be stable. Consider the following example:
49 A5 B3 C0
2 A5 B3 C5
49 A0 B3 C5

B is the Score winner, yet half of the voters prefer either A or C over B.

Yes sorry. That is a typographical error. Ill fix it in the original post.

Correct. This is a very subtle criteria and took me a while to get my head around. It works. There are many papers in a related field about it.

That is an interesting example {C} is not preferred by anybody. {B,C} is preferred by 99% but you need 100% if K’=K. Does this example fail any other “Proportionality Criteria” for the winner set AB? This criteria is not about getting the best winner set but getting a winner set which is stable and this stability is intended to imply PR. I think in this example all three sets {A,B} , {A,C} and {BC} are stable. There can always be multiple stable sets. The group of stable sets is called the core. Selecting the best winner set from in the core is a different issue. I would think Utility would be the best metric for this.

If S={B} then K=1
For S’={A} or {C} then K’=1
K’/K=1 not 1/2. You would would need 100% of people to prefer a different winner in a single winner case. For them to prefer would imply that score is higher. This means a single member score winner is always stable.

If we’re using the formula that I proposed leads to Droop proportionality

that’s how I got 1/2.

Yup, unanimity criterion.

1 Like

OK, I missed that. I never really thought Droop proportionality was anything more than a hack. Now there is decent evidence there are issues.