Some extensions of stable winner sets (and discussion on Justified Representation)

I’ll leave the discussion on Justified Representation (covered in this paper https://arxiv.org/abs/1407.8269) to others.

Continuing the discussion from:

While it appears there will always be stable winner sets when using the Hare stability definition (V(S,S’)/n >= K’/K), there may not be when using the Droop stability definition (V(S,S’)/n >= K’/(K + 1). (I’d conjecture this is related to how you can have Condorcet cycles in both single-winner and multi-winner cases of Condorcet PR, where majorities prefer some candidate or set of candidates over a set that is currently pairwise-beating another set.)

1-winner example with no stable set under Droop stability: 1 voter likes Candidate A, and 1 voter likes Candidate B. Under Droop stability (really Hagenbach-Bischoff stability) no set is stable, because half of the voters prefer A over B yet also B over A.

So in order to keep the usefulness of the stability concept even in situations where no set is stable, I suggest using the following “generalized stable winner set” definition: “the core is the smallest set of winner sets that block the stability of all other sets”. A voting method which always selects from the core might be considered a “generalized-stable” method and passes the generalized stable winner set criterion. In the above example, {A} and {B} are both in the core, since they both block the stability of all other sets (“all other” being an empty set of winner sets) and each other. Note that this definition is analogous to the Smith Set (block = beat) and thus we can make a slightly different definition which is analagous to the Schwartz Set: “the core is the smallest set of winner sets that are unblocked by all other sets.”

I think that these definitions either exactly or very closely reduce to the original stable Hare winner set definition, just as the Schwartz and Smith Set always reduce to the Condorcet winner when one exists (or weak Condorcet winners in general actually I’m not sure about weak CWs). They basically capture the fact that even if no one winner set is stable, some sets of winner sets are “more stable” than others, and are thus still to be considered better.

(In fact, I think these generalized definitions really do become some form of the Smith and Schwartz Set if you apply the stable set concept to Condorcet/Condorcet PR methods.)

Finally got around to reading this. This is actually an amazing paper. It gives a more formal definition on Hare Quota Criterion with Justified Representation. They then extend it to groups which deserve multiple candidates with extended justified representation.

The only issue is that it is only defined for Approval Ballots. I think it would be pretty simple to extend to score. The KP-transoform interpretation where you interpret each score level as a new ballot seems natural. Then you would be talking about the size of groups in terms of score. Instead of in terms of whole voters.

They reference the work of somebody else who make a modification to make it more consistent with Perfect Representation in the limiting case. This property was called proportional justified representation and they give a link to the paper. There is a lot of work in this area from these authors.

They also prove that there is a Sequential Phragmen method which satisfies this. @Toby_Pereira this is you area of expertise. https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14757

1 Like

I have made a page. https://electowiki.org/wiki/Justified_representation

If anybody knows how to do the math formatting to get this into the wiki it would help make it more digestible for the general public.

I’m going through some of this stuff now. I haven’t read the final paper yet (with sequential Phragmen) but I’ll put my thoughts so far.

I don’t read mathematical notation very well so I don’t have as good a grasp of some of these concepts as I would like, but I’ve tried to understand the basic definitions and find the English language definitions in the text. Justified representation:

This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee.

The logic behind this definition is that if k candidates are to be selected, then, intuitively, each group of n/k voters “deserves” a representative. Therefore, a set of n/k voters that have at least one candidate in common should not be completely unrepresented. To start with this paper:

Extended justified representation:

The definition of EJR interprets “a group N* deserves at least ℓ representatives” as “at least one voter in N* gets ℓ representatives”.

It basically generalises justified representation for when a group has two or more Hare quotas, rather than just the one in justified representation.

These seem quite weak criteria as they only require that one voter in the group gets any candidates elected (rather than electing a candidate that actually has a Hare quota of support). The paper suggests stronger criteria that are impossible to satisfy though.

Then moving on to this paper:

Perfect representation:

Consider a ballot profile A = (A1, . . . , An) over a candidate set C, and a target committee size k, k ≤ |C|. We consider only ballot profiles for which a positive integer m exists such that n = mk. We say that a set of candidates W, |W| = k, provides perfect representation (PR) if it is possible to partition the set of agents in k equal size disjoint subsets N1, . . . , Nk (N = N1 ∪ · · · ∪ Nk, Ni ∩ Nj = ∅ for i, j = 1, . . . , k, i 6= j, and |Ni| = m for i = 1, . . . , k), such that it is possible to assign each candidate w in W to one (and only one) subset Ni so that for all pairs (w, Ni) all the agents in Ni approve their assigned candidate w. We say that an approval-based voting rule is a PR voting rule if for every profile A = (A1, . . . , An) and every target committee size k it does not output any winning set of candidates W that does not provide PR for (A, k) if at least one set of candidates W0 that provides PR for (A, k) exists.

I couldn’t see a nice English explanation, but it seems to me that for a voting method to pass this, it would have to be possible to (where possible) assign each candidate to one particular group of voters where every voter in the group has approved the candidate and where all the groups of voters are the same size. Obviously not every election scenario would allow the candidates and voters to be divided up so neatly, but in cases where this is possible, a method passing perfect representation must provide a result where it is possible to do this.

Proportional justified representation:

From my understanding this is like extended justified representation except that instead of saying that one voter in the group needs to have approved the requisite number of candidates, these candidates can be approved by different voters in the group.

Anyway, apart from perfect representation all these criteria seem oddly weak in that they only make demands about a single voter, or in proportional justified representation just one voter per candidate that the group “deserves”.

It is also said that PAV (as in Thiele) passes justified representation, extended justified representation and proportional justified representation. But this seems strange given that it definitely isn’t proportional by a reasonable definition. As I pointed out here:

So I can’t see how this would pass extended justified representation or proportional justified representation. Maybe someone who understands the papers and definitions better could clarify.

Finally, I’m not sure that perfect representation is necessarily desirable. Take the following example:

2 to elect

100 voters: ABC
100 voters: ABD
1 voter: C
1 voter: D

I think perfect representation would demand the election of CD, whereas I would prefer AB.

Edit - Actually that Thiele example might be wrong. I’ll come back to this later. And I’ll post in the thread it came from too.

Edit 2 - The correct result actually gives a higher satisfaction score as can be seen by comparing this with this. So maybe it does pass those criteria.

Glad I was not the only one. Have a look at the electowiki page I made. I put some of it in more familiar semantics

I thought of it that way at first too but you are just getting confused by the poor clarity of the definition. They define the group by the fact that everybody in the group holds some properties. Instead of just saying that they worded it as "nobody in the group can fail’ the properties.

Yea those are useless.

I made a page for Perfect Representation too. It is important to note that this is not a general thing but a specific result. When everybody bullet votes and all groups make exactly one hare quota. It is sort of the limiting case. The argument is that EJR does not produce perfect representation when it exists so it is not a good criteria. Then they produce a similar metric (PJR) which will get Perfect Representation in that special case. PJR is a fix to EJR which means EJR is sort of broken.

Taking into account what I said above you will see that they are not. In fact if you look at the table I added to the electowiki page there are very few systems which pass them. It is only slightly weaker than requiring a Stable Winner Set which no known system can fulfil.

I can’t be sure what they mean by the Union in the definition of PJR. I think I have the interpretation of the Intersection correct for EJR but I do not think that it is the criteria we would want. I was actually thinking of writing to the authors to see if they could be a bit more clear and put it in terms of aritmetic operations on an approval matrix. I would also want to ask them how they would generalize this to score. The KP transform can be used of course but I am not sure that it makes sense in this specific context. I can CC you when I email them if you want. I am waiting to see if somebody can decode their notation so I do not have to write to them saying I do not understand.

It still seems a bit strange because if there is a group that vote together on certain candidates, there might be some of these voters that also vote for other candidates with very little support. E.g.

99 voters: A
1 voter: AB

These 100 voters might make a Hare quota, and wouldn’t justified representation be passed if B is elected?

Sure, that would be good.

If B is elected then that voter would be satisfied in the B voter group.

The Justified Representation would be for the group of 99. Are you getting at the concept of surplus handling? Like if the B group is almost 2 quotas and so the AB voter is really only effectively partially satisfied?

I’m not sure I do get this. If you had to define justified representation in as close to English as possible (so no notation) how would you do it? My understanding is that if a Hare quota of voters all approve a particular candidate then at least one voter in that group must have a candidate that they approved elected.

I can understand that they can’t say that if a Hare group of voters approve a particular candidate then that candidate will be elected, because it’s possible for a greater number of candidates than there are seats available to get a Hare quota of approvals. But if we go back to my example:

99 voters: A
1 voter: AB

This wasn’t meant to be all the votes, but just a sample of them. Let’s say that a Hare quota is exactly 100 votes. So all those 100 voters in the sample are part of the group, including the AB voter. So electing B would satisfy this. Of course, if a Hare quota was 99, then electing B wouldn’t be enough. There would still be a whole Hare quota of voters approving a particular candidate, none of whom would get a representative, so A would have to be elected.

I’ve finally got round to reading through this paper. It seems that what they call var-Phragmen is what we call Ebert’s method. I wonder if Phragmen himself even considered the method before settling on the one he did, so it might not be remotely new at all.

Anyway, the criteria they look at are quite interesting. Thiele PAV passes justified representation and proportional justified representation. Max Phragmen passes these and perfect representation as well.

However, these criteria do require voters all voting as a block, and there are problems when they overlap. If we look at the examples here I would say that none of these methods actually passes proportional representation at a more basic level. I would say that it is a necessary condition (but not sufficient) that for v voters, assuming that each voter approves enough candidates, then if v candidates are elected, then it should be possible to assign each voter to one candidate where the voter has approved that candidate (although they may obviously also have approved others that they haven’t been assigned to). Obviously there will never be the same number of voters and candidates, but if a voting method doesn’t do this when pressed then it can still cause problems in other cases. The examples linked to show failures for each method.

This is different from perfect representation, where it requires that equal-sized groups of voters can be assigned to each candidate where the ballots make it possible. It would demand that CD be elected in the following case:

2 to elect

100 voters: ABC
100 voters: ABD
1 voter: C
1 voter: D

If A, B and C are parties instead of individual candidates, my criterion would demand the election of at least one C and one D candidate only if there are at least 202 seats.

Phragmen methods with optimal approval removal do pass this criterion I think.

Edit - I always find it interesting that the academics and the internet forum posters are generally in a slightly different position, although I think we are actually at an advantage because we’re more likely to read their stuff than them ours, so we can have a more complete knowledge. I’m not sure if they’re aware of the limitations of their criteria.

Yes, was this how Phragmen originally formulated it?

No it would not. Perfect representation is only defined in the specific limiting case. It does not apply in other examples like this one.

Did you understand the notation in PJR? I am still confused by it.

What were your thoughts on Sequential Phragmen? It does the balancing which you say is the source of nonmonotonicity in Phragmen methods. Well, it does A balancing.

Not as far as I know, but I was just thinking that it’s possible that he considered various ways of achieving proportionality from loads. rangevoting.org describes what I think is the original formulation. But it has a step that Warren says is peculiar (and it does seem to be peculiar) -

Immediately after a candidate is elected, we then redistribute the costs among his approvers, to make their ballots each have equal costs.

I think most people would take Phragmen to be max-Phragmen rather than using that odd step.

Is that step what you mean by the balancing? In any case I don’t think it’s a good step as a voter who has just approved one currently-elected candidate could suddenly find themselves with the same load as a block of voters who have five. But the seq-Phragmen mentioned in the paper looks to be just sequential max-Phragmen, and that would still have the same failure of monotonicity.

From earlier in the thread:

I don’t think this is correct though, especially as the example in the paper is not a case of bullet voting.

Perfect representation (PR)

Consider the following example. Let k = 4. We have 6
candidates, C = {c1, . . . , c6}. 8 agents submit the following approval ballots. A1 = {c1}, A2 = {c2}, A3 = {c3},
A4 = {c4}, A5 = {c1, c5, c6}, A6 = {c2, c5, c6}, A7 =
{c3, c5, c6} and A8 = {c4, c5, c6}. Now consider the following possible set of winners W = {c1, c2, c3, c4}. Clearly
W provides PR because we can partition the set of agents
in 4 disjoint subsets of size 2 (N1 = {1, 5}, N2 = {2, 6},
N3 = {3, 7} and N4 = {4, 8}) such that it is possible to assign each candidate in W to one (and only one) subset so that
all the agents approve their assigned candidate (assign c1 to
N1, c2 to N2, c3 to N3 and c4 to N4).

So I do think my example above is a case where passing perfect representation is not necessarily desirable.

Not exactly, but I try and get an understanding of the criteria through the text as well. But basically, it seems to me the EJR requires that one voter in the group gets the correct number of representatives, whereas PJR makes the lesser requirement that these representatives do not all need to have been approved by one specific voter, but can be approved by different voters in the group.

We believe that another argument for PJR is that it captures better the idea of when a large enough group of agents
should be allocated several representatives, because for PJR
it is enough that the required number of representatives is
achieved counting all the candidates that are approved at least
by one agent in the group, while EJR requires one agent in the
group to approve the required number of representatives in
the winning set. Moreover, we believe that this requirement
that “one agent in the group approves the required number of
representatives in the winning set” is unjustified: one should
expect that each candidate in the winning set should represent
many agents, and not that an agent is represented by several
candidates. Of course, when a group of agents agree in approving the same set of candidates, and the group is large
enough to deserve several representatives, both PJR and EJR
require that each of the agents in such group is represented
by several (and the same) representatives.

Justified representation is for a single Hare quota, and looking at this discussion of EJR and PJR confirms to me more that it only requires a single voter to be represented - my original interpretation. But the point being that if they vote together, they will all be represented anyway, so the criterion won’t normally be subject to such strange cases as only one voter of the group being represented - although this can technically happen if the group is exactly one Hare quota in size.

I wrote up a page with Warren’s definition. https://electowiki.org/wiki/Phragmén’s_Method I then added a section with the implementations and links to their own pages

Please expand if there is more

There is a complicated balancing, unless I misinterpreted.

Hmm, OK. I think we agree that this is not really the property we are interested in anyway.

I will write to the authors.