Guest Post: Rethinking STV Fundamentals

75 views
Skip to first unread message

Kevin Baas

unread,
Jun 26, 2016, 4:36:53 PM6/26/16
to The Center for Election Science

Brian Olson

unread,
Jun 26, 2016, 9:58:21 PM6/26/16
to electio...@googlegroups.com
I like it a lot!
I'm going to have to implement this "STV 2.0" (unless you have a better name for it) into my own election simulation tinkering.

On Sun, Jun 26, 2016 at 4:36 PM, Kevin Baas <happy...@gmail.com> wrote:

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Toby Pereira

unread,
Jun 27, 2016, 11:09:08 AM6/27/16
to The Center for Election Science
What does your method do in the single-winner case? Is it equivalent to an existing method?

Kevin Baas

unread,
Jun 27, 2016, 2:02:42 PM6/27/16
to The Center for Election Science
in the single-winner case it's at least similiar to borda count.

not sure if it's exactly equivalent, but it might be.

(though unlike borda count, it has two rounds of explicit tie breaking rules.)

Kevin Baas

unread,
Jun 27, 2016, 2:07:17 PM6/27/16
to The Center for Election Science
I just consulted my spreadsheet, https://docs.google.com/spreadsheets/d/18AN5xli49l39Fh5bRQerLPF0iT5AJpEjY6dvUzk-TUI/edit#gid=0

it's not exactly equivalent to borda count.

particularly, it passes this Independance of clones test: https://en.wikipedia.org/wiki/Independence_of_clones_criterion#Borda_count  where borda fails.
and it passes this later-no-harm test: https://en.wikipedia.org/wiki/Later-no-harm_criterion#Borda_count where borda fails.

Nevin Brackett-Rozinsky

unread,
Jun 29, 2016, 11:01:53 AM6/29/16
to The Center for Election Science
Excellent write-up Kevin, you described your system very well.

In the single-winner case, I can confirm that *if every voter ranks every candidate* then your system is equivalent to the Borda count.

This is easy enough to show:

With 1 seat the quota is 100%, so the only “sets to ignore” that matter are those which ignore all-but-one candidate.

If we ignore everyone except candidate k, how many choice demotions will there be? Well, that is simply a matter of counting how far down each ballot candidate k occurs.

Top of the ballot mean 0 demotions, second place means 1, and so forth. When we add all those up we get, essentially, the negative of the Borda count. Technically, in an n-candidate race with v voters, we get (n-1)*v minus the Borda count.

The winner is the candidate who minimizes that quantity. Since the (n-1)*v term is constant, and minimizing a negative means maximizing its opposite, we see that the winner is the candidate who maximizes the Borda count.

Thus, assuming Kevin is correct in his results about the superiority of his system over STV, one corollary of his research is that the Borda count is superior to instant-runoff voting. My own simulations also confirm that the Borda achieves better outcomes than IRV, so he and I concur on this point.

Furthermore, if some voters do not rank all candidates, then the number of choice demotions from them cannot exceed the number of candidates they ranked. Thus when we take the negative of choice demotions, we see that it is equivalent to a modified Borda count where your first choice receives not n-1 points (one less than the number of candidates), but only m points (the number of candidates you ranked above the bottom).

In other words, the Borda count grants full voting power to people who only rank some of the candidates, meaning in particular their top choice counts just as much as everyone else’s. By contrast Kevin’s method in the single-winner case, if I understand it correctly, reduces the voting power of anyone who does not rank every single candidate, because they cannot possibly contribute the full number of choice demotions.

A slight modification whereby exhausted ballots count as n-1 choice demotions would make Kevin’s system exactly equivalent to the Borda count in the single-winner case. This would restore equal voting power to everyone.

Regardless, still leaving aside the multi-winner situations and focusing solely on single-winner elections, the bottom line here—the big takeaway from Kevin’s investigation—is that the pre-existing IRV method is a flawed, convoluted, multi-step approximation of the superior, simpler, single-step Borda count.

Of course the Borda count has flaws of its own, but both Kevin’s work and my own empirical simulations agree that Borda is better than IRV.

For comparison, my simulations show that with honest voters the Borda count does somewhat better than approval voting, approximately on par with score voting. And with strategic voters, the Borda count is approximately on par with approval voting, while score voting does somewhat better.

Nevin

Kevin Baas

unread,
Jun 29, 2016, 12:58:56 PM6/29/16
to The Center for Election Science
Thanks!  Glad you found it well described, that was one of my big concerns in writing it.

In the single winner case, the system i describe is not exactly the same as borda.  it is better:

* Where borda fails Later-no-harm, ( https://en.wikipedia.org/wiki/Later-no-harm_criterion#Borda_count ) this system does not/
* Where borda fails independance-of-clones, ( https://en.wikipedia.org/wiki/Independence_of_clones_criterion#Borda_count ) this system does not.

another difference is that Borda doesn't have any method of transferring votes, so it can't be simply extended to multi-winner without producing very skewed results.  the system i describe can transfer votes, and works well in multi-winner.

while i generally feel that in the single-winner case, borda is better than IRV, i am certain that the system i describe is better than both.

by the way, i've done some simulations myself.  Hopefully those results will be coming in a paper...

Nevin Brackett-Rozinsky

unread,
Jun 29, 2016, 1:43:17 PM6/29/16
to The Center for Election Science
Yes, your write-up flows nicely, beginning with a readily-understandable motivation, and progressively disclosing the details of your solution. I especially appreciate the “spider / fly” analogy. One minor area that could use clarification is, unless I missed something, the concept of reweighting the ballots was sprung on the user in the algorithmic section without prior introduction. I would suggest to mention in prose that reweighting is used rather than the direct transfer of ballots shown in the examples, and why.

Regarding the single-winner version of your system, there really is not any room for disagreement or debate. If every voter ranks every ballot, then the results are mathematically identical to the Borda count (offset by a constant), because the number of choice demotions when ignoring all-but-one candidate on a ballot is exactly the Borda point value (offset by a constant) for that candidate.

And if you modify your system to count an exhausted ballot as having n-1 choice demotions (where n is the number of candidates) then the equivalence will hold even when some voters rank fewer candidates.

Nevin

Kevin Baas

unread,
Jun 29, 2016, 2:19:21 PM6/29/16
to The Center for Election Science
Counter-example, all voters rank all candidates:

66 A,B
34 B,A

BORDA: A has 66+0=66 borda points, B has 0+34=34, A wins

proposed system:

     ballots: 100.0
     quota: 100.0
     temporarily ignoring  (demotions: 0.0 ballots: 0.0 candidates: 2.0)
leading choices: A: 66.0 B: 34.0
     temporarily ignoring B (demotions: 34.0 ballots: 34.0 candidates: 1.0)
leading choices: A: 100.0 B: 0.0
elected A (above quota) 100.0

66 A,B,C
34 B,C,A

(c is a clone for b)

BORDA: A has 2*66+0=132 borda points, B has 1*66+2*34=134, C has 0*66+1*34=34, B wins

proposed system:

     ballots: 100.0
     quota: 100.0
     temporarily ignoring  (demotions: 0.0 ballots: 0.0 candidates: 3.0)
leading choices: A: 66.0 B: 34.0 C: 0.0
     temporarily ignoring C (demotions: 0.0 ballots: 0.0 candidates: 2.0)
leading choices: A: 66.0 B: 34.0 C: 0.0
     temporarily ignoring B (demotions: 34.0 ballots: 34.0 candidates: 2.0)
leading choices: A: 66.0 B: 0.0 C: 34.0
     temporarily ignoring B,C (demotions: 68.0 ballots: 34.0 candidates: 1.0)
leading choices: A: 100.0 B: 0.0 C: 0.0
elected A (above quota) 100.0

proposed system is clone independent (A,A), borda count is not. (A,B)

Nevin Brackett-Rozinsky

unread,
Jun 29, 2016, 4:17:49 PM6/29/16
to The Center for Election Science
You have carried out your example without using the system you described in the article you linked.

Ballots:
66 A > B > C
34 B > C > A

Borda scores:
A: 132
B: 134
C: 34

Under Borda, candidate B wins.

Your method:
Ignore {}: (A=66, B=34, C=0, demotions=0), no one reaches quota
Ignore {A}: (A=0, B=100, C=0, demotions=66), B reaches quota
Ignore {B}: (A=66, B=0, C=34, demotions=34), no one reaches quota
Ignore {C}: (A=66, B=34, C=0, demotions=0), no one reaches quota
Ignore {A,B}: (A=0, B=0, C=100, demotion=166), C reaches quota
Ignore {A,C}: (A=0, B=100, C=0, demotions=66), B reaches quota
Ignore {B,C}: (A=100, B=0, C=0, demotions=68), A reaches quota

The are four possible sets-to-ignore which result in a candidate reaching quota:
Ignore {A}: B wins after 66 demotions
Ignore {A,B}: C wins after 166 demotions
Ignore {A,C}: B wins after 66 demotions
Ignore {B,C}: A wins after 68 demotions

We identify from those sets the ones which minimize choice demotions:
Ignore {A}: B wins after 66 demotions
Ignore {A,C}: B wins after 66 demotions

Both cause B to win, and per your tie-break procedure we prefer the set which affects the fewest ballots. Both sets affect 66 ballots. The second tiebreaker is “most candidates”, which means our chosen set is {A,C}.

Per your own written and published explanation of your voting system, the outcome of this election is for B to win when we ignore {A,C}, with 66 choice demotions.

As I said before, there is no room for debate about the fact that your system is exactly equivalent to the Borda count (in the single-winner case where all voters rank all candidates), because the procedure by which you defined your system necessarily yields the Borda count when the number of choice demotions is subtracted from a constant (in this case 200, in general (n-1)*v).

I strongly recommend that you move away from your repeatedly-demonstrated propensity to argue against mathematical facts.

Nevin

Kevin Baas

unread,
Jun 29, 2016, 6:45:03 PM6/29/16
to The Center for Election Science

What I wrote was an explanation of an algorithm.  I put that algorithm in Java and created a user interface for it here:


If there's any difference in the algorithm and what you understood from the article, that is a failure of communication.

The algorithm is a mathematical fact, as is its output, and you can verify it for yourself by looking at the source code and/or running scenarios.

I strongly recommend that you move away from your repeatedly-demonstrated propensity to argue against mathematical facts.



Kevin Baas

unread,
Jun 29, 2016, 6:54:59 PM6/29/16
to The Center for Election Science
Ah crap, there's a bug in my code!

I'll have to adjust and recreate the spreadsheet.

Kevin Baas

unread,
Jun 29, 2016, 7:14:04 PM6/29/16
to The Center for Election Science

Found it.  So to get the ordering, i get the first score, then multiply that by the highest value it could have, then add the second score, etc.
 
In calculating these multipliers, I wasn't considering the weight of the ballots.

this:
double[] multipliers = new double[]{
num_candidates,
num_candidates*ballots.size(),
ballots.size(),
num_candidates*ballots.size(),
};
should have been this:

double num_ballots = 0;
for( int i = 0; i < ballots.size(); i++) {
num_ballots += ballots.get(i).weight;
}
double[] multipliers = new double[]{
num_candidates,
num_candidates*num_ballots,
num_ballots,
num_candidates*num_ballots,
};
Which means i'll also have to re-run the sort order tests, and possibly change the sorting rules.

sigh.

Anyways, thanks Nevin!  Much appreciate the fortuitous cross-validation!

Sorry I got a little snipey.  I looked over what you had carefully and I was like "No, he did it right... huh.... B should have won."


but now the fact that that mistake was helpful.... hmm... maybe that's an accidental innovation...
i'll see what the sort order testing shows now and go from there.

Nevin Brackett-Rozinsky

unread,
Jun 29, 2016, 7:58:44 PM6/29/16
to The Center for Election Science
I am glad that you were able to fix a bug in your code. However I am surprised that something related to ballot weighting would affect the single-winner case.

My understanding of your algorithm is that ballots are only reweighted when they are used to elect a candidate, and thereafter have less input toward filling subsequent seats.

In the single-winner case I would expect all ballots to have weight 1 throughout the procedure. Am I mistaken?

Nevin

Kevin Baas

unread,
Jun 29, 2016, 8:25:29 PM6/29/16
to The Center for Election Science
before counting, identical ballots are merged.

so if you have 66 a,b,c ballots, that's 1 a,b,c, ballots with a weight of 66.

this is an entirely neutral step - it just a different way to represent the same data that save a lot of cpu and memory, esp. in large elections.

so in this case it was multiplying by 2(1+1) instead of 100(66+34).

Kevin Baas

unread,
Jun 30, 2016, 11:33:59 AM6/30/16
to The Center for Election Science
well interestingly enough, using demotions + affected ballots as the first sort rule does seem to consistently be better than using demotions as the first rule.

not sure i can mathematically justify this, though.  so i'm going to leave the rules as is.

another interesting thing, after fixing my bug and re-testing, it looks like i can use the borda values of potential eliminations as the first rule, and then fall back to # of demotions as the second rule, and then since the borda values are additive, one can develop constraints that would allow one to iterate through the combinations in lower average computational time.  (since, e.g. we know that the 2-set with lowest borda value is always composed of the 2 1-sets with lowest borda value)

Nevin Brackett-Rozinsky

unread,
Jun 30, 2016, 3:04:54 PM6/30/16
to The Center for Election Science
That makes sense, the Borda scores should provide a useful heuristic over the search space.

What metric do you employ for determining whether one rule is better than another?

And have you compared the “betterness” of your current “sort by demotions” against the alternative “sort by ballots affected”? If so, what were the results? (I presume in each case the other approach would serve as tiebreaker.)

Best,
Nevin

Kevin Baas

unread,
Jun 30, 2016, 4:53:59 PM6/30/16
to The Center for Election Science
i have 42 test cases i gathered from the internet.

i run automated tests on all test cases, all sort orders.

results are here:


"elimination sort order" sheet.

0 = # candidates (more is better - cause that means fewer demotions per candidate)
1 = borda value
2 = affected ballots
3 = demotions.

you'll see that  (- since the bug fix -) if you start with 3 (demotions, the remaining sort items don't matter.
but you can also start with borda, and as long as you do demotions next, it comes out the same for all test cases.
Reply all
Reply to author
Forward
0 new messages