Large data collecting organizations, like Facebook and Google, and federal institutions, like The U.S. Census Bureau and Medicare, often release summary statistics about individuals and populations. These data products are incredibly useful tools for multiple resource allocation, policy-making and scientific endeavors. The US census alone informs agencies across the country as to how to apportion resources. Decisions like congressional seat apportionment, school funding and emergency response plans all depend on census data [20] . Google's releases of search trends or map data inform many companies' advertisement and logistics strategies [34] . Likewise Facebook's trove of user interaction data was found to be valuable in studying the impact of social media on elections and democracy [3] .
While these data releases are very useful, they have the potential to reveal sensitive information about individuals, especially through the analysis of multiple such datasets [16, 28, 36] . As a result, Differential Privacy (DP) [12, 13] has arisen as the gold standard of privacy protection through the addition of randomized noise. However, due the fundamental law of information recovery [11] , making an unbounded number of releases from a dataset (even if each release were differentially private) will eventually allow an attacker to accurately reconstruct the underlying dataset. Because of this, data curators must bound the amount of information released using a parameter known as the privacy loss budget . Traditional privacy mechanisms are generally focused on minimizing the overall error induced by differential privacy, where error trades off with .
Almost all of the work in differential privacy up until now has focused (often implicitly) on the single analyst case. In this case a single analyst specifies one or more queries or tasks that are answered under the same privacy loss budget such that the overall error is minimized. However, in the real world there are often multiple analysts or stakeholders interested in a particular dataset, and the privacy loss budget must apply across the release of answers to the queries of all of the analysts. While it is well known how to answer multiple queries or generate synthetic data under differential privacy with limited privacy budget [4, 8, 10, 18, 25, 26, 29, 30, 33, 35, [37] [38] [39] we know of no differentially private mechanisms designed with the interests of multiple analysts in mind.
One straightforward adaptation to the multi-analyst case is to simply aggregate the queries of all analysts into a single workload for an existing privacy mechanism. Such a mechanism then optimizes for total error and is agnostic to as to which queries belong to which analysts. Such an approach may arbitrarily exhaust more privacy budget on the queries of one agent over another, leaving some analysts with more accurate results than others. In other words, there is the potential for the queries of one analyst to interfere with the quality of the results for another analyst.
Another approach is to partition each agent and give them each their own fraction of the total privacy budget to use. While this prevents the aforementioned kind of interference, it can result in a substantial overall degradation in performance when there is overlap between analyst queries. This overlap can be explicit when different analysts ask the same queries or implicit when different analysts ask related queries that can be more efficiently answered jointly than by simply answering each independently.
We are interested in designing effective shared systems for multianalyst differentially private data release that achieves the best of both of these aforementioned ideas: (1) providing guarantees to individual analysts and (2) ensuring good overall performance. We call this the multi-analyst differentially private data release problem.
Overview of approach and contributions. Our work introduces and investigates the multi-analyst differentially private data release problem.In this problem a data curator has a dataset in which multiple analysts are interested in. Each analyst asks the data curator a set of queries to be answered in a differentially private manner. The data curator then answers all of the queries using a fixed privacy loss budget and releases the answer to all queries to each analyst. In this context we ask the question "How should one design a privacy mechanism when multiple analysts may be in competition over the limited privacy budget".
We describe three minimum desiderata which we argue that any mechanism in this setting should satisfy. These require that if an analyst was given a choice to either join a group of analysts and answer their queries together or to have their queries answered independently, with their share of the privacy budget, an analyst should always weakly prefer to join the group. We experimentally show that existing mechanisms for answering multiple queries such as HDMM [29] do not satisfy these properties in practical settings. We then introduce an adaptation of the existing Select Measure Reconstruct paradigm designed for the multi-analyst setting.
We show that existing mechanisms applied with no changes either do not satisfy these properties or are prone to high amounts of error. We then design and test mechanisms designed to satisfy these properties while remaining efficient.
Our main contributions in this work are as follows.
• We study (for the first time) differentially private query answering across multiple analysts. We consider a realistic setting where multiple analysts pose query workloads and the data owner makes a single private release to answer all analyst queries. • We define three minimum desiderata that that we will argue any differentially private mechanism should satisfy in a multi-agent setting -Sharing Incentive, Non-Interference and Adaptivity. • We show empirically that existing mechanisms for answering large sets of queries violate at least one of the desiderata described. • We introduce variants of the existing Select Measure Reconstruct paradigm which are designed to utilize the group structure of the problem and satisfy the given desiderata in practice. • We introduce mechanisms within the adapted Select Measure Reconstruct paradigm which provably satisfy all of the desiderata while maintaining efficiency. • We show through experiments that the mechanisms which utilize the adapted Select Measure Reconstruct paradigm satisfy all the desiderata given while still remaining efficient with respect to total error.
Organization. In the next section we describe the relevant background information such as the definitions of differential privacy and matrix mechanisms. In section Section 2 we briefly discuss differential privacy and other required background information. In Section 3 we formally define the multi-analyst differentially private data release problem as well as some notation. In Section 4 we describe the desiderata that we believe any mechanism designed for multi-analyst differential privacy should satisfy. In Section 5 we describe how existing mechanisms can be used in this setting as well as introduce new mechanisms designed for this setting. In Section 6 we then test these mechanisms in both practical settings as well as pathological cases designed to violate the desiderata.
Differential Privacy [12, 13] is a formal model of privacy that grantees each individual that any query computed from sensitive data would have been almost as likely as if the individual had opted out. More formally Differential privacy is a property of a randomized algorithm which bounds the ratio of output probabilities induced by changes in a single record. Formally differential privacy is defined as follows Definition 1 (Differential Privacy). A randomized mechanism M is -differentially private if for any instance , any ′ which differs in at most one row, and any outputs ⊆ (M):
The parameter often called the privacy budget quantifies the privacy loss. Here we focus exclusively on -Differential Privacy, i.e when = 0.
The Laplace mechanism is a differentially private primitive which underlines the algorithms used here. We describe the vector version of the Laplace mechanism here. we describe it in vector form. Let ( ) denote independent samples from a Laplace distribution with mean 0 and scale .
Definition 2 (Laplace Mechanism, Vector Form). Given an × workload matrix , the randomized algorithm which outputs the following vector is -differentially private.
Differentially private releases compose with eachother in that if there are two private releases of the same data with two different privacy budgets the amount of privacy lost is equivalent to the sum of their privacy budgets. More formally we have the following.
Theorem 1 (DP composition [13] ). Let M 1 be an 1 -differentially private algorithm and M 2 be an 2 -differentially private algorithm. Then their combination defined to be M 1,2 ( ) = (M 1 ( ), M 2 ( )) is
Of the many algorithms proposed in the literature, we will consider a class of measures that invoke the Select, Measure, Reconstruct paradigm, where instead of directly answering the queries, they first select a new set of strategy queries. They then measure the strategy queries using a privacy protecting mechanism (in this case the Laplace Mechanism [13] ) and finally reconstruct the answers to the original input queries from the noisy measurements. Examples of mechanisms that follow this paradigm are the Matrix Mechanism [27] and it's derivatives such as HDMM [29] . These mechanisms are designed to answer linear counting queries however they can be extended to answer non-linear queries by adding post processing steps which reconstruct non linear queries from answers to several linear counting queries. As in most of the differential privacy literature, we use mean squared error as our error metric.
Problem Definition. We consider the setting where there are analysts with associated positive weights 1 , 2 . . . ∈ normalized so that the weights sum to one. These weights represent the fraction of the total privacy budget that each analyst is entitled to and can be interpreted as the relative importance of each analysts queries; the natural default is to use proportional weights of 1/ for every analyst. From these weights each analysts entitled share of the budget is . If the mechanism being used is known ahead of time and the expected error can be found analytically, one can assign weights to each analyst to grantee enough of the privacy budget to achieve a minimum expected error under that mechanism.
Each analyst submits a set of queries 1 , 2 . . . which they would like answered. We call this set of queries workload = { 1 , 2 . . . }. In the case of multiple analysts, we have workload for the th analyst. We thus have the set of workloads W = { 1 , 2 , . . . , }. The data curator then answers all of the queries using a multi-analyst differentially private mechanism and outputs a single data release containing the answer to all queries to all of the analysts. We define a multi analyst differentially private mechanism as a function that takes as input each analysts set of queries, their respective shares of the privacy budget and the overall privacy budget and outputs a single data release containing the answers to all of the queries. For clarity of the desiderata and proofs we introduce the idea of a dynamic collective of analysts. The collective is a group of analysts who decided to join together and answer their queries using a joint mechanism using the sum of all of the analysts entitled privacy budget. We represent each analyst as having a choice to either join the collective and give their entitled budget to the communal pool or to answer their query answers on their own.
We argue that any multi-analyst differentially private mechanism should incentivize a rational agent to participate in the collective. For example, given the choice between (a) participating the shared mechanism with other analysts or (b) having their queries answered independently with their share of the privacy budget, analysts should always weakly prefer (a). Similarly, such a mechanism should never cause any individual analyst to regret that another analyst is participating in the shared mechanism, causing their performance to degrade by more than an amount proportional to the privacy budget spent on the other analyst. Finally, such a mechanism should be able to adapt to and optimize for the queries being asked by all analysts.
In this section we formalize these criteria through three separate desiderata: Sharing Incentive, Non-Interference, and Adaptivity. We introduce each of the desiderata as well as current common practice through a rolling example which demonstrates the importance of these desiderata even in a simple case. Example 1. Alice Bob and Carol are analysts working on a private dataset of US COVID-19 deaths by age provided by the Center for Disease Control [2]. The populations are split into 11 buckets by age. The data curator decides to use a privacy budget of = 1. Each of the analysts are entitled to an equal share of the privacy budget (that is, each has weight 1/3). Alice and Bob both have want to ask the Identity workload, a histogram of the counts by age. Carol however wants to ask for the total of all counts in the database.
We believe that any multi-analyst differentially private mechanism must satisfy three minimum desiderata. The first desiderata, the Sharing Incentive requires that each analyst, in expectation, receives at at most as much error as if they had computed their query answers independently using the same mechanism and their fraction of the privacy budget. This captures the idea that each analyst should always benefit from joining the collective. The Sharing Incentive is formally defined as follows.
Definition 3 (Sharing incentive). Let (M, W, ) be the mean squared error of analyst under mechanism M with with set of workloads W and privacy budget as parameters.
A mechanism M satisfies the Sharing Incentive if for every analyst the following holds.
The data curator decides to split each analyst off and give them each /3 of the privacy budget in order to answer their queries independently using HDMM. In this case Alice and Bob both receive a total expected error of ±244 people while Carol receives an expected error of ±22 people.
Alternatively Alice Bob and Carol each decide to join together and answer their queries under the total privacy budget using HDMM. Alice Bob and Carol merge their workloads together and run HDMM on the new combined workload. Alice and Bob receive ±24 people as expected their error which is less than their error using the independent mechanism. However Carol received ±24 people as her expected error which is more error than in the independent case where her expected error was ±22 people thus violating the Sharing Incentive.
In this case Carol would optimally answer her query independently while Alice and Bob join together. If the mechanism were to satisfy the Sharing Incentive Carol would be guaranteed no worse error by joining Alice and Bob and as such should always make that choice.
The second desiderata is Non-Interference, which states that adding an additional analyst to the collective group, with their associated share of the privacy budget, should not increase the error experienced by any of the analysts already in the collective. This desiderata ensures that no analyst in the collective can ask a (intentionally or unintentionally) malicious set of queries which would increase the error of any of the other analysts more than if they had never joined the collective. This makes it so that adding more analysts to the collective (and with them more privacy budget) can only improve the utilities of all agents. Formally, we define Non-Interference as follows.
Definition 4 (Non-interference). Let Err (M, W, ) be the expected error of analyst under mechanism M with privacy budget . A mechanism M satisfies Non-Interference if for all analysts , , for all workloads ,
Where W is the set of all workloads.
Example 1. (continued) Alice and Bob have decided to join the collective and answer their queries together since they have the same queries. They run the joint mechanism on their queries using 2 3 of the budget. Here they both receive ±22 people as expected error. Carol then joins the collective. They then rerun the same mechanism using the entire budget. In this case Alice and Bob receive an expected error of ±24 people, which is more than their original ±22 people expected error therefore violating Non-Interference.
In this case Alice and Bob would optimally not allow Carol to join into the collective since her addition makes them worse off. If the mechanism were to satisfy Non-Interference Alice and Bob would be guaranteed that no matter what workload Carol asks they can be to be no worse off for allowing Carol into the collective. Any mechanism which satisfies the Sharing Incentive ensures that no malicious actor or amateur analyst asking a poorly designed workload can increase the error experienced by any other analyst.
Our third desideratum is Adaptivity, which states that a mechanism should be able to adapt to the inputs given. We say that a mechanism is adaptive if it changes its query answering strategy based off all the inputs given. This ensures that a mechanism can adapt to the specific queries being asked by analysts in order to avoid high error for particular sets of queries. Example 1. (continued) The data curator chooses to use a nonadaptive mechanism which always releases data by answering the Identity workload. Alice and Bob are happy since this is their exact workload. Carol however is punished since her query workload cannot be efficiently reconstructed using the identity workload and receives an expected error of ±24 people, which is worse than her independent expected error of ±22 people.
An adaptive mechanism would be able to adapt it's query answering strategy in order to account for Carols queries therefore reducing her error. The concept of Adaptivity highlights the flaws of various trivial mechanisms which satisfy Sharing Incentive and Non-Interference by intentionally ignoring the inputs or interactions between analysts inputs.
There are two existing approaches for answering queries for multiple analysts. The first, which we call independent mechanisms, splits the budget amongst each of the analysts, based off their weights, and then uses some workload answering mechanism to answer each individual workload. While this approach satisfies both Sharing Incentive and Non-Interference it is generally inefficient as the same query may be answered multiple times using different sections of the budget.
The second method joins all the queries of each analyst together and answers them using a query workload mechanism such as HDMM [29] . This method insures that all the queries are answered efficiently using the given budget however has no guarantee as to how much error each analyst receives. Since these mechanisms are optimized for overall error of the workload this approach favors analysts who have large workloads who are similar to others while small more niche workloads receive higher error. Naive implementations of these mechanisms neither satisfy Sharing Incentive nor Non-Interference but are efficient overall.
An ideal mechanism should have the benefits of both approaches. It should allow analysts to benefit from sharing budget and answering similar queries in a joint manner without violating either the Sharing Incentive or Non-Interference. Such a mechanism would allow analysts to answer their queries together in an efficient manner that ensures all analysts benefit for participating in the system.
We introduce four classes of mechanisms for multi-analyst query answering. These classes are differentiated by the choice of whether and how to introduce a Collect step (corresponding to aggregating the queries of the multiple analysts) into the Select Measure Reconstruct Paradigm. We describe each class in general terms and give a specific example of a mechanism within that class for multi-analyst query answering. We also prove or show empirically which desiderata are satisfied for the example mechanisms.
We call the first two classes independent and workload agnostic. These classes use existing mechanisms without explicitly considering a Collect step. These are considered as baselines to which we compare other mechanisms; it is easy to see in theory and we show empirically that these mechanisms lead to poor performance with respect to total error. We call the other two classes of mechanisms Collect first and Select first. These mechanisms adapt the Select Measure by aggregating all analysts' queries either before or after the selection step. While the simplest Collect first mechanism merely aggregates queries and optimizes total error, we introduce two specific mechanisms which we call the Weighted Utilitarian Mechanism and the Waterfilling Mechanism that aim to satisfy all desiderata while remaining efficient in terms of total error.
Independent Mechanisms give each analyst their a share of the overall privacy budget proportional to their weights 1 , . . . and 
answers each analysts' queries independently of one another using some workload answering mechanism. Mechanisms of this class by definition satisfy both Sharing Incentive and Non-Interference since analysts always have the same expected error regardless of how many analysts are in the collective or what their queries are. However, these mechanisms are not efficient as they typically answer each individual query with less privacy budget than other mechanisms and may answer the same or similar queries multiple times. In particular, consider the pathological example of analysts, each of whom asks the same single linear counting query to be answered with the Laplace Mechanism. In this case, the expected error of the Independent Mechanism is √ times that of simply answering the query once with the full privacy budget, even accounting for the analysts post processing by averaging their independent results.
Workload Agnostic Mechanisms always answer the same set of full rank queries with the entire budget regardless of the analysts inputs.
Mechanisms of this class also trivially satisfy both Sharing Incentive and Non-Interference. Since the actual workload is ignored, Sharing Incentive is satisfied because joining the collective ensures you receive query answers using the entire privacy budget as opposed to only a fraction of the budget. Likewise since the mechanism ignores the actual workload, Non-Interference is trivially satisfied. However, Workload Agnostic Mechanisms are not adaptive and this causes them to be inefficient with respect to total error, even for a 
⊲ + is the Moore-Penrose inverse of and + = . 
In this section we describe the remaining classes of mechanisms. Both adapt the Select Measure reconstruct paradigm. by introducing a collection step where each of the analysts' queries are aggregated into a single query set. The classes differ in where the collection step occurs.
Collect First Mechanisms aggregate all analysts' queries before the selection step in a Select Measure Reconstruct framework.These mechanisms combine all of the workloads of each analyst into some weighted query set then run the selection step to select a single strategy workload for all the analysts workloads. Utilitarian Mechanism is an example of a mechanism which falls into this particular class. The Utilitarian Mechanism first aggregates each analysts' queries by creating a multi-set of queries which contains all the analysts' queries with multiplicity equal to the number of analysts asking the query. We then run a selection step on this joint query set. In general, we would expect this mechanism to achieve the minimum expected total error across all analysts, but the mechanism can easily violate both Sharing Incentive and Non-Interference. We show this empirically in Section 6 in pathological and realistic examples.
Weighted Utilitarian Mechanism is a variant of the Utilitarian Mechanism that attempts to directly optimize for the Sharing Incentive. This is achieved by weighting the queries prior to the collection step. This requires an additional set of parameters, which we call them workload weights Ω = { 1 , 2 , . . . , }, where is the weight for workload . After weighting each of the queries the Utilitarian Mechanism is run the weighted query sets. Utilitarian Mechanism is simply the special case of Weighted Utilitarian Mechanism with 1 = 2 = · · · = = 1. Since we would like to satisfy Sharing Incentive, we would like to have our expected error better than the results of Independent Mechanism. We thus set the weight as the inverse of the expected error of Independent Mechanism for each analyst, as
This is equivalent to optimizing on a weighted utilitarian objective where an analysts utility is above 1 if they have less error than required to satisfy Sharing Incentive and is below one if they have more error than is required to satisfy Sharing Incentive. In Section 6 we show that the mechanism satisfies the Sharing Incentive in experiments but fails to satisfy Non-Interference. The Waterfilling Mechanism is an example mechanism in this class. The mechanism generates a sensitivity 1 strategy for each analyst using the given selection step. These strategies are then scaled by the weight of each analyst. The mechanism will then assign each individual query to a bucket. Buckets represent groups of queries that are similar enough that they can all be answered with a single representative query. Each bucket contains a representative query that will be answered and an associated weight which represents how much of the privacy budget will be used to answer that bucket.
In practice we create the buckets using angular equality. That is for each query if a bucket exists that has a representative query that is equal to times some scalar then belongs in that bucket. In this case the weights for each of these queries is the the scalar .
Once the mechanism generates a strategy for each analyst those strategies are split into their independent queries. For each of those queries the mechanism assigns a weight (usually each query is given an equal share of the analysts entitled privacy budget) and finds a bucket to which to add the query. If a bucket does exist the analyst adds their query to the bucket and adds the associated weight to the buckets existing weight. If a proper bucket doesn't already exist the analyst creates a new bucket for the query with it's associated weight. From these buckets the mechanism constructs a single joint set of strategy queries by taking the representative query from each bucket and weighting it by the buckets weight. The joint strategy queries are then measured directly.
Theorem 2. Adding an analyst to the collective in the Waterfilling Mechanism cannot increase the expected error of any analyst.
Proof. Let be the strategy queries produced by a Waterfilling Mechanism for − 1 analysts and ′ be the strategy queries for analysts (adding one from previous case). The th analyst is entitled of the budget. First let us prove a few properties of the Waterfilling Mechanism.
Lemma 3. The introduction of an additional analyst with weight to the collective of a waterfilling mechanism can only increase the sensitivity of the query set by . Formally written as follows. 
When a new analyst is added to the collective for each of their queries they have two options they may either create a new bucket or add their query to an existing bucket. If they add a new bucket that query becomes part of the final strategy query set adding it's sensitivity to the overall sensitivity. If they add their query to an existing bucket the weight of that query increases by the weight of that query, therefore increasing the overall utility by the weight 19 return ans of that query. Since the weight of all of an analysts queries must equal their overall weight the increase in sensitivity is equal to the overall weight of the analyst. We note that since each analyst is entitled to of the budget and the sensitivity of the strategy query set is equal to the sum of each analysts weights that the scale of the noise used to answer the query set is the same regardless of the number of analysts in the collective. The scale of the noise added to each query in the set is as follows.
Where 1 ≤ ≤ . We now consider two different perspectives when an additional analyst is added to the collective. We first consider the case of an analyst who is already in the collective, Alice, and how their utility is affected by an additional analyst joining. We then consider the case of the analyst joining the collective, Bob, and how their utility changes as they join the collective.
Consider Alice, an analyst already in the collective. If the new analyst being added shares no queries with Alice then her queries remain unchanged and the noise being added stays the same ensuring that her query answers remain utility neutral. If Bob shares queries with Alice then the weights of Alice's queries will increase. This reduces the the amount which Alice's queries need to be re-scaled to reconstruct her original strategy queries therefore reducing her expected error. Therefore adding Bob to the collective can only either be error neutral or negative for Alice.
Likewise consider Bob an analyst to be added to the collective. From Bob's perspective adding Bob to the existing collective is equivalent to adding all the members of the existing collective to a collective consisting of only Bob. Just like Alice adding any analysts to Bobs collective is either utility neutral or positive. Since adding an additional analyst is error neutral or negative for both Alice and Bob then no analyst can see an increase in error from an additional analyst joining the collective. □
Since an analyst joining the collective can not increase the error for any analyst no analyst will see an increase in error as they go from the independent case to part of the collective. Therefore any waterfilling mechanism satisfies the Sharing Incentive.
Likewise due to Theorem 2 no analyst joining the collective can increase the error of any analysts in the collective. Therefore the waterfilling mechanism satisfies Non-Interference.
Corollary 2. Any waterfilling mechanism satisfies Non-Interference.
Of note in practice we use HDMM as the selection step for this mechanism. When using matrix mechanisms or variants thereof the waterfilling mechanism in addition to ensuring that each strategy matrix has sensitivity 1 each column of the strategy matrix should also have norm 1. In our experiments this is done by using HDMM as a selection step which guarantees a strategy matrix with all column norm 1. Practically any matrix can be made to satisfy this condition by scaling the columns.
Likewise in practice we consider an approximate HDMM waterfilling mechanism. In this approximate version we do not use strict angular equality to test for membership in a bucket but instead use an approximate version where queries that vary slightly may be put in the same bucket. This is done to account for numerical errors that may arise during the optimization step in HDMM. When using this approximate version of angular equality for queries we lose the provable guarantee of the Sharing Incentive and Non-Interference. However see that in practice the Waterfilling Mechanism still satisfies all the desiderata so long as the allowed deviation for queries is not too large.
Mechanisms of this class have two main benefits. First the selection step can be done by any pre-existing algorithm to select representative workloads such as the HDMM selection step or the Matrix Mechanism selection step. In the case of joint mechanisms this is not the case as the selection mechanism must be altered to support multiple analysts and workloads. The second benefit is that the waterfilling mechanisms allow for budget to be allocated directly to representative queries as opposed to joint mechanisms which rely on an optimization task to allocate budget appropriately. Like independent and workload agnostic mechanism waterfilling mechanisms can provably satisfy both Sharing Incentive and Non-Interference.
Here we show experimentally that in practical settings the Utilitarian Mechanism violates the Sharing Incentive and both the Utilitarian and Weighted Utilitarian mechanisms violate Non-Interference. We then proceed to show that even when pathological settings, designed to violate the desiderata are introduced the Weighted Utilitarian mechanism satisfies the Sharing Incentive and the Waterfilling mechanism satisfies all of the desiderata.
We also measure the overall efficiency of our mechanisms and show that the Waterfilling mechanism satisfies all of the desiderata and can still maintain a low overall error. Likewise we show that even though the Independent mechanism and the Identity mechanism satisfies both the Sharing Incentive and Non-Interference, they come at the cost of high overall error in some practical cases.
We designed experiments to test both the desiderata and efficacy of our mechanisms. In general, experiments are of 2 kinds: a practical setting to test measure the efficacy of our mechanisms in practice and a pathological set of workloads designed to show if any mechanism violates the desiderata. For each of these experiments we use HDMM [29] as the selection step, but any selection step can be used in practice. As HDMM is a variant of the matrix mechanism (MM) [26] , the mechanism is data independent for linear queries and the expected error of the matrix mechanism can be analytically calculated for any given strategy matrix (the matrix form of the strategy queries). We let MM( ) be the matrix mechanism with strategy matrix . Given a workload of queries in matrix form and a privacy budget the expected error of MM( ) is
In addition, we can consider the Identity Mechanism a variant of matrix mechanism with a fixed identity strategy matrix , MM( ). We note some commonly used workloads and their corresponding workload matrices in Table 2 .
In addition, Waterfilling mechanism has a tolerance parameter . determines by how much two vectors may deviate in order to be considered equal. We experimented with several values of and found = 0.001 is a value that achieves good overall accuracy. As such we set it to be 0.001 in all our experiments. Note that a too large may make Waterfilling mechanism violate Sharing Incentive or Non-Interference as queries which are significantly different may be put into the same bucket. A too small may consider very similar queries to be different and do not combine most queries. This can lead to a large expected error.
For the figures, each workload is given an abbreviations as follows: Ind (Independent HDMM), Iden (Identity mechanism), Util (Utilitarian HDMM), WUtil (Weighted Utilitarian HDMM), and Water (HDMM Waterfilling mechanism). For each experiment we run the optimization 10 times and pick the strategy with the minimum The sum of all categories 1 × all-ones row matrix Singleton
One single category 1 × row matrix , with 1 in the th entry and 0 in other entries Prefix Sum
The prefix sum of all categories × lower triangular matrix of ones H2 workload Hierarchical matrix H 2 (2 − 1) × matrix: vertical stack of / ⊗ for = 1, 2, 4, . . . , loss. Since HDMM is data independent the experiments do not require a particular dataset.
We design several empirical measures to provide an overall understanding of the mechanisms. We also turn our desiderata into quantifiable measures to better assess the performance of our mechanisms. All measures are with respect to a single mechanism and a single set of workloads.
Total Error is the sum of expected errors of all analysts. This is a common measure found in the literature to show the efficiency of the algorithm.
Maximum Ratio Error of a mechanism M for an analyst is the expected error of M divided by the expected error of the independent mechanism. For non-independent adaptive algorithms, it is a measure of Sharing Incentive as it measures to what extent one analyst gets better or worse off compared to asking the query on their own. We present the maximum of the ratio errors among all analysts. For a mechanism M, a workload set W and a total privacy budget , we let Err (M, W, ) be the expected error of analyst . The maximum ratio error amongst all analysts is max Err (M, W, ) Err (M, , )
.
If the value is larger than 1, the mechanism violates Sharing Incentive as the error in the joint case is greater than the error experienced in the independent case.
Empirical Interference is a quantifiable measure to show the extent which a mechanism violates Non-Interference or the distance from violating it. For each analyst , we define the interference with respect to another analysts as the ratio of the expected error for analyst when all analysts are included to the case when excluding analyst . If this ratio is larger than 1, analyst can be worse off when analyst joins the workload set. The detailed definition is as below.
Let W = { 1 , . . . , } be the set of workloads of analysts. We also define W = W \ . Then, suppose we have a differential private mechanism M. We define the interference of analyst on analyst to be
This represents the relative change in error experienced by analyst when analyst joins the collective. We then define the interference of mechanism M on the set W as the maximum of interference among all analysts, as
Intuitively, it represents the maximum ratio increase of the expected error of any analyst when another analyst joins the workload set. If M ( ) ≤ 1, we have mechanism M satisfies Non-Interference on W. We would like this value to be negative or as small as possible.
Since M is usually a non-deterministic mechanism, rerun the mechanism with W may give different strategy matrices to other analysts. Thus, we fix strategy matrices for select first mechanisms to ensure a more reasonable comparison. Since the strategy used by collect first mechanisms is dependent on each analysts input it is not possible to fix the strategy matrix.
We create practical settings using a series of random steps using the census example workloads provided in [29] . We tested on the race workloads with data size = 64.
(1) We first fix the dataset size . We then generate the number of analysts by picking an integer uniformly random from [2, max ]. We let the number of analysts be . (2) Each analyst then pick a workload uniformly random from the set of 8 workloads, including 3 race workloads, Identity, Total, Prefix Sum, H2 workload, and custom workload. (3) If they get custom workload, we chose their matrix size by picking an integer uniformly random from [1, 2 ]. (4) For each query in matrix we chose a class of query uniformly sampled from the set including range queries (0-1 vector with contiguous entries), singleton queries, sum queries (random 0-1 vector) and random queries (random vector). The query is thus a random query within its class. (5) The custom workload is thus a vertical stack of the queries. (6) We repeat this procedure times to get randomly chosen sets of workloads. We call them instances.
We tested different max . We present the results for max = 20 as a representative in Section 6.3. The figure is a box plot of = 100 instances generated randomly from the above procedure. The green line represents the median and the green triangle represents the mean. The box represents the bulk from the 25th percentile to the 75th percentile. It is the same for all other box plots in this paper.
We experimented on other max from 5 to 30 and the results are qualitatively similar. We also experimented on a workload set without census workloads and they give qualitatively similar results. Figure 6 : Total Errors, Maximum Ratio Errors and Empirical Interference for randomly generated practical settings (above) and 1-way marginals (below). Values of maximum ratio error and empirical interference above 1 signify a violation of Sharing Incentive and Non-Interference respectively. Fig. 6a gives an overall view of the efficiency of different mechanisms. As expected, Utilitarian HDMM, a mechanism optimized for overall error, performs the best. Meanwhile Independent HDMM, a mechanism which does not utilize the group structure of the problem at all performs the worst. The other three mechanisms have similar errors and are not much worse than Utilitarian HDMM. Fig. 6b shows how other mechanisms compared with Independent HDMM in terms of maximum ratio error among all analysts. Utilitarian HDMM violates Sharing Incentive in a small number of instances as there are some outliers with maximum ratio error larger than 1. Weighted Utilitarian and Waterfilling mechanism satisfied Sharing Incentive. Although Identity also has some outliers larger than 1, since independent HDMM is not the independent form of this mechanism it does not violate Sharing Incentive.
However, since the error from identity is independent of the other analysts choices any analyst who receives poor error under Identity will receive that same poor error regardless of the number of analysts or their workloads. These analysts are arbitrarily punished by the mechanism since it cannot adapt to any analysts' needs. This demonstrates how violating Adaptivity makes Identity undesirable. Fig. 6c gives an empirical indication on whether a mechanism satisfies Non-Interference in practical setting. It can be seen that both Utilitarian and Weighted Utilitarian HDMM violate Non-Interference cases. Weighted Utilitarian has fewer instances which violating Non-Interference than Utilitarian. Also, the extent of violation is generally smaller for Weighted Utilitarian. The other three mechanisms do not violate Non-Interference as we expect.
From our experiment results, we can see that our HDMM Waterfilling mechanism have achieved our main goal of providing a mechanism which satisfies all three desiderata while maintaining high utility. It is also worth noting that Weighted Utilitarian HDMM also satisfies Sharing Incentive empirically and can provide a higher utility with a small violation of Non-Interference.
We also experiment on another common type of workloads, the marginals. For a dataset with attributes with domain size for the th attribute, we can define a -way marginal as the follows. Let be a size subset of {1, 2, . . . , }, we can express the workload as the Kronecker product 1 
Here is the identity workload matrix and is the total workload matrix. Specifically, a 0-way marginal is the Total workload and a -way marginal is the Identity workload. Also, since there are size-subset of {1, 2, . . . , }, there are different -way marginals. In our experiments for simplicity, we use attributes all with domain size 2. Similar to Step 1 and 2 in the practical setting in Section 6.3, the detailed experiment procedure is as follows. We first fix , , and the maximum number of analysts max . We then generate the number of analysts by picking an integer uniformly random from [2, max ]. We let the number of analysts be . Each analyst then pick a workload uniformly random from the set of -way marginals. Here, we show the results for 1-way marginal with = 8 and max = 20 in Section 6.3. In this case = 256. This figure also contains 100 instances. In particular, there are 1-way marginals each corresponds to an attribute. For the 1-way marginal with attribute , it consists of 2 queries, where one is the total query with predicate attribute equals to 0, and the other is with predicate attribute equals to 1. Fig. 6d shows Identity mechanism is worse than the Waterfilling mechanism and the 2 Utilitarian mechanisms. The addition of the 1way marginals drastically increases the error of identity compared to that of the other mechanisms. This is an example where the Identity perform poorly with regard to total error for a common type of workloads. This is also observed for 1-way marginals with = 6, 7, 9, 10. Although there are workloads where Identity mechanism performs well, the Adaptivity of other mechanisms allow them to be suitable for most cases. Identity mechanism thus should be only used when the data curator has the prior knowledge that workloads analysts tend to ask are all good with Identity mechanism. Fig. 6e and Fig. 6f are qualitatively similar to those in practical settings. It also verifies the Waterfilling mechanism satisfies both Sharing Incentive and Non-Interference. Also with lower total error, it is clearly better than Identity mechanism for these workloads. The Utilitarians have lower errors but violates Non-Interference quite often.
In previous experiments, all workloads are linear and the expected error can thus be calculated without data. Our mechanisms can also be used for non-linear queries. We now experiment on some non-linear queries including mean, medium, and percentiles based on a histogram.
Error in this case is data-dependent and needs to be empirically calculated using real datasets. We use the Census Population Projections [1] . The dataset is Population Changes by Race. We choose year 2020 and Projected Migration for Two or more races. This dataset can show the difference between mechanisms clearly. The size of data is = 86, representing ages from 0 to 85.
As in the previous 2 experiments, the experiment procedure is as follows. We fix the maximum number of analysts max . We then generate the number of analysts by picking an integer uniformly random from [2, max ]. We let the number of analysts be . Each analyst then pick a query uniformly random from the set of 4 queries, including mean, medium, 25-percentile, and 75-percentile. Mean is reconstructed from the workload containing the Total query and the weighted sum query, a vector representing the attribute values (0 to 85 in our case). Medium and percentiles are reconstructed from the Prefix Sum workload . The expected error here is the mean squared error of 10000 samples calculated using the Laplace mechanism.
We show the results of 100 instances (sets of queries) with max = 20 in Fig. 7. Fig. 7a shows that Independent mechanism performs much worse than all other mechanisms in terms of total error. Fig. 7b is the zoomed in version of Fig. 7a , removing Independent. Since the answer of a non-linear query is reconstructed using the result of a different linear workload, Utilitarian does not guarantee to have the lowest total errors. We can see that Weighted Utilitarian outperforms Utilitarian here. The other two mechanism have higher total errors, and the Waterfilling mechanism has a better median total errors than Identity. Fig. 7c and Fig. 7d shows the max ratio errors and empirical interference. Since Independent and Identity mechanism satisfy Sharing Incentive and Non-Interference by definition, we omit them here. We can see that all 3 other mechanisms satisfy Sharing Incentive as they all have max ratio errors smaller than 1. The 2 Utilitarian mechanisms violate Non-Interference as shown in Fig. 7d . Waterfilling mechanisms satisfies Non-Interference. The outliers are due to numerical errors since we are using empirical expected errors instead of analytical ones.
These results show that our mechanisms are also good for nonlinear queries and have similar properties as the instances with linear queries. The results are qualitatively similar for max = 10.
The next set of experiments uses pathological settings, where we purposely constructed sets of workloads to detect whether our mechanisms violates Sharing Incentive and Non-Interference. We design this experiment with the intuition that if the the uncommon workload only provides a small proportion of privacy budget but requires a large change in the strategy, the analysts with the common workload will suffer. For example strategies that work well for the total workload perform badly when used to answer the identity workload. Therefore when − 1 analysts ask the total workload and the th analyst asks the the identity workload the strategy chosen by the mechanism must change drastically to adjust for the th analyst and therefore reduce the overall utility of the − 1 analysts.
In the experiment, every set of workloads consists of 1 uncommon workload and − 1 common workloads. We experimented on 3 types of workloads: Singleton, Identity, and Total. We fixed the size of data = 16 and tried different values of ∈ [2, 10].
We present the results for 1 identity workload with − 1 total workload (identity-total) in Fig. 8 , since it can best show the violation of Sharing Incentive and Non-Interference. Since Independent and Identity mechanism both trivially satisfy these 2 properties, we only present results for Utilitarian HDMM, Weighted Utilitarian HDMM and HDMM Waterfilling mechanism. Fig. 8a shows that only Utilitarian violates Sharing Incentive and the violation is significant. Fig. 8b shows both Utilitarian and Weighted Utilitarian violates Non-Interference and the violation of Utilitarian is much more significant. Waterfilling mechanism satisfies both of them as expected.
Overall we see as in Fig. 6a that the traditional method of independently answering using fractional budgets results in an enormous increase in overall error when compared to joint mechanisms. For Ind Iden Util WUtil Water example in our practical cases we see over an order of magnitude difference between independent HDMM and HDMM waterfilling. We show in Fig. 6b that a naively implemented joint mechanism (utilitarian HDMM) can result in violation of the Sharing Incentive resulting in some analysts gaining their extra utility at the expense of other analysts who are worse off than in the independent case. Likewise Fig. 6c shows that naively implemented joint mechanisms can allow analysts to (unintentionally or intentionally) interfere with other analysts by asking vastly different query sets. In the same vein in Fig. 6d we show that mechanisms which are non-adaptive may suffer great losses in utility based off the queries being asked.
Of the mechanisms proposed the waterfilling mechanism satisfies all three desiderata given while still retaining low overall error. While the waterfilling mechanism performed well it failed to outperform the utilitarian mechanisms which directly optimize on (weighted or unweighted) overall error. As such we suggest using the waterfilling mechanism in settings where the provable grantees of the Sharing Incentive and Non-Interference are of the upmost importance.
As for the weighted utilitarian mechanism we have not found any single case practical or pathological in which it does not satisfy the Sharing Incentive however we have not been able to prove that it does satisfy the Sharing Incentive. In addition, the weighted utilitarian mechanism only slightly violates Non-Interference in the practical settings as in Fig. 6c . In all other experiments, empirical interference of the weighted utilitarian mechanism is significantly smaller than the utilitarian mechanism. Because of this additional flexibility the weighted utilitarian mechanism is able to vastly outperform the waterfilling mechanism in most cases when considering overall error. As such we suggest using the weighted utilitarian mechanism in settings where the need for extra accuracy outweighs the need for provable guarantees.
There has already been significant work on answering sets of queries in a differentially private manner, including theoretical lower bounds on error [7, 17] and many practical algorithms [4, 8, 10, 18, 25, 26, 29, 30, 33, 37, 39] . Each of these mechanisms primarily attempts to optimize the total error (or utilitarian social welfare) instead of distributing error in some manner. Likewise these mechanisms are not intended for any group answering setting but are instead designed for single analyst use.
There has been some work at the intersection of fairness and privacy, such as analyzing how ensuring privacy in models or decision making affects the accuracy of certain subgroups [5, 6, 9, 22, 24] . In contrast, our work focuses on achieving a fair distributions of utility for the analysts involved not the individuals who's information is in the database.
Sharing computational resources such as memory and network has been considered in the context of resource allocation for data centers and networking [14, 15, 19, 21, 23, 31, 32] . For example, the influential work on dominant resource fairness [15] studies the allocation of several heterogeneous computational resources among agents (the owners of various jobs in a data center) and designs protocols that are simultaneously efficient and ensure good treatment of all agents through Sharing Incentive and strategy-proof guarantees. This theoretical work has substantial real-world implications, and is implemented in the Apache Mesos system [19] . In a sense, our work considers the same questions of how to design an effective shared system from the perspective of differential privacy and data release, recognizing that in the common case where there are multiple analysts, privacy budget is indeed a shared resource.
In this paper, we initiated a study into the problem of DP query answering across multiple analysts. We formulated three desiderata -sharing incentive, non-interference and workload adaptivity. We evaluated existing and new DP mechanisms with respect to these desiderata and empirically evaluated their error characteristics.
In this paper, we considered mechanisms that can be represented in the select-measure-reconstruct mechanisms. However this problem can be posed in the context of richer query classes like those involving non-linear queries (graph queries, joins) that would require the DP mechanism to explicitly introduce bias in answers.
In this work we assume that each agent submits a static preselected workload. As such we have ignored interactions between agents and their workload selections. We leave to future work the analysis of agents incentives and strategic behaviour in this context.
We do not know whether the Weighted Utilitarian Mechanism satisfies the Sharing Incentive. There is no case where the Sharing Incentive is violated in our experiments. However, we are also unable to prove that it satisfies the Sharing Incentive in all cases. We leave the satisfaction of this property as an open question for future work.