Thursday, March 19, 2009

Non-Monotonicity: Part I

Since the results of Burlington's mayoral election were announced, battle has raged across the internet between advocates of instant runoff voting and those who have better ideas. Several points are being argued discussed, but the most confusing in the issue of non-monotonicity. What's that word even mean?

Monotonic, if you remember your algebra, means that a function, f(x), is either always increasing or always decreasing as x increases. A function that goes up for a little while and then goes back down is non-monotonic. You could think of it as "if more is better, than even more is even better". And that's (sort of) how the analogy comes over to voting methods: under a monotonic method, getting more votes is always better. So under a non-monotonic method, getting more votes is sometimes bad, or, getting fewer votes is sometimes good.

There are three issues at stake here: first, is IRV non-monotonic? This is an unqualified "yes", although IRV advocates will claim that it's so rare as to be inconsequential in real-life elections. (More on that later.) Second, did the recent election in Burlington exhibit non-monotonicity? This is also an unqualified "yes", which one might think would give pause to those claiming that non-monotonicity is ultra-rare. (Rather, they have decided to argue that it didn't really happen.) And finally, does it matter? This is the only issue of the three which can be up for debate, which we'll do in Part II. But first, we'll pause to prove points one and two.

IRV is non-monotonic

The easiest way to show this, is to construct an example. First, the election needs to have at least three candidates; let's call them 'K', 'M', and 'W'. Secondly, we need to construct a set of ballots where one candidate, let's pick K, is the winner, but in such a way that if we improve K's ranking on some of the ballots, they instead lose. Easy enough:

29 ballots: K > M > W
25 ballots: M > K > W
32 ballots: W > M > K

M, with the fewest top-ranking ballots, is eliminated, and K defeats W by an impressive 54 to 32 margin. But! if we improve K's position on just eight ballots, like this:

29 ballots: K > M > W
25 ballots: M > K > W
24 ballots: W > M > K
8 ballots: K > W > M

Then instead candidate W, with only 24 top-ranking ballots, is eliminated, and M defeats K by a 49 to 37 margin. To repeat: by improving K's score on a small number of ballots, K went from being the winner to being the loser. Which is a very non-intuitive result. It's also possible to create a situation where decreasing a losing candidate's rank on some ballots can cause them to win (but I leave that as an exercise to the reader). If either of these cases is possible to construct for a given voting method, then getting more votes is not always better, and by definition the voting method is non-monotonic.

What about Burlington?

So clearly these situations can happen under IRV. The next question is if the Burlington election was one of those situations. The proof of this is almost trivial, since the numbers (and names) in the above example were pulled from the results of the Burlington election (with a few complicating but non-relevant omissions.)

The real question is, why do IRV's supporters insist that this is not the case? I wish I knew! It seems to stem from a lack of understanding of the words "if" and "could", as in "If the outcome of the election could be changed by...", as their argument is that this election "could" have been non-monotonic "if" some voters changed their ballots "but they didn't". No, no, no! If they could then it is non-monotonic! A lot of bad-blood is being spilled over this non-disputable point, and I don't understand why the opposition persists, as it only serves to distract us from the real discussion.

Which we'll cover in the next installment.

No comments:

Post a Comment