Friday, January 02, 2009

Randomness in Voting

Every voting scheme has the property that in some scenario a change of a single vote can change the outcome. When a major election has a very close result, like the current senate race in Minnesota or the 2000 presidential race in Florida, every vote gets scrutinized very carefully and the process can drag out for months.

This scrutinization ignores the randomness factor. Some people got stuck in traffic or maybe had some emergency that prevented them from voting. Some people went to the wrong voting area or their registration got lost. Some people just plain filled in the wrong oval, voting for the wrong candidate. These problems are rare and roughly cancel themselves out but in a very close election like Minnesota the randomness greatly outweighs the disputed ballots. Yet because of the hard cut-off the scrutinized ballots get the most attention.

I suggest we eliminate the hard-cut off by adding our own randomness. For simplicity suppose we had two candidates, Al and Norm, who received x and y votes respectively. We flip z=x+y uniform random coins. If the number of heads is at most x we declare Al the winner and Norm the winner otherwise. If x > z/2+ 10 z1/2 then this process would make Al the winner almost all the time. But as x and y get very close the probability that Al wins approaches 1/2. Since a change of a few disputed votes won't affect the probability dramatically, we won't have so many battles over so little.

6 comments:

  1. In http://arxiv.org/abs/cs/0503039 (Section 3), Leonid Levin makes a similar point.

    ReplyDelete
  2. Then scrutinization would consist of carefully checking each flipped coin to determine if it was heads or tails, with protests involving those coins that have nicks or are scuffed (possibly indicating bias). In the worst case, each coin would have to be tested for "fairness", with protests being lodged against the use of coins which flipped 101-99.

    ReplyDelete
  3. At least one benefit of this idea would be increased funding for research on pseudorandomness :)

    ReplyDelete
  4. Lol imagine of Al receives 90% of the votes, but ends up losing the coin flip. I imagine the population would be pretty angry ...

    ReplyDelete
  5. Your system presupposes only two candidates (or only two candidates of significance)...how do you fairly treat third candidates? Particularly in circumstances such as those of Minnesota; where the vote is extremely close between two candidates with the third candidate receiving 15% of the vote.

    ReplyDelete
  6. @Lance: I think this is pretty brilliant. I thought of it again because just now, 6 months after you posted this, the Minnesota election was *finally* decided.

    @Anonymous: I think it generalizes ok. Each vote is a little pie spinner with the candidates getting a fraction of the pie corresponding to their fraction of the vote. There's now a negligible chance that the third-party candidate with 15% of the vote will have a plurality of the spinners land on him/her.

    ReplyDelete