Search papers, labs, and topics across Lattice.
This paper investigates the impact of differential privacy on voting outcomes, particularly focusing on how the noise introduced can skew results in close elections. By analyzing various voting rules, the authors establish both upper and lower bounds on the margin of victory necessary for private mechanisms to yield the same winner as non-private methods. Notably, they reveal that achieving these guarantees for the Single Transferable Vote (STV) is computationally intractable unless NP is contained in BPP, highlighting a critical trade-off between privacy and utility in voting systems.
A striking trade-off emerges: ensuring differential privacy in voting can render computationally simple tasks intractable, especially for STV.
Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close. We study how precise central differential privacy and local differential privacy can be for common voting rules, including Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable Vote (STV). Our measure of precision is the margin of victory needed for a private mechanism to return the same winner as the non-private rule with high probability. We give private algorithms for publishing the winner and prove upper bounds on the required margin for these algorithms. We also prove lower bounds showing that nontrivial margins are necessary; many of these bounds match the corresponding upper bounds up to logarithmic factors. For STV, an information-theoretic upper bound matches the lower bound, but we prove that this guarantee cannot be achieved in polynomial time unless NP $\subseteq$ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.
