Suppose we model n votes in an election between two candidates as n i.i.d. uniform random variables in {-1,1}, so that 1 represents a vote for the first candidate, and -1 represents a vote for the other candidate. Then, for each vote, we flip a biased coin (with fixed probability larger than 1/2 of landing heads). If the coin lands tails, the vote is changed to the other candidate. In an election where each voter has a small influence on the election’s outcome, and each candidate has an equal chance of winning, the majority function best preserves the election’s outcome, when comparing the original election vote to the corrupted vote. This Majority is Stablest Theorem was proven in 2005 by Mossel-O’Donnell-Oleszkiewicz. The corresponding statement for elections between three or more voters has remained open since its formulation in 2004 by Khot-Kindler-Mossel-O’Donnell. We show that Plurality is Stablest for elections with three candidates, when the original and corrupted votes have a sufficiently small correlation. In fact, this result is a corollary of a more general structure theorem that applies for elections with any number of candidates and any correlation parameter.

(joint with Alex Tarter)

Zoom ID: 978 1848 8609 (opens 15 min prior to the meeting)
Passcode: last 4 digits of the zoom id in the reverse order