Decisive Margins in Differentially Private Voting

• URL: http://arxiv.org/abs/2608.18772v1
• Date: Wed, 19 Aug 2026 10:29:19 GMT
• Title: Decisive Margins in Differentially Private Voting
• Abstract summary: 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.<n>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)
• Score: 20.175634288058166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  This paper introduces a novel proof technique based on a multi-player communication game.<n>We show that winning this communication game requires transmitting information proportional to the number of over-active users.<n>We show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
  arXiv  Detail & Related papers  (2026-02-12T17:49:07Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections.<n>The margin of victory, or simply'margin', is the smallest number of ballots that need to be manipulated to alter the set of winners.<n>Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
  A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead.
  arXiv  Detail & Related papers  (2024-10-22T18:33:02Z)
• Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise [7.110450972801578]
  We consider the problem of private distributed multi-party multiplication.<n>It is well-established that Shamir secret-sharing coding strategies can enable perfect information-theoretic privacy in distributed computation.
  arXiv  Detail & Related papers  (2023-09-28T02:13:13Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• Successive Refinement of Privacy [38.20887036580742]
  This work examines how much randomness is needed to achieve local differential privacy (LDP) A motivating scenario is providing multiple levels of privacy to multiple analysts, either for distribution or for heavy-hitter estimation. We show that we cannot reuse random keys over time while preserving privacy of each user.
  arXiv  Detail & Related papers  (2020-05-24T04:16:01Z)
• Bounding, Concentrating, and Truncating: Unifying Privacy Loss Composition for Data Analytics [2.614355818010333]
  We provide strong privacy loss bounds when an analyst may select pure DP, bounded range (e.g. exponential mechanisms) or concentrated DP mechanisms in any order. We also provide optimal privacy loss bounds that apply when an analyst can select pure DP and bounded range mechanisms in a batch.
  arXiv  Detail & Related papers  (2020-04-15T17:33:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.