And the Winner is Probably...

In Provably Probable Social Choice I talked about the Gibbard-Satterthwaite theorem and its somewhat depressing conclusion that no deterministic voting system can completely prevent dishonest/tactical voters from unfairly influencing elections. Also in that post, I compared this social choice theorem with a similar result in distributed computing, Byzantine Agreement. In both realms, it seems that randomness must be an essential ingredient in any full solution.

There are many good, efficient solutions to various distributed computing problems that are probabilistic in nature. But what about random voting? The very idea seems silly. But is it?

In fact there has been a good bit of recent research into probabilistic voting algorithms that is starting to yield some interesting results.  For example, weighted lottery voting basically puts all the votes into a hat and chooses one at random. The single ballot chosen determines the winner. Surprisingly perhaps, this simple probabilistic procedure may be a good way to elect legislatures with multiple representatives from multiple districts. One reason is that it is completely immune to tactical voting.

Suppose that, for a given weighted lottery election, candidate A has 60% of the votes, candidate B has 30%, candidate C has slightly less than 10% and candidate D has only a single vote. With this voting procedure, the favored candidate will probably win the election. But there is some chance A will lose in favor of B or C. And there is even a small chance that candidate D, with only a single vote, will win! I know what you're thinking — this isn't practical. But think what happens when we do this for each member of a legislature, say a hundred representatives, all elected from their individual districts using weighted lottery voting. In the end, the distribution of representatives will conform to the distribution of voters across all districts. Yes, there may be some anomalies in the state house, so to speak, but if you trust the laws of probability (and I do), the overall make-up of the legislature will reflect the opinions and expressed wishes of the electorate. Now, I don't know of anyone who has seriously suggested that weighted lotteries be used in real world elections, but it is nonetheless tantalizing to look at some of the practical advantages to be gained by doing so.

First, like most probabilistic algorithms in the field of distributed computing, this procedure is dirt simple. There is no tallying of votes, no backroom subjective judgement about which ballots to count and which to ignore, no arithmetic of any kind involved in determining who the winner is. You simply put all the ballots into a basket (physically or electronically), shake it up, and then have a good-looking spokesmodel choose the winner. This procedure will likely promote higher voter turnout. With most of the deterministic voting schemes in use today, a voter who finds herself in an extreme minority may decide to skip the whole voting hassle if she feels there is absolutely no way her vote will matter. With the probabilistic scheme, however, there is always a possibility her vote will not only matter, but completely determine the outcome of the election! Similarly, there will be higher candidate participation because this algorithm (unlike winner-take-all deterministic plurality algorithms) does not inherently favor a two-party system. It is always possible for a third party to win an election.

The most promising advantage of probabilistic voting schemes like this one is that they are impossible to "cheat." More precisely stated, the best way to get your favorite candidate to win is to actually vote for him. This is not the case with any deterministic voting algorithm if there are four or more candidates. You might say, well, cheating isn't very common because it's so hard for individual voters to devise effective cheating strategies. Not so. In fact, there is one kind of cheating that is especially widespread and particularly destructive: the gerrymander. Ruling parties, with the help of computer software, commonly re-draw district lines so as to minimize or completely remove the voting influence of those who would vote against them. This practice is completely legal, completely constitutional, and completely despicable. And it works solely because of our choice of voting systems. Perhaps the most egregious example of gerrymandering in the entire US occurs in my home town of Austin, Texas. In congressional District 25, shaped like the practice's namesake salamander, Austinites share a voting pool that stretches hundreds of miles to the South, all the way to the Mexican border. No one disagrees the only purpose for this strange arrangement is to cheat in the congressional elections. A probabilistic voting scheme, like weighted lottery voting, would completely eliminate the gerrymander. As long as districts contain an equal number of voters, as required by the Supreme Court, the ideological composition of the legislature will, with high probability, reflect the ideological distribution of the voters.

But this simple probabilistic voting scheme is only remotely practical for legislative-type elections, where the, perhaps, negative effects of an improbable choice of representative can be diluted by all the other members of the legislature. The method is ill-suited for executive elections where a single, powerful governor or president is chosen by chance. For those kinds of elections, you really want a probabilistic algorithm that usually honors the majority choice, if there is one, and steps in with a coin flip only when it needs to. One example of that sort of algorithm is called double range voting.

With this clever, though more complex, voting procedure, each voter casts two ballots (or one ballot with two sub-ballots), awarding preference points in a given range, say zero to five stars, to each of the candidates. The first range ballot is tallied to identify the first-, second-, and third-place winners. Usually, the first-place winner is chosen as the winner of the whole election and we're done. But there is a (tunably small) chance the algorithm will ignore the first-place choice and pick the winner to be one of the second- or third-place candidates instead. In that case, the second ballot is used to make the binary choice. Since binary choices are immune to the Gibbard-Satterthwaite limitation, there is no reason for voters to vote tactically on the second ballot, and since it isn't possible to know which candidates will be #2 and #3, the second ballot may just as well be a completely honest reflection of the voter's choices among all candidates. Obviously, this is not a mathematical proof, but I'm sure you get the idea. The outcome is, usually the majority candidate wins, but sometimes the second or third most favored candidate wins, and as reward for suffering this small uncertainty, the election becomes immune to tactical voting.

These and other probabilistic voting procedures all suffer the same drawback: lack of transparency. When the outcome of an election involves a random choice, how do you prove ex post facto that the choice was indeed random? If I randomly choose a number, say 42, how can I prove to you my choice was just as likely as any other integer? How do I prove that the good-looking spokesmodel didn't use sleight of hand to deliberately choose a certain ballot out of the basket? More practically, how do I prove that the computer-generated random selection was indeed, random? If I use a physical process to generate a random selection, like repeatedly flipping a "fair" coin, how can you be sure the coin was really fair? And for the deeply paranoid (or inquisitive) among us, how do we know there is even such a thing as randomness? Maybe everything in the universe is predictable, if you just have a big enough computer.

My next few posts will examine these kinds of questions from the points of view of computer science, physics, mathematics, and theology. Given the demonstrated importance of randomness in distributed computing and social choice, we should at least investigate whether it actually exists.