Stardate 20020318.1527

(On Screen): I love mathematical impossibility proofs. I think it's fantastic when someone proves that something which we all think is desirable is mathematically impossible. If the proof holds up, it means that the problem is insoluble for everyone, everywhere, for all of time and no amount of creativity is capable of surmounting it. The mathematically impossible is the one mountain which cannot be climbed.

Gödel spoiled the game for all of mathematics by proving that it was impossible for any mathematical system to be complete. In any mathematical system which is sufficiently rich to permit the question "Is this system complete?" to be framed within the system, he proved that the answer had to be "no". There will always be statements within the system which are true but which cannot be proved, and other statements whose truth values are indeterminate. Interestingly, those statements might be provable within a different mathematical system, but then those systems will in turn have their own unprovable statements. It is a pernicious result; it is a blemish. It is marvelous.

Turing ruined things for computer science before computer science even existed. Long before anyone had even built a reasonable programmable computer, Turing showed that if they had certain very broad characteristics, that there were certain problems they could not be certain to solve in finite time. And the "stopping problem" is no esoteric example, either; there are a lot of practical and useful things which are isomorphic to the stopping problem.

One of the less well known impossibility proofs won a Nobel Prize for Kenneth Arrow. He showed that an ideal voting system was impossible. Any such system, if it did not have even more serious flaws, suffered from a situation where some participants in the system would have more influence than others did. Not to put too fine a point on it, some people's votes are worth more than others.

It's not just that all existing systems suffer from this flaw; all conceivable systems will, if they are not flawed in even worse ways. Arrow came up with six axioms to describe an ideal voting system, and they are not all that controversial. For example, one of them was unanimity: If every voter votes for a certain outcome, that should be the system's choice. That may seem obvious, but then all of Arrow's axioms were obvious, except one. None of them is particularly controversial, but he proved that the set of all systems satisfying all six was the null set (i.e. there aren't any).

That one less obvious axiom takes some explaining, but it's important nonetheless. It's called "transitive preference". If the voting populace prefers choice A to choice B, and if they prefer choice B to choice C, then the system should prefer choice A to choice C. To put it a different way, introduction of choice C into the election shouldn't affect the outcome.

The problem is that if A > B and B > C but C > A, then an oligarchy can affect the outcome of an A-versus-B choice by first introducing an A-versus-C choice (which C would win) and then cause B to win the resulting comparison of C to B. Thus by introducing choice C into an A-versus-B decision, the oligarchy could subvert the voting populace's preference between A and B.

When these kinds of voting cycles come up, it means that those responsible for scheduling elections can manipulate matters. As strange as it may seem, this actually happens.

San Francisco is changing its election system so that instead of selecting the one candidate you most prefer, you rank all candidates. This is subject to considerable confusion by voters, but that's not the real problem with it. The real problem is that it permits a third party candidate to alter the outcome of a runoff.

In a straight election between A and B, assume that A wins. But with this kind of ranking system, if candidate C enters the race, the result can be a situation where A and B are the two leaders (with A leading) but that when the runoff is counted then B ends up getting a higher score than A and wins the election. So by introducing a third candidate into the race, the voters' preference for A over B is altered and B wins the runoff.

How? Suppose that the way it works is that your top choice gets 3 points, your second choice gets 2, and your third choice gets 1. If everyone who prefers A votes A,B,C, but everyone who prefers B votes B,C,A, then it means that A is either first place or third place, but B never places lower than second. So while A is the first place vote more often than any other, B actually gets more points.

200 voters in the election divide their votes as follows:
  99 people vote A,B,C: A=297, B=198, C=99
  98 people vote B,C,A: B=294, C=196, A=98.
  3 people vote C,A,B: C=9, A=6, B=3
    A total=401
    B total=495
    C total=304

No-one gets a majority, so points are used for the runoff. B wins the election. But if C had not been a choice, A would have won because the majority of voters (102 out of 200) preferred A to B.

It has to be understood that every election system is subject to this to some degree (that's what Arrow proved), but some are far more susceptible to it than others are, and ranking systems have a difficult time escaping from it. Nearly always a multi-choice election based on a ranking system will suffer from this to some extent.<