No, this isn’t about the recent US presidential elections.

In one of those “Yay I get to combine all my weird obsessions” moments, I’ve been playing around with using linear programming to construct provably minimal examples of specific election results. It actually works pretty well – it’s easy to to do for things like plurality voting, borda count and Condorcet winners, and it turns out to be almost possible to do for instant runoff voting (I haven’t figured out how to specify the instant runoff winner in a single linear problem, but you can specify an exact instant runoff drop-off order and then brute force by just considering all the relevant permutations).

Anyway, in the course of doing this I came up with the following really nasty small election example:

• 6 votes of A, C, B, D
• 3 votes of B, D, C, A
• 3 votes of D, B, C, A
• 1 vote of C, D, B, A

Why is this election so nasty? Basically the electorate is divided into two groups: A near majority who think A is great, and a bare majority who can’t agree on much of anything except that they hate A. If you want an interpretation of how these results came about, you could imagine that A is a right wing candidate in a slightly majority left-wing constituency, C is a centrist candidate, and B and D are two left wing candidates who are running against each other and have split the vote.

But regardless of interpretation, what results is an election that is very sensitive to which voting system you use. In particular four fairly common choices of system each elect a different one of the four candidates:

• The plurality winner is A, with 6 votes.
• The Borda count winner is B: The Borda scores are A at 31,  B at 35, C at 34, and D at 30.
• The Condorcet winner is C:  7 voters (the first and last group) prefer it to B and D and 7 voters (everyone but the first group) prefer it to A.
• The Instant Runoff Voting winner is D: In the first round C drops out with only 1 vs 3, 3 and 6 first choice preferences. This transfers a vote to D, causing B to drop out in the next round at 3 vs 4 and 6 first choice preferences. B then transfers their first choice votes to D as well, and finally D has a majority at 7 out of 13 votes, so D wins.

This is the smallest election with these winners and this specific drop-off order, in the sense that it has the fewest number of distinct votes cast (caveat: Where no individual vote has more than 100 voters casting it. This probably doesn’t matter), and amongst those elections with four distinct votes having this property it also has the smallest number of total votes (it also does some minimizing amongst those, but that’s more for aesthetics and doesn’t correspond to an obviously interesting property).

I originally thought all of the voting systems were doing badly on this election, but actually on further reflection I think they’re all behaving in an extremely typical fashion for them.

To frame this in terms of the interpretation above:

• Plurality voting elects the right wing candidate because the left wing vote got split.
• IRV collapses the two left wing candidates together and elects the one with slightly larger support due to the centrist tie breaker vote.
• Borda vote does similarly but breaks the tie in the opposite direction because it counts the fact that the A voters prefer B over D for something.
• The Condorcet candidate is a centrist compromise between the two sides that everybody can tolerate but nobody is thrilled about.

So which candidate you think is correct really depends on what you’re going for – there’s a legitimate question to be asked about how centrist you really want your elected leader to be, and about how justified that is in this case. If you decide that because you’ve got a bare majority the you should elect a more left-wing leader, the question of B vs D seems to come down to whether you want to go for a candidate the other side hates or one the other side really hates.

I don’t know about you, but right now having leaders the other side only hates sound pretty good to be honest. So although I didn’t intend this to be an argument for any of these systems, maybe Borda count comes out of this looking pretty good.

Given that, I feel the title is rather over promising matters. So here’s an even worse election:

• 6 votes A, B, D, C
• 5 votes C, A, B, D
• 5 votes D, C, B, A
• 2 votes B, C, A, D
• 2 votes B, D, C, A

This has more or less the same properties as the above one: A is the Plurality winner, B is the Borda winner, D is the IRV winner.

However, C is no longer the Condorcet winner because there no longer is a Condorcet winner. Instead C is merely the Kemeny-Young winner, a system which always elects the Condorcet winner when there is one and has some claim to being the “best” such electoral system (in the sense of being the closest to capturing the same spirit as the Condorcet criterion), but is horribly impractical for any significantly large number of candidates.

To see why this happens, lets look at the majority preferences amongst the candidates:

• 11 voters prefer A to B
• 13 voters prefer A to D
• B and C are tied with 10 votes each
• 15 voters prefer B to D
• 14 voters prefer C to A
• 13 voters prefer D to C

So we have a Condorcet cycle where A is strictly preferred to B, B is strictly preferred to D, D is strictly preferred to C, and C is strictly preferred to A.

The Kemeny Young rule works by looking at all rankings of the candidates and giving them a cost associated by how much they disagree with this ordering. For each voter and each pair of candidates, the ordering incurs a cost of one if the voter disagrees with that ordering of that pair.

There are better algorithms for this than just considering all orderings of the candidates, but fortunately we only have four candidates so we can just brute force it to see why this works out this way.

The full list isn’t very informative, but here’s a partial list:

This gives us the following scores:

• “C, A, B, D” scores 50
• “A, B, D, C”, “B, C, A, D”, “B, D, C, A” and “C, B, A, D” each score 52
• “B, A, D, C “scores 54
• Everything else scores 58 or higher
• “D, B, A, C” scores 70

(The example was specifically constructed to give “C, A, B, D” as the unique Kemeny-Young best ordering: In much the same way as with IRV, it’s easy to specify the Kemeny-Young ordering but hard to specify just the Kemeny-Young winner)

Because it’s the leader of the unique minimum cost ordering, C wins under the Kemeny-Young rule.

As you can see it’s quite a close fight – there isn’t a huge amount of difference between the lowest cost and the runner up cost, and in the second lowest cost orderings don’t really agree on who should win – the only thing that seems to be consistent is that it shouldn’t be D. This sort of close race tends to be why Kemeny-Young calculations become difficult very quickly.

I’m finding it hard to come up with an interpretation of this election, so lets run the instant runoff vote and see if it’s enlightening (I’m ambivalent about IRV as a system, but watching how votes transfer can help elaborate on coalitions).

Initially B drops out, having only four first choice votes. These split equally between C and D, leaving us with the following configuration:

• 6 votes A, D, C
• 7 votes C, A, D
• 7 votes D, C, A

Now A, the previous plurality winner, has the lowest first choice votes so drops out and transfers votes to D:

• 7 votes C, D
• 13 votes D, C

So D wins the runoff over C.

So I think maybe the way to look at this is that A is an independent candidate of some sort that is distracting from the main stream set of candidates B, C and D. Lets see what happens to the election if we start by taking A out:

• 8 votes B, D, C
• 5 votes C, B, D
• 5 votes D, C, B
• 2 votes B, C, D

So B becomes the plurality candidate, with fully half the first choice vote. The majority preferences remain as they were (because they are not affected by the removal of A): C is still majority tied with B, B is still strictly preferred to D, D is still strictly preferred to C. So there’s still no Condorcet winner.

Removing has made instant runoff voting result in ambiguity though: C and D are tied as to who will drop out. If C drops out then it transfers votes to B, which wins. If D drops out, it transfers votes to C, which is now tied with B. In neither case does D, the original IRV winner, win! This is particularly interesting because the voters who put A first all strictly prefer B to D, and C to D, so removing their first choice candidate arguably results in a better result for them (if you break ties by flipping a coin, they get a better option 3/4 of the time).

The Borda winner (which can change by dropping a candidate) is still B.

I don’t know how enlightening that was, but it seems to reinforce the interpretation that B, C and D are an extremely fractious lot who are probably not going to get along, and unless we elect RON instead (the only candidate who can promise change!) we’re probably going to see the continuation of voting through other means.