Least surprise in elections

We have seen that it's not easy to collect several players into teams that have well-defined strength. Such surprises come up even when we're not dealing with teams. Indeed, they happen even in seemingly straightforward situations such as elections.

Suppose, for example, we have two candidates running for office, and every voter gets to vote for a single candidate. The winning candidate will obviously be the one who received the most votes, and it hard to argue that this state of affairs is anything but fair.

Unfortunately, adding even one more candidate makes the situation much more complicated. Suppose, for example, that we have candidates A1, A2, and B, so named because A1's position is almost identical to A2's position (and, of course, both A1 and A2 are very different from B). Suppose that 40% of the voters support B and 60% would be happy with either A1 or A2.

What would you expect the election results to be? In the absence of any reason to choose A1 or A2, a reasonable result would be 30% for A1, 30% for A2, and 60% for B. B wins by a landslide even though either of the other candidates would be preferred by more than half the voters.

One solution to this problem is for A1 and A2 to get together and decide that they don't both need to be running. Instead, one of them can withdraw in favor of the other, on the assumption that doing so will prevent B from being elected. Of course, in real life, both A1 and A2 are likely to say "You first," so this suggestion works better in theory than in practice.

Another possible solution is for a third party to suggest to voters that if they are thinking of voting for A2, they would do better to vote for A1 instead. That way, they get a candidate who is almost as good from their viewpoint, and they avoid electing B. If A1 and A2 are truly indistinbuishable, this is a fine idea. But what happens if A1 and A2 are subtly but significantly different? Now a voter who supports A2 will be under pressure to vote insincerely--that is, to vote for someone other than the favorite candidate in order to maximize the desirability of the election resuts.

There are many voting schemes intended to avoid surprises such as this one. To my knowledge, none of them work perfectly in all situations. That is, they all cause surprises of one kind or another in some circumstances.

If we can't avoid surprises in a situation as simple as voting, what makes us think we can avoid them in programming-language design?

Posted by Andrew Koenig at 02:48 PM  Permalink