Monday, November 30, 2009

I have to get this one out quick, because its ridiculously topical

The recent Liberal party spill was a fantastic example of how, when an electorate is strongly polarised, a preferential voting system* can massively disadvantage a compromise, "moderate" candidate who's position lies close to the median.

Lets assume for simplicity that all the Liberals who voted for Turnbull preferred Hockey to Abbott, and likewise all the Abbot voters also preferred Hockey to Turnbull. Its likely a pretty fair assumption given the rancour between the two camps.

So can infer that the preferences of the partyroom were then:

35 x {Abbott, Hockey, Turnbull}
26 x {Turnbull, Hockey, Abbott}

And thanks to the subsequent "redistribution" in the second round vote, we know we had

7 x {Hockey, Abbott, Turnbull}
15 x {Hockey, Turnbull, Abbott}
1 x {Hockey, no second preference} - the notorious informal "no" vote.

Note something here. 49 to 35 voters prefer Hockey to Abbott - a substantial majority. And likewise a massive 58 to 26 voters prefer Hockey to Turnbull, all of the "right" faction and a fair portion of the "left" faction too.

So Hockey "beats" both Abbott, and Turnbull - pairwise, he is more preferred than either of his opponents. In a Hockey vs Abbott or a Hockey vs Turnbull election, Hockey wins.

What's going on here? Sure in America and Britain with their crazy first-past-the-post systems you can get spoiling effects, where Nader costs the Democrats the election by siphoning off their supporters, but preferential voting prevents that! That's why we have it. Family First or the Nationals can run for a seat safe in the knowledge they won't split the conservative vote, because their preferences will go to the Liberals (assuming of course voters are sensible and rational and order their preferences properly, which they don't... but lets optimistically assume that such confusion is a small effect.)

Well, nonetheless, their is a spoiling effect in play. While you might be tempted to say Hockey has split the moderate vote, that's not really true - Turnbull failed to attain a majority with Hockey out of the picture. Actually, Turnbull has split the moderate vote; if he'd stood aside, Hockey would have won, and the liberals would still have a relatively centrist leader. Instead of an unelectable one.... but lets not go into that now.

The lesson - preferential voting prevents some arguably undesirable election effects - Nader would not hurt the Democrats if that Presidential election happened in Australia - but not all of them. And so the question, now, is: can we do better?

Another system

Lets look at those votes again shall we?

35 x {Abbott, Hockey, Turnbull}
26 x {Turnbull, Hockey, Abbott}
7 x {Hockey, Abbott, Turnbull}
15 x {Hockey, Turnbull, Abbott}
1 x {Hockey, no second preference}

Is there another way to determine a winner? Well sure there's lots, we could draw them out of a hat. But, another sensible seeming way?

Let's make one up. For every first preference, I will give a candidate three points. For every second preference, two points; and for every third preference, one point. The person with the most points, wins. Seems kinda fair, right? Its similar to the way they score motor racing, I believe.

This gives us:

Abbott: 35 x 3 + 26 x 1 + .... ah I won't clutter things up with all the figures here. Easier to check in a spreadsheet, like I have, if you don't believe my arithmetic.

Abbott: 160
Turnbull: 150
Hockey: 191

Hurrah! Hockey wins! I successfully invented a new way to run elections to rig the Liberal leadership for the candidate I prefer.

Well, actually, I'd prefer Abbott to lead the party - Hockey hasn't the intellect for the job, while Abbott is quite smart - he'll at least hopefully make for an effective enough opposition to pressure the government - and even though I vehemently disagree with him on many issues there's no chance he'll get elected, so that's all good. Turnbull would be my choice, but I'm not in the Liberal caucus let alone rigging their elections.

Much more to the point, I can't take credit for the system. Its a well-known idea amongst voting theorists, called Borda Counting, although its very little utilised in the real world to my knowledge. I can't name a democracy that elects public officials this way.

So.... if its so great, why isn't it more popular in the real world?

Poor marketing, probably. Also, it doesn't... feel quite right. There's some intuitive sense that we shouldn't be giving away points like this. After all if I'm to distribute points, I should be able to choose to distribute them in any fashion I want, in which case, as I'm a regular voter who doesn't like all this complication I'm likely to distribute them all to my favourite candidate.... and then we're right back to first-past-the-post land.

Well, that intuition (which is mine, you might not share it) is wide of the mark - Borda count does have some quite desirable properties. We've already seen evidence of a possible advantage in this election over the distribution of preferences - it picked out the more consensus, middle of the line candidate from the Liberal leadership ballot.

Will it always? Can Borda Counting, like preferential voting, fail to pick the consensus candidate?

What do we mean?

To ask these kinds of questions about voting systems I need to be more precise. What do I mean by the consensus candidate?

Actually, I've already given a pretty robust definition of what I mean, what the heart of the original concern is:

So Hockey "beats" both Abbott, and Turnbull - pairwise, he is more preferred than either of his opponents. In a Hockey vs Abbott or a Hockey vs Turnbull election, Hockey wins.

This is a mathematically precise idea, and an important one in voting theory. A candidate who, based on people's stated preferences, would have beaten any of his or her opponents in a one on one election is a Condorcet Winner.

It might seem like a pretty abstract concept, which is why I spent so many damn words there building up to introducing it by motivating it with a real life example.

An election may have either one Condorcet Winner or no Condorcet winners. While you might think its an unusual situation except in maybe a tight three horse race like our example, actually many real worldelections do have a Condorcet Winner.

Another definition (And no, I don't care if I'm boring you :P Can you tell I was once a mathematician?) A voting system that is guaranteed to elect the Condorcet winner, when there is one, is, funnily enough, called Condorcet.

We've already seen our preferential voting system is not Concordent. Our question is now is the Borda Count system Condorcet?

The answer is perhaps surprisingly no. Even though Borda Count would have given victory to our Condorcet winner, Joe Hockey, it doesn't always do so. Proof left as an exercise to the mathematically inclined readers. For those who'd settle for a counterexample, wikipedia is your friend.

So do any Condorcet voting systems actually exist?

Yes! Here's one:

1. Check if any candidate is the Condorcet winner (which is easy)

2. If so, they win.

3. Otherwise, pick the winner out a hat.

Ooooh. That's not so good. For a start, it fails a nice little property called determinism: the same set of votes should always give the same result. Under a non-deterministic system like this, any candidate could call a recount, and most likely get a different result each time.

How about instead we try:

3. Otherwise, the winner is whoever's name comes first by alphabetical order
Still not very good. It isn't random, it's deterministic... but.... step 3, well, it's ignoring the voters wishes. In fact there are a wide variety of properties that reasonably try to embody the idea that an election should respond to what voters want; that the only thing about a candidate that matters for the outcome should be the voters preferences. This system fails miserably to satisfy all these ideas.

Nonetheless, there are Condorcet systems out there that aren't crazy, and do make sense, and they are used in the real world - not for electing politicians, but for running private organisations - the ones that give us Wikipedia, and Debian Linux, and the Free State Project. There might, perhaps, be some correlation between the fact that seemingly only associations of nerds use these systems, and the fact they are very mathematically complex relative to the others we've discussed here.

But, if they give the right result, why can't we use them?? Does it matter if they're complicated, so long as we get the person who truly deserves to in?

Well, in some sense it does. The less the average voter is able to understand their voting system, the less empowered they are to exercise their sovereignty, and a less open and transparent a democracy results. This is a bad thing in and of itself.

But the fundamental issue is much worse than that.

The crux of it all

Here's where people who were shouting disagreement way back at the beginning get a see in. Maybe I've been going about it all wrong. Maybe its not important that the Condorcet winner wins an election. Often such a candidate is a kind of a "least of all evils"; indeed, this is more or less how I've depicted Hockey. The compromise candidate, that no one especially wants to win, but that no one objects to very strongly, so they're preferred by (distinct!) majorities over the candidates that provoke strong feelings and polarise the debate. Is such wishy-washy middle of the road stuff really what we want, from political leaders? Maybe we want someone who stands for something, anything, even if its not always going to be what we stand for.
Well OK, lets we can let that criterion go. Damn, that was a massive waste of blog space no?

I'm only putting it to one side though for the sake of exploring the issues. In fact, I want to finish up here by briefly looking into some other properties. If we're going to design the perfect voting system, we should look for more basic features that we all know we definitely want to see. We've already seen a couple of obvious ones, like determinism. Well, here's another I hope you can agree to:

We call a voting system monotonic if voting for somebody can't make them lose.*** If a voting system is not monotonic, we call it batshit crazy.

OK right, all voting systems need to be monotonic. Agreed? Good.

Ours isn't.
"Huh?" you say. "Surely you're not serious?"

Sadly I am. Elections in Australia, from the Liberal Party caucus, to the lower house by-elections the Liberal Party will be getting thumped in because of their caucus, are not monotonic. You can hurt a candidates' prospects by ranking them higher.

Some political scientists have argued that in most real life political system violations of monotonicity would be rare. Still, the fact it can happen at all bothers me. It should bother you.

All these properties voting systems fail to satisfy, jeeze louise. Obviously, we've got to send voting system people back to the drawing board, and get them to invent new systems that work!

If you've got a good sense for where I'm going with this, and why I'm parading mind numbing details of elections and too much maths style arguments than is healthy for a blogger who wants people to actually read what he's written, you might guess what the response is.

They can't invent such systems; they simply don't exist. At least in the sense that, for a lot of really reasonable sounding sets of criteria, it can be proven mathematically that no voting system can possibly obey all of them.

I love impossibility theorems in mathematics - not such a thing doesn't happen to exist, like pink unicorns; such a thing, which sounds quite reasonable, a voting system that makes sense, can't possibly exist, no matter how hard you look, you'll never find one, any more than 2 + 2 will ever equal 5.

Arrow's impossibility theorem is probably the most famous single thing in voting systems theory, and was the first substantial impossibility result. Indeed Kenneth Arrow, an economist,was one of the pioneers of applying theoretical mathematics to what has turned out to be the quite deep and subtle question of how to decide the results of elections when more than two options are available to choose from (although the first person to do so at all pre-dated him by centuries - a certain Marquis de Condorcet, who's name might seem familiar if you've being paying attention. )

Perhaps some may take heart in the fact that there is quite a bit of dispute about whether all of Arrow's criteria really are reasonable or necessary, or whether perhaps we can think out side the square and use systems that don't conform to Arrow's assumptions about what voting looks like. And yet, surely enough, there have also been other key impossibility results established in the field, that show we're seemingly pretty stuck with certain quite undesirable imperfections.
So while we can be thankful to live in a democratic society and indeed an increasingly democratic world, it's not all happy sailing. Even before you consider vote rigging, or corruption, or a biased media, or any of the other countless real world problems that can plague an election, there is a far more powerful force resisting the democratic will. The very laws of mathematics, inescapable even in a perfect world, ensure it is always debatable whether any election was ever really fair.


* Throughout the post I treat a system with multiple rounds of voting in real time, like the Liberals leadership ballot, as equivalent to a system where you write down your entire list of preferences in advance, like when we vote for our MPs. If your preferences don't change over the course of the election, these should be equivalent systems. They won't actually be equivalent, due to tactical voting considerations - you can sometimes be better off voting in a manner that goes against your actual preferences, and the additional information available between rounds when the process happens in real time increases gives increased opportunities to do so - but that's an additional technical complication that doesn't really effect the substance of my main point, so I didn't go into it.

** Actually both Borda Counting, and the Australian system, are preferential - you vote by making a list of preferences. The correct technical term for how we vote in Australia is Instant Runoff Votig, (IRV); it is merely one of a variety of ways of voting using preferences. However this isn't a very widely used term in this country, and only a very few voting system geeks, who I don't think read this blog, would have a clue the hell what I talk about. Since those who understand the mechanics of our system tend to think of its distinguishing feature as being the use of preferences, in contrast to the first past the post systems of the U.K. and the U.S., I have stuck with the incorrect but comprehensible terminology.

*** The mathematicians might want more rigour. Properly speaking, a voting system is monotonic if changing one vote so that Candidate X is higher on the list, but all other candidates are kept in the same relative order, can't change the result from Candidate X winning to Candidate X losing.

How can our voting system possibly fail punish a Candidate for someone preferring them? Basically, the problem is that if you put your preferred candidate Lisa Simpson in say second place, the candidate you have in first, say Duff Man, can knock out rivals in early rounds of voting, but then ultimately the flow of preferences can give Lisa the win in the last round against Duff Man. However if you instead swap your first and second place and put Lisa first, Duff Man might get eliminated early without your crucial first preference. With Duff Man gone earlier, his voters' preferences now get distributed, and those preferences might let say Mr Burns limp all the way to the final round picking up lots of second, third, etc. preferences from every eliminated candidate as he goes and finally triumphing over Lisa.

I'd construct a numerical example, but, I can't be bothered.

Monday, November 9, 2009

Prose's abatement

Blogging under
Deprivation of slumber
Hypomania's many hyper
Tendencies tend to be
Exacerbated, precipitated
A mist of words
Becomes a deluge

A news article has confirmed
The world's gone as mad as you'd heard
The only response possible -
Outraged loquacity, tumbles
Forth, unconstrained, with only the steady rattling
Of the Eee PC's battered keys to protest at the prattling

An aside, a brief build-up, mere foreplay to the climax of self-righteous indignity
Becomes much more of, shall we say, a tangent, gaining nuance, losing brevity
Til the point is reached, at which distraction from the judicial theme is wrought insufferable
Of course, such artistry must not be abridged - but mayhap, it is shuffleable?

So then, the post, once, in outline, contained sufficiently, by the ample boundaries of a mere few paragraphs
Is now possessed of parts - one and two - each more substantial than nigh any article to be found within the Daily Telegraph
But now stop the press, what's this? It surely cannot be true - that part two, too, asserts its "right to be serialised?"
Can we burden readers thus, when even part one, solus, is proving far too long for mine own weary old eyes?

This madness must cease! (Not the world's now, take note)
It's the blog that's diseased! (Not the way people vote)
An introductory sentence (Of the linguistic sort)
Now spans three separate entries! (Makes those gaol terms seem short....)

How does one conquer
Such prolific prose?
Could a poem deliver?
Grant salvation?
Who knows?


Please forgive the attempt at such an unaccustomed and ill-suited form, but my incompletable, uneditable blog ranting was really giving me the shits ;-)

I do plan to proceed with the original posts, eventually... once some substantial editing has taken place.