STAR test cases

[endolith]

I started writing a STAR implementation but got slowed down by the tie-breaking complexity. Here are my work in progress implementation and unit tests in case they're useful. (Some of the WDS examples are not correct, and he never responded to my emails.)

• https://github.com/endolith/elsim/blob/master/elsim/methods/star.py
• https://github.com/endolith/elsim/blob/master/tests/test_star.py

I'd like more examples of corner cases if you know of a list. Real-world election ballot lists would be good, too.

[mikefranze]

Thanks for the link, I think this will be very useful. I just added a PR with the basic unittest framework. Our STAR implementation is pretty basic at the moment, no ties or anything, so I'm interested in reading through what you've done. There's some tie breaker documentation here and we have some javascript implementations here

[endolith]

These tiebreakers get confusing fast. If you try to write out tests for every possible scenario, the scenarios keep branching off with ties within ties within ties. For example:

• A=2, B=1, C=0
• A=1, B=0, C=1

Totals are A=3, B=1, C=1, so A is a finalist, but B and C are tied.

So find pairwise winner between B and C. 1 voter prefers B>C, one prefers C>B, so they're tied, no pairwise winner.

"If needed you can also compare them each head-to-head against the highest scoring candidate." So if 2 voters prefer A>B, while 1 prefers A>C, then C goes to the runoff? (And then A wins.)

• A=2, B=1, C=0, D=0
• A=1, B=0, C=1, D=0
• A=1, B=0, C=0, D=1

Totals are A=4, B=1, C=1, D=1, so A is a finalist, but B, C, D are tied.

So try to find pairwise winner between B, C, and D. There is none, it's a tie.

So compare with highest scoring candidate.

3 A>B
2 A>C
2 A>D

So C and D are tied? Pick one randomly for the runoff? (Then A wins regardless.)

Also minimax has three different interpretations when you allow equal rankings. https://en.wikipedia.org/wiki/Minimax_Condorcet_method#Variants_of_the_pairwise_score

[mikefranze]

The link above should cover these scenarios. In your second case with a multi candidate tie, A is the Condorcet winner and C and D tie for runner up. I don't think there's a need to break the tie further. In other cases with true ties it's ok to just report that the result is a tie.

[endolith]

But the instructions say "Take each candidate and compare them head-to-head with the others in the tie." So it doesn't matter that A is Condorcet winner for deciding the 2nd candidate who goes to the runoff. It needs to select one of them, if only to display who it was.

[endolith]

OK I made a big table and found there are 12 possible scenarios with the "minimum tiebreaker" method, and made a test case for each (rows are voters, columns are candidates A B C, numbers are scores)

1. One highest-scoring, one 2nd-highest. One preferred in runoff (B in this example):

0	5
2	4

2. One highest-scoring, one 2nd-highest. Both tied in runoff, break tie using scores, highest-scoring wins (B):

0	5
3	2

3. Two tied for highest-scoring, both go to runoff, one wins in runoff (B):

0	2
1	2
4	1

4. Two tied for highest-scoring, also tied in runoff, decide A or B randomly:

1	3
4	2

5. One highest-scoring, two or more tied for second-highest. One Condorcet winner among tied (C). One is preferred in runoff (A):

5	2	3
5	2	3
5	2	0

6. One highest-scoring, two or more tied for second-highest. One Condorcet winner among tied (C). Runoff is tied, highest-scoring (A) wins:

5	2	3
5	2	3
1	2	2
1	4	2

7. One highest-scoring, two or more tied for second-highest. No Condorcet winner among tied, break 2nd place randomly (B or C). One is preferred in runoff (A):

5	2	3
5	2	3
4	3	2
1	4	3

8. One highest-scoring, two or more tied for second-highest. No Condorcet winner among tied, break 2nd place randomly (B or C). Both are tied in runoff, highest-scoring wins (A).

5	2	3
5	2	3
1	3	2
1	4	3

9. Three or more tied for highest-scoring. One Condorcet winner and one 2nd-place Condorcet winner go to runoff. Condorcet winner wins (A):

2	1	0
2	1	0
2	1	0
2	1	0
1	0	0
0	0	4
0	5	5

10. Three or more tied for highest-scoring. Two tied for Condorcet winner (A and B), both go to runoff. True Tie, break randomly:

2	2	0
2	2	0
1	1	5

11. Three or more tied for highest-scoring. One Condorcet winner in tiebreaker and two or more tied for 2nd place CW. Break tie randomly (B or C). Condorcet winner (A) wins runoff:

2	1	1
2	1	1
3	5	5

12. Three or more tied for highest-scoring. No Condorcet winner in tiebreaker, choose two randomly. Neither wins runoff, choose winner randomly (A B or C):

5	5	5
2	2	2

[mikefranze]

This has been a rabbit hole that we've been working on for a while. There's a few people deep diving on different tie breaker protocol including the minimax algorithm specified in the site. We're currently looking into an even simpler protocol based on the Ranked Robin voting method. For this reason I'd caution against putting too much more work into this rabbit hole. In the meantime we've updated the instructions to just

1. Ties in the Runoff round should be broken in favor of the candidate who was scored higher if possible.
2. Ties in the Scoring round should be broken in favor of the candidate who was preferred head-to-head by more voters.
3. Ties which can not be broken as above are considered a "True Tie."

So in scenarios where there are multiple candidates who tie in the score round it will be labeled as a true tie and up to whoever is running the election to break it with their preferred tie breaking protocol. I'm hoping to get some of those protocols added to this repo so there are multiple options available.

[adienes]

Wrote this in the slack but I'll copy it here. The 'simple' scenarios (i.e. 1, 2, 3, 4, or the unlisted scenario of one highest score, exactly two tied for second, with one preferred over the other) are already going to be rare, and the resolutions @mikefranze put above work great.

Any of the other scenarios ("True Tie") would be so astronomically rare I don't think it's worth any of the added complexity to specify other protocols like Ranked Robin or 'Minimax' etc. etc. Even just introducing the concept of a Condorcet winner feels like an avoidable cognitive burden for voters. I agree that in general it is nice to elect a Condorcet winner, but in this kind of edge case I really don't think it matters.

If it is necessary to specify exactly what to do in the case of a "True Tie," I would strongly recommend something more straightforward. Here are some examples:

• Break tie in favor of candidate with most scores of 5.
• Break tie in favor of candidate with most scores of 3+
• Break tie in favor of candidate with fewest scores of 0

And so on.

[endolith]

For this reason I'd caution against putting too much more work into this rabbit hole. In the meantime we've updated the instructions to just

1. Ties in the Runoff round should be broken in favor of the candidate who was scored higher if possible.

2. Ties in the Scoring round should be broken in favor of the candidate who was preferred head-to-head by more voters.

3. Ties which can not be broken as above are considered a "True Tie."

This is still the same 12 scenarios I've described above, no? Or are three-way ties not included in "ties"?

[endolith]

one highest score, exactly two tied for second, with one preferred over the other

That's numbers 5 and 6

If it is necessary to specify exactly what to do in the case of a "True Tie," I would strongly recommend something more straightforward.

Simplicity is nice. I still haven't finished my STAR implementation because of handling the "three or more tied for highest-scoring" cases, where I need to find 2nd-place Condorcet winners, etc.

[endolith]

Sorry for all the questions, I'm just trying to make sure my implementation is 100% correct.

Ties in the Scoring Round should be broken in favor of the candidate who was preferred head-to-head by more voters.

So in this 3-voter, 4-candidate scenario

 	A	B	C	D
1	5	2	4	4
2	4	5	2	2
3	2	4	5	5

What would the "minimal tiebreaker" do? This is considered a "True Tie" because there is no Condorcet winner, so choose between A, B, C, D randomly? (Even though A wins more matchups over the alternatives?)

And in this

    Allison, Bill, Carmen, Doug = 0, 1, 2, 3
    election = [[5, 4, 1, 4],
                [5, 4, 1, 4],
                [2, 4, 1, 2],
                [4, 3, 2, 1],
                [0, 5, 4, 4],
                [3, 2, 4, 2],
                [3, 1, 5, 3],
                [3, 1, 5, 3],
                [1, 3, 2, 2],
                [4, 3, 5, 5]]

All candidates get the same score, and there is no Condorcet winner, but you still need to identify the Smith Set(?) and choose randomly from within that set {A, B, C} because they all beat D pairwise? (Which is non-trivial?)