# differentially_private_condorcet_voting__5c12b6d1.pdf

Differentially Private Condorcet Voting

Zhechen Li1, Ao Liu2, Lirong Xia2, Yongzhi Cao1 , Hanpin Wang3,1

1Key Laboratory of High Conﬁdence Software Technologies (MOE), School of Computer Science, Peking University, China 2Department of Computer Science, Rensselaer Polytechnic Institute 3School of Computer Science and Cyber Engineering, Guangzhou University, China lizhechen@pku.edu.cn, liua6@rpi.edu, xialirong@gmail.com, caoyz@pku.edu.cn, whpxhy@pku.edu.cn

Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method (CMLAP λ ), exponential Condorcet method (CMEXP λ ), and randomized response Condorcet method (CMRR λ ), where λ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efﬁciency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, CMRR λ satisﬁes (non-approximate) probabilistic Condorcet criterion, while CMLAP λ and CMEXP λ satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.

1 Introduction Voting is a commonly used method for group decision making, where voters submit their preferences over a set of alternatives, and then a voting rule is applied to choose the winner. A major and classical paradigm behind the design and analysis of voting rules is the axiomatic approach (Plott 1976), under which voting rules are evaluated by their satisfaction to various normative properties, known as (voting) axioms. For example, the Condorcet criterion requires that whenever there exists a Condorcet winner, which is the alternative that beats all other alternatives in their head-to-head competitions, it must be selected as the winner. Recently, privacy in voting has become a critical public concern. There are a series of works on examining the differential privacy (DP) (Dwork 2006) of voting (Shang et al. 2014; Hay, Elagina, and Miklau 2017; Yan, Li, and Liu 2020). These works mainly focused on applying several randomized mechanisms to existing voting rules, proving upper bounds on the privacy-preserving level (also called privacy budget, denoted by ϵ throughout the paper), and then evaluating the utility loss (measured by accuracy or mean square error) due to randomness. However, the upper bounds on privacy in most of them are not tight, which means that the ex-

Corresponding Author. Copyright c 2023, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

act privacy-preserving level of the mechanisms is unclear. Moreover, we are not aware of a previous work on making voting private while maintaining the satisfaction to desirable voting axioms beyond strategyproofness (Lee 2015). Therefore, the following question remains largely open.

How can we design private voting rules that satisfy desirable axiomatic properties?

Our contributions. We propose a novel class of randomized voting rules, denoted by CMRand λ , based on the celebrated Condorcet method, which chooses the Condorcet winner when it exists, where Rand is a randomized function (called a mechanism in DP literature) that introduces noises to pairwise comparisons between alternatives, and λ represents the level of noise. To choose a winner, CMRand λ applies Rand with parameter λ to the pairwise comparisons for the input proﬁle until a Condorcet winner appears, and then chooses it as the winner. We focus on three classes voting rules in this family, namely CMLAP λ , CMEXP λ , and CMRR λ , which are obtained by applying the Laplace mechanism, exponential mechanism, and randomized response mechanism, respectively. Under these mechanisms, while it may take exponentially many iterations to obtain the winner by deﬁnition, we show that the winner can be efﬁciently sampled (Lemma 1). Our main technical contributions are three-fold. First, we prove that all the three classes of voting rules are differentially private by characterizing the upper and lower bounds on the privacy budget ϵ (Theorem 1). Second, we study the satisfaction of our voting rules to probabilistic variants to Condorcet criterion (p-Condorcet, requiring the winning rate of the Condorcet winner is not lower than the other alternatives), Pareto efﬁciency (p-Pareto, which requires the winning rate of a is not lower than b, if a Pareto dominates b), monotonicity (a-monotonicity, which ensures the winning rate of each alternative does not decrease when her ranking is lifted by any voter simply), strategyproofness (SDstrategyproofness, SD-SP for short, which ensures that no voter can beneﬁt herself in the sense of stochastic dominance by changing her vote), and participation (lexi-participation, which ensures that no voter can improve the result of the voting lexicographically by withdrawing her vote). Besides, we consider the approximate version of p-Condorcet (α-p Condorcet, Deﬁnition 5) and SD-SP (α-SD-SP, Deﬁnition

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

p-Condorcet α-p-Condorcet p-Pareto a-Mono. α-SD-SP Lexi-Par. Strong Lexi-Par.

CMRR λ eλ e(2 2m)λ CMEXP λ 1+eλ/2 (1+e λ/2) m 1 e(2 2m)λ

CMLAP λ 2eλ 1 e λ

2 m 1 e(2 2m)λ

Table 1: The satisfaction of our mechanisms to the voting axioms, where indicates that the row rule satisﬁes the column axiom, and indicates that the rule does not satisfy the axiom. The expressions in the table represent the level of satisfaction to the approximate axioms (the α in α-p-Condorcet and α-SD-SP).

7), and the strong version of lexi-participation (Deﬁnition 8). Our results suggest that CMLAP λ outperforms CMEXP λ in all aspects examined in the paper, while CMRR λ sometimes achieves better p-Condorcet but only satisﬁes standard lexiparticipation, instead of the strong version (Theorems 2 - 8). The results in the second part are summarized in Table 1. Third, we investigate the relations between DP and the voting axioms. We prove that Condorcet criterion and Pareto efﬁciency are incompatible with DP, and capture the upper bounds of satisfaction to p-Condorcet under ϵ-DP (Proposition 4 - 6). Besides, we show that DP guarantees a lower bound of satisfaction to SD-strategyproofness (Proposition 7). All of the missing proofs can be found in Appendix.

Related work and discussions. To the best of our knowledge, DP was ﬁrst applied to the rank aggregation problem in (Shang et al. 2014). They analyzed the error rates and derived upper bounds on them. Lee proposed an algorithm which is both differentially private and robust to strategic manipulation for tournament voting rules (Lee 2015). Hay et al. used Laplace mechanism and exponential mechanism to improve the privacy of Quicksort and Kemeny-Young method (Hay, Elagina, and Miklau 2017). Kohli and Laskowski explored DP, strategyproofness, and anonymity for voting on single-peaked preferences (Kohli and Laskowski 2018). Torra analyzed the privacy-preserving level of random dictatorship with DP, which is a well-known randomized voting rule (Torra 2019). He investigated the condition where random dictatorship is differentially private, and improved the mechanism to achieve DP for general cases. Yan et al. made tradeoff between accuracy and privacy in rank aggregation to achieve local DP via Laplace mechanism and randomized response (Yan, Li, and Liu 2020). Most of the above works did not consider the tradeoffs between privacy and those desirable properties, and the privacy bounds of them are usually not tight. Liu et al. proposed the exact version of distributional DP (Bassily et al. 2013) and studied the privacy-preserving level of several voting rules, but they did not investigate how to improve the privacy (Liu et al. 2020). Beyond social choice, DP has also been considered in other topics of economics, such as mechanism design (Pai and Roth 2013; Xiao 2013), and matching and resource allocation (Hsu et al. 2016; Kannan et al. 2018). There is a large literature on the analysis of randomized voting (Brandt 2017), most of them studied the satisfaction to axiomatic properties, e.g., complexity of manipulation (Walsh and Xia 2012), strategyproofness (Aziz, Brandl, and

Brandt 2014, 2015), Pareto efﬁciency (Brandl, Brandt, and Hofbauer 2015; Gross, Anshelevich, and Xia 2017), participation (Brandl, Brandt, and Hofbauer 2019) and monotonicity (Brandl, Brandt, and Stricker 2018). The fairness properties of sortition have also been investigated (Benad e, G olz, and Procaccia 2019; Flanigan et al. 2020, 2021). The approximation of those properties was also studied. Procaccia discussed how much a strategyproof randomized rule could approximate a deterministic rule (Procaccia 2010). Birrell and Pass explored the approximate strategyproofness for randomized voting rules (Birrell and Pass 2011). They bounded the difference of the expectations of the utility function with a parameter, but the ratio seems to be more natural for DP.

2 Preliminaries Let A = {a1, a2, . . . , am} denote a set of m 2 alternatives. For any n N, let N = {1, 2, . . . , n} be a set of voters. For each j N, the vote of voter j is a linear order j L(A), where L(A) denotes the set of all linear orders over A, i.e., all transitive, antireﬂexive, antisymmetric, and complete binary relations. Let P = { 1, 2, . . . , n} denote the (preference) proﬁle. For each j N, let P j denote the proﬁle obtained from P by removing j. A (randomized) voting rule is a mapping r: L(A)n (A), where (A) denotes the set of all probability distributions on A. Given a proﬁle P L(A)n, let SP [a, b] denote the number of voters who prefer a to b, i.e., SP [a, b] = |{j N : a j b}|. Let w P [a, b] = SP [a, b] SP [b, a] be the majority margin of a over b. Then the weighted majority graph (WMG) of P can be deﬁned: the vertices of WMG are alternatives in A and there is a directed edge from a to b with weight w P [a, b] if and only if w P [a, b] > 0. Similarly, letting UP [a, b] = Sgn(w P [a, b]), the unweighted majority graph (UMG) of P can also be deﬁned: the set of vertices is A and there is an unweighted directed edge from a to b if and only if UP [a, b] = 1, where Sgn denotes the sign function, i.e., Sgn(x) = x/|x| for all x = 0 and Sgn(0) = 0. The Condorcet winner of P is an alternative a A, such that UP [a, b] = 1 for all b A\{a}, denoted by CW(P). Notice that the Condorcet winner is completely determined by the UMG, we also use CW(UP ) to denote the Condorcet winner claimed by the UMG.

Axioms of voting. A voting rule r satisﬁes Condorcet criterion, if P[r(P) = CW(P)] = 1 holds for all proﬁle P that CW(P) exists. The rule r satisﬁes Pareto efﬁ-

ciency, if P[r(P) = b] = 0 for all proﬁle P, where exists a, b A that a j b for all j N. And r satisﬁes absolute monotonicity (Brandl, Brandt, and Stricker 2018), if P[r(P) = a] P[r(P ) = a] holds for all P, P , such that P j = P j, j = j, and j is a pushup of a in j, i.e., j raises the position of a in j, and keeps the relative position of other alternatives unchanged. A randomized rule r satisﬁes SD-Strategyproofness (Aziz, Brandt, and Brill 2013), if for all P, P and j N that P j = P j and j = j, P b ja P[r(P) = b] P b ja P[r(P ) = b], for all a A 1. A voting rule satisﬁes lexi-participation if for all P, P that P = P\{ j}, there does not exist a A, such that P[r(P) = a] < P[r(P ) = a] and P[r(P) = b] = P[r(P ) = b] for all b j a. Differential privacy (Dwork et al. 2006) is a theoretical guarantee of privacy that requires a function to return similar outputs while receiving similar inputs. Deﬁnition 1 (Differential privacy). A function r with domain D is ϵ-differentially private (ϵ-DP for short) if for all O Range(r) and P, P D differing on only one record,

P[r(P) O] eϵ P[r(P ) O].

In other words, a function r is ϵ-DP, if the ratio between the probabilities for the outputs of any pair of neighboring datasets to be in any given set O must be upper bounded by eϵ. In the context of social choice, r is a voting rule and

D = L(A) = L(A) L(A)2 ,

and P, P are two proﬁles differing on only one voter s vote. Under this requirement, the winner of any DP voting rule will not be signiﬁcantly inﬂuenced by any single voter s vote. As a result, any individual s vote will not be revealed by announcing the winner of the voting process. Notice that Deﬁnition 1 does not require the eϵ upper bound to be tight. The tight upper bound is captured by exact DP, formally deﬁned as follows. Deﬁnition 2 (Exact differential privacy (Dwork 2006)). A voting rule r is exact DP (ϵ-e DP for short) if it is ϵ-DP and there does not exist ϵ < ϵ such that r is ϵ -DP. For both DP and e DP, the privacy budget ϵ usually is decided according to the users demand. For example, i OS 11 requires ϵ 43 and i OS 10 requires ϵ 14 (Orr 2017)2. In the next section, we provide upper and lower bounds for the required noise level for any user-deﬁned privacy budget.

3 Differentially Private Condorcet Methods In this section, we propose a novel class of randomized voting rules. We apply three randomization mechanisms and obtain three classes of voting rules. By analyzing the worst cases, we prove that all of the three rules are differentially private, and our bounds of privacy budget are tight.

1In fact, absolute monotonicity and SD-strategyproof are equivalent to the nonperverseness and the strategyproofness in (Gibbard 1977), respectively. 2i OS has may have stronger privacy requirement for some speciﬁc data types (e.g., ϵ 8 for Safari Auto-play intent detection data) (Apple Inc. 2017).

Mechanism 1: Randomized Condorcet Method

Input: Proﬁle P, Parameter λ, Randomization Rand Output: Winning alternative

1 Function Select Rand(S, λ):

2 Get randomized unweighted graph U Rand λ,P with randomized mechanism Rand;

3 if There exists Condorcet winner a for U Rand λ,P then

4 return a;

6 Select Rand(S,λ);

7 Function CM Rand(P, λ):

8 Compute SP [a, b] for all a, b A;

9 Select Rand(SP , λ);

As mentioned in Section 2, the existence of Condorcet winner is completely determined by the UMG. In our mechanism, denoted by CMRand λ , a randomization mechanism Rand generates a noisy UMG for the given proﬁle, and the voting rule outputs the Condorcet winner. If the Condorcet winner does not exist, the mechanism will generate another UMG, until the Condorcet winner exists, as shown in Mechanism 1. Remark. Notice that for each pair of alternatives a, b A, U Rand λ,P [a, b] and U Rand λ,P [b, a] are determined simultaneously, i.e., U Rand λ,P [a, b] = 1, if and only if U Rand λ,P [b, a] = 1. Thus, any noisy UMG U Rand λ,P produced in Mechanism 1 claims at most one Condorcet winner. In other words, our mechanism is a well-deﬁned map from L(A) to (A). In the randomization process, we adopt three different methods, which are deﬁned as follows. Deﬁnition 3. Given λ > 0, the three randomization mechanisms are Laplace mechanism: Given proﬁle P, for any ai, aj A that i < j, let ˆw P [ai, aj] = w P [ai, aj] + Xij for all ai, aj A and ˆw P [aj, ai] = ˆw P [ai, aj], where

Xij i.i.d Lap(1/λ)3. Under such a mechanism, the noisy UMG is

U LAP λ,P [a, b] = Sgn( ˆw P [a, b]).

Exponential mechanism: For proﬁle P,

P[U EXP λ,P [a, b] = 1] eλ SP [a,b]/2,

P[U EXP λ,P [a, b] = 1] eλ SP [b,a]/2.

Randomized response: For the majority margin w P of a given proﬁle P, if w P [a, b] = 0,

U RR λ,P [a, b] =

( Sgn(w P [a, b]), w.p. eλ

1+eλ , Sgn(w P [a, b]), w.p. 1 1+eλ .

3The Laplace distribution with scale parameter 1/λ, of which the probability density function (PDF) is fλ(x) = λ

Figure 1: The lower and upper bounds of privacy budget (left: m = 5, right: m = 20).

If w P [a, b] = 0, then

P[U RR λ,P [a, b] = 1] = P[U RR λ,P [a, b] = 1] = 1/2. The three randomization mechanisms above are denoted by LAP, EXP, and RR, respectively. For each Rand {LAP, EXP, RR}, the Condorcet winner may not exist for the noisy UMG U Rand λ,P . Thus, our mechanism may need to perform the randomization for several times. In fact, for any given proﬁle P, the expected times of randomization is exp(Θ(m)) (see Appendix A.1). However, such a mechanism with high time complexity can be sampled efﬁciently, as shown in the following lemma. Lemma 1. For any Rand {LAP, EXP, RR} and λ > 0, CMRand λ can be sampled as follows:

For any P L(A) , CMLAP λ (P) is a probability distribution in (A), such that for any a A,

P[CMLAP λ (P) =a] Y

b =a Fλ(w P [a, b]),

where Fλ(x) = R x fλ(t)dt is the cumulative distribution function (CDF) of Lap(1/λ). For any P L(A) , CMEXP λ (P) is a probability distribution in (A), such that for any a A,

P[CMEXP λ (P) = a] Y

1 1 + e λ w P [a,b]/2 .

For any P L(A) , CMRR λ (P) is a probability distribution in (A), such that for any a A,

P[CMRR λ (P) = a] eλ |B(a)|

(1 + eλ)m 1 ,

where B(a) = {b A : SP [a, b] > SP [b, a]}. Since there are totally m alternatives, and the value of P[CMRand λ (P) = a] for each a A in Lemma 1 can be computed in O(m) time. Therefore, CMRand λ can be sampled in O(m2) time. Now, we are ready to show the DP bounds of our rules. For simplicity , we use Gλ(x) to denote P[U Rand λ,P [a, b] = 1], where w P [a, b] = x. For example, when Rand = LAP, Gλ(x) = Fλ(x); when Rand = EXP, Gλ(x) = 1 1+e λx/2 .

Theorem 1. Given λ > 0 and Rand, suppose that CMRand λ satisﬁes ϵ-e DP. When Rand {LAP, EXP}

ln Gm 1 λ (2) Gm 1 λ ( 2) Gλ(2) Gλ( 2) 2m 2

When Rand = RR, (m 1)λ ϵ 2(m 1)λ. Proof Sketch. For the upper bound, w.l.o.g., we make comparison between the winning probabilities of a1 under neighboring proﬁle P and P . According to Lemma 1, we have

P[CMRand λ (P) = a1] =

i=2 P[U Rand λ,P [a1, ai] = 1]

i =j P[U Rand λ,P [aj, ai] = 1] .

Then we can prove that for any a A and any Rand, Y

b =a P[U Rand λ,P [a, b] = 1] e(m 1)λ Y

b =a P[U Rand λ,P [a, b] = 1].

Further, we have P

b =a P[U Rand λ,P [a, b] = 1] P

b =a P[U Rand λ,P [a, b] = 1] e(m 1)λ.

As a consequence, for any Rand {LAP, EXP, RR},

P[CMRand λ (P) = a1] P[CMRand λ (P ) = a1] e2(m 1)λ,

which completes the proof of upper bound. For the lower bound, consider the proﬁle P with n = 2k: k voters: a1 a2 am; k 1 voters: am 1 am 2 a1 am; 1 voter: am am 1 a1. And another proﬁle P : k + 1 voters: a1 a2 am; k 1 voters: am 1 am 2 a1 am.

Then the lower bound is P[CMRand λ (P )=am] P[CMRand λ (P )=am]. With Theorem 1, we can get the upper and lower bounds of exact privacy budget ϵ for any given λ. The relations between the lower and upper bounds when m = 5 and m = 20 are shown in Figure 1.

4 Axioms-Privacy Tradeoff In this section, we analyze our voting rules with axioms mentioned in Section 2. We show that our rules do not satisfy Condorcet criterion and Pareto efﬁciency. To address these challenges, we explore probabilistic variants of them. Then we discuss the satisfaction to absolute monotonicity, SD-strategyproofness, and lexi-participation. To begin with, we analyze our voting rules with Condorcet criterion. But unfortunately, CMRand λ does not satisfy Condorcet criterion with any Rand {LAP, EXP, RR} and λ R+, though it is designed based on the Condorcet method. Intuitively, for any P L(A)n and any pair of alternatives a, b A, P[U Rand λ,P [a, b] = 1] < 1. Then

P[CMRand λ (P) = a] Y

b A\{a} P[U Rand λ,P [a, b] = 1] < 1,

even when a is the Condorcet winner. To deal with this, we propose a probabilistic variant of Condorcet criterion, which is shown in the following deﬁnition. Deﬁnition 4 (Probabilistic Condorcet criterion). A randomized voting rule r satisﬁes probabilistic Condorcet criterion (p-Condorcet) if for every proﬁle P that CW(P) exists and all a A\{CW(P)},

P[r(P) = CW(P)] P[r(P) = a].

At a high level, Deﬁnition 4 is a relaxation of the Condorcet criterion, since it does not always require the voting rule r to select the Condorcet winner. Further, the following theorem holds. Theorem 2. For any λ > 0, CMRR λ satisﬁes p-Condorcet.

In other words, CMRR λ satisﬁes a weak version of Condorcet criterion for any λ > 0. However, the results for CMEXP λ and CMLAP λ are relatively negative.

Proposition 1. CMEXP 0.5 and CMLAP 0.5 do not satisfy p Condorcet. To measure how much CMEXP λ and CMLAP λ deviate from p-Condorcet, we further extend the axiom. Deﬁnition 5 (α-Probabilistic Condorcet criterion). A randomized voting rule r satisﬁes α-probabilistic Condorcet criterion (α-p-Condorcet) if for every proﬁle P that CW(P) exists and for all a A\{CW(P)},

P[r(P) = CW(P)] α P[r(P) = a].

Note that a larger α is more desirable, as α-p-Condorcet is almost equivalent to the standard Condorcet criterion when α . Especially, it reduces to p-Condorcet when α = 1. For CMEXP λ and CMLAP λ , the following theorem holds. Theorem 3. For any λ > 0,

Figure 2: The satisfaction of p-Condorcet with different λ.

CMEXP λ satisﬁes 1+eλ/2 (1+e λ/2) m 1 -p-Condorcet;

CMLAP λ satisﬁes 2eλ 1 e λ

2 m 1 -p-Condorcet;

CMRR λ satisﬁes eλ-p-Condorcet. Proof Sketch. Since there is only one proﬁle P, the normalizations in Lemma 1 are not necessarily considered anymore. Here we take CMEXP λ as an example. Since CW(P) = a, we have w P [a, c] 1, for any c A\{a}, which indicates that P[CMEXP λ (P) = a] has a lower bound. Similarly, P[CMEXP λ (P) = b] has an upper bound for any b A\{a}. Then the lower bound of P[CMEXP λ (P )=a] P[CMEXP λ (P )=b] can be derived. With Theorem 3, we can obtain a more general version of Proposition 1, which is shown as follows.

Proposition 2. Given λ > 0, CMEXP λ satisﬁes p-Condorcet

when ln(eλ/2+1) ln(eλ/2+1) λ/2 +1 m; CMLAP λ satisﬁes p-Condorcet

when λ+ln 2 ln 2 ln(2 e λ) + 1 m.

Notice that both of the LHS of the two inequalities in Proposition 2 are increasing functions of λ which diverge when λ . Thus, for any m, there must exist some λ satisfying the inequalities. Since the upper and lower bounds of the privacy budget can completely be determined by λ, we use λ to denote the privacy level. Also, we use the parameter α in Deﬁnition 4 to denote the level of satisfaction to p-Condorcet, then the tradeoff curves when m = 5 are shown in Figure 2. Similar to the Condorcet criterion, our new class of voting rules do not satisfy Pareto efﬁciency either. Suppose there is an alternative b A, which is Pareto dominated by a A in proﬁle P, i.e., a j b for all j N. Then for any λ and Rand {LAP, EXP, RR}, we have

P[CMRand λ (P) = b] Y

c =b P[U Rand λ,P [b, c] = 1].

According to the Deﬁnition of LAP, EXP, and RR, P[U Rand λ,P (b, c)] > 0 for all c A, which indicates that CMRand λ does not satisfy Pareto efﬁciency. However, a still dominates b in another way. Formally, we have the following deﬁnition.

Deﬁnition 6 (Probabilistic Pareto efﬁciency). A randomized voting rule r satisﬁes probabilistic Pareto efﬁciency (p Pareto) if for each pair of alternatives a, b A that a k b holds for all k N,

P[r(P) = a] P[r(P) = b].

This deﬁnition is a relaxation of Pareto efﬁciency. For our voting rules, the following theorem holds.

Theorem 4. For any λ > 0, CMRR λ , CMEXP λ , and CMLAP λ satisfy p-Pareto. Proof Sketch. Let a, b A be the pair of alternatives that a j b holds for any j N. Then for any j N and any c A\{a, b} such that b j c, we have a j c. Further,

S[a, c] = |{j N : a j c}| |{j N : b j c}| = S[b, c].

Hence, w P [a, c] w P [b, c], for all c A\{a, b}. Then the theorem holds due to the monotonicity of CDFs. Unlike Condorcet and Pareto, the deﬁnition of monotonicity, strategyproofness, and participation are related to two distinct proﬁles. For monotonicity, we use the notion of absolute monotonicity in (Brandl, Brandt, and Stricker 2018). Intuitively, in Mechanism 1, for any a A, whenever a voter i switches her preference i to i by lifting a simply, a will be more likely to defeat any b A\{a} in the one-on-one comparisons. As a consequence, a will be more likely to be the winning alternative in our CMRand λ . Formally, we have the following theorem.

Theorem 5. For any λ > 0, CMRR λ , CMEXP λ , and CMLAP λ satisfy a-monotonicity. Proof Sketch. Let P and P be two proﬁles in L(A)n, such that P j = P j and j is a pushup of a A in j. Then we only need to prove that Y

b =a P[U Rand λ,P [a, b] = 1] Y

b =a P[U Rand λ,P [a, b] = 1],

which is true due to the monotonicity of CDFs. Next, we discuss the strategyproofness of CMRand λ . We adopt the notion of SD-strategyproofness (Aziz, Brandt, and Brill 2013), which implies the absolute monotonicity. However, the results for our rules are not so positive.

Proposition 3. CMRR 1 , CMEXP 1 , and CMLAP 1 do not satisfy SD-strategyproofness. Similar to Deﬁnition 5, we extend the notion of SDstrategyproofness. Deﬁnition 7 (α-SD-Strategyproofness). A voting rule r satisﬁes α-SD-strategyproofness (α-SD-SP for short) if for all P, P and j N, such that P j = P j and j = j, X

b ja P[r(P) = b] α X

b ja P[r(P ) = b], for all a A.

Especially, α-SD-strategyproofness reduces to the standard SD-strategyproofness when α = 1. For our rules, the following theorem holds.

Theorem 6. For any λ > 0, CMRR λ , CMLAP λ and CMEXP λ satisfy e(2 2m)λ-SD-strategyproofness. Proof Sketch. W.l.o.g., for any Rand {LAP, EXP, RR} and any proﬁles P = { 1, 2, . . . , n}, P = { 1, 2 , . . . , n} and a A, we have

P[CMRand λ (P) = a] e(2 2m)λ P[CMRand λ (P ) = a].

Therefore, for any a A, P b 1a P[CMRand λ (P) = b] P b 1a P[CMRand λ (P ) = b] e(2 2m)λ,

which completes the proof. Finally, we discuss the participation of our voting rules. We use the notion of lexi-participation, which requires that a participating agent is always no worse off under lexicographical order. In our rules, each participating voter j can beneﬁt herself, since the majority margin w[a, b] for any a j b will increase due to her vote. Formally, the following theorem holds. Theorem 7. For any λ > 0, CMLAP λ , CMEXP λ , and CMRR λ satisfy lexi-participation. Proof Sketch. On the one hand, we can prove that the winning probability of the top-ranked alternative of the voter i will not decrease after she submits her vote. On the other hand, if there exists any alternative a that

P[CMRand λ (P) = a] < P[CMRand λ (P\{ i}) = a],

there will exists another alternative b that b i a, and

P[CMRand λ (P) = b] < P[CMRand λ (P\{ i}) = b],

which completes the proof. Theorem 7 shows that for any Rand {LAP, EXP, RR}, CMRand λ will not harm any participating voter under lexicographical order. Further more, CMLAP λ and CMEXP λ satisfy a stronger notion, which is deﬁned as follows. Deﬁnition 8 (Strong lexi-participation). A voting rule r satisﬁes strong lexi-participation if for all P, P that P = P\{ j}, there exists a A, such that P[r(P) = a] > P[r(P ) = a] and P[r(P) = b] = P[r(P ) = b] for all b j a. Intuitively, strong lexi-participation guarantees that each voter can beneﬁt from her vote, while lexi-participation only ensures that each voter will not be harmed by her vote. For CMLAP λ and CMEXP λ , we have the following theorem.

Theorem 8. For any λ > 0, CMLAP λ and CMEXP λ satisfy strong lexi-participation. Proof Sketch. When Rand = {LAP, EXP}, for any λ > 0, any pair of a, b A, P[U Rand λ,P [a, b] = 1] are strictly increasing functions of w P [a, b]. Thus, the top-ranked alternative of a voter strictly increases when she submits her vote, which completes the proof. However, CMRR λ does not satisfy strong lexi-participation, since only one vote may be not able to increase the winning probability of any alternative. For example, consider

Condorcet criterion

Pareto efﬁciency

Incompatible

ϵ-Differential privacy

Incompatible

α-p-Condorcet

e ϵ-SD-Strategyproofness

Figure 3: Relations between ϵ-DP and other axioms, where X Y indicates that X implies Y , a solid line between X and Y indicates that X, Y are compatible with some condition, and a dash line between X and Y means that X, Y are incompatible.

the proﬁle P, where the votes of all n (n 3) voters are exactly the same, a1 a2 am. Then for any i1 < i2, we have SP [ai1, ai2] = n and SP [ai2, ai1] = 0. For any P that P = P\{ j}, we have SP [ai1, ai2] = n 1 and SP [ai2, ai1] = 0 for any i1 < i2. Then it follows that U RR λ,P [ai1, ai2] = U RR λ,P [ai1, ai2], for all i1, i2 {1, 2, . . . , m}. As a result, we have

P[CMRR λ (P) = ai] = P[CMRR λ (P ) = ai], for all ai A,

which indicates that CMRR λ does not satisfy strong lexiparticipation.

5 Differential Privacy as a Voting Axiom

In Section 4, we explored the tradeoffs between privacy and some voting axioms. In this section, differential privacy is regarded as an axiomatic property of voting rules. The relations between DP and some of the voting axioms are discussed. Our results are summarized in Figure 3. As proved previously, for any Rand {LAP, EXP, RR}, CMRand λ does not satisfy Condorcet criterion under DP. Furthermore, we can prove that they are incompatible.

Proposition 4. There is no voting rule r satisfying Condorcet criterion and ϵ-DP for any ϵ > 0.

Proof Sketch. Suppose there is a voting rule r satisfying Condorcet criterion and ϵ-DP, where ϵ > 0. Then the Condorcet criterion ensures that there exist some proﬁle P and alternative a A that P[r(P) = a] = 0. However, all proﬁles in L(A)n are somehow connected by the DP-inequality. As a result, for such a proﬁle P, we have P[r(P) = b] = 0 for each b A, which leads to a contradiction. Similarly, Pareto efﬁciency is also incompatible with DP, which indicates that the stronger notions of efﬁciency, e.g., PC-efﬁciency and SD-efﬁciency (Brandt 2017) are all incompatible with DP. Formally, we have the following result.

Proposition 5. There is no voting rule r satisfying Pareto efﬁciency and ϵ-DP for any ϵ > 0.

To show the limitation of the tradeoff between Condorcet criterion and DP by any mechanism, we measure the incompatibility between Condorcet criterion and DP using the notion of α-p-Condorcet. The result is shown as follows.

Proposition 6. There is no voting rule satisfying ϵ-DP and α-p-Condorcet with α > eϵ.

Proof. Let P, P be proﬁles that CW(P) = a,CW(P ) = b, P j = P j, and j = j. Then

P[f(P) = a] α P[f(P) = b] α eϵ P[f(P ) = b]

α2 eϵ P[f(P ) = a] α2 e 2kϵ P[f(P) = a].

Thus, α2e 2ϵ 1, i.e., α eϵ.

The SD-strategyproofness is compatible with DP, as the trivial voting rule, i.e., P[r(P) = a] = 1/m, for all a A, satisﬁes SD-strategyproofness and 0-DP. In fact, DP admits a lower bound of satisfaction to strategyproofness. To be more precise, we use the notion of α-SD-strategyproofness. Then the following proposition holds.

Proposition 7. Any voting rule satisfying ϵ-DP satisﬁes e ϵSD-strategyproofness.

Proof. Suppose that r is a voting rule satisfying ϵ-DP and P, P are proﬁles differing on only one voter s ballot. Then, for any j N and any a A, DP indicates that

P[r(P) = a] e ϵ P[r(P ) = a].

Then we have X

b ia P[r(P) = b] e ϵ X

b ia P[r(P ) = b],

which completes the proof.

As is shown in Proposition 7, the satisfaction to strategyproofness increases when ϵ decreases. This is quite intuitive, since there is little motivation for an adversary to manipulate the voting process when the outcomes of neighboring datasets are very similar.

6 Conclusion and Future Work In the paper, we proposed three classes of differentially private Condorcet methods and explored their accuracy-privacy tradeoff and axioms-privacy tradeoff. Further, we investivated the relations between DP and other axioms. For future work, we plan to explore more axioms for randomized voting rules and design new voting rules performing better on satisfaction to the axioms. The design and analysis of DP mechanisms for other social choice problems, such as multiwinner elections, fair division, and participatory budgeting, are also promising directions for future work.

Acknowledgments ZL acknowledges the National Key R&D Program of China under Grant 2020YFB1005702 for support. AL acknowledges the RPI-IBM AI Horizons scholarship for support. LX acknowledges NSF #1453542 and a Google Research Award for support. YC acknowledges NSFC under Grants 62172016 and 61932001 for support. HW acknowledges NSFC under Grant 61972005 for support.

References Apple Inc. 2017. Differential Privacy Technical Overview. https://www.apple.com/privacy/docs/Differential Privacy O verview.pdf. Accessed: 2022-08-16. Aziz, H.; Brandl, F.; and Brandt, F. 2014. On the incompatibility of efﬁciency and strategyproofness in randomized social choice. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence (AAAI-14), 545 551. Aziz, H.; Brandl, F.; and Brandt, F. 2015. Universal Pareto dominance and welfare for plausible utility functions. Journal of Mathematical Economics, 60: 123 133. Aziz, H.; Brandt, F.; and Brill, M. 2013. On the tradeoff between economic efﬁciency and strategy proofness in randomized social choice. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-13), 455 462. IFAAMAS. Bassily, R.; Groce, A.; Katz, J.; and Smith, A. 2013. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS-13), 439 448. IEEE Computer Society. Benad e, G.; G olz, P.; and Procaccia, A. D. 2019. No stratiﬁcation without representation. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC-19), 281 314. ACM. Birrell, E.; and Pass, R. 2011. Approximately strategy-proof voting. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI-11), 67 72. AAAI Press. Brandl, F.; Brandt, F.; and Hofbauer, J. 2015. Incentives for participation and abstention in probabilistic social choice. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 1411 1419. IFAAMAS. Brandl, F.; Brandt, F.; and Hofbauer, J. 2019. Welfare maximization entices participation. Games and Economic Behavior, 114: 308 314. Brandl, F.; Brandt, F.; and Stricker, C. 2018. An analytical and experimental comparison of maximal lottery schemes. In Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18), 114 120. Morgan Kaufmann. Brandt, F. 2017. Rolling the Dice: Recent Results in Probabilistic Social Choice. In Endriss, U., ed., Trends in Computational Social Choice, chapter 1. AI Access. Dwork, C. 2006. Differential Privacy. In 33rd International Colloquium on Automata, Languages, and Programming (ICALP-06), 1 12. Springer.

Dwork, C.; Kenthapadi, K.; Mc Sherry, F.; Mironov, I.; and Naor, M. 2006. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt-06), 486 503. Springer. Flanigan, B.; G olz, P.; Gupta, A.; Hennig, B.; and Procaccia, A. D. 2021. Fair algorithms for selecting citizens assemblies. Nature, 596(7873): 548 552. Flanigan, B.; G olz, P.; Gupta, A.; and Procaccia, A. D. 2020. Neutralizing self-selection bias in sampling for sortition. In Advances in Neural Information Processing Systems (Neur IPS-20), volume 33, 6528 6539. MIT Press. Gibbard, A. 1977. Manipulation of schemes that mix voting with chance. Econometrica: Journal of the Econometric Society, 45(3): 665 681. Gross, S.; Anshelevich, E.; and Xia, L. 2017. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence (AAAI-17), 544 550. Hay, M.; Elagina, L.; and Miklau, G. 2017. Differentially private rank aggregation. In Proceedings of the 2017 SIAM International Conference on Data Mining (SDM-17), 669 677. SIAM. Hsu, J.; Huang, Z.; Roth, A.; Roughgarden, T.; and Wu, Z. S. 2016. Private matchings and allocations. SIAM Journal on Computing, 45(6): 1953 1984. Kannan, S.; Morgenstern, J.; Rogers, R.; and Roth, A. 2018. Private Pareto optimal exchange. ACM Transactions on Economics and Computation, 6(3-4): 1 25. Kohli, N.; and Laskowski, P. 2018. Epsilon voting: Mechanism design for parameter selection in differential privacy. In 2018 IEEE Symposium on Privacy-Aware Computing (PAC-18), 19 30. IEEE. Lee, D. T. 2015. Efﬁcient, private, and eps-strategyproof elicitation of tournament voting rules. In Proceedings of the Twenty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-15), 2026 2032. AAAI Press. Liu, A.; Lu, Y.; Xia, L.; and Zikas, V. 2020. How private are commonly-used voting rules? In Proceedings of the 36th Conference on Uncertainty in Artiﬁcial Intelligence (UAI20), volume 124, 629 638. PMLR. Orr, A. 2017. Google s differential privacy may be better than Apple s. Technical report, the Mac Observer. Pai, M. M.; and Roth, A. 2013. Privacy and mechanism design. ACM SIGecom Exchanges, 12(1): 8 29. Plott, C. R. 1976. Axiomatic Social Choice Theory: An Overview and Interpretation. American Journal of Political Science, 20(3): 511 596. Procaccia, A. D. 2010. Can approximation circumvent Gibbard-Satterthwaite? In Proceedings of the Twenty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-10), 836 841. AAAI Press. Shang, S.; Wang, T.; Cuff, P.; and Kulkarni, S. R. 2014. The application of differential privacy for rank aggregation: Privacy and accuracy. In 17th International Conference on Information Fusion (FUSION-14), 1 7.

Torra, V. 2019. Random dictatorship for privacy-preserving social choice. International Journal of Information Security, 19(4): 1 9. Walsh, T.; and Xia, L. 2012. Lot-based voting rules. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12), 603 610. IFAAMAS. Xiao, D. 2013. Is privacy compatible with truthfulness? In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS-13), 67 86. ACM. Yan, Z.; Li, G.; and Liu, J. 2020. Private rank aggregation under local differential privacy. International Journal of Intelligent Systems, 35(1): 1492 1519.