Decisive Margins in Differentially Private Voting

Decisive Margins in Differentially Private Voting Quentin Hillebrand1 , Pasin Manurangsi2 , Vorapong Suppakitpaisarn3 , Phanu Vajanopath4

arXiv:2608.18772v1 [cs.DS] 19 Aug 2026

1

University of Copenhagen, Denmark 2 Google Research, Thailand 3 The University of Tokyo, Japan 4 University of Wrocław, Poland

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 ⊆ BPP. This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and utility.

1

Introduction

Differential privacy has become a standard formal framework for protecting individual-level data in statistical analysis. It requires that the published result of an algorithm reveal only limited information about any one individual’s record, even to an adversary with arbitrary side information. This guarantee is especially important when the data being aggregated is sensitive, because it allows useful population-level information to be released while limiting the privacy risk to each participant (Dwork et al. 2006b; Dwork and Roth 2014). Local differential privacy (LDP) strengthens this protection by removing the need for a trusted central curator. In the local model, which goes back to randomized response and was later formalized in the differential-privacy literature, each individual randomizes her own record before sending any message to the aggregator (Warner 1965; Kasiviswanathan et al. 2011; Erlingsson, Pihur, and Korolova 2014). This makes LDP particularly attractive in settings where the data collector should not see raw user data, at the cost of injecting more noise than in the central model. Voting is a natural setting where these privacy guarantees are important. A single ranking can reveal political views, strategic preferences, or institutional priorities, so publishing election information without privacy can expose sensitive

individual preferences. Prior work has therefore studied privacy for voting from several perspectives, including LDP vote aggregation, differentially private rank aggregation, the privacy of commonly used voting rules, and differentially private voting rules (Wang et al. 2019; Alabi et al. 2022; Hillebrand et al. 2026; Liu et al. 2020; Li et al. 2023). For voting, however, privacy noise has a particularly sharp effect: a small amount of noise can change the declared winner when the election is close. Thus, even if the non-private voting rule is easy to evaluate, a private mechanism may return an erroneous winner unless the election is sufficiently decisive. Our contributions. This paper asks how decisive an election must be before private winner publication is reliable. We study this question for central differential privacy and local differential privacy, focusing on common voting rules such as Plurality, Condorcet, Maximin, Plurality with Runoff, and Single Transferable vote (STV). Our measure of precision is the margin of victory (MoV) (Xia 2012; Bhattacharyya and Dey 2021), the minimum number of voters whose preferences must be changed to alter the result. In other words, we study the following question: What is the smallest MoV required for an election, so that the correct outcome can be differentially privately published with high probability? Table 1 summarizes the main results. Our first contribution is a set of private algorithms for publishing election winners together with upper bounds on the margin they require. In the central model, the exponential mechanism gives a general logarithmic-MoV guarantee. For rules where the relevant margin quantities can be computed efficiently, this also yields efficient algorithms; for Maximin, we use a polynomial-time approximation for the exact MoV. In the local model, where each voter privatizes their own message before aggregation, we give non-interactive and interactive protocols based on noisy plurality scores, pairwise statistics, and STV elimination statistics. Our second contribution is a set of lower bounds showing that nontrivial margins are necessary. In the central model, packing arguments give matching logarithmic lower bounds for broad classes of rules. In the local model, testing and marginal-release reductions imply that the usefulness thresh-

Setting Central DP upper bounds Central DP lower bounds Non-interactive LDP upper bound Non-interactive LDP lower bound Interactive LDP upper bound Interactive LDP lower bound

Plurality O(log m) Ω(log m) √ Õ( n) √ Ω̃( n) √ Õ( n) √ Ω̃( n)

Maximin O(log m) Ω(log m) √ Õ(m n) √ Ω̃(m n) √ Õ(m n) √ Ω̃( n)

Runoff O(log m) Ω(log m) √ Õ(m n) √ Ω̃(m n) √ Õ( n) √ Ω̃( n)

STV O(log m)† Ω(log m) √ Õ(2m/2 n) √ √ Ω̃(min{n/m, 2Ω( m) n}) 2√ Õ(m n) √ Ω̃( n)

Condorcet O(log m) Ω(log m) √ Õ(m n) √ Ω̃(m n) √ Õ( mn) √ Ω̃( n)

Table 1: Summary of margin-of-victory thresholds for private winner publication. Here n is the number of voters and m is the number of candidates. Dependencies on the privacy budgets and failure probabilities are omitted for brevity. The STV central-DP upper bound marked by † is information-theoretic; under NP ⊈ BPP, it cannot be achieved in polynomial time. √ old must grow with n, up to logarithmic factors, for several rules. Many of these lower bounds match the corresponding upper bounds up to logarithmic or rule-dependent factors. For LDP, a highlight of our results is “the cost of noninteractivity”, a provable privacy–interactivity trade-off for Condorcet, Plurality with Runoff, and STV. For these rules, non-interactive algorithms require a larger margin of victory than interactive algorithms. The separation is especially striking for STV: interaction improves the dependence on the number of candidates superpolynomially. In the nonsatu√ √ rated regime, the non-interactive lower bound is 2Ω( m) n, e 2 √n). This is a whereas the interactive upper bound is O(m significant departure from the non-private setting, where a voter can report her entire ranking in a single round. For central DP, the most remarkable case among our results is once again STV. Information-theoretically, the generic central DP upper bound matches the lower bound. Computationally, however, this precision is out of reach: assuming NP ⊈ BPP, no polynomial-time central-DP algorithm can achieve the same high-precision guarantee for STV (Theorem 3.3). This gives a rare example of a computationally tractable task that becomes intractable when one simultaneously requires differential privacy and high-precision recovery of the non-private result. Previously, such results are only known in specific settings such as synthetic data generation and high-probability learning tasks (Dwork et al. 2009; Ullman and Vadhan 2020; Georgiev and Hopkins 2022; Ghazi et al. 2026). We hope that our proof–which relates NP-hardness of approximation to the intractability of DP algorithms–can contribute to further study on this broader line of research. Organization. We next provide preliminaries. Then, we present our results for central DP in Section 3. Our LDP results are separated into two sections, Section 4 for noninteractive LDP and Section 5 for interactive LDP. Due to space constraints, we provide proof sketches in the main body and full proofs are deferred to the appendix.

2 2.1

Preliminaries

Voting

Let C = {c1 , . . . , cm } be the candidate set, and ΠC be the set of all rankings of the candidates. A preference profile is a tuple π = (π1 , . . . , πn ) ∈ ΠnC , where πi is voter i’s ranking. A voting rule is a function r : Π∗C → C ∪ {⊥} that returns either a winning candidate or ⊥ when no winner exists.

Two profiles π = (π1 , . . . , πn ) and π ′ = (π1′ , . . . , πn′ ) are k-neighbors if they differ in at most k voters’ rankings: there exists S ⊆ [n] with |S| ≤ k such that πi = πi′ for every i∈ / S. We call 1-neighbors simply neighboring profiles. Voting rules. We consider the following voting rules. • Plurality: For a profile π = (π1 , . . . , πn ) and each candidate c ∈ C, let scoreplu (c) be the number of voters who rank c first. Plurality outputs a candidate c⋆ ∈ arg maxc∈C scoreplu (c). • Scoring-based rules: A scoring rule is parameterized by a vector s = (s1 , . . . , sm ) with s1 ≥ · · · ≥ sm ≥ 0. A candidate ranked in position j by a voter receives score sj , and the candidate withPthe largest total score wins. n Pm Formally, scores (c; π) := i=1 j=1 sj · 1[πi (j) = c]. Plurality is the scoring rule with s = (1, 0, . . . , 0). Other examples include Borda, with s = (m−1, m−2, . . . , 0), and Veto, with s = (1, 1, . . . , 1, 0). • Maximin: For candidates a, b ∈ C, let Nπ (a ≻ b) be the number of voters who rank a above b, and define the pairwise margin Dπ (a, b) = Nπ (a ≻ b) − Nπ (b ≻ a). The maximin score of a is scoremaximin (a) = minb∈C\{a} Dπ (a, b). Maximin outputs a candidate with maximum maximin score. • Condorcet: The Condorcet rule outputs a candidate c if Dπ (c, a) > 0 for every a ∈ C \ {c}; if no such candidate exists, it outputs ⊥. • Plurality with Runoff: Plurality with Runoff proceeds in two rounds. In the first round, we compute each candidate’s plurality score scoreplu (c) and select the two candidates with the highest plurality scores; denote them by c1 , c2 . In the second round, we conduct a head-tohead majority vote between c1 and c2 : we output c1 if Nπ (c1 ≻ c2 ) > Nπ (c2 ≻ c1 ), and otherwise output c2 . • Single Transferable Vote (STV): To define STV, it is convenient to introduce a notation: for every set S ⊆ C, let π|S ∈ ΠS denote the preference π when restricted to S. The STV rule eliminates one candidate per round. Initially, A = C. In each round, we count first-place votes in the restricted profile (π1 |A , . . . , πn |A ) and eliminate a candidate with the fewest such votes. After m − 1 eliminations, the remaining candidate wins. In all rules above, we assume that ties are broken based on some prespecified order on the candidates. For our work, a specific order is unimportant, as long as it is consistent.

Margin of Victory. Margin of victory (e.g. (Xia 2012)), a standard measure for decisiveness (or stability) of an election, will play a central role in our work. Specifically, the margin of victory is the number of voters required to change the outcome of an election, as defined more formally below. Definition 2.1 (Margin of Victory (MoV)) Given a preference profile π and a voting rule r, the margin of victory, denoted by MoV(π, r), is the smallest integer k for which there exists a k-neighbor π ′ of π such that r(π ′ ) ̸= r(π). Xia (2012) show that MoV(π, r) can be computed in polynomial time when r is Plurality, Condorcet, a scoring rule, or Plurality with Runoff. In contrast, it is known that computing MoV is NP-hard for Maximin and STV (Xia 2012; Bartholdi and Orlin 1991). As explained below, differential privacy (DP) requires the output to be random. We desire algorithms that output the correct winner with high probability as long as MoV is large. This is captured in the usefulness definition below. Definition 2.2 ((τ, γ)-usefulness) We say that an algorithm M is (τ, γ)-useful for voting rule r if, for all π such that MoV(π, r) ≥ τ , we have Pr[M(π) = r(π)] ≥ 1 − γ. We also refer to τ as the (γ-)decisive margin for M.

2.2

Differential Privacy

We next recall the definition of (central) differential privacy, adapted to our voting setting. Definition 2.3 (DP (Dwork et al. 2006b,a)) An algorithm M is ε-DP if, for all neighboring profiles π, π ′ and all output events O, Pr[M(π) ∈ O] ≤ eε · Pr[M(π ′ ) ∈ O]. One of the most widely-used tools in DP is the exponential mechanism (McSherry and Talwar 2007), which allows us to optimize any score function. The mechanism description and its utility are summarized below. Definition 2.4 (Exponential mechanism) Let O be a finite set, and let q : ΠnC × O → R be a score function. Define the sensitivity of q as ∆(q) := maxπ∼π′ , a∈O q(π, a) − q(π ′ , a) where π ∼ π ′ denotes neighboring profiles. For ε > 0, the exponential mechanism Mexp outputs an element  a ∈ O with probability Pr[Mexp (π) = a] ∝ exp

ε·q(π,a) 2 ∆(q)

. Then Mexp is ε-DP.

Theorem 2.5 Define OPT(π) := maxa∈O q(π, a). Then, for any β ∈ (0, 1), with probability  at least 1 − β, q(π, Mexp (π)) ≥ OPT(π) − 2∆(q) ln ε

2.3

|O| β

.

Local Differential Privacy

We use the standard local model of differential privacy (Kasiviswanathan et al. 2011). In the non-interactive model, each voter applies a private randomizer on their own data and send the results to the aggregator. Definition 2.6 (Non-interactive ε-LDP) A local randomizer R satisfies ε-LDP if, for all rankings π, π ′ and all output events O, Pr[R(π) ∈ O] ≤ eε Pr[R(π ′ ) ∈ O]. A noninteractive ε-LDP algorithm sends each voter a randomizer

fixed before any messages are observed and receives one message from each voter. In other words, it can be written M(π) = A(R1 (π1 ), . . . , Rn (πn )), where each Ri is an ε-LDP randomizer and A is the aggregator. On the other hand, the interactive setting allows the voters and the aggregator to perform arbitrary communication protocol. The privacy constraint here is that the transcript of the protocol (which includes all messages from all the parties) has to be differentially private. Definition 2.7 (Interactive ε-LDP) An interactive local protocol accesses the profile only by querying voters. In each round, as a function of the transcript so far, it chooses a set of voters and randomizers to apply to those voters’ rankings. The transcript is the ordered record of the public randomness, queried voters, selected channels, and exchanged messages. Let Tr(π) denote the full transcript on profile π. The protocol is ε-LDP if, for every voter i, every pair of profiles π, π ′ differing only in voter i’s ranking, and every transcript event O, Pr[Tr(π) ∈ O] ≤ eε Pr[Tr(π ′ ) ∈ O]. For the vector releases in Sections 4 and 5, we use the LDP mean-estimation randomizer of Duchi, Jordan, and Wainε ε wright (2018). We 1
write κε = (e + 1)/(e − 1), which is Θ max ε , 1 for all ε > 0. Lemma 2.8 (Duchi, Jordan, and Wainwright 2018) There is a constant CDJW with the following property. For every x ∈ Rd satisfying ∥x∥2 ≤ r, the DJW randomizer RDJW (x; r, ε) is ε-LDP, and is unbiased, i.e. E[RDJW (x; r, ε)] = x. Moreover, for every unit vector u, the centered projection ⟨RDJW (x; r, ε) − x, u⟩ is sub-Gaussian with parameter at most CDJW κε r.

3

Central Differential Privacy

In this section, we describe our algorithms and lower bounds for the central DP model (Definition 2.3).

3.1

Algorithms

Generic algorithm. We start by describing a mechanism that works for any voting rule r. Our mechanism applies the exponential mechanism (Definition 2.4) with O = C ∪ {⊥} and score function  0, if a = r(π), q(π, a) := (1) − MoV(π, r), otherwise. For neighboring profiles π and π ′ , we have | MoV(π, r) − MoV(π ′ , r)| ≤ 1. Moreover, r(π) ̸= r(π ′ ) can occur only when MoV(π, r) ≤ 1. Therefore, ∆(q) ≤ 1. Thus, a direct application of Theorem 2.5 yields the following. Theorem  3.1 For any ε > 0,there exists an ε-DP algorithm that is 2 log((m+1)/γ) + 1, γ -useful for all γ ∈ (0, 1/2). ε The theorem is only information-theoretic: it is efficient only when the MoV score can be evaluated efficiently. As discussed in Section 2.1, this is the case for Plurality, Condorcet, scoring rules, and Plurality with Runoff.

An efficient algorithm for Maximin. For Maximin, exact MoV computation is NP-complete. Nevertheless, the approximation of (Xia 2012, Theorem 12) gives a useful surrogate. If w and w′ have the largest and secondlargest maximin scores, respectively, and r is Maximin, write ∆mm := scoremaximin (w) − scoremaximin (w′ ). Accounting for our fixed tie-breaking rule adds at most one vote to the usual two-approximation guarantee, so MoV(π, r) − 1 ∆mm ≤ ≤ MoV(π, r). (2) 2 4 Importantly, this surrogate ∆mm can be efficiently computed. Thus, we may apply the exponential mechanism to the surrogate score, defined below, instead.  0, if a = r(π), (3) q ′ (π, a) = −∆mm /4, otherwise. Changing one vote changes every maximin score by at most 2, and hence changes ∆mm by at most 4 while the winner remains fixed. If the winner changes, both the old and new top-two gaps are at most 4, since the old and new winners’ scores can move by at most 2 each. It follows in both cases that ∆(q ′ ) ≤ 1. Thus, as above, the exponential mechanism yields an efficient algorithm for Maximin: Theorem 3.2 For any ε > 0, there exists  a polynomial-time  ε-DP algorithm for Maximin that is 4 log(m/γ) + 2, γ ε useful for all γ ∈ (0, 1/2). Computational barrier for STV. For STV, the MoV is NP-hard to compute. Thus, we cannot directly instantiate Theorem 3.1 to get an efficient algorithm. One might hope– via some surrogate score similar to Maximin or some other means–that we can devise an efficient algorithm for STV. Unfortunately, we show that this is impossible under a standard complexity assumption, as stated more precisely below. Theorem 3.3 Suppose that NP ⊈ BPP. For any positive constants C1 , C2 , C3 , ε and γ ∈ (0, 1) with C3 > 4C1 , there is no ε-DP (nm)O(1) -time algorithm that is
simultaneously (C1 log(m)/ε, γ)-useful and mC2 , 1/mC3 -useful. As stated in the introduction, this is one of the few examples of computational problems for which DP makes it intractable. Below we sketch the proof of this theorem. Hardness of approximation of MoV. As a first step, we show that it is NP-hard to approximate MoV of STV to within a factor of n1−ζ for any constant ζ > 0. This factor is (essentially) optimal since a trivial n-approximation exists. Moreover, our result is a direct improvement over that of Bartholdi and Orlin (1991) who proved an NP-hardness of approximation with a factor of 2. Computational hardness for DP algorithm. Our inapproximability result seems ostensibly unrelated to privacy. Nevertheless, we use this to prove Theorem 3.3 as follows. Assume for the sake of contradiction that an algorithm M in Theorem 3.3 exists. We use it to estimate the MoV of STV as follows by running M(π, r) many times. If every run returns the original winner, then we know that the MoV

should be large. Meanwhile, if at least one run returns a different winner, then we know that the MoV should be small. To make this proof work, we need a rather precise set of parameters, which we specify in the appendix.

3.2

Lower Bounds

We now prove matching central-DP lower bounds using a packing argument (Hardt and Talwar 2010). Such an argument requires many nearby profiles with different winners, as formalized below. Assumption 3.4 There exists a constant κ > 1 such that, for every t ∈ N, there are profiles π 1 , . . . , π m satisfying: 1. r(π i ) = ci for all i ∈ [m], 2. MoV(π i , r) ≥ t, 3. π i , π i′ are (κt)-neighbors for all i, i′ ∈ [m]. Under the above assumption, the standard packing lower bound proof (Hardt and Talwar 2010) yields the following: Lemma 3.5 Let ε > 0 and γ ∈ (0, 0.2). Suppose that r satisfies Assumption 3.4. Then, any ε-DP algorithm Mk that j ln(0.4m/γ) is (τ, γ)-useful for rule r must satisfy τ ≥ . κε Note here that, when κ is a constant, this asymptotically matches our upper bound (Theorem 3.1). For the remainder of this section, we show that every rule r considered in our work satisfies Assumption 3.4 for a constant κ. Rules satisfying the majority criterion. A voting rule satisfies the majority criterion if any candidate ranked first by more than half of the voters must win. By simply taking each π i to be a profile with 2t voters all of whom rank ci first, we can immediately show: Lemma 3.6 Any voting rule that satisfies Majority Criterion also satisfies Assumption 3.4 with κ = 2. Plurality, Condorcet, Maximin, Plurality with Runoff, and STV all satisfy the majority criterion, so Lemmas 3.5 and 3.6 imply the following asymptotically tight lower bound. Corollary 3.7 For any ε > 0 and γ ∈ (0, 0.2), any ε-DP algorithm M that is (τ, γ)-useful for Plurality, Condorcet, Maximin, Plurality with Runoff, or Single Transferable Vote must satisfy τ = Ω(ln(m/γ)/ε). Scoring-based rules. Some scoring rules, such as Veto , do not satisfy the majority criterion, so the previous construction does not apply. We instead build a profile with many voters and then carefully perturb it to favor any prescribed candidate. By such a construction, we can show: Lemma 3.8 Any non-trivial1 scoring rule satisfies Assumption 3.4 with κ = 4. Combining Lemmas 3.5, 3.8 yields the tight lower bound. Corollary 3.9 For any ε > 0 and γ ∈ (0, 0.2), any ε-DP algorithm M that is (τ, γ)-useful for any non-trivial scoring rule must satisfy τ ≥ Ω(ln(m/γ)/ε). 1 We say that a scoring rule is non-trivial if the scoring vector s = (s1 , . . . , sm ) satisfies s1 ̸= sm .

3.3

Rules Beyond Our Framework

While our  framework above provides tight bounds of  log(m/γ) for all rules of interest in this paper, we reΘ ε mark that there  are in fact  rules whose optimal decisive marlog(m/γ) gin is not Θ . One such rule is the following “near ε unanimity” rule parameterized by n0 , τ0 with n0 > 2τ0 : • When n ≤ n0 , we always declare a tie, i.e., r(π) = ⊥. • When n > n0 , the winner is the candidate that is most preferred by at least n − τ0 voters. If no such candidate exists, declare a tie. This rule admits an ε-DP algorithm with (oγ,ε (log m), γ)usefulness. The algorithm privately counts first-place votes using discrete Laplace noise and then applies the rule. For sufficiently large n0 and τ0 ≥ Θ(log(m)/ε), the relevant scores are far from the decision boundary except in a constant-width band, yielding (Oγ,ε (1), γ)-usefulness.

4

Non-Interactive Local Differential Privacy

We next consider non-interactive LDP (Definition 2.6). We remark that all of our (interactive or non-interactive) LDP algorithms are efficient, and we will not state this explicitly in the theorem statements.

4.1

Plurality

We start by the Plurality rule, which has the simplest algorithm and lower bound proof. Upper bound. The Plurality algorithm is simply the LDP histogram algorithm2 . More specifically, each voter privatizes the one-hot vector of their favorite candidate using the DJW randomizer. That is, if voter i ranks wi first, let f (πi ) = vi ∈ {0, 1}m where vi,wi = 1 and vi,c = 0 for every c ̸= wi . Since ∥vi ∥2 = 1, the voter can release ṽi = RDJW (vi ; 1, ε) while satisfying ε-LDP. The aggregator sums P the noisy vectors and outputs w̃ ∈ arg maxcj ∈C i∈[n] ṽi,j . The following theorem follows from the sub-Gaussian guarantee in Lemma 2.8. Theorem 4.1 There is a non-interactive εLDP algorithm for Plurality which is     p  O max 1ε , 1 · n log(m/γ) , γ -useful for ε > 0 and γ ∈ (0, 1/2). Lower bound. A direct two-point mean-testing reduction gives the following non-interactive LDP lower bound, which asymptotically matches the upper bound for γ < 1/mΩ(1) and ε ≤ Θ(1). Theorem 4.2 There are constants C ′ , c, ε0 > 0 such that the following holds for Plurality. For 0 < ε ≤ ε0 and 2 1 e−cnε ≤ γ < 10 , no non-interactive ε-LDP algorithm is ′p C n log(1/γ), γ -useful. ε 2

We state our algorithm using the randomizer of (Duchi, Jordan, and Wainwright 2018) to unify the notations across all the results. However, other LDP histogram algorithms, e.g. RAPPOR (Erlingsson, Pihur, and Korolova 2014), also work here.

Proof sketch. Draw every vote independently from one p of two binary distributions whose means are ±Θ( log(1/γ)/(nε2 )). With probability at least 1 − γ, the resulting Plurality election has the corresponding winner and p margin Ω( n log(1/γ)/ε). A mechanism useful below this threshold would therefore distinguish the two distributions with error O(γ). The strong data-processing inequality for local privacy (Duchi, Jordan, and Wainwright 2018) and the Bretagnolle–Huber testing bound rule this out. □

4.2

Condorcet, Maximin, Plurality with Runoff

Next, we consider Condorcet, Maximin, Plurality with Runoff. For these rules, the decisive margin increases √ (compared to Pluraity) increases by a factor of O( m). This increase is due to the fact that each voter now needs to privatize the pairwise election, which increases the ℓ2 norm of √ the contribution vector to O( m), as formalized below.
Upper bounds. Fix an orientation of the q = m 2 unordered candidate pairs. For a ranking π, define its pairwise vector P (π) ∈ {−1, 1}q by Pa,b (π) = 1[π(a) ≻ π(b)] − 1[π(b) √ ≻ π(a)] for each oriented pair (a, b). Thus ∥P (π)∥2 = q, and the sum of the (a, b) coordinates over all voters is exactly the pairwise margin Dπ (a, b). √ Each voter releases Zi = RDJW (P (πi ); q, ε), using Lemma 2.8. This is a ε-LDP release. The aggregator sets Pn e Pe = i=1 Zi and reads D(a, b) from the appropriately e signed coordinate of P . The estimate is unbiased, and independence across voters together with 2.8 gives h i  Lemma t2 e Pr |D(a, b) − Dπ (a, b)| > t ≤ 2 exp − 2C 2 κ2 qn . DJW ε In the runoff algorithm we also use the DJW-privatized plurality vector ṽ = (ṽi )i∈[m] from Section 4.1, with privacy budget ε/2; the DJW pairwise release also uses budget ε/2. By composition, their joint release is ε-LDP. Condorcet: The aggregator outputs a candidate c if e a) > 0 for every a ∈ C \ {c}, and outputs ⊥ if no D(c, such candidate exists. Maximin: The aggregator computes each candidate’s noisy maximin score s] coremaximin (a) := e b), and outputs the candidate with maximinb∈C\{a} D(a, mum score. Plurality with Runoff: Based on the vector ṽ, the aggregator selects the top two candidates c, c′ with the highest noisy plurality scores. For the second stage of the runoff rule, e c′ ) the aggregator computes the noisy pairwise margin D(c, e c′ ) > 0, and c′ otherwise. and outputs c if D(c, Thus, we obtain the following theorem from the subGaussian guaranty in Lemma 2.8. Theorem 4.3 The non-interactive algorithms described above for Condorcet, Maximin, and Plurality with Runoff √ are ε-LDP and (τ, γ)-useful for τ = Õε,γ (m n). Lower bounds. To prove (nearly) matching lower bounds, we reduce from the two-way marginal problem: Definition 4.4 (k-way marginal) For a Boolean dataset X = (x1 , . . . , xN ) where x1 , . . . , xN ∈ {0, 1}d and A ⊆

[d] with |A| = k, the k-way marginal indexed by A is the PN Q conjunction count QA (X) = i=1 j∈A xi,j . Our lower bound reduces non-interactive LDP release of all normalized two-way marginals to private winner recovery. A key point in our reduction for non-interactive algorithms is that we can reuse privatized values to answer multiple queries3 . At a high-level, this framework proceeds as follows4 : • For each xi , we create one data-dependent ranking πi which is then privatized to yi = Ri (πi ). • For each query A, do the following (possibly repeatedly): – We create additional query-dependent rankings ′ π1′ , . . . , πL and run the randomizer to get yj′ = Rj (πj ) ′ – From the combined output y1 , . . . , yN , y1′ , . . . , yL , we compute the winner of the election. – Use the winner to estimate QA (X). As mentioned earlier, we reuse the randomized responses y1 , . . . , yN multiple times to answer multiple queries. We defer the exact descriptions of the rankings to the appendix, but we sketch the high-level idea here. Roughly speaking, we think of each candidate cj as a coordinate j of the dataset. Our data-dependent rankings are constructed so that the head-to-head margin between cj and ck encodes P voters act as a “threshi xi,j xi,k . The query-dependentP olding query” that checks whether i xi,j xi,k ≥ τ for some threshold τ . If this is true, then cj is the winner; otherwise, ck is the winner. The margin of victory in the constructed election is proportional to the distance from the threshold. A nonadaptive scan of all fixed thresholds therefore recovers all two-way marginals under LDP. Combining this reduction with the known two-way marginal lower bound (in Theorem E.4) yields the following winner-recovery lower bound. Corollary 4.5 There are constants c, ε0 > 0 such that, for 0 < ε ≤ ε0 , every non-interactive ε-LDP algorithm for Condorcet, Maximin, or Plurality with Runoffthat is n (τ, γ)-useful √ o 2 2 e with γ ≤ c/(m n ) must satisfy τ = Ω min n, m ε n .

4.3

STV

Upper bound. For STV, the aggregator must know noisy plurality scores after every possible set of eliminations. Therefore, the ℓ2 norm of each contribution vector becomes √ O( 2m ) = O(2m/2 ), which results in such a blow-up factor in the decisive margin. More formally, let I := {(S, c) : S ⊆ C, |S| ≥ 2, c ∈ S} and define T (π) ∈ {0, 1}I by setting TS,c (π) = 1 if c is the highest-ranked candidate in S under π, and TS,c (π) = 0 otherwise. For each non-singleton set S, exactly one coordinate√ indexed by S equals one. Hence ∥T (π)∥2 = rT := 2m − m − 1. Each voter releases Zi = RDJW (T (πi ); rT , ε). By Lemma 2.8, this release is 3

This observation has been used before in non-private LDP lower bounds, e.g. in (Ghazi et al. 2023; Eden et al. 2025). 4 This description is simplified for the main body. E.g., in the actual reduction, we use two data-dependent rankings per one xi .

ε-LDP, unbiased, and has coordinatewise sub-Gaussian error with parameter at most CDJW κε rT . Our algorithm then simply follows the STV protocol, eliminating candidates one-by-one, where we use the above release to estimate the score of every remaining candidate. Theorem 4.6 The non-interactive algorithm described above STV is ε-LDP and (τ,  for  γ)-useful for τ = p 1 m/2 Õ max ε , 1 · 2 n log(1/γ) . Lower bound. Similar to above, we reduce from k-way marginal. We can now utilize a larger range of values of k, since the query-dependent rankings can be used to “select” the candidates eliminated in the first rounds. Specifically, we instantiate two extreme values of k below: k = 2 and k = Θ(m). The former yields a better dependency for large m, whereas the latter gives a better bound for small m. Corollary 4.7 There are constants c, ε0 > 0 such that, for 0 < ε ≤ ε0 , every non-interactive ε-LDP algorithm for Single Transferable Vote that is (τ, γ)-useful with γ ≤ e c/(mm/2 n2 ) must satisfy τ = Ω(max{L 2 , Lhigh }) where    √  √ m n n n Ω(√m) L2 = min n, , Lhigh = min , 2 . ε m ε We remark that, while we require the failure probability γ to be quite small, the dependency on γ in the upper bound in √ Theorem 4.6 is only O( log γ). Therefore, this only effects √ our upper bound by a factor of Õ( m). On the other hand, the more interesting remaining gap here is the 2O(m) term versus √ Ω( m) the 2 term in our upper and lower bounds, respectively. Closing this gap is an interesting open question.

5

Interactive Local Differential Privacy

We next consider the interactive LDP model (Definition 2.7). Unlike a non-interactive protocol, an interactive protocol can decide what to query next after seeing earlier private reports. This fits naturally with a few voting rules–including Plurality with Runoff, STV, and Condorcet–that already proceed in “rounds”. Our interactive protocols essentially mirror the description of these rounds, where we estimate only the statistics needed at the current round. This results in reduced noise (and decisive margins) compared to non-interactive LDP algorithms from the previous section.

5.1

Plurality with Runoff

Upper bound. The protocol first privately estimates all plurality scores using half of the privacy budget and selects the two noisy finalists. It then spends the remaining budget estimating their head-to-head scores and returns the noisy runoff winner. Thus, the second query depends only on the privatized first-stage output. Theorem 5.1 For every ε > 0 and γ ∈ (0, 1/2), there is an interactive ε-LDP algorithm  forPluralitypwith Runoff that  is 1 (τ, γ)-useful with τ = O max ε , 1 · n log(m/γ)

Proof sketch. With probability 1 − γ,p every score used in the two stages is within λ = O(κε/2 n log(m/γ)) of its true value. If the protocol errs, changing at most 2λ + 2 rankings either removes the true winner from the runoff or makes the noisy opponent reach the runoff and defeat it. □

5.2

STV

Upper bound. STV can be naturally implemented: In each of the m − 1 elimination rounds, the protocol privately estimates the plurality scores restricted to the remaining candidates and eliminates the candidate with the smallest noisy score. Each round uses privacy budget ε/(m − 1). The analysis uses the following structural fact. Consider any proposed STV elimination sequence that ends at a candidate other than the true winner. Then the margin of victory is at most the sum, over all rounds, of the proposed candidate’s plurality-score excess above the round minimum plus a quadratic term in the number of candidates. This gives the following result, where an O(m) factor is from the DP composition theorem and the other is due to the above fact–which accumulates the errors across rounds. Theorem 5.2 For every ε > 0 and γ ∈ (0, 1/2), there is an interactive for STV that is (τ, γ)-useful  ε-LDP algorithm  p m 2 with τ = O m + m · max ε , 1 · n log(m/γ) . Proof sketch. A union bound over all scores released along path gives simultaneous error λ =  the realized  p O κε/(m−1) n log(m/γ) . The eliminated candidate is within 2λ of the true round minimum. The tie-breaking choice therefore makes the preceding structural fact applicable, so an erroneous output can occur only when MoV(π, r) ≤ 2(m − 1)λ + O(m2 ). □

5.3

Condorcet

Upper bound. Our Condorcet protocol organizes the candidates into a knockout tournament. In each round, the remaining candidates are paired, and the protocol privately evaluates their head-to-head contests. After ⌈log2 m⌉ rounds, only one candidate remains. The protocol then uses one final round to verify that the surviving candidate defeats every opponent; otherwise it returns ⊥. The analysis relates pairwise margins to the MoV. If w is a Condorcet winner, the margin of victory is at most one plus w’s smallest head-to-head victory margin. If the outcome is ⊥, then, for any candidate c, the margin of victory is at most 1+3 log2 m plus three times the largest head-to-head margin by which another candidate defeats or ties c. Theorem 5.3 For every ε > 0 and γ ∈ (0, 1/2), there is an interactive ε-LDP algorithm for Condorcet voting thatis  p 1 (τ, γ)-useful with τ = Õ max ε , 1 · mn log(m/γ) Proof sketch. Each voter’s contribution in every batch √ has ℓ2 -norm at most m. With probability 1 − γ, all estimated pairwise margins are therefore within λ =  p 1 Õ max ε , 1 · mn log(m/γ) 2λC of their true values. The preceding structural bounds imply that the protocol only errs if MoV is at most O(λ · log m). □

Note that it is crucial to use an O(log m)-round knockout tournament in our implementation. If we instead naively implement the protocol in m rounds (eliminating one candidate in each round), then we need to apply the DP composition theorem, resulting in a privacy budget of only ε/m per round √ and an error of Õε (m n) instead. This would not even improve upon our non-interactive guarantee (Theorem 4.3)!

5.4

Lower Bound

The interactive guarantees cannot improve the dependence on the number of voters below the usual locally private meantesting rate, even with only two candidates. Theorem 5.4 There are constants C, ε0 > 0 such that the following holds for two-candidate Plurality. For 0 < ε ≤ ε0 and 0n < γ ≤ 1/6,  no interactive ε-LDP algorithm is √ o n C min n, ε , γ -useful. Proof sketch. We reduce the fully interactive locally private simple hypothesis testing problem to the winner publication problem. When ε is small, use the two point-mass distributions, which produce unanimous profiles with margin Ω(n). Otherwise, use two√binary distributions separated in total √ variation by Θ(1/(ε n)); concentration gives margin Ω( n/ε). The fully interactive testing lower bound of Joseph et al. (2019) rules out a constant-error test in both regimes. With two candidates, Plurality, Condorcet, Maximin, Plurality with Runoff, and STV all select the majority √ candidate. Hence Theorem 5.4 gives the same Ω(min{n, n/ε}) lower bound for every voting rule studied in this work.

6

Conclusion

We gave upper and lower bounds on the decisive margin of victory for private voting mechanisms. In the central model, all the rules considered have the same logarithmic margin dependence, although the optimal STV guarantee cannot be achieved in polynomial time unless NP ⊆ BPP. In the local model, the required margin grows with the amount of information each voter must report. This particularly affects multi-stage rules. Interaction reduces the cost by publishing statistics only for the realized stages, whereas a non-interactive protocol must publish all statistics that might be needed later. Consequently, non-interactive protocols can require substantially larger margins, especially for STV. In terms of open questions, several gaps between upper and lower bounds remain in the local model. Specifically, in the interactive local model, our upper bounds for STV and Condorcet still depend polynomially on m. On the other hand, proving a matching lower bound seems beyond currently known techniques, since our output is simply a candidate among m choices. Meanwhile, existing work (e.g. (Acharya Ω(1) different possible outcomes to et al. 2023)) requires 2m arrive at a lower bound that is polynomial in m. Thus, closing this gap might have implications beyond private voting.

Acknowledgment We thank Jittat Fakcharoenphol for helpful discussion during the early stages of this work.

References Acharya, J.; Canonne, C. L.; Sun, Z.; and Tyagi, H. 2023. Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints. In NeurIPS. Alabi, D.; Ghazi, B.; Kumar, R.; and Manurangsi, P. 2022. Private Rank Aggregation in Central and Local Models. In AAAI 2022, 5984–5991. Bartholdi, J. J.; and Orlin, J. B. 1991. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4): 341–354. Berman, P.; Karpinski, M.; and Scott, A. D. 2003. Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT. Electron. Colloquium Comput. Complex., TR03-022. Bhattacharyya, A.; and Dey, P. 2021. Predicting winner and estimating margin of victory in elections using sampling. Artificial Intelligence, 296: 103476. Darmann, A.; and Döcker, J. 2021. On simplified NPcomplete variants of Monotone 3-SAT. Discret. Appl. Math., 292: 45–58. Duchi, J. C.; Jordan, M. I.; and Wainwright, M. J. 2018. Minimax Optimal Procedures for Locally Private Estimation. Journal of the American Statistical Association, 113(521): 182–201. Dwork, C.; Kenthapadi, K.; McSherry, F.; Mironov, I.; and Naor, M. 2006a. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT 2006, 486–503. Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. D. 2006b. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC 2006, 265–284. Dwork, C.; Naor, M.; Reingold, O.; Rothblum, G. N.; and Vadhan, S. 2009. On the complexity of differentially private data release: Efficient algorithms and hardness results. In STOC 2009, 381–390. Dwork, C.; and Roth, A. 2014. The Algorithmic Foundations of Differential Privacy, volume 9(3–4) of Foundations and Trends in Theoretical Computer Science. Now Publishers Inc. Eden, T.; Liu, Q. C.; Raskhodnikova, S.; and Smith, A. 2025. Triangle counting with local edge differential privacy. Random Structures & Algorithms, 66(4): e70002. Edmonds, A.; Nikolov, A.; and Ullman, J. 2020. The power of factorization mechanisms in local and central differential privacy. In STOC, 425–438. Erlingsson, Ú.; Pihur, V.; and Korolova, A. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In CCS 2014, 1054–1067. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2009. How Hard Is Bribery in Elections? J. Artif. Intell. Res., 35: 485–532. Georgiev, K.; and Hopkins, S. B. 2022. Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation. In NeurIPS. Ghazi, B.; Guzmán, C.; Kamath, P.; Knop, A.; Kumar, R.; and Manurangsi, P. 2026. Computational Hardness of Private Coreset. In FORC, 1:1–1:14.

Ghazi, B.; Kamath, P.; Kumar, R.; Manurangsi, P.; and Sealfon, A. 2023. On computing pairwise statistics with local differential privacy. NeurIPS, 27129–27146. Hardt, M.; and Talwar, K. 2010. On the geometry of differential privacy. In STOC, 705–714. Hillebrand, Q.; Manurangsi, P.; Suppakitpaisarn, V.; and Vajanopath, P. 2026. Improved Differentially Private Algorithms for Rank Aggregation. In AAAI 2026, 17032–17039. Joseph, M.; Mao, J.; Neel, S.; and Roth, A. 2019. The Role of Interactivity in Local Differential Privacy. In FOCS, 94–105. Kasiviswanathan, S. P.; Lee, H. K.; Nissim, K.; Raskhodnikova, S.; and Smith, A. 2011. What Can We Learn Privately? SIAM Journal on Computing, 40(3): 793–826. Li, Z.; Liu, A.; Xia, L.; Cao, Y.; and Wang, H. 2023. Differentially Private Condorcet Voting. In AAAI 2023, 5755–5763. Liu, A.; Lu, Y.; Xia, L.; and Zikas, V. 2020. How Private Are Commonly-Used Voting Rules? In UAI, 629–638. McSherry, F.; and Talwar, K. 2007. Mechanism Design via Differential Privacy. In FOCS 2007, 94–103. Ullman, J. R.; and Vadhan, S. P. 2020. PCPs and the Hardness of Generating Synthetic Data. J. Cryptol., 33(4): 2078–2112. Wang, S.; Du, J.; Yang, W.; Diao, X.; Liu, Z.; Nie, Y.; Huang, L.; and Xu, H. 2019. Aggregating Votes with Local Differential Privacy: Usefulness, Soundness vs. Indistinguishability. arXiv:1908.04920. Warner, S. L. 1965. Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. Journal of the American Statistical Association, 60(309): 63–69. Xia, L. 2012. Computing the margin of victory for various voting rules. In EC 2012, 982–999.

A

Margin-of-Victory Certificates

This section collects the voting-rule facts used in the later utility proofs. For each rule, we show that an inaccurate winner can be reported only when the margin of victory is small relative to the errors in the estimated scores or pairwise margins. The later analyses therefore have two steps: they bound the estimation error of the private algorithm and then apply the corresponding result from this section. The same second step applies to both the non-interactive and interactive algorithms. Throughout this appendix, when candidate scores are estimated, se(c) denotes the estimated score of candidate c, and se = (e s(c))c∈C denotes the vector of these estimates. Each result specifies the corresponding true score being estimated.

A.1

Plurality

The margin of victory for positional scoring rules, including Plurality, can be computed exactly (Xia 2012, Theorem 5). The following elementary certificate is also closely related to the score-gap bound used by Bhattacharyya and Dey (2021, Lemma 3). Lemma A.1 (Plurality certificate) Suppose w is the Plurality winner on π. For every c ̸= w,   scoreplu (π, w) − scoreplu (π, c) MoV(π, r) ≤ + 1. 2 Consequently, if the estimated Plurality scores satisfy |e s(c)− scoreplu (π, c)| ≤ η for every candidate c, then a candidate maximizing se can differ from w only if MoV(π, r) ≤ η + 1.

If the noisy runoff winner differs from the true runoff winner, then   ζ MoV(π, r) ≤ 2 + max 2η, η + . 2 Proof. Let w be the true runoff winner, let d be the other true finalist, and let a, b be the noisy finalists. First suppose w ∈ / {a, b}. For each x ∈ {a, b}, scoreplu (π, w) − scoreplu (π, x) ≤ 2η. Write q = scoreplu (π, w) and set     scoreplu (π, w) − scoreplu (π, x) tx = max 0, +1 . 2 Then tx ≤ η + 1, so ta + tb ≤ 2η + 2. If q ≥ ta + tb , change disjoint sets of ta and tb rankings that place w first so that they instead place a and b first, respectively. Each change decreases w’s score by one and increases the chosen candidate’s score by one. Thus both a and b strictly outrank w, so w misses the runoff. It remains to consider q < ta + tb . Since w is the true runoff winner, we must have q > 0: if q = 0, at most one candidate can have positive first-round score while w is a finalist, and that candidate is ranked first by every voter and therefore defeats w head to head. Change all q rankings that place w first so that they place a first and w last. Candidate w now has score zero and a has positive score. If w misses the runoff, the outcome has changed. Otherwise, no candidate other than a has positive score, since any such candidate would join a in the runoff ahead of w. Hence every voter ranks a first, and a defeats w unanimously. This construction uses q < ta + tb ≤ 2η + 2

Proof. Let ∆ = scoreplu (π, w) − scoreplu (π, c) and t = ⌊∆/2⌋ + 1. Change t rankings that place w first so that they place c first. This decreases the score gap between w and c by 2t > ∆, so c strictly outranks w in the resulting profile. For the second claim, if c maximizes the estimated score, then scoreplu (π, w) − scoreplu (π, c) ≤ 2η.

changes. Now suppose w is a noisy finalist but loses the noisy runoff to a candidate a. If a ̸= d, then

The first claim now gives MoV(π, r) ≤ η + 1.

Set

A.2

□

scoreplu (π, d) − scoreplu (π, a) ≤ 2η.

    scoreplu (π, d) − scoreplu (π, a) t = max 0, +1 . 2

Plurality with Runoff

Exact computation of the margin of victory for Plurality with Runoff was studied by Xia (2012, Theorem 7). A related certificate in terms of first-round scores and pairwise margins appears in Bhattacharyya and Dey (2021, Lemma 8); the formulation below is tailored to separate errors in the two stages of the noisy computation.

selects the two candidates with largest estimated scores, and b b) of their pairwise margin satisfying uses an estimate D(a,

Then t ≤ η + 1. If scoreplu (π, d) > 0, there are at least t rankings with d first. Change t of them to place a first and place a above w. Candidate a then strictly outranks d and is therefore a true finalist. The only exceptional case is scoreplu (π, d) = scoreplu (π, a) = 0, when t = 1; changing one ranking with w first in the same way makes a a finalist. Such a ranking exists because, as argued above, a true runoff winner has positive first-round score. If a = d, take t = 0, since a is already a true finalist. If these changes remove w from the runoff, the outcome has already changed. Otherwise, the true finalists are now w and a. Because a wins their noisy comparison and its estimated pairwise margin has error at most ζ,

b b) − Dπ (a, b)| ≤ ζ. |D(a,

Dπ (w, a) ≤ ζ.

Lemma A.2 (Runoff certificate) Suppose a noisy computation for Plurality with Runoff uses first-round estimates se(c) satisfying |e s(c) − scoreplu (π, c)| ≤ η

for every c ∈ C,

The first-round changes all place a above w, so they cannot increase this margin. Let D′ (w, a) be the margin after those changes and set   ′   D (w, a) u = max 0, +1 . 2 Then u ≤ ζ/2 + 1. Change u additional rankings that place w above a by moving a immediately above w. This cannot decrease a’s first-round score and makes D′ (w, a) − 2u < 0, so a wins the runoff. The total number of changes in this case is at most ζ t + u ≤ η + + 2. 2 Taking the larger of the two case bounds proves the claim. □

A.3

Condorcet

Lemma A.3 (Condorcet certificate) Suppose w ∈ C is the Condorcet winner on profile π. Then MoV(π, r) ≤ 1 + min Dπ (w, c). c∈C\{w}

Alternatively, suppose the Condorcet rule outputs ⊥ on π. Then, for every candidate c ∈ C, MoV(π, r) ≤ 1 + 3 log2 m + 3 max Dπ (a, c). a∈C\{c}

Proof. First consider the case where the Condorcet rule outputs a candidate w. Let ∆ :=

min Dπ (w, c),

c∈C\{w}

c⋆ := arg min Dπ (w, c).

If ra > 0, then |Va ∪ X| ≤ ⌊n/2⌋, so at least half of the remaining voters x ∈ [n] \ X rank a above c. Adding any such voter to X decreases a’s contribution from 2ra − 1 to 2ra −1 − 1. Therefore, for a uniformly random x ∈ [n] \ X, 1 X ra −1 f (X) − Ex [f (X ∪ {x})] ≥ 2 2 a∈C\{c} ra >0

≥

Hence Ex [f (X ∪ {x})] ≤ 43 f (X), so some x ∈ [n] \ X satisfies the claimed inequality. At X = ∅, parity of the pairwise margins gives ra ≤ max{1, ∆c }, and hence f (∅) ≤ m2∆c . Since f is integervalued, the process stops with f (X) = 0 once f (X) < 1. A greedy algorithm that repeatedly chooses the best voter returns a set X of size at most 1 + log4/3 (m2∆c ) ≤ 1 + 3 log2 m + 3∆c . Let π ′ be obtained from π by moving c to the top of every ranking indexed by X. Since f (X) = 0, we have ra = 0 for every a ̸= c. By the definition of ra , this implies jnk |Va ∪ X| ≥ 1 + . 2 Every voter in Va already ranks c above a, and every voter in X does so after the modification. Hence, in π ′ , strictly more than half of the voters rank c above a. This holds for every a ̸= c, so c is the Condorcet winner on π ′ . The original outcome was ⊥; therefore changing at most |X| rankings changes the outcome, and MoV(π, r) ≤ |X| ≤ 1 + 3 log2 m + 3∆c ,

c∈C\{w}

Changing the relative order of w and c⋆ in ⌊∆/2⌋ + 1 voters who place w above c⋆ makes Dπ′ (w, c⋆ ) < 0 in the resulting profile π ′ . Thus w is no longer a Condorcet winner, and MoV(π, r) ≤ ⌊∆/2⌋ + 1 ≤ 1 + ∆. Now suppose the rule outputs ⊥. Fix a candidate c ∈ C and define ∆c := max Dπ (a, c). a∈C\{c}

For each a ∈ C \ {c}, let Va ⊆ [n] be the set of voters who rank a above c, and write Va = [n]\Va . By definition, |Va | ≤ (n+∆c )/2. We will find a set X of at most 1+3 log2 m+3∆c voters such that, after moving c to the top of those voters’ rankings, candidate c defeats every a ̸= c head to head. Let X f (X) := (2ra − 1), a∈C\{c}

where n jnk o − |Va ∪ X| . ra := max 0, 1 + 2 We claim that whenever f (X) > 0, there exists x ∈ [n] \ X such that 3 f (X ∪ {x}) ≤ f (X). 4

1 f (X). 4

□

as claimed.

A.4

Maximin

The relationship between the Maximin score gap and the margin of victory is due to Xia (2012, Theorem 12); see also the related score-gap certificate of Bhattacharyya and Dey (2021, Lemma 5). We record the resulting consequence for noisy pairwise margins. Lemma A.4 (Maximin certificate) Let w and w′ have the largest and second-largest maximin scores, respectively, and define ∆mm = scoremaximin (w) − scoremaximin (w′ ). Then ∆mm MoV(π, r) − 1 ≤ ≤ MoV(π, r). 2 4 In particular, ∆mm + 1. 2 Moreover, if all pairwise margins are estimated to error at most η, a candidate maximizing the noisy maximin score can differ from w only if MoV(π, r) ≤

MoV(π, r) ≤ η + 1.

Proof. The first two inequalities are the two-approximation guarantee of Xia (2012, Theorem 12), with the additive one accounting for the fixed tie-breaking rule. Rearranging the first inequality gives the displayed upper bound on MoV. Suppose every pairwise margin has error at most η, and let s] coremaximin (a) denote the resulting noisy maximin score of candidate a. Every pairwise margin entering the minimum that defines a candidate’s maximin score changes by at most η. Therefore that minimum also changes by at most η. Thus, for every a ∈ C,

• for each j ∈ {0, . . . , m − 1}, min scoreplu (π (i) |C−j , c) = s⋆j ;

c∈C−j

• for each j ∈ {i, . . . , m − 1} and every c ∈ C−j , scoreplu (π (i) |C−j , c) = scoreplu (π|C−j , c).

Let w b ̸= w maximize the noisy maximin score. The optimality of w b for the noisy scores gives

The base case i = 0 follows from π (0) = π. Fix i ∈ {0, . . . , m − 1} and assume the properties hold for π (i) . Consider the rankings whose top candidate in C−i is ci+1 . Choose ∆i of them that are last to give their vote to ci+1 , meaning that the first round in which they contribute to ci+1 is as late as possible. Such a ranking has the form

scoremaximin (w) ≤ s] coremaximin (w) + η

· · · ≻ ci+1 ≻ · · · ≻ d ≻ · · · ,

|] scoremaximin (a) − scoremaximin (a)| ≤ η.

≤ s] coremaximin (w) b +η ≤ scoremaximin (w) b + 2η. Because w′ has the second-largest true maximin score, scoremaximin (w′ ) ≥ scoremaximin (w). b Therefore ∆mm = scoremaximin (w) − scoremaximin (w′ ) ≤ 2η. The preceding bound now gives MoV(π, r) ≤ ∆mm /2 + 1 ≤ η + 1. □

A.5

Single Transferable Vote

For STV, we convert a near-minimum elimination path into an upper bound on the margin of victory and then derive the corresponding error certificate. A closely related elimination-path bound appears in Bhattacharyya and Dey (2021, Lemma 9). Our formulation includes an additive m2 term to enforce the desired path under fixed tie-breaking. Lemma A.5 (STV upper certificate) Suppose w is the STV winner on π, and consider distinct candidates c1 , . . . , cm with cm ̸= w. Define C−i = C \ {c1 , . . . , ci },

s⋆i = min scoreplu (π|C−i , c). c∈C−i

Then MoV(π, r) ≤ m2 +

m−1 X

scoreplu (π|C−i , ci+1 ) − s⋆i .

i=0

Proof. For i = 0, . . . , m − 1, let ∆i := scoreplu (π|C−i , ci+1 ) − s⋆i ≥ 0. Pm−1 We will show that by changing m2 + i=0 ∆i rankings, we can make cm win. First observe that the sequence (s⋆i ) is nondecreasing, since remaining candidates can only gain votes from one round to the next. We construct by induction profiles π (0) , π (1) , . . . , π (m) , with π (0) = π. For each i ∈ {0, . . . , m − 1}, we modify exactly ∆i rankings in π (i) to construct π (i+1) . We maintain the following properties: • for each j ∈ {0, . . . , i − 1}, candidate cj+1 has plurality score exactly s⋆j in π (i) |C−j ;

where d is the second preferred candidate below ci+1 in C−i . Swap ci+1 and d, leaving the relative order of every other candidate unchanged. Each change decreases the score of ci+1 in C−i by one and transfers that vote to d. Hence scoreplu (π (i+1) |C−i , ci+1 ) = s⋆i . For j > i, the restrictions to C−j are unchanged, because once ci+1 is removed the relative order of the remaining candidates is the same. It remains to verify the earlier rounds j < i. Such a modification can only lower the score of ci+1 and raise the score of d. Fix j < i and let uj = scoreplu (π (i) |C−j , ci+1 ). The rankings contributing to ci+1 in round j are precisely the earlier-contributing rankings among those that contribute to it in round i. Because we modify the ∆i latest-contributing rankings, at least min{uj , s⋆i } of its round-j votes remain. The induction hypothesis gives uj ≥ s⋆j , while the monotonicity of the round minima gives s⋆i ≥ s⋆j . Hence the new round-j score of ci+1 is at least s⋆j . No other score decreases, so no score falls below the original round minimum, and the induction properties hold for π (i+1) . Consequently, in π (m) , candidate ci+1 is among the minimum-score candidates in round i + 1 forPevery i. The number of changed rankings so far is at most i ∆i . The intended candidate may still be tied for the minimum. To make the elimination order independent of tie-breaking, we add a staircase. Let J = {j ∈ [m] : cj ̸= w} and L=

X j∈J

j≤

m(m + 1) ≤ m2 . 2

Suppose first that at least L rankings in π (m) place w first. Choose pairwise disjoint sets Xj of such rankings, with |Xj | = j for every j ∈ J. In each ranking in Xj , move cj immediately above w, preserving the relative order of all other candidates. Before w is eliminated, candidate cj ̸= w receives an additional j votes in every round in which it remains. Thus, in

round i + 1, the staircase bonuses of the surviving candidates ci+1 , . . . , cm other than w are i + 1, i + 2, . . . , m. Since every surviving candidate previously had score at least s⋆i , while ci+1 had score exactly s⋆i , either w or ci+1 is eliminated in that round. Therefore the elimination order follows c1 , c2 , . . . , cm−1 until w is eliminated. Since cm ̸= w, the resulting winner differs from w. It remains to handle the case in which fewer than L rankings in π (m) place w first. Change all of these rankings by moving cm to the top and w to the bottom. Candidate w then has zero score in the first STV round. A zero-score candidate cannot win STV: while another zero-score candidate is eliminated, no votes transfer, and once w is the only zero-score candidate, it is the unique minimum and is eliminated. Thus these fewer than L ≤ m2 additional changes also produce a winner other than w. The total number of changes is at most m−1 X

proving the claim. □ Corollary A.6 (STV error certificate) Suppose an approximate STV computation starts with S0 = C. In each round i ∈ {0, . . . , m − 2}, it computes estimates (e si (c))c∈Si of the round scores, eliminates a candidate c∈Si

Remark A.7 For every m ≥ 4, there is a profile π on m candidates with STV winner w and distinct candidates c1 , . . . , cm , where cm ̸= w. For i ∈ {0, . . . , m − 1}, define C−i = C \ {c1 , . . . , ci },

s⋆i = min scoreplu (π|C−i , c). c∈C−i

Then, for every i ∈ {0, . . . , m − 1}, scoreplu (π|C−i , ci+1 ) − s⋆i = 0, but

(m − 3)2 . 64 Proof. Let k = m − 2, let C = {a, b, x1 , . . . , xk }, and fix the tie-breaking order MoV(π, r) ≥

m−1 X

m(m + 1) + ∆i ≤ m2 + ∆i , 2 i=0 i=0

ci+1 ∈ arg min sei (c),

Necessity of the quadratic term. Lemma A.5 bounds the STV margin of victory by m2 plus, for each round, the difference between the Plurality score of the candidate proposed for elimination and the minimum Plurality score among the remaining candidates. The following remark shows that the m2 term cannot be removed in general: even when every such difference is zero, changing the STV winner may require Ω(m2 ) ranking changes.

Si+1 = Si \ {ci+1 },

and finally returns the unique candidate cm ∈ Sm−1 . Suppose cm differs from the true STV winner and, for every realized round i and every active candidate c ∈ Si , |e si (c) − scoreplu (π|Si , c)| ≤ η. Then

MoV(π, r) ≤ m2 + 2(m − 1)η. Proof. Let w be the true STV winner. By assumption, cm ̸= w. For i ∈ {0, . . . , m − 2}, the active set before eliminating ci+1 is Si = C−i = C \ {c1 , . . . , ci }. Choose a candidate di ∈ C−i having minimum true score in this round, so scoreplu (π|C−i , di ) = s⋆i . Since the approximate computation eliminates a candidate of minimum estimated score, scoreplu (π|C−i , ci+1 ) ≤ sei (ci+1 ) + η ≤ sei (di ) + η ≤ scoreplu (π|C−i , di ) + 2η = s⋆i + 2η. Thus the score excess appearing in Lemma A.5 is at most 2η in each of the m − 1 elimination rounds. When i = m − 1, only cm remains, so its score equals the minimum and the final excess is zero. Summing these bounds and applying Lemma A.5 gives MoV(π, r) ≤ m2 + 2(m − 1)η. □

a ≺ x1 ≺ · · · ≺ xk ≺ b, where y ≺ z means that y is eliminated before z when their scores are equal. Set R = k 2 , and consider the profile consisting of • R rankings of the form a ≻ b ≻ x1 ≻ · · · ≻ xk ; • (m − 1)R rankings of the form b ≻ a ≻ x1 ≻ · · · ≻ xk ; • for each i ∈ [k], R rankings of the form xi ≻ xk ≻ · · · ≻ xi+1 ≻ a ≻ b ≻ xi−1 ≻ · · · ≻ x1 . Candidate b wins: candidate a is eliminated in the first round by the tie-breaking rule, after which b has strictly more than half of the votes. On the other hand, along the proposed order xk , . . . , x1 , b, a, the next candidate is tied for the minimum in each restricted election. Thus the displayed score excess is zero. It remains to show that the margin of victory of b is at least (m − 3)2 /64. Set ℓ0 =

(m − 3)2 (k − 1)2 = , 64 64

and let π ′ differ from π on T < ℓ0 rankings. Since T < R/4, candidate b cannot be eliminated while at least two other candidates remain: its score is at least (m−1)R−T , whereas the total score of all other candidates is at most (m−1)R+T , so one of them has score at most (m − 1)R + T < (m − 1)R − T. 2 If b faces some xi in the final round, then after a is eliminated, b has at least mR − T votes, while xi has at most kR + T < mR − T votes. Thus b still wins. It remains to consider a final round between a and b. This requires the elimination order to begin with xk , xk−1 , . . . , xq , where q = ⌈k/2⌉ + 1. Otherwise, suppose the order first breaks

when xi is eliminated while xj is the highest-index remaining candidate with j > i and j ≥ q. The votes of xj+1 , . . . , xk have transferred to a, while eliminating xi transfers its votes to xj , which then has at least 2R − T > R + T votes. All other remaining x-candidates are eliminated before xj and transfer to it. When only a, b, xj remain, candidate a has at most (k − j)R + T ≤ (⌊k/2⌋ − 1)R + T votes, while xj has at least jR − T ≥ qR − T , so a cannot reach the final round. We now show that this required prefix itself needs at least ℓ0 changes. Write y1 , . . . , yp = xk , . . . , xq ,

p = ⌊k/2⌋.

If p = 1, the original first-round scores of a and y1 = xk are both R, and the tie-breaking rule eliminates a before y1 . Reversing this order requires at least one change, which is more than ℓ0 . Hence suppose p ≥ 2. For each i ∈ [p], let ai be the score of yi when it is eliminated, and let Bi be the block of R original rankings that place yi first. The sequence (ai ) is strictly increasing. Indeed, when yi is eliminated, yi+1 remains and precedes yi in the tie-breaking order, so yi must have strictly smaller score; the score of yi+1 cannot decrease before its own elimination. Let r be the largest index with ar < R, and set r = 0 if no such index exists. Suppose first that r ≥ p/2. Since the ai are strictly increasing integers and ar ≤ R − 1, R − ai ≥ r − i + 1

for every i ≤ r.

At least R − ai rankings in Bi must have been changed; otherwise more than ai unchanged rankings would still give their vote to yi when it is eliminated. The blocks B1 , . . . , Br are disjoint, and hence T ≥

r X i=1

(R − ai ) ≥

r(r + 1) p2 (k − 1)2 ≥ ≥ ≥ ℓ0 . 2 8 32

Now suppose r < p/2. Put h = p − r and choose the integer round   h s=r+ . 2 Then r < s < p. Strict increase gives as ≥ R + s − r − 1. When ys is eliminated, each of the p−s remaining candidates ys+1 , . . . , yp must therefore have score at least R + s − r. Along this elimination prefix, an unchanged ranking outside the candidate’s own block does not contribute to any of these remaining candidates. Thus their total score excess over the original value R must come from changed rankings, and one changed ranking contributes at most one such vote in this round. Consequently,    h p2 (k − 1)2 h ≥ ≥ = ℓ0 . T ≥ (p − s)(s − r) = 2 2 16 64 Here the penultimate inequality uses h = p − r > p/2, and the last uses 2p ≥ k − 1. Both cases contradict T < ℓ0 . Therefore b remains the winner after fewer than ℓ0 ranking changes, proving MoV(π, r) ≥ (m − 3)2 /64. □

B

Hardness of Approximation for STV

We give a non-private hardness result for STV. This result is used twice: first to show strong inapproximability of MoV-related optimization problems, and then to rule out efficient centrally private STV algorithms with strong usefulness guarantees. For this appendix, we use a directed variant of MoV. For each a ∈ C ∪ {⊥}, let Move(π, r, a) denote the smallest integer k such that there exists a k-neighbor π ′ of π with r(π ′ ) = a. The problem Bribery (Faliszewski, Hemaspaandra, and Hemaspaandra 2009) asks us to approximately compute Move(π, r, a) from (π, r) and a desired outcome a ̸= r(π). This problem is sometimes called constructive bribery, while the problem of computing MoV is also known as destructive bribery. We have Move(π, r, r(π)) = 0 and MoV(π, r) = min Move(π, r, a). a̸=r(π)

Theorem B.1 (Used in Theorem 3.3) Let ζ > 0 be an arbitrary constant. Given an STV instance (π, r) with winner w = r(π) and a candidate a ̸= w, it is NP-hard to distinguish between the following two cases: • (YES) For every positive integer k ≤ n1−ζ , there exists a k-neighbor π ′ of π such that r(π ′ ) = a and MoV(π ′ , r) ≥ k2 . In particular, this implies MoV(π, r) ≤ Move(π, r, a) ≤ 1. • (NO) Move(π, r, a) = MoV(π, r) ≥ n1−ζ . Furthermore, this holds even when m ≤ nζ . Before proving the theorem, we record two immediate approximation-hardness corollaries. The additional YEScase guarantee MoV(π ′ , r) ≥ ⌈k/2⌉ is not needed for these corollaries; it is included for the later DP lower bound. Corollary B.2 For any constant ζ > 0, it is NP-hard to approximate MoV for STV to within a factor of n1−ζ . Corollary B.3 For any constant ζ > 0, it is NP-hard to approximate Bribery for STV to within a factor of n1−ζ . Both results are nearly tight: changing all votes gives a trivial n-approximation. They also strengthen the earlier factor-2 hardness from (Xia 2012), which builds on the NP-hardness of distinguishing MoV(π, r) = 1 from MoV(π, r) = 2 (Bartholdi and Orlin 1991). The reduction is from 3SAT. The input is a 3CNF formula Φ with M clauses over N variables; each clause is a disjunction of three literals. Let X be the variable set. An assignment is a function ψ : X → {0, 1}, and it satisfies Φ if every clause is satisfied. We say that Φ has bounded literal degree d if every literal appears in at most d clauses. We use the following result of (Berman, Karpinski, and Scott 2003).5 Theorem B.4 (Berman, Karpinski, and Scott 2003) It is NP-hard to decide whether a given 3CNF formula Φ with bounded literal degree 2 is satisfiable. 5 See also (Darmann and Döcker 2021), which gives a simplified and generalized reduction.

The reduction below is inspired by the set-cover-based reduction of (Bartholdi and Orlin 1991). Reducing from 3SAT gives a smaller construction and makes the amplification needed for approximation hardness more transparent.

B.1

Reduction and Proof of Theorem B.1

Consider a 3CNF formula Φ with bounded literal degree 2. Let x1 , . . . , xN be its variables and c1 , . . . , cM its clauses. Since each clause has three and each literal appears at  literals  most twice, N3 ≤ M ≤ 4N . The candidate set C contains 3 the following 4N + 2 candidates: • Winner Candidates: two candidates w and a, where w is the winner in the constructed profile and a is the alternate winner. • Literal Candidates: candidates yxi and yx̄i for each variable xi . • Selection Candidates: candidates zxi and zx̄i for each variable xi .   Let t = 1000 · (2000N 2 )1/ζ and D = 10N . The profile π consists of the following voters; unspecified suffixes may be ordered arbitrarily. • Winner voters: 4Dt voters with preferences w ≻ a ≻ · · · . • Alternate Voters: 4Dt − 1 voters with preferences a ≻ w ≻ ···. • For each literal ℓ of variable xi , with negation ℓ̄, create: – Assignment Voters for ℓ: (D + 5i − 4)t voters ranking zℓ ≻ yℓ̄ ≻ yℓ ≻ w ≻ a ≻ · · · . – Selection Voters for ℓ: 4t voters ranking zℓ ≻ zℓ̄ ≻ yℓ ≻ yℓ̄ ≻ w ≻ · · · . – Literal Voters for ℓ: (D + 5i + 1)t voters ranking yℓ ≻ yℓ̄ ≻ w ≻ · · · . • Clause Voters: for every clause ci with literals ℓi,1 , ℓi,2 , ℓi,3 , create t voters ranking yℓi,1 ≻ yℓi,2 ≻ yℓi,3 ≻ w ≻ a ≻ · · · . The resulting instance has m = 4N + 2 candidates and n ≤ 2000N 2 t voters. By the choice of t, we have t ≥ 1000 · n1−ζ and m ≤ nζ . The key property of the construction is that the elimination order is stable under fewer than t/2 vote changes. Proposition B.5 Let κ be non-negative integer such that κ < t ′ 2 . For any π that is a κ-neighbor of π, the elimination order for STV on π ′ must be as follows: 1. In the j-th round for j ∈ [3N ], let i = ⌈j/3⌉ and ℓi ∈ {xi , x̄i }. The eliminations are as follows: • Case A: j = 3i − 2. zℓi is eliminated. • Case B: j = 3i − 1. yℓi is eliminated. • Case C: j = 3i. zℓ̄i is eliminated (where ℓ̄i is the negation of ℓi ). 2. In the (3N + 1)-th round, one of w or a is eliminated. 3. In the (3N +1+i)-th round for i ∈ [N ], yℓ̄i is eliminated. 4. Finally, the remaining one among w or a is the winner. Proof. We start by proving item 1. We prove this by strong induction. Assume that this is true for all rounds up to j − 1. Then, the three cases proceed as follows:

• Case A: j = 3i − 2. For both ℓi ∈ {xi , x̄i }, the vote count of zℓi in π in this round is (D + 5i)t (from Assignment Voters for ℓi and Selection Voters for ℓi ) whereas the vote counts for all other candidates are ≥ (D + 5i + 1)t. Thus, the gap is t > 2κ. Since the vote count of each candidate w.r.t. π ′ differs that w.r.t. π by at most κ < 2t , we can conclude that one of them must be eliminated in this round. • Case B: j = 3i − 1. The vote count of yℓi is now at most (D + 5i + 3)t (from Literal Voters for ℓi , and possibly 2t Clause Voters) in π. Meanwhile, the vote counts of all other candidates are at least (D + 5i + 4)t. (In particular, zℓ̄i receives 4t additional votes from Selection Voters for ℓi in the previous round.) As a result, the gap is at least t > κ/2 again, and we can conclude that yℓi must be eliminated in π ′ . • Case C: j = 3i. In this round, zℓ̄i has a vote count of (D + 5i + 4)t while all other candidates have vote counts at least (D + 5(i + 1))t. Thus, we can again conclude that zℓ̄i is eliminated. Now, in the (3N + 1)-th round, we can see that all the remaining Literal Candidates have vote counts at least (4D + 20i + 2)t (from all Assignment Voters, Selection Voters and Literal Voters of itself and its negation) in π. Meanwhile, a has at most 4Dt votes in π. Thus, since the gap is more than 2κ, the Literal Candidates cannot be eliminated in this round. Thus, either a or w must be eliminated. Finally, once a or w is eliminated, the other candidate o will have at least 8Dt votes in π. Meanwhile, all the other Literal Candidates have only at most (4D + 20i + 4)t vote counts in π before o is eliminated. Since the gap between these two are more than 2κ, we can once again conclude that all Literal Candidates are eliminated before o and, thus, o remains the winner. □ Given Proposition B.5, it is simple to check that w wins the election if the list of preferences is π. Namely, after the first 3N rounds, a will have at most 4Dt − 1 votes while w has at least 4Dt votes, so the former gets eliminated. Thus, w is left as the winner. We will next prove the completeness and soundness of the reduction. Completeness. Suppose that there exists a satisfying assignment ψ of Φ. Let ℓ1 , . . . , ℓN denote the literals that are set to false by ψ. Fix k ≤ ⌊t/6⌋. (Recall that ⌊t/6⌋ ≥ n1−ζ .) We construct π ′ from π by keeping all the voters’ preference except for k of the Winner Voters where we change them to zℓ̄1 ≻ · · · ≻ zℓ̄N ≻ a ≻ w ≻ · · · . We claim that a at least  kis the winner of the election and that it has MoV ′′ . To see that this is the case, consider any π that is a 2 k 
′ ′′ − 1 -neighbor of π . Note that this means that π is 2  
 
a k + k2 − 1 -neighbor of π. Since k + k2 − 1 < 4t , we may apply Proposition B.5. We claim that zℓi is eliminated in round 3i − 2 for all i ∈ [N ]. Again, this can be seen via induction: Suppose this holds in previous rounds. In the round 3i−2, due to the voters we changed, zℓ̄i will have a vote count of (D + 5i)t + k in ′ π ′ while the vote  kcount 
of zℓi remains at′ (D + 5i)t in π . ′′ Since π is a 2 − 1 -neighbor of π , zℓi must also be

eliminated in π ′′ . It also follows (from Proposition B.5) that the corresponding yℓi is eliminated in round 3i − 1. Now, consider the (3N + 1)-th round. Since ψ is a satisfying assignment, none of the Clause Voters votes for w in this round. Thus, in π ′ , w only receives the vote counts from the (4Dt − k) Winner Voters that were not changed. Meanwhile, a receives votes from both the Alternate Voters and the k Winner Voters that were adjusted, for a total count ′ of (4Dt− 1 + k)
in π . Since this gap (2k − 1) is greater than 2 k2 − 1 , we can conclude that w is eliminated in π ′′ . Thus, by Proposition B.5, a must be a winner in π ′′ . Soundness. Suppose that Φ admits no satisfying assignment. Consider any π ′ that is a κ-neighbor of π for any κ < t/2. From Proposition B.5, the candidates eliminated in the first 3N rounds (for π ′ ) consists of N literal variables, one from each variable xi . Let ψ denote the assignment that sets all of these literals to false. By our assumption, at least one clause is violated in Φ. At round (3N + 1), the corresponding Clause Voters will have w as their most preferred candidate. Thus, w has vote count of at least 4Dt + t in π. Meanwhile, a has vote count at most 4Dt in π. Since κ < t/2 (and from Proposition B.5), we can conclude that a is eliminated in this round for π ′ . Thus, by Proposition B.5, we can conclude that w remains the winner of the election. In other words, MoV(π, r) ≥ ⌈t/2⌉ ≥ n1−ζ as desired.

C

Additional Details for Central Differential Privacy

This appendix supplies the proofs omitted from Section 3. We first analyze the utility of the generic exponential-mechanism algorithm and its efficient Maximin variant. We then prove the computational barrier for private STV and conclude with the packing lemmas used for the central-DP lower bounds.

C.1

Upper Bounds

We begin with the information-theoretic algorithm, whose score is the negative margin of victory for every outcome other than the true winner. Proof of Theorem 3.1. For the score function in (1), the optimal utility is attained by r(π) and equals OPT(π) = q(π, r(π)) = 0, and |O| = m + 1. Set   2 m+1 L = log and τ = L + 1. ε γ If MoV(π, r) ≥ τ , then every a ̸= r(π) satisfies q(π, a) ≤ −τ < −L. By Theorem 2.5, with probability at least 1 − γ the exponential mechanism returns an outcome with utility at least −L. The only such outcome is r(π), including when r(π) = ⊥. □ For Maximin, the efficiently computable score gap in (2) approximates the margin of victory within a factor of two, up to the one-vote adjustment needed for fixed tie-breaking. Indeed, changing one vote changes each maximin score by at most 2, so fewer than ∆mm /4 changes cannot alter the winner. Conversely, the construction in (Xia 2012, Theorem 12) changes ∆mm /2 votes to make the original winner cease to be the unique maximin-score maximizer. From such a tie,

one additional vote suffices to change the winner selected by any fixed tie-breaking rule. This proves (2). Proof of Theorem 3.2. For q ′ , we have OPT(π) = 0 and |O| = m. Set   2 m L = log and τ = 2L + 2. ε γ By (2), if MoV(π, r) ≥ τ , then every a ̸= r(π) satisfies ∆mm MoV(π, r) − 1 1 ≤− ≤ −L − . 4 2 2 Theorem 2.5 returns an outcome with score at least −L with probability at least 1 − γ. Hence it must return r(π), proving the stated threshold. □ q ′ (π, a) = −

C.2

Computational Barrier for STV

The generic exponential mechanism is not efficient for STV because its score requires computing the STV margin of victory. The next proof strengthens this observation: any efficient private algorithm satisfying the two usefulness guarantees in Theorem 3.3 would solve the hard gap instance constructed in Theorem B.1. Proof of Theorem 3.3. Suppose for contradiction that such an algorithm M exists. We use it to solve the distinguishing problem in Theorem B.1 with ζ = 1/(C2 + 1): • Independently run M(π, r) for R = ⌊mC3 /3⌋ repetitions. • If all the runs return w, then output NO. • Otherwise, output YES. The running time is polynomial. We analyze the two cases. • (YES) Let k = ⌈4C1 log(m)/ε⌉. For all sufficiently large instances, k ≤ n1−ζ , so Theorem B.1 gives a k-neighbor π ′ of π such that r(π ′ ) = a and   k C1 log m MoV(π ′ , r) ≥ ≥ . 2 ε Usefulness therefore gives Pr[M(π ′ , r) = a] ≥ 1 − γ. By group privacy, p := Pr[M(π, r) = a] ≥ e−εk Pr[M(π ′ , r) = a] ≥ (1 − γ)e−ε m−4C1 . Since C3 > 4C1 , for all sufficiently large m this is at least 5m−C3 . Also, for sufficiently large m, R ≥ mC3 /4. Consequently, the probability of outputting YES is at least 2 1 − (1 − p)R ≥ 1 − e−pR ≥ 1 − e−5/4 > . 3 • (NO) Since m ≤ nζ and ζ = 1/(C2 + 1), we have n1−ζ ≥ mC2 . Thus MoV(π, r) ≥ n1−ζ ≥ mC2 . Since
C2 C3 M is m , 1/m -useful, each run outputs w with probability at least 1 − 1/mC3 . By the union bound, the probability that any of the R ≤ mC3 /3 runs does not output w is at most 1/3. Hence our algorithm outputs NO with probability at least 2/3. Thus, we solve the distinguishing problem in Theorem B.1 with probability at least 2/3 in polynomial time, implying NP ⊆ BPP. □

C.3

Packing Lower Bounds

We next prove the generic packing lemma from Section 3. The proof compares the probability of a fixed candidate under two nearby profiles with different robust winners. Proof of Lemma 3.5. Let M be an ε-DP algorithm that is (τ, γ)-useful. Suppose for contradiction that   ln(0.4m/γ) τ < T := . κε If T = 0, the claimed lower bound is immediate, so assume T ≥ 1. Let π 1 , . . . , π m be profiles guaranteed by Assumption 3.4 with t = T . By the definition of usefulness, we must have Pr[M(π 1 ) = c1 ] ≥ 1 − γ. Thus, there must exist i ∈ [m] \ {1} such that γ Pr[M(π 1 ) = ci ] ≤ . m−1 Since π 1 , π i are (κT )-neighbors, we have

For each candidate ci , construct π i from π base as follows. Identify the 2t rankings in which ci is last, x1 ≻ x2 ≻ · · · ≻ xm−1 ≻ ci . and move ci to the first position in those rankings, shifting all other candidates down by one position: ci ≻ x1 ≻ x2 ≻ · · · ≻ xm−1 . In the modified profile π i , candidate ci gains ∆ points in each of the 2t changed rankings: scores (ci ; π i ) = scores (ci ; π base ) + 2t∆. Every other candidate is shifted down in the modified rankings, so monotonicity of the scoring vector implies that its score cannot increase: scores (cj ; π i ) ≤ scores (cj ; π base ) (4)

= scores (ci ; π base )

ε·(κT )

Pr[M(π i ) = ci ] ≤ e

· Pr[M(π 1 ) = ci ] γ . ≤ eε·(κT ) · m−1 However, usefulness on π i requires this probability to be at least 1 − γ. Therefore   1 (m − 1)(1 − γ) ln(0.4m/γ) T ≥ · ln > , κε γ κε where the last inequality uses γ < 0.2. This contradicts the definition of T , so τ ≥ T . □ It remains to verify the packing assumption for the voting rules considered in the paper. We first handle every rule satisfying the majority criterion, then give a separate symmetric construction for arbitrary non-trivial scoring rules.

∀cj ̸= ci .

Thus ci wins in π i . Moreover, its score advantage over every other candidate is at least 2t∆. Changing one preference can decrease this gap by at most 2∆, so MoV(π i , r) ≥ t. Finally, π i and π j each differ from π base in 2t preferences, so they are 4t-neighbors. □

D

Additional Details for Non-Interactive LDP: Plurality

This appendix proves the non-interactive LDP upper and lower bounds for Plurality from Section 4. For the upper bound, we first establish simultaneous accuracy of the DJWprivatized score vector and then translate score accuracy into winner recovery. For the lower bound, we reduce locally private two-point mean testing to winner publication in a two-candidate Plurality election.

Rules satisfying the majority criterion. Proof of Theorem 3.6. For each i ∈ [m], let π i be a profile with 2t voters, all of whom rank ci first. The majority criterion gives r(π i ) = ci ; changing fewer than t voters cannot remove ci ’s strict majority; and any two such profiles are 2t-neighbors. Thus Assumption 3.4 holds with κ = 2. □

D.1

Scoring rules. For scoring rules that need not satisfy the majority criterion, we start from a cyclic profile in which every candidate has the same score and perturb it to favor a prescribed candidate. Proof of Lemma 3.8. Construct a symmetric base profile π cycle with exactly m rankings. For 1 ≤ i ≤ m, the i-th ranking is the cyclic shift ci ≻ ci+1 ≻ · · · ≻ cm ≻ c1 ≻ · · · ≻ ci−1 . By symmetry, every candidate appears once in every rank position. Hence all candidates have the same score in π cycle :

Algorithm 1 Local publication of DJW-privatized vote vectors s̃ for Plurality

scores (c; π cycle ) = s1 + · · · + sm

∀c ∈ C.

Let ∆ = s1 − sm > 0. Let π base consist of 2t copies of π cycle . This profile has 2mt voters and all candidates are tied: scores (c; π base ) = 2t (s1 + · · · + sm )

∀c ∈ C.

(4)

Upper Bound

Private score release. Each voter represents their topranked candidate by a one-hot vector. The DJW randomizer privately releases this vector, and the aggregator sums the reports to estimate every plurality score simultaneously.

Require: Privacy parameter ε > 0, candidate set C = {c1 , . . . , cm } 1: for all voters i ∈ [n] do 2: Let wi be voter i’s top-ranked candidate  1 if cj = wi , 3: Initialize the one-hot vector vi,j ← 0 otherwise 4: Release ṽ i ← RDJW (v i ; 1, ε) 5: end for Pn 6: Aggregate the scores s̃ ← i=1 ṽ i 7: return s̃ Corollary D.1 For ε > 0, γ ∈ (0, 1/2), p λ = CDJW κε 2n log(2m/γ),

and s̃ the output of Algorithm 1,   Pr max |s̃j − scoreplu (cj )| > λ ≤ γ. j∈[m]

Proof. Since ∥v i ∥2 = 1, Lemma 2.8 implies that each release is ε-LDP and unbiased. For each cj ∈ C, the centered error s̃j − scoreplu (cj ) =

n X (ṽi,j − vi,j )

Set

i=1

is a sum of independent sub-Gaussian random variables and is therefore sub-Gaussian with parameter at most √ CDJW κε n. Thus   λ2 γ Pr[|s̃j − scoreplu (cj )| > λ] ≤ 2 exp − 2 = . 2CDJW κ2ε n m A union bound over the m candidates proves the claim.

□

Winner recovery. The preceding uniform error bound implies that an incorrect noisy winner can occur only when the true plurality score gap, and hence the margin of victory, is small. p Proof of Theorem 4.1. Let λ = CDJW κε 2n log(2m/γ), and condition on the event from Corollary D.1. If the algorithm outputs c ̸= w, then scoreplu (w) − scoreplu (c) ≤ 2λ. Lemma A.1 gives MoV(π, r) ≤ λ + 1. Therefore every profile with MoV(π, r) ≥ λ + 2 is recovered correctly on the conditioned event, which happens with probability at least 1 − γ. □

D.2

Lower Bound

The proof directly reduces two-point mean testing to publishing the winner of a two-candidate Plurality election. Proof of Theorem 4.2. Suppose such an algorithm M exists. Let a > 0 be a sufficiently small universal constant, and set r a log(1/γ) nθ ap n log(1/γ). θ= , τ= = ε n 4 4ε By choosing the constant c in the theorem small enough, the 2 assumption γ ≥ e−cnε ensures that θ ≤ 1/2. Let P+ and P− be the distributions on {−1, 1} given by 1+θ , 2 1−θ , P− (1) = 2 P+ (1) =

1−θ , 2 1+θ P− (−1) = . 2 P+ (−1) =

Interpreting a sign 1 as the ranking c1 ≻ c2 and a sign −1 as c2 ≻ c1 , P+ has mean θ and favors candidate c1 , whereas P− has mean −θ and favors candidate c2 . We consider the following two hypotheses: H+ : (X1 , . . . , Xn ) ∼ P+⊗n ,

Let S be the sum of the signs. Hoeffding’s inequality gives     nθ nθ2 Pr S < ≤ exp − , ⊗n 2 8 P+     2 2 nθ2 nθ ≤ exp − = γ a /(8ε ) . Pr S>− ⊗n 2 8 P−

H− : (X1 , . . . , Xn ) ∼ P−⊗n .

We draw the votes according to one of these hypotheses, run M, and declare H+ if it returns c1 and H− if it returns c2 .

  a ε0 = min 1, √ . 8 Then 0 < ε ≤ ε0 implies a2 /(8ε2 ) ≥ 1, and hence 2 2 γ a /(8ε ) ≤ γ. On the complementary event the Plurality winner agrees with the hypothesis and the score gap is at least nθ/2. Since one vote change alters this gap by at most 2, the margin of victory is at least nθ/4 = τ . Usefulness therefore makes the testing error under each hypothesis at most 2γ. It remains to show that no locally private transcript permits such a test. Let Q+ and Q− be the transcript distributions under the two hypotheses. The strong data-processing inequality for non-interactive local privacy (Duchi, Jordan, and Wainwright 2018) gives DKL (Q+ ∥Q− ) ≤ Cnε2 θ2 = Ca2 log(1/γ) for a universal constant C. Taking a sufficiently small makes this less than log(1/(8γ)). To spell out the testing step, let A be the event that the test declares H+ (equivalently, that M returns c1 ), and let Ac denote its complement, the event that the test declares H− (equivalently, that M returns c2 ). Taking H+ as the null hypothesis, the type-I error is declaring H− when H+ is true, while the type-II error is declaring H+ when H− is true. Their probabilities are eI = Q+ (Ac ),

eII = Q− (A).

Consequently,
eI + eII = 1 − Q+ (A) − Q− (A) ≥ 1 − dTV (Q+ , Q− ). The Bretagnolle–Huber inequality gives p dTV (Q+ , Q− ) ≤ 1 − e−DKL (Q+ ∥Q− ) . √ Since 1 − 1 − x ≥ x/2 for x ∈ [0, 1], these two displays imply 1 eI + eII ≥ e−DKL (Q+ ∥Q− ) > 4γ. 2 But the preceding usefulness argument gave eI , eII ≤ 2γ, and hence eI + eII ≤ 4γ, a contradiction. Taking C ′ = a/4 proves the theorem. □

E

Additional Details for Non-Interactive LDP: Condorcet, Maximin, and Runoff

This appendix fills in the non-interactive LDP details for Condorcet, Maximin, and Plurality with Runoff from Section 4. We first derive all three upper bounds from a common DJW release of pairwise margins. We then develop a generic marginal-release framework and instantiate it with a two-way profile generator to obtain the lower bounds for Condorcet, Maximin, and Runoff.

E.1

Upper Bounds

Pairwise-margin accuracy. All three algorithms use the same private pairwise statistics release, as described in Section 4.2. The following notation records the simultaneous coordinate error
of the DJW release. Let q = m 2 and, for privacy budget ρ > 0 and failure probability β ∈ (0, 1), define p Λpair (ρ, β) := CDJW κρ 2qn ln(2q/β). By Lemma 2.8 and a union bound over the q pairwise coordinates, every estimated pairwise margin is simultaneously accurate to within Λpair (ρ, β) with probability at least 1 − β. Condorcet. For Condorcet, an error either hides a true winner’s weakest victory or creates an apparent winner on a profile whose non-private outcome is ⊥. Theorem E.1 (Details for Theorem 4.3) There exists a non-interactive ε-LDP algorithm that is (τ, γ)-useful for Condorcet voting, where

Algorithm 2 Non-Interactive Algorithm for Plurality with Runoff Require: Preference profile π = (π1 , . . . , πn ), privacy parameter ε Ensure: Winner c ∈ C 1: Each voter releases a DJW-privatized plurality vector using Algorithm 1 with privacy budget ε/2 2: Each voter releases a DJW-randomized pairwise vector using the construction from Section 4.2 with privacy budget ε/2 3: Aggregate the noisy plurality scores ṽ and the noisy e pairwise margins D 4: Let a, b be the two candidates with the largest coordinates of ṽ e b) > 0 then 5: if D(a, 6: return a 7: else 8: return b 9: end if

τ = 1 + 3 log m + 3Λpair (ε, γ). In particular, for 0 < ε ≤ 1, ! p m n ln(m/γ) τ =O . ε Proof. The algorithm is the pairwise DJW release and Condorcet aggregator described in Section 4.2, so it is noninteractive and ε-LDP. Let λ = Λpair (ε, γ) and condition on the event that every estimated pairwise margin is within λ of its true value. The preceding concentration bound shows that this event has probability at least 1 − γ. If the true Condorcet outcome is a candidate w and the algorithm does not output w, then w fails some noisy headto-head comparison, so Dπ (w, d) ≤ λ for some d ̸= w. Lemma A.3 then gives MoV(π, r) ≤ 1 + λ < τ . If the true Condorcet outcome is ⊥ and the algorithm e a) > 0 for every a ̸= c, so outputs a candidate c, then D(c, Dπ (a, c) < λ for every a ̸= c. Hence maxa̸=c Dπ (a, c) < λ, and Lemma A.3 gives MoV(π, r) < 1+3 log m+3λ = τ . Therefore, whenever MoV(π, r) ≥ τ , the algorithm returns the true Condorcet outcome with probability at least 1 − γ. □ Maximin. For Maximin, uniform pairwise accuracy directly controls every candidate’s noisy maximin score. Theorem E.2 (Details for Theorem 4.3) There exists a non-interactive ε-LDP algorithm that is (τ, γ)-useful for the Maximin voting rule, where τ = Λpair (ε, γ) + 2. In particular, for 0 < ε ≤ 1, ! p m n ln(m/γ) . τ =O ε Proof. The algorithm is the pairwise DJW release and Maximin aggregator described in Section 4.2, so it is noninteractive and ε-LDP. By the concentration bound above, with probability at least 1 − γ, e b) − Dπ (a, b)| ≤ λmm := Λpair (ε, γ). max |D(a, a̸=b

Condition on this event. Recall that scoremaximin (a) and s] coremaximin (a) denote the true and noisy maximin scores of a, respectively. Since each pairwise margin is accurate to within λmm , every maximin score is also accurate to within λmm . The noisy-error consequence in Lemma A.4 shows that an erroneous output requires MoV(π, r) ≤ λmm + 1 < τ . Hence, whenever MoV(π, r) ≥ τ , the algorithm cannot err on the conditioned event, and it returns the true winner with probability at least 1 − γ. □ Plurality with Runoff. Algorithm 2 combines the private plurality release from Appendix D with the common pairwise release above. Its aggregator is the same noisy runoff rule as in the interactive protocol; the difference is that all pairwise margins are released before the finalists are known. Theorem E.3 (Details for Theorem 4.3) There exists a non-interactive ε-LDP algorithm that is (τ, γ)-useful for Plurality with Runoff, where   λpair τ = 3 + max 2λplu , λplu + , 2 p λplu = CDJW κε/2 2n ln(4m/γ), λpair = Λpair (ε/2, γ/2). In particular, for 0 < ε ≤ 1, ! p m n ln(m/γ) τ =O . ε Proof. Algorithm 2 is non-interactive because each voter applies the same combined randomizer once. The noisy plurality release is ε/2-LDP, and so is the DJW pairwise release. By composition, the algorithm is ε-LDP. By Corollary D.1, with privacy budget ε/2 and failure probability γ/2, all noisy plurality scores are within λplu of their true values with probability at least 1 − γ/2. By

the DJW concentration bound, with failure probability γ/2, every noisy pairwise margin is within λpair of its true value. Thus, with probability at least 1 − γ, both events hold. We condition on this event. Lemma A.2, with η = λplu and ζ = λpair , shows that an erroneous output requires   λpair MoV(π, r) ≤ 2 + max 2λplu , λplu + < τ. 2 Therefore the algorithm outputs the true winner with probability at least 1 − γ whenever MoV(π, r) ≥ τ . □

E.2

Generic Marginal-Release Framework

Beginning with this subsection, we develop the noninteractive lower bounds for Condorcet, Maximin, and Plurality with Runoff. For a Boolean dataset X = (x1 , . . . , xN ) with xi ∈ {0, 1}d , recall from Definition 4.4 the k-way marginal vector Q(X) = (QA (X))A∈([d]) . We denote by Q̄(X) = Q(X)/N k the vector of normalized marginals. We start by stating the following lower bounds for releasing normalized k-way marginals from (Edmonds, Nikolov, and Ullman 2020). Theorem E.4 (Edmonds, Nikolov, and Ullman 2020) For every non-interactive ε-LDP mechanism M, with 0 < ε ≤ 1, releasing all normalized marginals, the following minimax lower bounds hold, up to logarithmic factors: 1. For two-way marginals6 ,    d e sup E∥M(X) − Q̄(X)∥∞ ≥ Ω min 1, √ . ε N X 2. More generally, for k-way marginals with 1 ≤ k ≤ d/2, sup E∥M(X) − Q̄(X)∥∞ X ( √ )! Ω( k) (d/k) e min 1, √ ≥Ω . ε N Our lower bounds reduce private marginal release to private winner publication. We first isolate the properties required of a rule-specific profile generator, then analyze a nonadaptive threshold scan that converts useful winner predictions into accurate marginal estimates. Compatible profile generators. The only rule-specific ingredient in our reduction is a profile generator that encodes each query and threshold as an election. Fix a voting rule r and a non-interactive LDP algorithm Mr . On a profile π = (π1 , . . . , πn ), the algorithm applies its randomizers7 Rr1,ε , . . . , Rrn,ε on π1 , . . . , πn respectively, and then runs its aggregator on the privatized messages. The profile generator F has four components: 6 This lower bound follows from two-way parity queries, which can be simulated using two-way marginals by querying both the original and bit-flipped inputs. Combining the two marginals yields the count of inputs with xi ⊕ xj = 0, recovering parity with at most a factor-of-two increase in the privacy and error parameters. 7 This notation includes the special case in which every voter uses the same randomizer.

• Fcand constructs the candidate set C; • Fdata constructs the data-dependent profile π X where each ranking in π X depends on exactly a single xi , and the per-ranking privacy budget ε′ ; • Fquery constructs a query profile π A and designated winner wA ; (τ )

• Fthres constructs a threshold profile π A . For query A and threshold τ , the election profile is π X ◦ (τ ) πA ◦ πA . The generator is useful when the winner tests the marginal PN Q value µA = i=1 j∈A xi,j . The following definition records the four properties needed by the reduction. Definition E.5 (Compatibility) A non-interactive LDP voting algorithm for r and a profile generator F are compatible at target budget ε if, for every threshold τ ∈ [N ], the output (C, π (τ ) , wA , ε′ ) ← F(d, X, A, τ, ε) satisfies: PN Q (i) wA = r(π (τ ) ) if and only if i=1 j∈A xi,j ≥ τ ; PN Q (ii) MoV(π (τ ) , r) ≥ i=1 j∈A xi,j − τ ; (iii) every π (τ ) has the same number of rankings, independent of A and τ ; (iv) sε′ = ε, where s is the maximum number of data-dependent rankings that depend on any one record xi . Non-adaptive threshold scan. Compatibility lets us recover µA by testing all thresholds. It is important that these tests are fixed in advance: because they reuse the same privatized copy of π X , their errors need not be independent, so an adaptive argument cannot treat them as independent trials. Algorithm 3 first privatizes the data-dependent profile π X once and reuses those messages in every test. For each marginal query A and threshold τ , it appends the public query and threshold profiles produced by F, generates their messages, and runs the voting aggregator. Compatibility makes the event that the aggregator returns wA a test of whether µA ≥ τ . The indicator T [τ ] records the result of this test, and the largest accepted threshold is used as the estimate µ̂A . Only the reused messages for π X depend on the private dataset; the remaining messages are generated from public rankings and incur no additional privacy loss. The next lemma bounds both the high-probability and expected errors. The expected-error statement is useful because the marginal lower bounds invoked below are formulated in expectation. Lemma E.6 Let X be a dataset and let Mr be an ε′ -LDP algorithm that is (τ, γ)-useful for voting rule r. Let Q(X) be the vector of all k-way marginal answers. If there is a profile generator F compatible with Mr at target budget ε, and each record contributes at most s data-dependent rankings, then ε′ = ε/s by condition E.5, and there is an ε-LDP algorithm M such that   d Pr[∥M(X) − Q(X)∥∞ > τ + 1] ≤ N γ. k

Algorithm 3 Non-Adaptive Reduction to ε-LDP k-Way Marginals

E.3

Input: Data x1 , . . . , xN where xi ∈ {0, 1}d for all i ∈ [N ] LDP Algorithm: Mr with randomizers (Rri )i∈[n] and aggregator Ar Profile Generator: F composed of components Fcand , Fdata , Fquery , Fthres . 1: C ← Fcand (d). 2: (π X , ε′ ) ← Fdata (X, ε). 3: Let nX = |π X | and privatize its rankings once using the corresponding randomizers Rr1,ε′ , . . . , RrnX ,ε′ . 4: for all A ⊆ [d] such that |A| = k do 5: (π A , wA ) ← Fquery (A). 6: Let T be an array of size N . 7: for all τ ∈ [N ] do (τ ) 8: π A ← Fthres (A, wA , τ ). (τ ) 9: Randomize the public rankings in π A ◦ π A using the corresponding remaining randomizers RrnX +1,ε′ , . . . , Rrn,ε′ . 10: Run Ar on the reused messages for π X and the public messages for this (A, τ ), obtaining w. 11: T [τ ] ← 1(w = wA ). 12: end for 13: µ̂A ← max({0} ∪ {τ ∈ [N ] : T [τ ] = 1}). 14: Output µ̂A for marginal query A. 15: end for

We now instantiate the generic reduction for two-way marginals. A single family of profile generators suffices for all three rules. The padding forces the two queried candidates to dominate all outsiders and keeps the election size fixed for every threshold.

Moreover, for the normalized answers Q(X)/N ,

Two-Way Reduction for Condorcet, Maximin, and Plurality with Runoff

Profile generator. For a dataset X = (x1 , . . . , xN ) with xi ∈ {0, 1}d , a query A = {j, k}, and privacy budget ε, (ν) define the generator F2way as follows. Assume, without loss of generality, that cj ≻σ ck in the fixed ranking σ. • Fcand (d) returns the candidate set C = {c1 , . . . , cd }. Let σ be a fixed ranking of C, and let σ R be its reverse. • Fdata (X, ε) returns (π X , ε′ ), where π X = (π1 , . . . , π2N ) and ε′ = ε/2. For each record xi , let Si = {cj : xi,j = 1} and S̄i = C \ Si , and define π2i−1 :

(σ |Si ) ≻ (σ |S̄i ),

π2i :

(σ R |S̄i ) ≻ (σ |Si ).

Exactly two rankings are associated with each data point, so ε′ = ε/2 satisfies condition E.5 (iv). • Fquery (A) returns (π A , wA ), where wA = cj and ′ π A = (π1′ , . . . , π4N +2ν ). For each i ∈ [2N + ν], set ′ π2i−1 :

cj ≻ ck ≻ (σ |C\{cj ,ck } ),

′ π2i :

ck ≻ cj ≻ (σ |C\{cj ,ck } ).

• Fthres (A, wA , τ ) returns the fixed-size profile (τ )

    M(X) Q(X) d τ +1 E − +N γ. ≤ N N N k ∞ Proof. The data-dependent messages are generated only once. Every record contributes at most s messages, each with privacy budget ε′ , so condition E.5 (iv) and composition theorem make their joint release ε-LDP. All remaining rankings are public, and every subsequent operation is postprocessing. Thus M is ε-LDP. Fix A and write µA = QA (X). For every fixed threshold τ satisfying |µA − τ | ≥ α, compatibility and usefulness imply that T [τ ] is correct with probability at least 1 − γ.
There are at most N kd fixed query–threshold pairs. A union bound, which does not require independence, shows that all such tests
are simultaneously correct with probability at least 1 − N kd γ. Condition on this event. No threshold greater than µA + α is accepted, so µ̂A ≤ µA + τ . Conversely, if µA > τ + 1, the integer τA = ⌊µA − τ ⌋ is accepted and satisfies τA > µA − τ − 1; if µA ≤ τ + 1, the default value 0 already satisfies the required lower bound. Thus |µ̂A − µA | ≤ τ + 1 for every A (the harmless +1 also covers non-integral τ and boundary ties). The normalized error is at most 1 on the complementary event. Splitting the expectation according to the good event proves the second inequality. □

+ N −τ − N +τ −1 π A = (πA ) ◦ (πA ) ,

where + πA :

cj ≻ ck ≻ (σ |C\{cj ,ck } ),

− πA :

ck ≻ cj ≻ (σ |C\{cj ,ck } ).

This profile has exactly 2N − 1 rankings for every τ ∈ [N ]. Pairwise-margin calculation. The two rankings associated with each data point are designed so that their net comparison between the queried candidates records exactly the corresponding two-way conjunction. Lemma E.7 For any ν ∈ Z≥0 , let (π X , ·) = Fdata (X, ·) be (ν) the data profile in F2way . For any j, k ∈ [d] with cj ≻σ ck , NπX (cj ≻ ck ) = 2µ11 + µ10 + µ01 + µ00 , NπX (ck ≻ cj ) = µ10 + µ01 + µ00 , where µab = |{i ∈ [N ] : xi,j = a ∧ xi,k = b}|. Proof. The two rankings associated with record xi compare cj and ck as follows: xi,j 1 1 0 0

xi,k 1 0 1 0

π2i−1 ≻ ≻ ≺ ≻

π2i ≻ ≺ ≻ ≺

Here ≻ means cj ≻ ck , and ≺ means ck ≻ cj . Counting the rows of the table gives the two displayed identities. □ The query profile contributes equally to the two pairwise directions, while the threshold profile gives ck a net pairwise advantage of 2τ − 1 over cj . Therefore we have the following consequence. Corollary E.8 For any ν ∈ Z≥0 , let π 2way be a profile (ν) generated by F2way . For any query A = {j, k} with cj ≻σ ck , Nπ2way (cj ≻ ck ) − Nπ2way (ck ≻ cj ) = 2µ11 − 2τ + 1, where µ11 = |{i ∈ [N ] : xi,j = xi,k = 1}|. Proof. The generated profile is the concatenation

candidate are at least 2N even when ν = 0. Because r ≤ N , changing fewer than r rankings preserves both the sign of the decisive comparison and the victories of the queried candidates over every outsider. The same queried candidate therefore remains the Condorcet and Maximin winner. Thus the margin of victory is at least |µ − τ |, and the compatibility conditions hold. □ For Plurality with Runoff, additional padding forces the same queried pair to be the two first-round finalists. Lemma E.10 (Plurality with Runoff) For Plurality with (2N ) Runoff, F2way is compatible with MPlu2 . Proof. Fix a query A = {j, k} with cj ≻σ ck , and write PN µ = i=1 xi,j xi,k . In the generated profile,

(τ )

π 2way = π X ◦ π A ◦ π A . By the preceding lemma, the data profile contributes pairwise margin NπX (cj ≻ ck ) − NπX (ck ≻ cj ) = 2µ11 . The query profile consists of 2N + ν rankings in each pairwise direction, so its contribution to the margin is zero. Finally, the threshold profile contains N − τ rankings with cj ≻ ck and N + τ − 1 rankings with ck ≻ cj , and therefore contributes (N − τ ) − (N + τ − 1) = 1 − 2τ. Adding the three contributions gives Nπ2way (cj ≻ ck ) − Nπ2way (ck ≻ cj ) = 2µ11 − 2τ + 1, as claimed. □ Thus, whenever cj and ck are the decisive pair for the voting rule, the designated candidate cj wins exactly when PN i=1 xi,j xi,k ≥ τ . Compatibility with the voting rules. We now verify the remaining compatibility conditions. For Condorcet and Maximin, the query profile makes the queried pair dominate every outside candidate, so their head-to-head comparison determines the winner. Lemma E.9 (Condorcet and Maximin) The profile gener(0) ator F2way is compatible with the non-interactive Condorcet and Maximin algorithms.

scoreplu (ca ) ≥ 2N + ν scoreplu (cℓ ) ≤ 2N

for each a ∈ A, for each ℓ ∈ [d] \ A.

With ν = 2N > 0, both cj and ck are therefore plurality finalists. Their runoff is decided by the pairwise margin in Corollary E.8, so Plurality with Runoff returns cj exactly when µ ≥ τ . Changing fewer than min{ν/2, |µ − τ |} rankings cannot either remove one of the queried candidates from the runoff or reverse the final pairwise comparison. With ν = 2N , the margin is at least |µ − τ |, and compatibility follows. □ Reduction and lower bound. The two compatibility lemmas let us invoke the generic marginal-release framework. We first state the resulting two-way reduction and then combine it with the local marginal lower bound. Theorem E.11 (Reduction for Corollary 4.5) Let X = (x1 , . . . , xN ) with xi ∈ {0, 1}d , and let Q(X) = PN Q (QA (X))A∈([d]) , where QA (X) = i=1 j∈A xi,j . If 2

there exists an ε/2-LDP algorithm for Condorcet, Maximin, or Plurality with Runoff—with d candidates and 12N − 1 voters—that is (α, γ)-useful, then there exists an ε-LDP algorithm M such that   d Pr[∥M(X) − Q(X)∥∞ > α + 1] ≤ N γ, 2 and     M(X) Q(X) α+1 d E − ≤ +N γ. N N N 2 ∞

Proof. Fix a query A = {j, k} with cj ≻σ ck , and write PN µ = i=1 xi,j xi,k . For every ℓ ∈ [d] \ A, the query profile ensures

Proof. Apply Lemma E.6 with k = 2 and use F2way for all three rules. Every generated election has

Nπ2way (cj ≻ cℓ ) − Nπ2way (cℓ ≻ cj ) ≥ 2N + 2ν,

2N + (4N + 4N ) + (2N − 1) = 12N − 1

Nπ2way (ck ≻ cℓ ) − Nπ2way (cℓ ≻ ck ) ≥ 2N + 2ν. Thus both queried candidates beat every outside candidate head-to-head. By Corollary E.8, cj beats ck exactly when µ ≥ τ ; otherwise ck beats cj . Hence one of cj , ck is the Condorcet winner, so both Condorcet and Maximin return cj exactly when µ ≥ τ . For completeness, set r = |µ − τ |. The decisive pairwise margin has absolute value 2r+1 when µ ≥ τ and 2r−1 otherwise. Moreover, the displayed margins against every outside

(2N )

voters. Each data point contributes exactly two rankings, each privatized with budget ε/2, so the induced marginal-release algorithm is ε-LDP. Lemma E.6 gives the stated bounds. □ Combining Theorem E.11 with Theorem E.4 gives the candidate dependence used in the summary table. Proof of Corollary 4.5. Set ε0 = 1/2 and apply Theorem E.11 with its privacy parameter set to 2ε, as well as d = m, N = Θ(n), and α = τ . The assumed voting algorithm is then the required (2ε)/2-LDP algorithm, and the

resulting marginal mechanism is 2ε-LDP. Since 2ε ≤ 1, Theorem E.4 applies; the factor of two is absorbed into the constants. If γ ≤ √ c/(m2 n2 ) for a sufficiently small c and τ = oe(min{n, m n/ε}), the expected normalized error √ in Theorem E.11 would be oe
(min{1, m/(ε N )}): the first term has this order, and N m 2 γ = O(1/N ). This contradicts the two-way case of Theorem E.4. Hence the displayed lower bound on τ follows. □ e √n/ε) non-interactive Corollary 4.5 explains the Ω(m LDP lower-bound entries for Condorcet, Maximin, and Plurality with Runoff in Table 1.

F

Additional Details for Non-Interactive LDP: STV

The non-interactive STV algorithm uses the same noisy elimination rule as the interactive protocol, but releases all statistics that might be needed before the elimination process begins. Recall that I = {(S, c) : S ⊆ C, |S| ≥ 2, c ∈ S}, and that TS,c (π) = 1 exactly when c is the highest-ranked candidate in S under ranking π. Consequently, n X

Require: Preference profile π = (π1 , . . . , πn ), privacy parameter ε Ensure: Winner c ∈ C 1: Each voter releasesP Zi = RDJW (T (πi ); rT , ε) n 2: Aggregate s eS,c ← i=1 Zi,S,c for every (S, c) ∈ I 3: A ← C 4: for j = 1 to m − 1 do 5: ej ← argminc∈A seA,c {Tie broken arbitrarily} 6: A ← A \ {ej } 7: end for 8: return the unique candidate in A Proof. We use Algorithm 4. Since each voter applies one εLDP DJW randomizer, the algorithm is non-interactive and ε-LDP. For each coordinate (S, c), Lemma 2.8 shows that Zi,S,c − TS,c (πi ) is sub-Gaussian with parameter at most CDJW κε rT . Independence across voters and a union bound over the DT coordinates therefore imply that, with probability at least 1 − γ, max |e sS,c − scoreplu (π|S , c)| ≤ λT .

(S,c)∈I

TS,c (πi ) = scoreplu (π|S , c),

i=1

P so the coordinates of i T (πi ) contain the round scores for every possible active set S. Each voter sends one DJW-privatized version of the entire vector T (πi ). After summing the reports, the aggregator has estimates seS,c for all (S, c) ∈ I. It starts with S = C, eliminates a candidate having minimum estimated score seS,c , and repeats using the coordinates indexed by the new active set. Although the realized active set depends on earlier noisy eliminations, every score that could be queried was included in the original release. Thus the voters send no further messages, and the algorithm remains non-interactive. The cost is that T (πi ) has coordinates for exponentially many active sets, which produces the 2m/2 dependence in the utility bound.

F.1

Algorithm 4 Non-Interactive Algorithm for STV

Upper Bound

Algorithm 4 uses the same noisy elimination aggregator as the interactive protocol. Its only difference is that it privately releases the plurality scores for every possible active set in advance. The following is a more precise version of Theorem 4.6. Theorem F.1 (Details for Theorem 4.6) There exists a non-interactive ε-LDP algorithm that is (τ, γ)-useful for STV, where τ = m2 + 2(m − 1)λT + 1, p λT = CDJW κε rT 2n ln(2DT /γ), √ rT = 2m − m − 1, DT = m2m−1 − m. In particular, for 0 < ε ≤ 1, ! p m2m/2 n ln(m2m /γ) τ =O . ε

Condition on this event. Corollary A.6 shows that an erroneous output requires MoV(π, r) ≤ m2 + 2(m − 1)λT < τ. Therefore every profile with MoV(π, r) ≥ τ is recovered correctly on the conditioned event. □

F.2

STV Lower-Bound Reductions

The reduction below uses the following certificate to show that the winner of its constructed STV election is stable under nearby profile changes. Intuitively, a set S ∈ S is an active candidate set that may be reached after a sequence of eliminations that we are willing to allow. We do not need to certify one fixed elimination order. Instead, at every such state S, the set E(S) contains the candidates that may safely be eliminated next, and deleting any one of them must lead to another certified state in S. The score-gap condition separates these candidates from the protected candidates in S \ E(S) by more than 2t. Since changing t rankings can alter each round score by at most t, this separation survives every allowed perturbation. Thus S is a branching family of possible active sets that starts at C, always contains w, and funnels every possible elimination sequence to the terminal set {w}. Lemma F.2 (STV lower certificate) Fix a profile π, a candidate w, and a nonnegative integer t. Suppose there is a family S of candidate sets such that C, {w} ∈ S and every S ∈ S contains w. For every S ∈ S \ {{w}}, suppose there is a nonempty set of safe eliminations E(S) ⊆ S \ {w} satisfying S \ {e} ∈ S

for every e ∈ E(S),

and min c∈S\E(S)

scoreplu (π|S , c) − min scoreplu (π|S , e) > 2t. e∈E(S)

Then w remains the STV winner after any t ranking changes, and hence MoV(π, r) > t. Proof. Changing t rankings changes every restricted plurality score by at most t. Thus, for every S ∈ S, some candidate in E(S) still has strictly fewer votes than every candidate in S \E(S). The candidate eliminated from S therefore belongs to E(S), regardless of tie-breaking, and the next active set remains in S. Induction from C shows that the only possible final active set is {w}. □ We now build a stronger STV gadget for arbitrary k-way marginals. Theorem F.3 (Reduction for Corollary 4.7) Let X = (x1 , . . . , xN ) with xi ∈ {0, 1}d , and let Q(X) = PN Q (QA (X))A∈([d]) , where QA (X) = i=1 j∈A xi,j . If k

there exists an ε/2-LDP algorithm for STV—with d + 3 candidates and (6k + 18)N − 2 voters—that is (τ, γ)-useful for γ ≤ 1/4, then there exists an ε-LDP algorithm M such that   d Pr[∥M(X) − Q(X)∥∞ > τ + 1] ≤ N γ, k and     M(X) Q(X) d τ +1 E − +N ≤ γ. N N N k ∞ Proof. We construct a compatible profile generator F . Let ν be a padding parameter, chosen below. • Fcand (d) returns C = {c1 , . . . , cd , c∗ , c′ , c′′ }. Let σ be a fixed ranking of the coordinate candidates c1 , . . . , cd . • Fdata (X, ε) returns (π X , ε′ ) with ε′ = ε/2, where π X = (π1 , . . . , π2N ) ◦ (π ∗ , π ′ , π ′′ )2N +ν . For each record xi , let Si = {cj : xi,j = 1} and S̄i = {cj : xi,j = 0}. The two data-dependent rankings are π2i−1 , π2i : (σ |S̄i ) ≻ c∗ ≻ c′ ≻ c′′ ≻ (σ |Si ). The padding rankings are π∗ :

c∗ ≻ c′ ≻ c′′ ≻ σ,

π′ :

c′ ≻ c∗ ≻ c′′ ≻ σ,

′′

c′′ ≻ c∗ ≻ c′ ≻ σ.

π :

Thus the padding part contains 2N + ν copies of each of π ∗ , π ′ , and π ′′ . • Fquery (A) returns (π A , wA ) with wA = c∗ and π A = ⃝j∈A (π (j) )4N +ν , where π (j) : cj ≻ c∗ ≻ c′ ≻ c′′ ≻ (σ |C\{cj ,c∗ ,c′ ,c′′ } ). • Fix any jA ∈ A, and let 0 πA : cjA ≻ c∗ ≻ c′ ≻ c′′ ≻ (σ |C\{cjA ,c∗ ,c′ ,c′′ } ).

Then Fthres returns the fixed-size profile (τ )

0 4(N −τ ) π A = (π ′ , π ′′ )2τ −1 ◦ (πA ) ,

using the same π ′ and π ′′ as above. The first term contains 2τ − 1 copies of each of π ′ and π ′′ , so the threshold profile contains exactly 4N − 2 rankings for every τ ∈ [N ]. PN Q Let µ = i=1 j∈A xi,j . Suppose the last remaining candidates are {c∗ , c′ , c′′ } ∪ {cj : j ∈ A}. At that point the first-place counts are candidate #votes cj for j ∈ A ≥ 4N + ν c′ 2N + ν + 2τ − 1 c′′ 2N + ν + 2τ − 1 c∗ 2N + ν + 2µ Set ν = 2N . Before all coordinate candidates outside A have been eliminated, each such candidate can receive first-place votes only from the 2N data-dependent rankings. In contrast, each of c∗ , c′ , c′′ has at least 2N + ν first-place votes from the padding, and each queried coordinate candidate has at least 4N + ν from the query profile. Hence all coordinate candidates outside A are eliminated before the displayed set remains. We first identify the winner. If µ < τ , then c∗ is eliminated first from the displayed set and its votes transfer to c′ . Candidate c′′ is then eliminated and also transfers to c′ . At that point c′ has 6N + 3ν + 4τ + 2µ − 2 votes, whereas every queried coordinate candidate has at most 6N + ν + 4(N − τ ) votes. Thus c′ wins. If µ ≥ τ , both c′ and c′′ are eliminated before c∗ and transfer their votes to it. Candidate c∗ then has at least 6N + 3ν + 2µ + 4τ − 2 votes and again exceeds the same upper bound for every queried coordinate candidate. Thus c∗ wins if and only if µ ≥ τ. It remains to certify the margin. Let δ = |µ − τ | and fix an integer t < δ; since δ ≤ N = ν/2, we also have t < ν/2. We describe the safe elimination sets required by Lemma F.2. While an outside coordinate candidate remains, all such candidates are safe to eliminate. Their score is at most 2N , whereas every protected candidate has score at least 2N + ν, giving a gap greater than 2t. If µ < τ , then at the displayed set only c∗ is initially safe: the next-smallest scores exceed its score by at least 2δ−1 > 2t. After c∗ is eliminated, every candidate other than the eventual winner c′ is safe. While c′′ remains, candidate c′ leads it by 2N + ν + 2µ > 2t. Once c′′ is eliminated, c′ leads every remaining queried coordinate candidate by at least 8τ + 2µ − 2 > 2t. These gaps can only increase as further queried candidates are eliminated. If µ ≥ τ , then c′ and c′′ are initially safe, and every other candidate leads them by at least 2δ + 1 > 2t. After one is

eliminated, its transfer only increases the lead over the other. Once both are eliminated, every queried coordinate candidate is safe, while c∗ leads each of them by at least 2µ + 8τ − 2 > 2t. Again, subsequent transfers go to c∗ and preserve the certificate. The active sets reachable through these safe eliminations form the family S in Lemma F.2. Therefore the corresponding winner, c′ when µ < τ and c∗ when µ ≥ τ , is unchanged after any t < δ ranking changes. Hence MoV(π, r) ≥ |µ − τ |. The number of voters is 2N +3(2N +ν)+k(4N +ν)+(4N −2) = (6k +18)N −2, so the generator is compatible with an ε/2-LDP STV algorithm, and Lemma E.6 gives the claimed marginal estimator. □ Combining this reduction with the k-way local marginal lower bound gives the following consequence. Proof of Corollary 4.7. Set ε0 = 1/2 and apply Theorem F.3 with its privacy parameter set to 2ε and α = τ . The resulting marginal mechanism is 2ε-LDP, so Theorem E.4 applies. First take k = 2 and d = m − 3. The generated election has n = 30N − 2, so N = Θ(n). The expected-error bound in Theorem F.3, together with the two-way marginal lower bound, gives   √  m n e τ = Ω min n, . ε Next take k = ⌊d/2⌋ = Θ(m). Now n = (6k + 18)N − 2, so N = Θ(n/m), and  Ω(√k) √ d = 2Ω( m) . k
The assumed bound on γ, together with kd ≤ 2d , makes the
failure term N kd γ negligible. The k-way marginal lower bound therefore gives ( )! p √ n/m n Ω( m) e min τ =Ω , 2 . m ε The factor m−1/2 in the second term is √ absorbed by decreasing the absolute constant hidden in Ω( m). Taking the stronger of the two choices of k proves the claim. □

G

Additional Details for Interactive Local Differential Privacy

This appendix gives the algorithms and complete proofs for the interactive LDP results in Section 5. The structural margin bounds used below are collected in Appendix A. As in the non-interactive analyses, each proof separates privacy and concentration from the deterministic margin certificate; interactivity changes only which statistics are released and their resulting error.

G.1

Plurality with Runoff

Algorithm 5 is the interactive counterpart of the noninteractive Algorithm 2. Both use half of the privacy budget to estimate the first-round Plurality scores and select two noisy finalists. The difference is how they obtain the runoff statistic. Because Algorithm 2 must collect all reports before the finalists are known, it releases noisy margins for every pair of candidates and then uses the margin for the selected pair. Algorithm 5 instead observes the privatized first-stage result and uses the remaining privacy budget to estimate only the head-to-head scores of those two finalists. This adaptive
second query avoids simultaneously estimating all m 2 pairwise margins and thereby improves the dependence of the accuracy bound on the number of candidates. Algorithm 5 Interactive Algorithm for Plurality with Runoff Require: Preference profile π = (π1 , . . . , πn ), privacy budget ε Ensure: Winner c ∈ C 1: Estimate the scores (score ^ plu (π, c))c∈C using Algorithm 1 with privacy budget ε/2 2: Let a and b be the two candidates with the highest scores in (score ^ plu (π, c))c∈C 3: Estimate the scores (score ^ plu (π|{a,b} , c))c∈{a,b} using Algorithm 1 with privacy budget ε/2 4: return arg maxc∈{a,b} score ^ plu (π|{a,b} , c)

Proof of Theorem 5.1. Algorithm 5 makes two calls to Algorithm 1, each with privacy budget ε/2, so sequential composition gives total privacy budget ε. p Let λ = CDJW κε/2 2n log(4m/γ). Apply Corollary D.1 to the first-stage release with failure probability γ/2. Conditional on its transcript, the selected pair {a, b} is fixed, and the second-stage release uses fresh randomness. The same corollary, now applied conditionally with failure probability γ/2, therefore controls the two second-stage scores. Since m ≥ 2, the displayed value of λ is sufficient for both stages. Thus, by a union bound, with probability at least 1−γ every estimate used by the algorithm is within λ of its true value. Condition on this event. The two second-stage score errors imply that the estimated pairwise margin has error at most 2λ. Lemma A.2, with η = λ and ζ = 2λ, shows that an erroneous output requires MoV(π, r) ≤ 2λ + 2. □

G.2

Single Transferable Vote

The interactive algorithm for STV is given in Algorithm 6. In an STV round with active candidate set S, we call scoreplu (π|S , c) the round score of candidate c ∈ S.

Algorithm 6 Interactive Algorithm for STV

Algorithm 7 Interactive Algorithm for Condorcet Winner

Require: Preference profile π = (π1 , . . . , πn ), privacy budget ε Ensure: Winner c ∈ C 1: A ← C 2: for j = 1 to m − 1 do 3: Estimate the scores (score ^ plu (π|A , c))c∈A using Algorithm 1 with privacy budget ε/(m − 1) 4: ej ← arg minc∈A score ^ plu (π|A , c) 5: A ← A \ {ej } 6: end for 7: return the unique candidate in A

Require: Preference profile π = (π1 , . . . , πn ), privacy budget ε Ensure: Winner c ∈ C ∪ {⊥} 1: C ′ ← C, Q ← ⌈log2 m⌉ + 1 2: while |C ′ | > 1 do 3: Partition C ′ into a collection P of disjoint pairs and, if |C ′ | is odd, one unpaired candidate u
4: Estimate all scores score ^ plu (π|{a,b} , d) {a,b}∈P us-

The aggregation rule is the same noisy elimination rule analyzed in Corollary A.6; only the way the round scores are obtained differs from the non-interactive algorithm. Proof of Theorem 5.2. Algorithm 6 makes m − 1 calls to Algorithm 1, each with privacy budget ε/(m − 1), so composition gives total privacy p budget ε. Let λ = CDJW κε/(m−1) 2n log(2m2 /γ). In each round, condition on the transcript before that round. The active candidate set is then fixed, and the round uses fresh randomizer randomness, so Corollary D.1 applies conditionally with failure probability at most γ/(m − 1). A union bound over the rounds therefore shows that, with probability at least 1 − γ, for every realized active set S and every c ∈ S, |score ^ plu (π|S , c) − scoreplu (π|S , c)| ≤ λ.

d∈{x,c}

one batched DJW release with privacy budget ε/Q 12: for each c ∈ C \ {x} do 13: if score ^ ^ plu (π|{x,c} , x) ≤ score plu (π|{x,c} , c) then 14: return ⊥ 15: end if 16: end for 17: return x probability at least 1 − γ, every plurality-score estimate used by the algorithm has error at most p λ = CDJW κε/Q 2mn log(4m2 /γ).

Condition on this event. Corollary A.6 shows that an erroneous output requires MoV(π, r) ≤ m2 + 2(m − 1)λ. □

G.3

d∈{a,b}

ing one batched DJW release with privacy budget ε/Q 5: for each {a, b} ∈ P do 6: c ← arg mind∈{a,b} score ^ plu (π|{a,b} , d) 7: C ′ ← C ′ \ {c} 8: end for 9: end while 10: Let x be the unique candidate in C ′
11: Estimate all scores score ^ plu (π|{x,c} , d) c∈C\{x} using

Condorcet Voting

For a collection P of p two-candidate contests, let BP (π) be the concatenation of the p one-hot vectors that record the top-ranked√candidate in each restricted ranking. Since ∥BP (π)∥2 = p, one release √ RDJW (BP (π); p, ρ) simultaneously estimates all 2p plurality scores under ρ-LDP. We combine the structural bound from Lemma A.3 with the accuracy of the batched pairwise releases. An erroneous noisy comparison yields a small true pairwise margin, which the lemma converts into an upper bound on the election’s margin of victory. Proof of Theorem 5.3. Algorithm 7 makes Q batched DJW releases, each with privacy budget ε/Q, so composition gives total privacy budget ε. Every batch contains at most√m − 1 contests, so its input vector has ℓ2 -norm at most m. Condition on the transcript before any batch. Its contests are then fixed, and its fresh reports satisfy Lemma 2.8 conditionally. There are at most Q ≤ m batches and at most 2m released coordinates per batch. Applying the conditional tail bound and a union bound over these at most 2m2 coordinates shows that, with

Consequently, with D̂(a, b) = score ^ ^ plu (π|{a,b} , a) − score plu (π|{a,b} , b), we have |D̂(a, b) − Dπ (a, b)| ≤ 2λ. We argue by contraposition. If the algorithm changes the outcome, then either a true Condorcet winner w loses one noisy head-to-head comparison, or a profile with no Condorcet winner produces a candidate c that wins all noisy head-to-head comparisons. In the first case, mind∈C\{w} Dπ (w, d) ≤ 2λ. In the second, maxa∈C\{c} Dπ (a, c) ≤ 2λ. Lemma A.3 then bounds the margin of victory by s  2 4m 1 + 3 log2 m + 6CDJW κε/Q 2mn log . γ □

G.4

Interactive lower bound

Proof of Theorem 5.4. Suppose √ for contradiction that an
interactive protocol is C min{n, n/ε}, γ -useful, where the universal constant C > 0 will be fixed below. The fully interactive simple-hypothesis-testing lower bound of Joseph et al. (2019, Theorem 5.3) implies that there is a universal

c0 > 0 such that distinguishing two distributions at totalvariation distance α with error at most 1/3 requires at least c0 /(ε2 α2 ) users, for 0 < ε ≤ 1. First suppose nε2 < c0 /2. Take P+ and P− to be the point masses on the rankings c1 ≻ c2 and c2 ≻ c1 , respectively. The resulting profiles and have margin at least
√ are unanimous n/2. A C min{n, n/ε}, γ -useful protocol, for C ≤ 1/2 and γ ≤ 1/6, would distinguish P+⊗n from P−⊗n with error at most 1/6, contradicting the testing lower bound with α = 1. Now suppose nε2 ≥ c0 /2. Let a α= √ , ε n where a > 0 is a sufficiently small universal constant, and let P+ and P− be the distributions on the two rankings defined by 1+α , 2 1−α . P+ (c2 ≻ c1 ) = P− (c1 ≻ c2 ) = 2

P+ (c1 ≻ c2 ) = P− (c2 ≻ c1 ) =

p Their encoded means are α and −α. Choosing a ≤ c0 /8 ensures α ≤ 1/2 and also makes n < c0 /(ε2 α2 ), so no fully interactive ε-LDP test distinguishes the two hypotheses with error at most 1/3. Choose the universal constant ε0 > 0 sufficiently small that   a2 1 exp − 2 ≤ . 8ε0 12 For 0 < ε ≤ ε0 , Hoeffding’s inequality shows that, under either hypothesis, with probability at least 11/12 the Plurality winner agrees with the sign of the mean and the score gap is at√least nα/2. The margin √ of victory √ is then at least nα/4 = a n/(4ε). Since min{n, n/ε} ≤ n/ε, taking C ≤ a/4 makes this margin at least the assumed usefulness threshold. The protocol would therefore yield a test with error at most 1/12 + 1/6 = 1/4, again a contradiction. Taking C ≤ min{1/2, a/4} proves the two regimes simultaneously. □

Related documents

• Accountability Among Allies: Intra-Party Competition and the Electoral Cost of Scandal#1169200
• Accountability Among Allies: Intra-Party Competition and the Electoral Cost of Scandal#1169030
• Hopeful Losers? A Moral Case for Mixed Electoral Systems#744956
• Movements, Moments, and the Eroding Antitrust Consensus#485932
• Uncertainty, equality, fraternity#771007