Decision Making with Differential Privacy under a Fairness Lens

1 Introduction

Statistics about groups of individuals are often used as inputs to critical decision processes. The U.S. Census Bureau, for example, releases data that is then used to allocate funds and distribute critical resources to states and jurisdictions. These decision processes may determine whether a jurisdiction must provide language assistance during elections, establish vaccine distribution plans, and allocate funds to school districts. The resulting decisions may have significant societal, economic, and medical impacts for participating individuals.

In many cases, the released data contain sensitive information whose privacy is strictly regulated. For example, in the U.S., the census data is regulated under Title 13, which requires that no individual be identified from any data released by the Census Bureau. In Europe, data release is regulated according to the General Data Protection Regulation, which addresses the control and transfer of personal data. As a result, such data releases must necessarily rely on privacypreserving technologies. Di�erential Privacy (DP) has become the paradigm of choice for protecting data privacy, and its deployments include data products related with the 2020 release of the U.S. Census Bureau [Abowd, 2018].

� Work done while the author was visiting Syracuse University.

Although DP provides strong privacy guarantees, it may induce biases and fairness issues in downstream decision processes, as shown empirically in [Pujol et al., 2020]. Since at least $675 billion are being allocated based on U.S. census data, the use of di�erential privacy without a proper understanding of these biases and fairness issues may adversely a�ect the health, well-being, and sense of belonging of many individuals. Indeed, the allotment of federal funds, apportionment of congressional seats, and distribution of vaccines should ideally be fair and unbiased. Similar issues arise in several other areas including election, energy, and food policies. The problem is further exacerbated by the recent recognition that commonly adopted DP mechanisms for data release may introduce unexpected biases on their own, independently of a downstream decision process [Zhu et al., 2021].

This paper builds on these observations and provides a step towards a deeper understanding of the fairness issues arising when di�erentially private data is used as input to several resource allocation problems. One of its main results is to prove that several decision problems with significant societal impact (e.g., the allocation of educational funds and the decision to provide minority language assistance on election ballots) exhibit inherent unfairness when applied to a differentially private release of the census data. To counteract this negative results, the paper examines the conditions under which decision making is fair when using DP, and techniques to bound unfairness. The paper also provides a number of mitigation approaches to alleviate unfairness on such decision making problems. More specifically, the paper makes the following contributions: (1) It formalizes the notion of bounded fairness for decision making subject to privacy requirements. (2) It characterizes decision making problems that are fair or admits bounded fairness. In addition, it investigates the composition of decision rules and how they impact bounded fairness. (3) It proves that several decision problems with high societal impact induce inherent biases when using a di�erentially private input. (4) It examines the roots of the induced unfairness by analyzing the structure of the decision making problems. (5) It proposes several guidelines to mitigate the negative fairness e�ects of the decision problems studied.

To the best of the authors' knowledge, this is the first study that attempt at characterizing the relation between di�erential privacy and fairness in decision problems. All proofs are reported in [Fioretto et al., 2021].

2 Preliminaries: Di�erential Privacy

Di�erential Privacy [Dwork et al., 2006] (DP) is a rigorous privacy notion that characterizes the amount of information of an individual's data being disclosed in a computation.

Definition 1. A randomized algorithm M : X ! R with domain X and range R satisfies �-di�erential privacy if for any output O � R and datasets x; x0 2 X di�ering by at most one entry (written x � x0 )

Parameter � >0 is the privacy loss, with values close to 0 denoting strong privacy. Intuitively, DP states that any event occur with similar probability regardless of the participation of any individual data to the dataset. DP satisfies several properties including immunity to post-processing, which states that the privacy loss of DP outputs is not a�ected by arbitrary data-independent post-processing [Dwork and Roth, 2013].

A function f from a dataset x 2 X to a result set R � R n can be made di�erentially private by injecting random noise onto its output. The amount of noise relies on the notion of global sensitivity �f = maxx�x0 k f (x)� f (x0 )k1: The Laplace mechanism [Dwork et al., 2006] that outputs f (x)+η, where η 2 R n is drawn from the i.i.d. Laplace distribution with 0 mean and scale �f=� over n dimensions, achieves �-DP.

3 Problem Setting and Goals

The paper considers a dataset x2X � R k of n entities, whose elements xi = (xi1; : : : ; x1k) describe k measurable quantities of entity i 2 [n], such as the number of individuals living in a geographical region i and their English proficiency. The paper considers two classes of problems:

• �An allotment problem P : X � [n] ! R is a function that distributes a finite set of resources to some problem entity. P may represent, for instance, the amount of money allotted to a school district.
• �A decision rule P : X � [n] ! f0; 1g determines whether some entity qualifies for some benefits. For instance, P may represent if election ballots should be described in a minority language for an electoral district.

The paper assumes that P has bounded range, and uses the shorthand Pi(x) to denote P(x; i) for entity i. The focus of the paper is to study the e�ects of a DP data-release mechanism M to the outcomes of problem P. Mechanism M is applied to the dataset x to produce a privacy-preserving counterpart ˜x and the resulting private outcome Pi( ˜x) is used to make some allocation decisions. Figure 1 provides an illustrative diagram.

Because random noise is added to the original dataset x, the output Pi( ˜x) incurs some error. The focus of this paper is to characterize and quantify the disparate impact of this error among the problem entities. In particular, the paper focuses on measuring the bias of problem Pi

which characterizes the distance between the expected privacy-preserving allocation and the one based on the ground truth. The paper considers the absolute bias jB i P j, in place of the bias B i P , when P is a decision rule. The distinction will become clear in the next sections.

The results in the paper assume that M, used to release counts, is the Laplace mechanism with an appropriate finite sensitivity �. However, the results are general and apply to any data-release DP mechanism that add unbiased noise.

4 Motivating Problems

This section reviews two Census-motivated problem classes that grant benefits or privileges to groups of people [Pujol et al., 2020].

Allotment problems The Title I of the Elementary and Secondary Education Act of 1965 [Sonnenberg, 2016] distributes about $6.5 billion through basic grants. The federal allotment is divided among qualifying school districts in proportion to the count xi of children aged 5 to 17 who live in necessitous families in district i. The allocation is formalized by

where x = (xi)i2[n] is the vector of all districts counts and ai is a weight factor reflecting students expenditures.

Figure 2 illustrates the expected disparity errors arising when using private data as input to problem P F , for various privacy losses �. These errors are expressed in terms of bias (left y-axis) and USD misallocation (right y-axis) across the di�erent New York school districts, ordered by their size. The allotments for small districts are typically overestimated while those for large districts are underestimated. Translated in economic factors, some school districts may receive up to 42,000 dollars less than warranted.

Decision Rules Minority language voting right benefits are granted to qualifying voting jurisdictions. The problem is formalized as

For a jurisdiction i, x s i , x sp i , and x spe i denote, respectively, the number of people in i speaking the minority language of interest, those that have also a limited English proficiency, and those that, in addition, have less than a 5 th grade education. Jurisdiction i must provide language assistance (including voter registration and ballots) i� P M i (x) is True.

Figure 3 illustrates the decision error (y-axis), corresponding to the absolute bias jB i P M (M; x)j, for sorted x s i , considering only true positives 1 for the Hispanic language. The figure shows that there are significant disparities in decision errors and that these errors strongly correlate to their distance to the thresholds. Similar issues were also observed in [Pujol et al., 2020].

5 Fair Allotments and Decision Rules

This section analyzes the fairness impact in allotment problems and decision rules. The adopted fairness concept captures the desire of equalizing the allocation errors among entities, which is of paramount importance given the critical societal and economic impact of the motivating applications.

Definition 2. A data-release mechanism M is said fair w.r.t. a problem P if, for all datasets x 2 X,

That is, P does not induce disproportionate errors when taking as input a DP dataset generated by M. The paper also introduces a notion to quantify and bound the mechanism unfairness.

Definition 3. A mechanismM is said �-fair w.r.t. problem P if, for all datasets x 2 X and all i 2 [n],

where � i B is referred to as the disparity error of entity i.

Parameter � is called the fairness bound and captures the fairness violation, with values close to 0 denoting strong fairness. A fair mechanism is also 0-fair.

Note that computing the fairness bound � analytically may involve computing the expectation of complex functions P. Therefore, in the analytical assessments, the paper recurs to a sampling approach to compute the empirical expectation ˆE[Pi( ˜x)] = 1 m P j2[m] Pi( ˜x j ) in place of the true expectation in Equation (2). Therein, m is a su�ciently large sample size and ˜x j is the j-th outcome of the application of mechanism M on dataset x.

1 This is because misclassification, in this case, implies potentially disenfranchising a group of individuals.

5.1 Fair Allotments: Characterization

The first result characterizes a su�cient condition for the allotment problems to achieve finite fairness violations. The presentation uses HPi to denote the Hessian of problem Pi, and Tr(�) to denote the trace of a matrix. In this context, the Hessian entries are functions receiving a dataset as input. The presentation thus uses (HPi) j;l(x) and Tr(HPi)(x) to denote the application of the second partial derivatives of Pi and of the Hessian trace function on dataset x.

Theorem 1. Let P be an allotment problem which is at least twice di�erentiable. A data-release mechanism M is �-fair w.r.t. P for some � < 1 if there exist some constant values c i jl (i 2 [n]; j; l 2 [k]) such that, for all datasets x 2 X,

The above shed light on the relationship between fairness and the di�erence in the local curvatures of problem P on any pairs of entities. As long as this local curvature is constant across all entities, then the di�erence in the bias induced by the noise onto the decision problem of any two entities can be bounded, and so can the (loss of) fairness.

The following corollaries illustrate the restrictions on the problem structure needed to satisfy fairness.

Corollary 1. If P is a linear function, thenM is fair w.r.t. P. Corollary 2. M is fair w.r.t. P if there exists a constant c such that, for all dataset x,

5.2 Fair Decision Rules: Characterization

The next results bound the fairness violations of a class of indicator functions, called thresholding functions, and discusses the loss of fairness caused by the composition of boolean predicates, two recurrent features in decision rules. The fairness definition adopted uses the concept of absolute bias, in place of bias in Definition 3. Indeed, the absolute bias jB i P j corresponds to the classification error for (binary) decision rules of Pi, i.e., Pr[Pi( ˜x) , Pi(x)]. The results also assume M to be a non-trivial mechanism, i.e., jB i P (M; x)j < 0:58i 2 [n]. Note that this is a non-restrictive condition, since the focus of data-release mechanisms is to preserve the quality of the original inputs, and the mechanisms considered in this paper (and in the DP-literature, in general) all satisfy this assumption.

Theorem 2. Consider a decision rule Pi(x) =1fxi � 'g for some real value '. Then, mechanismM is 0:5-fair w.r.t. Pi.

This is a worst-case result and the mechanism may enjoy a better bound for specific datasets and decision rules. It is however significant since thresholding functions are ubiquitous in decision making over census data.

The next results focus on the composition of Boolean predicates under logical operators. The results are given under the assumption that mechanismM adds independent noise to the inputs of the predicates P1 and P2 to be composed, which is often the case. This assumption for P1 and P2 is denoted by P 1 ?? P 2 . Future work will aim at generalizing this results to broader assumptions.

Theorem 3. Consider predicates P 1 and P 2 such that P 1 ??P 2 and assume that mechanismM is �k-fair w.r.t. P k (k 2 f1; 2g). Then M is �-fair for predicates P 1 _ P 2 and P 1 ^ P 2 with

where B k and B k are the maximum and minimum absolute biases for Mw.r.t. P k (for k = f1; 2g).

The result above bounds the fairness violation derived by the composition of Boolean predicates under logical operators.

The extended version of this work also include a surprising, positive compositional fairness result regarding predicates composed under a XOR operator [Fioretto et al., 2021].

6 The Nature of Bias

The previous section characterized conditions bounding fairness violations. In contrast, this section analyzes the reasons for disparity errors arising in the motivating problems.

6.1 The Problem Structure

The first result is an important corollary of Theorem 1. It studies which restrictions on the structure of problem P are needed to satisfy fairness. Once again, P is assumed to be at least twice di�erentiable.

Corollary 3. Consider an allocation problem P. Mechanism M is not fair w.r.t. P if there exist two entries i; j 2 [n] such that Tr(HPi)(x) , Tr(HPj)(x) for some dataset x.

The above implies that fairness cannot be achieved if P is a non-convex function, as is the case for all the allocation problems considered in this paper. A fundamental consequence of this result is the recognition that adding Laplacian noise to the inputs of the motivating example will necessarily introduce fairness issues. For instance, consider P F and notice that the trace of its Hessian

is not constant with respect to its inputs. Thus, any two entries i; j whose xi , xj imply Tr(HP F i ) , Tr(HP F j ). As illustrated in Figure 2, Problem P F can introduce significant disparity errors. For � = 0:001; 0:01, and 0:1 the estimated fairness bounds are 0:003, 3�10 �5 , and 1:2�10 �6 respectively, which amount to an average misallocation of $43,281, $4,328, and $865.6 respectively. The estimated fairness bounds were obtained by performing a linear search over all n school districts and selecting the maximal Tr(HP F i ).

Ratio Functions The next result considers ratio functions of the form Pi(hx; yi)=x =y with x; y2R and x�y, which occur in the Minority language voting right benefits problem P M i . In the following M is the Laplace mechanism.

Corollary 4. MechanismM is not fair w.r.t. Pi(hx; yi) = x =y and inputs x; y.

Figure 4 (left) provides an illustration linked to problem P M . It shows the original values x sp =x s (blue circles) and the expected values of the privacy-preserving counterparts

(red crosses) of three counties; from left to right: Loving county, TX, where x sp =x s = 4 =80 = 0:05, Terrell county, TX, where x sp =x s = 30 =600 = 0:05, and Union county, NM, where x sp =x s = 160 =3305 = 0:0484. The length of the gray vertical line represents the absolute bias and the dotted line marks a threshold value (0:05) associated with the formula P M i . While the three counties have (almost) identical ratios values, they induce significant di�erences in absolute bias. This is due to the di�erence in scale of the numerator (and denominator), with smaller numerators inducing higher bias.

Thresholding Functions As discussed in Theorem 2, discontinuities caused by indicator functions, including thresholding, may induce unfairness. This is showcased in Figure 4 (center) which describes the same setting depicted in Figure 4 (left) but with the red line indicating the variance of the noisy ratios. Notice the significant di�erences in error variances, with Loving county exhibiting the largest variance. This aspect is also shown in Figure 3 where the counties with ratios lying near the threshold value have higher decisions errors than those whose ratios lies far from it.

6.2 Predicates Composition

The next result highlights the negative impact coming from the composition of Boolean predicates. The following important result is corollary of Theorem 3 and provides a lower bound on the fairness bound.

Corollary 5. Let mechanismM be �k-fair w.r.t. to problem P k (k 2 f1; 2g). Then M is �-fair w.r.t. problems P = P 1 _ P 2 and P = P 1 ^ P 2 , with � > max(�1; �2).

Figure 4 (right) illustrates Corollary 5. It once again uses the minority language problem P M . In the figure, each dot represents the absolute bias jB i P M (M; x)j associated with a selected county. Red and blue circles illustrate the absolute bias introduced by mechanism M for problem P 1 (x sp ) = 1fx sp � 10 4 g and P 2 (x sp ; x spe )=1f x spe x sp >0:0131g respectively. The selected counties have all similar and small absolute bias on the two predicates P 1 and P 2 . However, when they are combined using logical connector _, the resulting absolute bias increases substantially, as illustrated by the associated green circles.

The extended version [Fioretto et al., 2021] also analyzes an interesting di�erence in errors based on the Truth values of the composing predicates P 1 and P 2 , and shows that the highest error is achieved when they both are True for ^ and when they both are False for _ connectors. This may have strong implications in classification tasks.

6.3 Post-Processing

The final analysis of bias relates to the e�ect of postprocessing the output of the di�erentially private data release. In particular, the section focuses on ensuring non-negativity of the released data. The discussion focuses on problem P F but the results are, once again, general.

The section first presents a negative result: the application of post-processing operator ��'(z) def = max('; z) to ensure that the result is at least ' induces a positive bias which, in turn, can exacerbate the disparity error of the allotment problem.

Theorem 4. Let ˜x = x + Lap(�), with scale � > 0, and ˆx = ��'( ˜x), with ' < x, be its post-processed value. Then,

Lemma 4 indicates the presence of positive bias of postprocessed Laplace random variable when ensuring nonnegativity, and that such bias is B i (M; x) = E[ ˆ xi] � xi = exp( '�xi � ) � � =2 for ' � xi. As shown in Figure 2 the e�ect of this bias has a negative impact on the final disparity of the allotment problem, where smaller entities have the largest bias (in the Figure ' = 0).

Discussion The results highlighted in this section are both surprising and significant. They show that the motivating allotment problems and decision rules induce inherent unfairness when given as input di�erentially private data. This is remarkable since the resulting decisions have significant societal, economic, and political impact on the involved individuals: federal funds, vaccines, and therapeutics may be unfairly allocated, minority language voters may be disenfranchised, and congressional apportionment may not be fairly reflected. The next section identifies a set of guidelines to mitigate these negative e�ects.

7 Mitigating Solutions

7.1 The Output Perturbation Approach

This section proposes three guidelines that may be adopted to mitigate the unfairness e�ects presented in the paper, with focus on the motivating allotments problems and decision rules.

A simple approach to mitigate the fairness issues discussed is to recur to output perturbation to randomize the outputs of problem Pi, rather than its inputs, using an unbiased mechanism. Injecting noise directly after the computation of the outputs Pi(x), ensures that the result will be unbiased. However, this approach has two shortcomings. First, it is not applicable to the context studied in this paper, where a data agency desires to release a privacy-preserving dataset ˜x that may be used for various decision problems. Second, computing the sensitivity of the problem Pi may be hard, it may require to use a conservative estimate, or may even be impossible, if the problem has unbounded range. A conservative sensitivity implies the introduction of significant loss in accuracy, which may render the decisions unusable in practice.

7.2 Linearization by Redundant Releases

A di�erent approach considers modifying on the decision problem Pi itself. Many decision rules and allotment problems are designed in an ad-hoc manner to satisfy some property on the original data, e.g., about the percentage of population required to have a certain level of education. Motivated by Corollaries 1 and 2, this section proposes guidelines to modify the original problem Pi with the goal of reducing the unfairness e�ects introduced by di�erential privacy.

The idea is to use a linearized version ¯Pi of problem Pi. While many linearizion techniques exists [Rebennack and Krasko, 2020], and are often problem specific, the section focuses on a linear proxy ¯P F i to problemP F i that can be obtained by enforcing a redundant data release. While the discussion focuses on problem P F i , the guideline is general and applies to any allotment problem with similar structure.

Let Z = P i aixi. Problem P F i (x) = ai xi=Z is linear w.r.t. the inputs xi but non-linear w.r.t. Z. However, releasing Z, in addition to releasing the privacy-preserving values ˜x, would render Z a constant rather than a problem input to P F . To do so, Z can either be released publicly, at cost of a (typically small) privacy leakage or by perturbing it with fixed noise. The resulting linear proxy allocation problem ¯P F i is thus linear in the inputs x.

Figure 5 illustrates this approach in practice. The left plot shows the fairness bound � and the right plot shows the empirical mean absolute error 1 m P m k=1 jPi(xk ) � Pi( ˜xm )j, obtained using m = 10 4 repetitions, when the DP data ˜x is applied to (1) the original problem P, (2) its linear proxy ¯P, and (3) when output perturbation (denoted M out ) is adopted. The number on top of each bar reports the fairness bounds, and emphasize that the proposed remedy solutions achieve perfect-fairness. Notice that the proposed linear proxy solution can reduce the fairness violation dramatically while retaining similar errors. While the output perturbation method reduces the disparity error, it also incurs significant errors that make the approach rarely usable in practice. The extended version [Fioretto et al., 2021] also discuss a solution based on a piecewise linear proxy function for the more complex decision rule P M .

It is important to note that the experiments above use a data release mechanismM that applies no post-processing. A discussion about the mitigating solutions for the bias e�ects caused by post-processing is presented next.

7.3 Modified Post-Processing

This section introduces a simple, yet e�ective, solution to mitigate the negative fairness impact of the non-negative postprocessing. The proposed solution operates in 3 steps: It first (1) performs a non-negative post-processing of the privacypreserving input ˜x to obtain value ¯x = ��'( ˜x). Next, (2) it computes ¯xT = ¯x� T ¯x+1�' . Its goal is to correct the error introduced by the post-processing operator, which is especially large for quantities near the boundary '. Here T is a temperature parameter that controls the strengths of the correction. This step reduces the value ¯x by quantity T ¯x+1�' . The e�ect of this operation is to reduce the expected value E[ ¯x] by larger (smaller) amounts as x get closer (farther) to the boundary value '. Finally, (3) it ensures that the final estimate is indeed lower bounded by ', by computing ˆx = max( ¯xT ; ').

The benefits of this approach, called ¯�, are illustrated in Figure 6, which show the absolute bias jB i P F j for the Title 1 fund allocation problem that is induced by the original mechanismMwith standard post-processing ��0 and by the proposed modified post-processing for di�erent temperature values T. The figure illustrates the role of the temperature T in the disparity errors. Small values T may have small impacts in reducing the disparity errors, while large T values can introduce errors, thus may exacerbate unfairness. The optimal choice for T can be found by solving the following:

where ˆxT is a random variable obtained by the proposed 3 step solution, with temperature T. The expected value of ˆx can be approximated via sampling. Note that naively finding the optimal T may require access to the true data. Solving the problem above in a privacy-preserving way is beyond the scope of the paper and the subject of future work. The reductions in the fairness bound � for problem P F are reported in Figure 7 (left), while Figure 7 (right) shows that this method has no perceptible impact on the mean absolute error.

7.4 Fairness Payment

Finally, this section focuses on allotment problems, like P F , that distribute a budget B among n entities, and where the allotment for entity i represents the fraction of budget B it expects. Di�erential privacy typically implements a postprocessing step to renormalize the fractions so that they sum to 1.

This normalization, together with nonnegativity constraints, introduces a bias and hence more unfairness. One way to alleviate this problem is to increase the total budget B, and avoiding the normalization. This section quantifies the cost of doing so: it defines the cost of privacy, which is the increase in budget B + required to achieve this goal.

Definition 4 (Cost of Privacy). Given problem P, that distributes budget B among n entities, data release mechanism M, and dataset x, the cost of privacy is:

Figure 8 illustrates the cost of privacy, in USD, required to render each county in the state of New York not negatively penalized by the e�ects of di�erential privacy. The figure shows, in decreasing order, the di�erent costs associated with a mechanism P F (��0( ˜x)) that applies a post-processing step, one P F ( ˜x) that does not apply post-processing, and one that uses a linear proxy problem ¯P F ( ˜x).

8 Conclusions

This paper analyzed the disparity arising in decisions granting benefits or privileges to groups of people when these decisions are made adopting di�erentially private statistics about these groups. It first characterized the conditions for which allotment problems achieve finite fairness violations and bound the fairness violations induced by important components of decision rules, including reasoning about the composition of Boolean predicates under logical operators. Then, the paper analyzed the reasons for disparity errors arising in the motivating problems and recognized the problem structure, the predicate composition, and the mechanism post-processing, as paramount to the bias and unfairness contribution. Finally, it suggested guidelines to act on the decision problems or on the mechanism (i.e., via modified post-processing steps) to mitigate the unfairness issues. The analysis provided in this paper may provide useful guidelines for policy-makers and data agencies for testing the fairness and bias impacts of privacy-preserving decision making.