 |
Abstract: In November 2004, New Hampshire voted 50% to 49% in favor of John Kerry. Citing concerns about the Diebold voting machines used, Ralph Nader paid for a recount. But unlike the Florida fiasco of 2000, this recount caused little change. Should we have expected it to?
Suppose that in an election between two parties, the voters vote independently and uniformly at random. Further suppose that there is an automatic recount in which each vote is changed independently with probability epsilon. What is the probability that the recount affects the outcome of the election? And how does this change under different voting systems (simple majority, electoral college, etc.)?
In this talk I will describe a new theorem showing that, in some sense, simple majority is the voting system that is stablest under recount noise. I will also describe several applications of this result, to such diverse fields as combinatorics, algorithmic complexity, and metric space embeddings.
This talk will be accessible to graduate students.
|