Consider this purely hypothetical situation. Suppose that you have a group of people who need to choose one person in their midst to receive an award. If there are only two nominees -- let's call them Alice and Bob -- then it's simple. Just take a vote, and the majority winner gets the award. But what if you throw in a third candidate, Carl? What now?

One possibility is to just take a three-way vote, and give the award to the person receiving the most votes. But that clearly isn't fair - what if Alice gets just over 1/3 of the votes, but everyone who voted for Bob would take Carl as their second choice (and vice versa)? This leads to sequential elimination voting -- drop the candidate who comes in third, and then have a runoff election between the other two candidates (in practice, this can be achieved with a single vote by having everyone rank their candidates). This is probably the most commonly-used voting system -- it's the system, for instance, used by the science fiction community to choose the Hugo Awards -- although the latter allows for a voter to choose "no award", which can lead to bizarre results.

Another possibility is to take sequential head-to-head votes -- have the voters choose between Alice and Bob, Bob and Carl, and Carl and Alice, and the person who wins both of his two elections gets the award. But a little thought reveals that this procedure isn't guaranteed to produce a result -- it's possible that Alice would defeat Bob AND Bob would defeat Carl AND Carl would defeat Alice. Yet another alternative would ask each voter to rank the three candidates, and assign, for instance, 3 votes for each first-place ranking, 2 votes for second-place, and 1 vote for third place.

The problem is that these different voting systems can produce different winners. So what is the best voting system once you get past two candidates? It seems reasonable to require that any voting system ought have the following properties:

- If the voters favor Alice ahead of Bob in a two-person election, and then Carl is introduced, the result should be the election of either Alice or Carl, but not Bob. Similarly, if Alice wins a three-person election by a majority vote, and one of the losing candidates drops out, Alice should still win against the remaining candidate.
- If Alice wins the election, and then some ballots are altered in such a way that the position of Alice is raised on some of the ballots without changing the order of the other candidates, then Alice should still win.

*any*reasonable voting system -- I wouldn't trust a voting system that violated them. But

*no*voting system can satisfy both of them, a result known as “Arrow’s Impossibility Theorem”. In a nutshell, Arrow’s Theorem shows that there is no perfect voting system when you have more than two candidates -- the best you can do is to try to find the least bad system.

## 5 comments:

What was the departmental application?

I'm not at liberty to say more than I've said in the post.

Sounds like a three-body problem.

It's amazing how many problems go from trivial to unsolvable when N goes from 2 to 3.

Fermat left a pretty little mess behind by making N>2.

In Mexico there are four main parties and a bunch of small ones, and all or some can run candidates for president. The winner is whoever gets the most votes, regardless of whether or not they obtain a majority. As you'd expect, the last three presidents had a plurality only.

Curiously, past one major temper tantrum in 2006, this has caused no major problems, and no calls for a second round or a ranking system.

Post a Comment