Local Differential Privacy Meets Computational Social Choice - Resilience under Voter Deletion

1 Introduction

In this paper, we consider the attack on an abstract voting system. We compare the manipulation cost under two scenarios of the voting system: the classical voting system, and the voting system where a local differential privacy (LDP) mechanism is adopted. Our goal is to quantify the difference brought by LDP schemes to a voting system under electoral manipulation.

Extensive research has been conducted towards characterizing the resilience of various voting rules (see, e.g., Brandt et al. [2016] for a survey). In many of these research works, the attacker is assumed to know the true preference of voters through pre-election polls. Many voting rules, especially fundamental rules like plurality, are found to be vulnerable [Faliszewski et al., 2009]. Can we enhance the resilience of a voting system by preventing the attacker from learning the preference of voters? Towards this, we observe that LDP mechanisms are a state-of-the-art approach to mitigating the leakage of sensitive information.

∗The full version of this paper is available at https://arxiv.org/abs /2205.00771

†Corresponding Author.

LDP mechanism serves as an important method in social science, particularly in voter turnout reports [Rosenfeld et al., 2016]. However, most existing research works on LDP focus on the analysis of each user's privacy, not much is known from the aspect of the system's security (see, e.g., Bebensee [2019] as a survey). Does the introduction of LDP mechanisms make the system more resilient? The most relevant research in this direction is a very recent paper [Cheu et al., 2021], where they showed that an attacker may manipulate a small percentage of users in an LDP mechanism to mislead the estimation of distribution parameters. However, their attack model is completely different from what we study in this paper.

We believe characterization of the resilience of a voting system under LDP mechanisms is a natural question that is worth investigating. The high-level description of the specific model we study in this paper is given as follows:

• Election setting: We consider the classical election where there are a set of candidates and a set of independent voters. We focus on the plurality rule (e.g., each voter votes for exactly one candidate). For each voter, we define the type 1 of his/her preference as the candidate he/she votes for. Candidate(s) receiving the highest score will be the co-winner(s).
• LDP mechanism: Every voter will locally and independently run a given LDP mechanism once to generate his/her reported preference which will be used for all pre-election polls. This is a common approach, see e.g., Google's RAPPOR [Erlingsson et al., 2014]. Otherwise, the attacker may be able to figure out the voter's true preference via his/her multiple reported preferences [Bebensee, 2019]. In this paper, we focus on two fundamental LDP mechanisms: randomized response and Laplace.
• Attack model: We consider electoral control by deleting

1 For each voter, the type of his/her preference is private information, and will be referred to as the true type to distinguish from the reported type which is generated by the LDP mechanism.

voters. The manipulation cost is the minimal number of voters the attacker should delete to make the designated candidate win.

We emphasize that the adoption of LDP mechanisms will not change the electoral result since the mechanisms are only used in pre-election polls. Voters will still vote according to their true preference in the election, but will respond using the reported preference in any pre-election polls. Therefore when the attacker launches the voter deletion attack prior to the election, he/she only knows the reported preference of voters instead of their true preference.

Measuring the impact of LDP mechanisms. In the classic election setting, the attacker knows the true preference of all voters. Whereas, after adopting the LDP mechanism, the attacker only knows the reported preference.

Inspired by the concept of PoA (price of anarchy) in algorithmic game theory [Koutsoupias and Papadimitriou, 1999], we introduce the metric PoLDP (power of LDP) to quantitatively characterize the resilience brought by the LDP mechanism. Roughly, we can view PoLDP as follows:

PoLDP = Minimal expected manipulation cost with LDP Minimal manipulation cost without LDP .

If PoLDP > 1, then it means the introduction of LDP mechanisms indeed increases the manipulation cost of the attacker, and thus enhances the resilience of the system; if PoLDP < 1, then it means the introduction of LDP mechanisms reduces the manipulation cost, and thus diminishes the resilience of the system. It should be noted that the value of PoLDP depends on the specific LDP mechanism as well as the value of the privacy parameter 2 .

As randomness is involved in an LDP mechanism, the manipulation cost under the LDP mechanism is a random variable, and our definition uses its expected value. One may ask what if this random variable takes a value significantly different from the expectation? Indeed, we will show that since the manipulation cost can be expressed as a summation of independent binary variables, probabilistic analysis guarantees that the manipulation cost as a random variable lies around its expectation with an extremely high probability, and consequently our definition of PoLDP by using the expected value is without loss of generality.

Our contributions. The main contribution of this paper is to give the first quantitative analysis of the effect brought by local differential privacy in a voting system under electoral control of voter deletion. We study two major LDP mechanisms that are widely adopted, randomized response and Laplace, and show that they can generally enhance the resilience of a voting system. We quantify such an effect through a measure called PoLDP. The larger PoLDP is, the more resilience LDP adds to the system.

Since LDP mechanisms introduce uncertainty, the attacker may need to pay a different manipulation cost to make sure the designated candidate wins with a different probability. That is, the manipulation cost, and consequently PoLDP, is a function of the winning probability.

2 See Definition 1 for the meaning of the privacy parameter ϵ.

For specific winning probability, we establish two integer linear programs to give a general upper and lower bound on the manipulation cost. Under some mild assumptions, we show that the upper and lower bound approach to the same value for a big range of the winning probability. That is the manipulation cost for a winning probability of 99.9% is almost the same as that for a winning probability of 0.1%.

Using probabilistic analysis, we give an efficient method to calculate the APoLDP (Asymptotic PoLDP) for voting systems satisfying certain conditions. Furthermore, we study the relationship between the value of APoLDP and the parameter ϵ of LDP mechanisms. For randomized response and Laplace mechanism, we give the closed-form expression of APoLDP for voting systems with only two candidates. For voting systems with multiple candidates, it becomes too complicated to obtain a simple mathematical formula. Instead, we analyze the maximal1 value of APoLDP, and the range of ϵ where APoLDP achieves the maximal value.

Interestingly, we observe that when the parameter ϵ of LDP mechanisms is below a certain threshold (we call it security threshold), APoLDP stays at its maximal value. Generally, LDP mechanisms with smaller ϵ can guarantee better privacy. But for manipulation via voter deletion, such kind of extra privacy provided by LDP mechanisms is redundant and can not add more resistance. The security threshold provides general guidance toward the application of LDP mechanisms.

Relatedworks. Local differential privacy has been increasingly accepted as a state-of-the-art approach for statistical computations while protecting the privacy of each participant. It was first formalized in [Kasiviswanathan et al., 2011]. Several important LDP mechanisms are studied and compared in the literature [Wang and Blocki, 2017; Bun et al., 2019; Qin et al., 2016], including the two major LDP mechanisms, randomized response and Laplace considered in this paper. LDP mechanisms have also been adopted by IT companies, e.g., RAPPOR by Google Chrome [Erlingsson et al., 2014]. We refer the reader to a comprehensive survey [Bebensee, 2019].

The study of the computational complexity of electoral control was initiated by Bartholdi III et al. [1992], who mainly analyzed the voting rule of plurality and condorcet, where the attacker's goal is to make a designated candidate win. Later, Hemaspaandra et al. [2007] studied a closely related model where the attacker's goal is to make the original winner lose. Following their research work, extensive research has been conducted towards understanding the resilience of voting systems under different electoral control methods and voting rules [Hemaspaandra et al., 2017; Magiera and Faliszewski, 2017; Maushagen and Rothe, 2016; Rey and Rothe, 2016]. While the research has characterized different voting rules as resilient or vulnerable, not much is known about protecting a vulnerable voting rule like plurality. Electoral control under partial information is also considered in the literature [Conitzer et al., 2011; Dey et al., 2018]. Very recently, Chen et al. [2018] and Yin et al. [2018] studied the protection of election through deploying defending resources.

2 Preliminary

In this section, we briefly introduce the concept of local differential privacy mechanism. We use the definition given by [Erlingsson et al., 2014].

Definition 1. ϵ-Local Differential Privacy: We say that an mechanism R satisfies ϵ-local differential privacy where ϵ > 0 if and only if for any input v, v′ and any y ∈ range(R) it holds that

where range(R) denotes the set of all possible outputs of the mechanism R.

We call R an ϵ-LDP mechanism if it satisfies the ϵ-local differential privacy. The privacy parameter ϵ characterizes the level of privacy provided by the LDP mechanism R. For example, perfect privacy is ensured when ϵ = 0. And, no privacy is guaranteed when ϵ = +∞.

As mentioned before, the type of true preference of each voter (we refer to it as true type) is private information. Voters will vote according to their true types in the election. In the meantime, we let every voter Vi independently and locally run an ϵ-LDP mechanism (which is the randomized response or Laplace in this paper) to generate a type of his/her reported preference (we refer to it as reported type) and use the reported type in all pre-election polls. Consequently, the reported type of each voter is public information.

Design Matrix. We now introduce the design matrix of an LDP mechanism. In our problem, the design matrix maps the true type to the reported type for each voter. Consider an arbitrary voter Vi. Let ti be the true type, and ri be the reported type generated by ϵ-LDP mechanisms. There are m candidates in the voting system. Consequently, there are m different types under plurality. Hence, we know that ti, ri ∈ [1, m].

Consider the probability that Vi has a true type v but reports u, i.e., the event that its reported type is u conditioned on the event that its true type is v, or Pr[ri = u|ti = v]. It is clear that since each voter independently and locally runs the LDP mechanism, Pr[ri = u|ti = v] is the same for all voters. Hence, we denote by puv = Pr[ri = u|ti = v], and let P = (puv)m×m. P is called the design matrix and is only dependent on the LDP mechanism.

We consider two major LDP mechanisms, randomized response and Laplace. Given the privacy parameter ϵ, we denote by P ϵ-ran = (pϵ-ran uv )m×m and P ϵ-lap = (pϵ-lap uv )m×m the design matrices for randomized response and Laplace, respectively. According to Wang et al. [2016], the design matrices are given by:

where Fµ,b(x) = 12 + 12 sgn(x-µ)(1-e(- |x-µ| b ) ) denotes the cumulative distribution function of Laplace distribution with mean µ and the variance 2b2 .

FromReported Type to True Type. Consider an arbitrary voter Vi. Again, let ti be its true type, and ri be its reported type. If we observe that Vi reports v as its type, what is the probability that its true type is u? More precisely, we consider Pr[ti = u|ri = v]. As each voter independently and locally runs the LDP mechanism, Pr[ti = u|ri = v] is the same for all voters. Hence, we denote by quv = Pr[ti = u|ri = v], and let Q = (quv)m×m.

The probabilities puv and quv are connected through Bayesian formulation. Let λj be the fraction of voters whose true type is j (i.e., there are nλj voters whose true type is j). We assume λj's are fixed positive values and denote pi = (pi1, pi2, . . . , pim) as the i-th row of the design matrix P . Then, we have

It is easy to see that puv's and quv's are independent of the number of voters n.

3 Formal Definition of PoLDP

The goal of this paper is to quantitatively analyze the effect of LDP mechanisms when applied to voting systems. Towards this, we consider two scenarios, the classical scenario without LDP and the new scenario with LDP, and compare the manipulation costs of the attacker under these two scenarios. Below we give details.

We denote Sm,λ(n) as the voting system which contains n voters namely {V1, . . . , Vn}, and m candidates namely {C1, . . . , Cm}. The parameter λ = (λ1, . . . , λm) which denotes there are nλi voters whose true type is i. The deletion cost for each voter is unit. Hence, there is no need to distinguish two voters who have the same true type.

There is an attacker who tries to make a designated candidate win via voter deletion. Without loss of generality, we assume that the designated candidate is C1.

In the classical scenario without LDP mechanisms, the attacker knows the true type of voters 3 (e.g., the parameter λ of the voting system), and can thus strategically delete voters (e.g., decide the number of voters that need to be deleted for each kind of true type) to make the designated candidate C1 be one of the co-winners. Hence, for the voting system S = Sm,λ(n), we define the minimal number of voters the attacker should delete as the manipulation cost of the attacker, and define it as f(S).

Consider the scenario where an LDP mechanism R is adopted. We also assume the attacker knows the parameter λ of the voting system 4 . But, the attacker needs to delete voters according to reported types instead of true types. Adopting the LDP mechanism introduces two kinds of uncertainties when considering the manipulation problem, as we discuss below.

3 This is a common assumption in computational social choice, see, e.g., Brandt et al. [2016].

4 For the rationality of this assumption, please refer to Section "Discussion".

• Realizations: Recall that there are nλi voters whose true type is i. We know that it is fixed for the voting system Sm,λ(n). However, the number of voters whose reported type is i, may be different 5 . Let nτi be the number of voters whose reported type is i where 1 ≤ i ≤ m, and let τ = (τ1, . . . , τm). Then, we know that

For any z ∈ P, τ = z is called a realization, and will occur with the probability Pr[τ = z] that depends on the LDP mechanism R.

• Winning Probability: The attacker observes a realization τ and decides the number of voters that need to be deleted for each reported type. More precisely, a feasible solution to the attacker under a fixed realization τ can be represented as a vector x = (x1, x2, · · · , xm) where xi ≤ nτi is the number of deleted voters whose reported type is i. As voters of the same reported type are indistinguishable from the attacker, we assume the attacker will randomly delete xi out of nτi voters of reported type i. Among these xi voters, the number of voters whose true type is i′ is a stochastic value for each i′ . Consequently, the attacker may or may not succeed in making C1 win. In other words, any feasible solution x to the attacker is associated with a winning probability which indicates the probability that C1 becomes a co-winner if the attacker deletes arbitrary xi voters whose reported type is i, given the observation τ .

Above all, for the voting system Sm,λ(n), we define the manipulation cost of the attacker under the LDP mechanism as follows:

Definition 2. The manipulation cost of a voting system S = Sm,λ(n) under an LDP mechanism R, given a winning probability ξ and a realization τ , is the minimal number of voters that need to be deleted to make the designated candidate one co-winner with a probability at least ξ and is denoted by f(S,R, ξ : τ).

5 To understand the effect of an LDP mechanism to a fixed voting system on average, we consider the independent application of the same LDP mechanism multiple times, and each time we may observe a different τ .

As the mechanism R defines a distribution of τ over P, we can define the expectation of f(S,R, ξ : τ) over all the realizations as below.

Definition 3. The expected manipulation cost of a voting system S = Sm,λ(n) under an LDP mechanism R, given a winning probability ξ, is the expected minimal number of voters that need to be deleted to make the designated candidate one co-winner with a probability at least ξ over all the realizations, and is denoted by f(S,R, ξ) = Eτ [f(S,R, ξ : τ)].

Compare the manipulation cost of the attacker in the above two scenarios (with or without LDP), the introduction of LDP may cause the cost to increase or decrease, and we measure such an increase or decrease through PoLDP, interpreted as the power of LDP. More precisely,

Definition 4. The PoLDP for a voting system S = Sm,λ(n) under an LDP mechanism R is defined as

We are interested in the value of PoLDP when the number of voters in the voting system is sufficiently large. Hence, we define the APoLDP (Asymptotic PoLDP).

Definition 5. The APoLDP for a voting systemS = Sm,λ(n) under an LDP mechanism R is defined as

4 Characterizing APoLDP

The goal of this section is to provide an efficient method to calculate APoLDP and study the relationship between APoLDP and the parameter ϵ of LDP mechanisms.

We prove that under certain conditions, the value of APoLDP is robust to the winning probability ξ, and can be calculated via a linear program. Specifically, we have the following theorem:

Theorem 1. If the voting system S = Sm,λ(n) under an LDP mechanism R satisfies that for any 1 ≤ j ≤ m either qij - q1j > 0 for all 2 ≤ i ≤ m, or qij - q1j < 0 for all 2 ≤ i ≤ m, then for any ξ ∈ (0, 1) it holds that

See the full version of this paper for the complete proof of Theorem 1. Here, we only give the roadmap of the proof.

• First, we use two integer linear programs ILP(τ, δ) and ILP(τ, δ) to give the upper and lower bound of f(S,R, ξ : τ) respectively. We establish ILP(τ, δ) as

Here, the decision variable xj denotes the number of voters with reported type j that need to be deleted. Recall that qjk is the probability that the true type of a voter is j conditioned on its reported type is k. Consequently, Eq (4a) implies that ˆΓj is the expected number of voters of true type j that are left after voter deletion, Eq (4b) ensures that the designated candidate C1 receives the highest votes in expectation, with a margin of δ ∑mj=1 (q1j + qij )xj . The margin will guarantee that C1 can win with a sufficiently large probability despite that we only consider the expected scores of candidates. More precisely, we have the following lemma.

Lemma 1. Let x∗ = (x∗1 , . . . , x∗m) denote the optimal solution to ILP(τ, δ). If the attacker deletes arbitrary x∗i voters whose reported type is i, then the winning probability of the designated candidate is at least 1 - me- cδ2 3 n , where c = qmin(λmax - λ1),qmin = mini,j qij , λmax = maxj λj .

Replacing constraint Eq (4b) of ILP(τ, δ) with ˆΓ1 ≥ ˆΓi - δ ∑mj=1 (q1j + qij)xj, we obtain another integer linear program and denote it as ILP(τ , δ). Then, we can have the following lemma.

• Lemma 2. Let x∗ = (x∗1 , . . . , x∗m) denote the optimal solution to ILP(τ, δ). If the attacker deletes yi voters whose reported type is i such that ∑j yj < ∑j x∗j := OPTILP(τ,δ), then the winning probability of the designated candidate is less than 2e- cδ2 3 n where c = qmin(λmax - λ1), qmin = mini,j qij , λmax = maxj λj .
• Second, we show that if certain condition holds, then the value of f(S,R, ξ : τ) is robust to the winning probability ξ. Specifically, we prove that for any ϵ ∈ (0, 1), the value of f(S,R, 1 - ϵ : τ) can be calculated via linear program LP(τ ) when the number of voters is sufficiently large.

Replacing constraint Eq (4b) of ILP(τ, δ) with ˆΓ1 ≥ ˆΓi, we introduce an "intermediate" integer linear program ILP(τ ) between ILP(τ , δ) and ILP(τ , δ). Denote LP(τ) as the linear relaxation of ILP(τ). We show that under certain conditions, if the number of voters is sufficiently large, then the upper bound and lower bound given by ILP(τ, δ) and ILP(τ, δ) approaches the same value which is exactly OPTLP(τ).

• Finally, we show a efficient way to calculate f(S, R, ξ). Recall the definition, we need to compute the optimal objective value of linear program LP(τ) for each fixed realization τ , and then taking the expectation over τ . We prove that if certain condition holds, we can first compute the expectation of τ (denoted as ˆ τ = E[τ]), and then compute the optimal objective value of integer program LP(ˆ τ ).

With Theorem 1, we are able to study the relationship between APoLDP and the privacy parameter ϵ for two classes of LDP mechanisms, randomized response and Laplace.

For voting systems with only two candidates, we prove that for any ξ ∈ (0, 1) APoLDP has the following closed-form expression which is derived by solving LP(ˆ τ ).

Here φ = λ2 - λ1, "ϵ-ran" stands for randomized response mechanism which satisfies ϵ-LDP and "ϵ-lap" stands for Laplace mechanism which satisfies ϵ-LDP.

For voting systems with multiple candidates, it is difficult to give the closed-form expression of APoLDP. Instead, we can have the following result.

Theorem 2. If the voting system S under an randomized response mechanism R satisfies ϵ-LDP and λi > λ1 for all 2 ≤ i ≤ m, then for any ξ ∈ (0, 1), APoLDP achieves the maximal value 1 1-∑mi=2 (λi-λ1) when θλ1 λmax-λ1 ≤ 1-θ m where λmax = maxi λi, i.e., when ϵ ≤ ln λmax λ1 .

The proof of Theorem 2 relies on showing two statements on LP(ˆ τ): (i) if ϵ ≤ ln λmax λ1 , then LP(ˆ τ) only admits one feasible solution where xk = nE[τk], meaning that deleting all the voters is the only solution to make the designated candidate C1 win; (ii) if ϵ > ln λmax λ1 , then there exists a feasible solution to LP(ˆ τ) whose objective value is strictly smaller than n. Unfortunately, the proof heavily utilizes the special structure of the design matrix for randomized response, and cannot be carried over to Laplace.

5 Numeric Experiments

In this section, we demonstrate PoLDP through numeric experiments 6 . In our experiments, the number of voters is set to be n = 108 . The number of candidates is set to be m = 2; 5. In this experiment, we generate the true type of each voter using two methods.

• The first method guarantees the difference in score between the designated candidate and the winner equals mφ where the true type of each voter is randomly generated from [1, m].

6 All experiments are performed on a computer with an Intel i7-6700 processor and 32GB memory. The code is available at https://github.com/polyapp/poldp

• The second method randomly generates the true type of each voter according to the real-world data-Sushi Data [Kamishima, 2003] which is a commonly used data set for generating preferences [Azari et al., 2012].

For ease of notation, we denote by T φ m the voting system generated by the first method, and Tm the voting system generated by the second method. For each kind of voting system, we generate 2000 instances.

The parameter is set to be ξ = 0.999, δ = 0.001, ϵ = 0.001. We observe that randomized response and Laplace mechanism on our randomly generated voting systems hold that:

and

This result suggests if we compare two solutions, one guarantees that the designated candidate wins by at least 99.9%, and the other guarantees that the designated candidate wins by at most 0.1%, then the two manipulation costs differ by at most 10%. In other words, on the voting systems we created PoLDP(S, R, 0.1%) and PoLDP(S, R, 99.9%) differ by at most 10% in average. Based on this, we simply calculate the manipulation cost with LDP mechanisms using OPTLP(ˆ τ ).

For voting systems with multiple candidates, we perform experiments on voting systems T5 and T φ 5 for φ = 0.1; 0.2. For ϵ = 0, 0.01, . . . , 0.49, 5, we compare the efficiency of randomized response and Laplace mechanism from two aspects: the average and the standard deviation of PoLDP (solid lines represent the average, and dotted shadows represent the standard deviation); the percentage of instances which has PoLDP larger than 99% of its maximal value (in short, the maximal percentage). We summarize the comparison in Figure 3-4.

We observe that the Laplace mechanism outperforms randomized response by always giving a larger PoLDP on all the voting systems we test. Moreover, the randomized mechanism is more sensitive to the selection of ϵ on voting systems T φ 5 . We can see from Figure 3, the average of PoLDP for randomized response decreases quicker than Laplace in the region ϵ ∈ [0, 2]. Interestingly, we also observe that the maximal percentage coincides with the value of PoLDP (e.g., the maximal percentage equals 100% where PoLDP stays at its maximal value) on voting systems T φ 5 .

More experimental results, including the analysis, are given in the full version of this paper.

6 Discussion

In real-world applications, although the exact value of λ is unknown, we can use a two-round implementation of LDP in voting to estimate λ: In the first round, a random subset A of voters are selected to report their types via the LDP mechanism; In the second round, all voters except those in A, report their types via the LDP mechanism. We use the reported types given by voters in A, to get an estimation of λ. It is generally sufficient to obtain a good statistical estimation through a reasonably small sample [Kenny, 1986]. In particular, |A| can be o(n) for sufficiently large n, and therefore it will only marginally affect the value of PoLDP.

7 Conclusion

We provide the first systematic study on how LDP mechanisms may improve the resilience of a voting system under electoral control by deleting voters. The metric PoLDP introduced in this paper gives general guidance towards the choice of the privacy parameter ϵ in LDP mechanisms.

Acknowledgments

Liangde Tao is partly supported by "New Generation of AI 2030" Major Project (2018AAA0100902). Lin Chen is partly supported by NSF Grant 2004096.