What is post-processing proof of differential privacy?

Post-processing immunity is a fundamental property of differential privacy: it enables arbitrary data-independent transformations to differentially private outputs without affecting their privacy guarantees .

What is differential privacy easily explained?

Differential privacy is a mathematical framework for ensuring the privacy of individuals in datasets . It can provide a strong guarantee of privacy by allowing data to be analyzed without revealing sensitive information about any individual in the dataset.

How do you prove differential privacy?

To achieve ϵ-differential privacy, we choose the scale parameter b as: b = ∆f ϵ With this choice of b, the Laplace mechanism A satisfies ϵ-differential privacy. and ∆f is the sensitivity of the function f. This completes the proof that the Laplace mechanism satisfies ϵ-differential privacy.

What are the three variants of differential privacy?

We consider three different variants of differential privacy (DP), namely approximate DP, Rényi DP (RDP), and hypothesis test DP .

What is the problem with differential privacy?

Preserving linkability This is also at odds with differential privacy: you cannot hide who is present in the sensitive dataset and also preserve linkability . Small changes in the data will be clearly visible, since one user will or will not be part of the output.

How to apply differential privacy?

The most common way to achieve differential privacy is through a mathematical formula called the Laplace mechanism , which will alter a controlled amount of data. A data scientist cannot identify any individual response as long as they don't know which data changed.

What are the parameters of differential privacy?

Privacy as a Quantifiable Measure To this end, the definition of differential privacy is equipped with parameters (" epsilon and delta ") that quantify the "privacy loss" -- the additional risk to an individual that results from her data being used.

What is differential privacy in Iphone Analytics?

It is a technique that enables Apple to learn about the user community without learning about individuals in the community . Differential privacy transforms the information shared with Apple before it ever leaves the user's device such that Apple can never reproduce the true data.

What is the differential privacy solution?

Differentially private solutions inject noise into a dataset, or into the output of a machine learning model, without introducing significant negative effects on data analysis or model performance . Differential privacy achieves this by calibrating the noise level to the sensitivity of the algorithm.

What are the results of differential privacy?

If the database contains data from a hundred people, each person's data contributes just 1%. The key insight of differential privacy is that as the query is made on the data of fewer and fewer people, more noise needs to be added to the query result to produce the same amount of privacy .

Is Privacy Compatible with Truthfulness?

8/12/2019 Is Privacy Compatible with Truthfulness?
1/31
Is Privacy Compatible with Truthfulness?
David XiaoLIAFACNRS, Universit Paris 7
Paris, [emailprotected]
November 23, 2012
Abstract
In the area of privacy-preserving data mining, a differentiallyprivate mechanism intuitively encouragespeople to share their databecause they are at little risk of revealing their own information.However,we argue that this interpretation is incomplete becauseexternal incentives are necessary for people toparticipate indatabases, and so data release mechanisms should not only bedifferentially private but alsocompatible with incentives,otherwise the data collected may be false. We apply the notion oftruthfulness from game theory to this problem. In certain settings,it turns out that existing differentially privatemechanisms do notencourage participants to report their information truthfully.
On the positive side, we exhibit a transformation that takestruthful mechanisms and transformsthem into differentially privatemechanisms that remain truthful. Our transformation applies togameswhere the type space is small and the goal is to optimize aninsensitive quantity such as social welfare.Our transformationincurs only a small additive loss in optimality, and it iscomputationally efficient.Combined with the VCG mechanism, ourtransformation implies that there exists a differentiallyprivate,truthful, and approximately efficient mechanism for anysocial welfare game with small type space.
We also study a model where an explicit numerical cost isassigned to the information leaked by amechanism. We show that inthis case, even differential privacy may not be strong enough of anotion tomotivate people to participate truthfully. We show thatmechanisms that release a perturbed histogramof the database mayreveal too much information. We also show that, in general, anymechanism thatoutputs a synopsis that resembles the originaldatabase (such as the mechanism of Blum et al. (STOC08)) may revealtoo much information.
1 Introduction
As our world becomes ever more digitized and connected, concernsabout the privacy of our personal in-formation have becomeincreasingly pressing. With various organizations collecting,accessing, and storingindividuals data, our desire to fully takeadvantage of the data has come into stark tension with theequallyimportant desire to keep information about various aspectsof our lives private, including for example ourmedical historiesand our demographic information.
Understanding and resolving this tension has been along-standing goal in the statistics and data analysisliterature[5, 16]. More recently, the theoretical computer science communityhas provided denitions and
a rigorous treatment of this question [7, 8, 11, 3, 12],culminating in the denition and study of differentialprivacy [11,8]. See [9] for a more complete overview of the area and furtherreferences.Differential privacy guarantees the following: a(randomized) data release mechanism is -differentially
private if, for any input database, any participant i in thedatabase, and any possible output of the releasemechanism s, thepresence or absence of participant i causes at most amultiplicative e change in theprobability of the mechanismoutputting s. The question is whether one can achieve privacy whileat thesame time preserving some notion of utility, since one couldalways build a trivially private (but not veryuseful) mechanismthat outputs a constant value without looking at the input data.The advantage of working with the rigorous denition provided bydifferential privacy is that one can now show that certaintasks canbe done with formal guarantees of utility and privacy [2, 3, 24,27, 15, 29].
1
8/12/2019 Is Privacy Compatible with Truthfulness?
2/31
8/12/2019 Is Privacy Compatible with Truthfulness?
3/31
determines the overall quality of the outcome ( e.g. the socialwelfare, which is just the sum of the individualutilities of allthe players).
A mechanism is a (possibly randomized) function mapping eachpossible setting of the players typesto an outcome. The mainproblem studied in mechanism design is to build mechanisms thatsatisfy thefollowing two properties:
Efficiency For any choice of the players types, the expectedglobal utility of the output of the mechanismshould be close to theoptimal global utility .2
Truthfulness For any choice of the players types, no singleplayer, say player i, can report a false type sothat (if all otherplayers remain honest) the mechanism gives an outcome with greaterexpected utilityto player i than if player i had reportedhonestly.
Since individual utilities may not be aligned with the globalutility, it turns out that implementing even verysimplefunctionalities satisfying the two criteria above simultaneously isnon-trivial. For example, the studyof the single-item auction ledto the Vickrey 2nd-price auction mechanism.
The combined model We can now see how the differential privacysetting can be comfortably re-statedusing game-theoreticterminology. An individual is a player, and each individualsprivate information ishis type. The database is just theconcatenation of all players types. The database release mechanismis just a mechanism in the game-theoretic sense. The quality metricis the global utility of the game, andtherefore accurate releasemechanisms correspond to efficient game-theoretic mechanisms. Inaddition tothe above, the individual utility functions now may alsoaffect players behaviors.
Truthfulness is essential not only because it is a standardgame-theory notion, but also because privacydoes not make sensewithout truthfulness. If the data being collected were misreported,it would be of littleuse to the database curator. Moreover,protecting the privacy of false data seems superuous.
Also, recall that in differential privacy, the concern is thatif there is too little privacy then individualsmay choose not toparticipate in a database. In the game theoretic setting,truthfulness and participationare closely related: one can alwaysextend a game to have a type that represents non-participation,andhave a player deviate to the type to representnon-participation. Conversely, a player who reports a typethat isindependent of his true type is in some sense choosing not toparticipate. In the rest of this paper,we will focus ontruthfulness, with the understanding that non-participation is aspecic kind of deviationfrom truthfulness.
Roadmap We will see that mechanisms that seem satisfactory whenprivacy is studied in isolation are notnecessarily satisfactorywhen truthfulness is also explicitly considered.
We will look at the relationship between differential privacyand truthfulness in two frameworks. Therst is to constructmechanisms that are truthful, efficient, and whose output satisesdifferential privacy.In this model, privacy is not given anexplicit numerical value, but is simply an additional property ofthe mechanism. We call such mechanisms PTE, and we show the rst PTEmechanisms by exhibiting atransformation from truthful andefficient mechanisms into PTE mechanisms for games where the typespaceis small and where the global utility is insensitive to anyparticular players type and depends only on thenumber of playerswho have each type.
The second framework is where the value of privacy is explicitlyquantied. We will assign a non-zero costto the amount ofinformation leaked by a mechanism, and we ask when does the cost ofrevealing informationoverwhelm the utility a player gets from thegame. We will show that when privacy has a non-zero cost,
even differentially private mechanisms may not motivateindividuals to reveal their true information.While the rstframework may seem overly simple by not quantifying privacy loss,the techniques devel-oped there have subsequently been shown toapply to the second framework as well (see Section 2.4.2).
2.2 Private, truthful, and efficient (PTE) mechanismsTheExponential Mechanism is not necessarily truthful Our rst resultrevisits the question of whether or not the Exponential Mechanismis truthful. Nissim et al. [31] already exhibited a counter-
2 Throughout this paper, efficiency refers to the game-theoreticnotion. Computational efficiency will be explicitly statedassuch.
3
8/12/2019 Is Privacy Compatible with Truthfulness?
4/31
example showing that the Exponential Mechanism is not truthful.However, the counter-example they giveis somewhat articial becauseit is easy to see that no efficient and truthful mechanism existsfor their game(even without considering privacy). We believe thefollowing Theorem 2.1 highlights the drawback of theExponentialMechanism in sharper relief than the counter-example of [31],because the LINE-1-FAC gamewe consider does have a truthful andefficient mechanism. In fact, we will see that there even exists aPTEmechanism for LINE-1-FAC .
We consider the well-studied 1-facility location on a line game,denoted LINE-1-FAC , which is a specialcase of the k-facilityproblem [ 31, 26, 1] and also of the single-peaked preference games[28, 33]. In theLINE-1-FAC game, each player has a point on theinterval [0, 1] and the mechanism is supposed to outputs [0, 1].Each individual wants to minimize their distance to s, while themechanism wants to minimize thesum of all the individuals distancesto s. This game does have a truthful and efficient mechanismwithoutmoney, namely outputting the left-most median players point[ 28]. We prove:
Theorem 2.1. For LINE-1-FAC , the Exponential Mechanism with anyprivacy > 0 is not truthful.
Transforming a truthful and efficient mechanism into a private,truthful, and efficient mecha-nism Our main positive technicalresult is a transformation for a large class of games that convertstruthfuland efficient mechanisms into PTE mechanisms.
More precisely, we work with the relaxed notion of (,)-differential privacy [ 10], which, in addition to the
e
multiplicative difference, also allows an additive error ,usually taken to be negligible, in the differencebetween the outputdistributions of two databases. Our transformation takes anytruthful and efficientmechanism and transforms it into a (,)-differentially private, truthful, and -efficient mechanism, whereis an additive approximation error that depends on , . Formaldenitions are deferred to Section 3.
These are the rst PTE mechanisms exhibited for non-trivialgames. Furthermore, our transformationpreserves other propertiessuch as computational efficiency and moneylessness, and it appliesto all gameswith small type space. Therefore, applying ourtransformation to the VCG mechanism gives a PTE mecha-nism for al lsocial welfare games with small type space.
As throughout this paper, we will assume in the following thatthe utility functions of each user is boundedin [1, 1], and thatthe global utility function is bounded between [n, n ]. Inparticular, this means that itis interesting to obtain mechanismsthat are -efficiency for = o(n).The transformation The idea of thetransformation is based on the ideas for privately releasinghistogramdata [11]. Suppose the type space of the game is a niteset of size q . For player inputs t = ( t1 , . . . , t n ) wheret iis the type of the ith player, we will let h denote the histogramwith q entries, one for each possible type,and where h j = |{i | ti = j }|, the number of players who have type j .Suppose eachindividual players utility function is v(t, s ) where t is theplayers type and s is an outcomeof the game; suppose that v lies inthe interval [1, 1]. Suppose that the global utility function w(t,s ) isanonymous ( i.e. it depends only on the histogram h and noton player identities), and is insensitive: namelyif h, h are closein 1 distance then for all outcomes s it holds that |w(h, s ) w(h,s )| is small. For example,the social welfare function, which isjust the sum of the individual players utilities, is an example ofsucha global utility function. Without loss of generality, we canassume that all mechanisms for games withsuch global utilityfunctions need only depend on the histogram of player types, ratherthan looking at theindividual players types. (We show this inAppendix A .)
At a high level, our transformation from truthful and efficientto PTE works by constructing the histogramof inputs, addingindependent noise distributed according to the two-sided geometricdistribution to each of the entries of the histogram, and thenrunning the original truthful and efficient mechanism on theperturbedhistogram. Care must be taken that the noise does notcreate negative entries into the histogram; simplytruncatingnegative entries to 0 does not give truthful mechanisms. We show away to achieve this inSection 4 . Our procedure gives the followingtheorem.
Theorem 2.2 (Informal) . Let , > 0. Let G be a game with atype space of size q and where the global utility function dependsonly on the histogram and is insensitive to individual playerstypes. Let M be a truthful and -approximately efficient mechanism.Then there exists a truthful mechanism M for the game G that is (,)-differentially private and is -approximately efficient for .Furthermore, if M is computationally efficient then so is M , andif M is moneyless then so is M .
4
8/12/2019 Is Privacy Compatible with Truthfulness?
5/31
We note that our transformation is applicable to many settingswhere small type space is natural: forexample, in some auctionsettings, the bids are discretized so there are only a few possiblevalues of bids; insurveys or questionnaires, the questions areoften multiple-choice and therefore take on only a few values.Inthe following we choose to highlight two particularly interestingapplications of our transformation.
Application to LINE-1-FAC We will show that using a simplerounding procedure and then applying
Theorem 2.2 to a mechansim for the discretized version of theLINE-1-FAC game, we can give a PTE mech-anism for LINE-1-FAC .
Corollary 2.3. For all , > 0, there is a (, )-differentiallyprivate, truthful, and O(n1/ 2 log(n/ )/ )approximately efficientmechanism for LINE-1-FAC .
Applying our transformation to this game highlights twofeatures: rst, although the Exponential Mecha-nism is not truthfulwhen applied to this game, our transformation shows there doesexist a private, truthful,and efficient mechanism for this game.Second, although our main transformation applies to games withsmallnite type space, our mechanism for LINE-1-FAC shows that in certaincases one can suitably discretizelarge or innite type spaces andthen apply our transformation.
PTE mechanism for all social welfare games with small type spaceIn fact, because the VCG
mechanism gives a general truthful and perfectly efficientmechanism (using money) for all social welfaregames, i.e. gamesoptimizing the sum of the individuals utilities, our main theoremimplies the following:
Corollary 2.4. Fix , > 0. For any game G with n players andwhere the type space has size q , and where the goal is to optimizesocial welfare, there is a truthful mechanism for G that is (,)-differentially private and is O(q log(q/ )/ )-approximatelyefficient.
2.3 The value of privacyPrior work (including the resultsoutlined in the previous section) studied privacy and utility asorthogonalfeatures. For example, in the above we showed that onecould achieve a truthful (with respect to utilityfunctions that donot consider privacy) and efficient mechanism that simultaneouslysatised differentialprivacy. However, if one really believes thatparticipants value their privacy, then this should explicitlybetaken into account in their utility functions. Not only does thisallow us to quantify how much participantsvalue their privacy, italso allows us to model tradeoffs between utility and privacy. Thatis, participantsmay be willing to sacrice some of the utility theyreap from a game by reporting a false type and therebyprotectingtheir privacy. Vice versa, participants may be willing to sacricetheir privacy if by doing so theygain a larger utility from theoutcome of the game. We will show that it is possible even for PTEmechanismsto leak too much information to achieve truthfulness ingames where there exists a tradeoff between utilityand privacy.
2.3.1 Quantifying privacy
The rst task is to dene a measure of how much information amechanism leaks. One natural conditionthat the information costshould satisfy is that it should be 0 if a player reports a typethat is independent of his honest type, since this means that theoutput of the mechanism does not contain information about histype,and so should not compromise his privacy. This criterion impliesthat information cost cannot solely be a function of the playerstype and the outcome of the game, because the notion independent ofthehonest type is inherently a statement about how the playerbehaves on al l possible values of his type. As athoughtexperiment, x any type t, and consider the following twostrategies: rst is the truthful strategy,and second the strategythat always outputs t regardless of what the players actual typeis. Then, in thecase that the players actual type is t, the twostrategies give exactly the same output, but intuitivelythetruthful strategy might reveal information about the playerstype while the constant t strategy does not.
Therefore our measure of information cost cannot be expressed asa modication of a traditional utilityfunction that depends solelyon the players type and outcome. Instead, we work with a measurethatdepends on the players strategy over all possible types.
5
8/12/2019 Is Privacy Compatible with Truthfulness?
6/31
We let IC M (,t,i ) denote the information cost to player i ofthe strategy , given that the (true) inputis t = ( t1 , . . . , t n) and that the mechanism is M . A strategy is simply a functionmapping types todistributions over types, so that if player i hastrue type t , then to use strategy he will sample t (t)and declaret to the mechanism.
In general the information cost can be highlyapplication-specic, and so we prefer to state our resultswithoutxing a specic information cost function. Rather, our results holdfor any information cost function
that satises the following assumptions:Players can hide theirdata: for any strategy that is independent of its input ( i.e. (t)= (t) for all
t, t ), then for all i, t it holds that IC M (,t,i ) = 0 .Costreects differential privacy: roughly, this condition requires that,if is the minimal value such
that M is a -differentially private mechanism, the informationcost cannot be much lower than .
We formalize the assumptions above in Section 5. We alreadyjustied the rst assumption above. Intuitively,the second assumptionsimply means that the amount of differential privacy (the ) isdominated by theapplication-specic information cost. In contextswhere the information cost did not satisfy the secondcondition,presumably this means that we have application-specic knowledgeabout what privacy concernsare relevant, and so it would be moresensible to study mechanisms that target directly theapplication-specic information cost rather than trying to usedifferential privacy as a generic tool.
In Appendix C we give some candidate denitions of informationcost.
Tradeoffs between the value of the game and the value of privacyGiven an information costfunction, we would like to explicitlyincorporate it into the utility of the player. Let us use the wordgamevalue or simply value to denote the benet that the playerextracts from the outcome of the game withouttaking into accountprivacy, and we will let overall utility be the game value minusthe information cost, andwe will say that such a utility isprivacy-sensitive.
2.3.2 Releasing histograms for LINE-1-FAC
Our rst negative result draws on the LINE-1-FAC game once again.Corollary 2.3 says that a PTE mechanismfor LINE-1-FAC exists, letus denote it by M (see Algorithm 4.10 for the denition of themechanism). Inorder to understand the following result, we rst givea rough description of M : M rst rounds the positionsof the playersto discrete points, then constructs a histogram of the playersrounded locations, perturbs thehistogram, and nally outputs themedian point of the perturbed histogram. Suppose now that, insteadof outputting the median, the mechanism outputs more than necessaryand also publishes the entire perturbedhistogram of the playerslocations as well. Call this mechanism M . We believe that M ,represents a plausiblesituation in the real world: an agencygathers data for a single explicit purpose, for example to decidewhereto build a hospital so as best to serve local residents, butthen publishes the entire perturbed histogram dataso that it may beof use to other agencies that may want to use it in a differentway.
M is actually PTE: truthfulness and efficiency remain becausethe facility location output is the same asM , while privacy alsoremains because the perturbation of the histogram was designed torender the entirehistogram differentially private. However, we showin Theorem 5.6 that if we set the parameters so that themechanismis (2, )-differentially private, then the information cost isgreater than . On the other hand,we show in Theorem 5.3 that thereexist situations where the amount of value that a player loses byignoringhis true type and declaring a xed type, say 0, is at moste( n ) . This implies the following:
Theorem 2.5 (Informal, see Corollary 5.8 ). The PTE mechanismfor LINE-1-FAC given by M is untruthful when one takes into accountthe information cost.
2.3.3 Releasing synopses.
We prove a more general theorem about the information cost ofany mechanism that publishes informationthat can be useful for manydifferent count queries: if Q is the type space of the players andF : Q {0, 1},then we dene the count query F (t) = 1n ni =1 F (t i). For example, in the case of a census, F might be theset ofhouseholds with two children, and F (t) would be the fraction ofall households that have two children.
6
8/12/2019 Is Privacy Compatible with Truthfulness?
7/31
We say that a mechanism M is a synopsis generator for a class ofpredicates C if, given an input databaset, it outputs a datastructure M (t) from which we can deduce F (t) for many F C. It wasshown by Blumet al. [3] that it is possible to constructdifferentially private and accurate synopsis generators.Subsequentwork has extended this to achieve better parameters [13,21].
Here we show that good synopsis generators must leakinformation:
Theorem 2.6 (Informal, see Theorem 5.11 ). If M is a goodsynopsis generator for a rich class of predicates,and IC M reectsdifferential privacy, then for almost all databases, theinformation cost of revealing a synopsis generated from thatdatabase is (1) with respect to at least one player.
This shows that synopsis generators such as the one proposed byBlum et al. [3] must inherently reveal alot of information someplayers type, and furthermore, that they must leak information onmost databases(more precisely, we will show that for any database,there is a nearby one where some player has a highinformationcost). Interestingly, the proof uses a construction of acombinatorial design to show that, forevery t, there exists anexponentially large family of t that differ little from t such thatone of them has aplayer with large information cost.
This theorem leads to the following consequences: consider amechanism M that publishes an output that(a) incentives playersparticipation by giving them some value and (b) includes a goodsynopsis. If the valueto each player diminishes by very little (sayvanishingly small) when a player mis-reports his type, buttheinformation cost is constant (as is implied by Theorem 2.6 ),then the mechanism cannot be truthful. Namely,individuals willprefer to lie because by declaring, say, a constant value, theywill gain in information costmore than enough to compensate fortheir loss in value. This may hold even if M is differentiallyprivate. Asa specic instantiation, we prove that if a mechanism Mapproximately solves the 1-facility location problemover any metricspace and simultaneously releases a synopsis, then M cannot betruthful. See Section 5.2for formal statements.
2.4 Comparison with related workSince the original version ofthis manuscript appeared in January 2011 [35], in the followingdiscussion weseparate previous work and subsequent work accordingto that date.
2.4.1 Previous work.
There has already been a fruitful interaction between gametheory and the study of differential privacy.The rst work combiningthe two is the Exponential Mechanism of McSherry and Talwar [ 27],whichachieves privacy, approximate truthfulness, and efficiency.Approximate truthfulness says that the amountany player can gain byannouncing a false type is small (but possibly positive).Approximate truthfulness isin fact a consequence of differentialprivacy, which says that any one players type can only affect theoutputdistribution of the mechanism by a little. McSherry andTalwar [27] interpret approximate truthfulness tomean that theplayer might as well announce his type honestly, since he haslittle incentive to deviate. Theyalso show that their mechanismachieves good efficiency (assuming the players behavetruthfully).
Unfortunately, the approach suffers from the following twodrawbacks, rst observed by Nissim et al. [31].First, in theExponential Mechanism, all possible strategies of any individualplayer lead to approximatelythe same output distribution of themechanism. If one accepts the interpretation that players areindifferentto small changes in their utility, then intuitivelyprivacy may even motivate players to lie : players areindifferentto the small amount of utility from the game outcome that is lostby lying, but they would preferto lie because that would reduce theamount of information leaked by the mechanism about theirprivatetype. (We will formalize this concern in Section 5, see alsothe discussion in Section 2.3 .) Thus, it seemsthat approximatetruthfulness cannot substitute for standard truthfulness whenprivacy is desired.
Second, Nissim et al. [31] showed that the Exponential Mechanismis not truthful for a game based ondigital goods auctions, andtherefore the relaxation to approximate truthfulness is inherentlynecessary. (Aswe mentioned, we show that Exponential Mechanism isnot truthful also for the LINE-1-FAC game.)
Nissim et al. [31] go on to show that by combining theExponential Mechanism with a Gap Mechanism that incentivizeshonesty, one can get a fully truthful mechanism. They apply thismechanism to give atruthful and approximately efficient mechanismfor the k-facility problem on a line, which is a more general
7
8/12/2019 Is Privacy Compatible with Truthfulness?
8/31
version of the 1-facility problem on a line that we will studyin this paper. Unfortunately, their mechanism isnot differentiallyprivate, because the Gap Mechanism relies on constraining thepost-actions of the players,and this constraint reveals the typesof the players in a very non-private way.
Ghosh and Roth [ 18] consider a question that is related butorthogonal to our work: they considerveried databases where eachplayer has private information that a database owner wants togather. Theirmechanism allows each player i to declare a pricingfunction ci : R R such that ci () represents the minimalpaymentthat player i would require to submit his information to a databasethat is then published via an-differentially private sanitizationmechanism. Their mechanism uses these pricing functions to computeavalue of and payment values that are paid out to each player suchthat enough of them are incentivizedto participate to make theoutcome of the sanitizer accurate. More follow-up works in thisdirection haveappeared recently [32, 17, 25]. The main differencewith our model is that in this line of work, it is assumedthat theplayers private information will be accurately reported, and theymay only lie about how muchthey value their privacy. In contrast,our model focuses on deviations resulting from players reportingfalseprivate information, but does not explicitly consider playerslying about their valuation of their privacy.
Feigenbaum et al. [14] study how to keep information privateeven from the database owner, i.e. beforerunning sanitization. Wedo not study this problem here and treat the database owner as atrusted party.We note however that, using standard cryptographicassumptions and protocols, one can replace a trusteddatabase ownerby a secure multiparty computation among the individuals.
2.4.2 Subsequent work
Subsequent to the initial version of this manuscript, Chen etal. [ 4] showed that it is possible to build truthfulmechanismseven when the players utilities explicitly take into account thecost of information leaked, thusanswering affirmatively one of theopen questions posed in the initial version of this manuscript.Their resultholds for a general class of information costs. Some oftheir mechanisms are inspired by the TE-to-PTEtransformation (Theorem 4.3 ) presented in this paper.
Huang and Kannan [23] resolve another problem posed in theoriginal version of this manuscript: theyshow that one can alterthe VCG mechanism to give a PTE mechanism for any social welfaregame. Thisbypasses the restriction of our transformation to smalltype spaces. We note that their result is neverthelessincomparableto ours in certain respects, because it inherently uses paymentsand so cannot be used toconstruct moneyless mechanisms, and theirmechanism is not necessarily computationally efficient (althoughforcertain specic games they acheive computational efficiency).
Nissim et al. [30] show that under certain assumptions about thedistribution of information costs of apopulation and assuming thatthe mechanism can restrict the reactions of individuals, one canbuild truthfulmechanisms that take into account the playersinformation costs.
3 Preliminaries
We let [q ] = {1, . . . , q }. We identify sets S with theuniform distribution over the set. For a distribution X ,we write xX to denote a random sample from that distribution. We letunderlined variables x denotevectors and xi the ith coordinate inthe vector. For x R n , we let x 1 = ni =1 |x i | denote the 1normand x = max i |x i | the norm.
Games A game with n players consists of the type space Q, aspace S of possible outcomes of the game,
a valuation function v : Q S [1, 1], and a global utilityfunction w : Qn S R . The valuationfunction v determines theprivate utilities of the players. When Q is nite, we let |Q| = q .For i [n], fort1 , . . . , t n , we let ti denote the vector with n1 entries given by t1 , . . . , t i1 , t i+1 , . . . , t n . Deneh(t) Z qthe histogram of the input, where h j = |{i | t i = j }|.We assume w.l.o.g. that the type space has a special type, and anyplayer that declares this special type is ignored. (Namely, aninput with n players, k of whom have type , is treated as an inputto the game with n k players with those k players removed.)We denethe following properties of games:
1. A game is anonymous if it has an anonymous global utilityfunction: let w be its global utility function,then there is afunction w such that for all t, s , it holds that w(t, s ) =w(h(t), s). In such cases, we
8
8/12/2019 Is Privacy Compatible with Truthfulness?
9/31
abuse notation and write w(h, s ) to mean w(t, s ) where h =h(t).2. An anonymous global utility function is insensitive if forall integers k, h h 1 k implies that forall s , |w(h, s ) w(h, s)|k.3. The social welfare is w(t, s ) =
ni=1 v(t i , s). It is anonymous and insensitive.
Mechanisms A mechanism M is a (randomized) function that takestypes t1 , . . . , t n for all of the players
and samples an outcome (s, p) M (t1 , . . . , t n ) where s S isthe game outcome and p : Q R is afunction determining payments.Namely, any player with type t must pay p(t) to the mechanism(since weonly consider anonymous games, payments only depend on thetype and not the identity of the player). Eachplayer tries tomaximize v(t i , s ) p(t i ) where (s, p) is the outcome of thegame.We say that M is moneyless if p 0 for all inputs and randomcoins. We are concerned with asymptoticanalysis, so M must be beable to handle any number of players n .
A player strategy is a function mapping the type space Q todistributions over Q. If a player usesstrategy , this means given atrue type t, the player samples from t (t) and reports t to themechanism.
1. We say a mechanism M is truthful if for every player i [n],and for all t and all strategies , it holdsthat E (s,p )M (t ) M[v(t i , s) p(t i )] E t i ( t i ) ,( s,p )M (t i ,t i ) [v(t i ,s) p(t i )].32. We say a mechanism is (n)-efficient if for allinputs t on n players, it holds that E M [w(t, M (t))] max sS w(t,s )
(n).
Observe that our denition of efficiency allows for an additiveerror. In contrast, most work in themechanism design literature onapproximate mechanisms deal with multiplicative error. However,additiveerror is more suitable when working with differentialprivacy.
Differential privacy A mechanism M is (, )-differentiallyprivate if for all i [n], all t Qn , all t Q,and all subsets U ofthe output space of M , it holds that Pr[M (t) U ] e Pr[M (ti , t )U ]+ . Typicallywe think of > 0 being a small constant and asbeing o(1), preferably negligible.Denition 3.1 (PTE mechanisms) . Amechanism M for a game dene by private valuation functionsv : Q [1,1] and global utility function w : Qn R is ( ,, )-PTE if it is (,)-differentially private,truthful (with respect to privatevaluations v), and -efficient (with respect to global utilityw).
Useful distributions We will frequently write = e . Let G denotethe geometric distribution over theintegers, with probability massfunction f (x) = 11+ |x |. Let H,,q be the following distribution:sample Gq . If > , output 0, otherwise output .It isstraightforward to calculate that for G :Pr[ | | ] =
2
1 + (3.1)
Lemma 3.2. For all i , j [q ] and U Z q , for sampled from H,,qit holds that:Pr[ U ] e2 Pr[ei ej + U ] + 2q
1+
where ei denotes the ith standard basis vector.
For completeness we provide a proof in Section B.1 .
Negative binomial distribution The negative binomialdistribution NB q, is dened using the proba-bility mass functionf(x) =
x + q 1q 1
(1 e )qex3 Observe that the value is calculated according to thetrue type t i on both sides, but the payment is calculatedaccording
to the declared type ( t i in one case, t i in the other). Thisis because the payment is what the mechanism asks the playertoplay, and this is a function of the declared type.
9
8/12/2019 Is Privacy Compatible with Truthfulness?
10/31
Fact 3.3 (e.g. [34]). We note the following:
1. The sum of q two-sided random geometric variables qj =1 j ,where each j is distributed according
to G , is distributed identically to Y Y where both Y, Y areindependent and identically distributed according to the NB q, .42.Suppose Y is distributed according to
NB q, . Then Pr[Y
t] = Pr[ Z
q ] where Z is a binomial
random variable for an experiment with q + t trials and successprobability (1 e ) for each trial.
4 PTE Mechanisms
4.1 The Exponential Mechanism not truthful for LINE-1-FAC
Denition 4.1. The LINE-1-FAC game is dened as follows. Theplayer types are t i [0, 1]. The outcomeof the game is a point s[0, 1]. The utility function is v(t, s ) = |t s| and the globalutility is the socialwelfare: w(t, s ) = i[n ] v(t i , s ) = i[n ]|t i s|.The moneyless mechanism that outputs the median (breakingties say by picking the left median point)of the {t1 , . . . , t n} is truthful and achieves optimal social welfare for this game[28].We now prove Theorem 2.1 , the fact that the ExponentialMechanism is not truthful for LINE-1-FAC .of Theorem 2.1 . For n =2 , set t 1 = 0 , t 2 = 2 / 3. (This can easily be extended to anarbitrary even numberof players n by placing n/ 2 players at 0 and(n/ 2 1) players at 1, and one player at 2/ 3.)Claim 4.2. For all> 0, if player 2 declares 1 then his utility under theExponential Mechanism is 5/ 18,while if he declares 2/ 3 then hisutility is strictly less than 5/ 18.of Claim 4.2 . The ExponentialMechanism M Exp generates an output s according to the densityfunctionf (s) = e
w ( t,s )
10 ew ( t,s ) ds. One can compute that the expected utility ofplayer 2 if he reports 1 is
10 |2/ 3s|ds =
5/ 18, since in this case there are exactly half the players at0 and at 1 and so the social welfare function(and hence themechanisms output) is uniform over [0, 1].If player 2 is truthful,then the social welfare equals w(t, s ) = s |2/ 3s|. The idea isthat this welfaredecreases as s increases past 2/ 3, and so theExponential Mechanism will give lower weight to the points in
[2/ 3, 1]. This will hurt player 2 and he will get worse utilitythan if he declared that he was at 1.We formalize this and analyzethe Exponential Mechanism for a truthful player 2. The expectedutilityof player 2 is:
V def
= E sM Exp (0 ,2/ 3) [v(2/ 3, s)] = 1
0 e (s + |2/ 3s |) |2/ 3 s|ds
1
0 e (s + |2/ 3s |) ds
We claim that for all > 0, it holds that V < 5/ 18. Thisis equivalent to proving
0 < V 5/ 18 = 1
0 e (s + |2/ 3s |) (|2/ 3 s| 5/ 18)ds
1
0 e (s + |2/ 3s |) ds
Observe that the denominator is positive, so it suffices toprove that the numerator is positive for all > 0.
Evaluating the integral we obtain that
1
0e (s + |2/ 3s |) (|2/ 3 s| 5/ 18)ds = e2/ 3
127
+ 9 5 e2/ 3( + 9)
362 (4.1)
Since e2/ 3 > 0 so we can multiply the LHS of Equation 4.1 by362e2/ 3 and simplify, and it suffices toprove that
4 23 + 9 5 e2/ 3( + 9) > 0 (4.2)
4 This follows from the fact that a two-sided geometric randomvariable is identical to the difference between twoone-sidedgeometric random variables, and the sum of one-sidedgeometric random variables is a negative binomial.
10
8/12/2019 Is Privacy Compatible with Truthfulness?
11/31
Input: types t1 , . . . , t n [q ]. Auxiliary input: , privacyparameters. Set = O(log(q/ )/ ).1. Sample H,,q2. Construct h = h ++ 1, where 1 is the all 1 vector.3. Output M (h ).
Algorithm 4.4. PTE mechanism based on a truthful and efficientmechanism M .
For large 0 the RHS of Equation 4.2 is dominated by thequadratic term. For instance it is easy tocheck that for all >1, it holds that e2/ 3 < 0.52 and so:4 2
3 + 9 5 e2/ 3( + 9) > 42
3 + 9 5 0.52( + 9) (4.3)> 4
2
3 4.48 + 4 .32 (4.4)> 0 (4.5)
where the nal inequality can be deduced by the fact that thequadratic polynomial in Equation 4.4 has no
real roots and is non-negative. Therefore we can restrict ourattention to the case 1. Using the Taylorexpansion of theexponential, we know that e2/ 3 123 + 22
9 43
81 + 2 4243 for 1, therefore Equation 4.2can be rewrittenas:
4 23 + 9 5 e2/ 3( + 9)
42
3 + 9 5 (1 23 + 22
9 43
81 + 2 4243 )( + 9)
= 42
3 + 9 5 9 + 22
3 + 6 23
9 22+ 4
4
81 + 4 3
9 25
243 24
27
= 23
9 24
81 25
243
> 3( 29 227 227 )> 0
where in the last two lines we use the fact that 1.
4.2 Transformation from TE to PTEWe now exhibit a generictransformation that converts a truthful and efficient mechanism Minto a PTEmechanism M . We assume M satises the following: on inputt, M computes its output depending only onh = h(t) (and never looksat the entries of t individually). (This is without loss ofgenerality for anonymousgames, see Appendix A .)
Theorem 4.3. Let G be a game with type space of size q and whoseglobal utility function is anonymous and insensitive. Suppose G hasa truthful and -efficient histogram mechanism M and that isnon-decreasing .5
Then for all , > 0, G also has a (2,, )-PTE mechanism M ,where (n) = (n + O(q log(q/ )/ ))+O(q log(q/ )/ ). M is given byAlgorithm 4.4 . Note that if M is computationally efficient, so isM , and if M is moneyless, so is M .
of Theorem 4.3 . Let M be the truthful and -efficient mechanism.By Equation 3.1 and the union bound,we can set = O(log(q/ )/ ) suchthat
Pr Gq
[ > ] < 2qe 1 + e
= (4.6)
5 This is a technical condition to simplify the expression for ;for any interesting we can articially increase it as somepoints tomake it satisfy this property.
11
8/12/2019 Is Privacy Compatible with Truthfulness?
12/31
In Algorithm 4.4 we construct a mechanism M (using set as justmentioned) that is private, truthful, and -approximately efficient.We prove that M is PTE:
Truthfulness Fix an input t. We claim that for every choice of ,the mechanism is truthful. We runM on the histogram h = h + + 1.Because is sampled from H,,q , it holds for every t Q thatht
ht
0. Suppose that, for this xing of , there is a deviation thatbenets some player, i.e. there
exists i and such that
E (s,p )M (h ) [v(t i , s) p(t i )] < E t ( t i ) , ( s,p )M(h e t i + e t ) [v(t i , s) p(t )]where et Z q is the tth standardbasis vector. Then this is also a deviation on the input h for theoriginalM , which contradicts the fact that M istruthful.Efficiency Let be sampled from H,,q and observe that . Forany input t dene h = h(t) andthe modied histogram h = h(t) + + 1.Observe that |h h|1 2q . By the insensitivity of w, it holdsthatfor all possible outcomes of the game s, it holds that w(h, s )w(h, s ) 2q . Therefore it holdsthat:
E M [w(h, M (h))]
E M [w(h , M (h))]
2q (4.7)
maxs w(h, s ) 2q (n + 2 q ) (4.8) w(h, s0) 2q (n + 2 q ) (4.9)maxs w(h, s ) 4q (n + 2 q ) (4.10)
In Equation 4.8 we use the efficiency of M , the fact that hcorresponds to a game with at most n + 2q players, and that (n) [0,2n] is non-decreasing. In Equation 4.10 s0 denotes the outcome thatmaximizesw(h, s ).
Applying Equation 4.10 to the expected utility of M , oneobtains the following:
E M [w(t, M (h))] = E H,,q ,M [w(t, M (h ))]
max
s
w(t, s )
(n + 2 q )
4q
Privacy Observe that Algorithm 4.4 is just perturbing thehistogram according to the distribution H,,q .Therefore, from Lemma3.2 , we know that for any adjacent h, h, it holds that for allsubsets U Z q thatPr[h + U ] e2 Pr[h + U ] + 2qe
1+ e
Since by our choice of we know that 2qe
1+ e , this shows the mechanism is (2, )-differentiallyprivate.
Note that one popular alternative way of perturbing thehistogram, by adding noise according to G toeach bin of thehistogram and then truncating negative bins to 0, does not seem toguarantee truthfulness.The problem is that the truncation processis non-linear, and so it is unclear how to prove that adeviation
in the perturbed game implies a deviation in the originalgame.
4.3 LINE-1-FAC has a PTE mechanismWe show that although theExponential Mechanism is not truthful for LINE-1-FAC (Denition 4.1), theredoes exist a mechanism that is truthful, differentiallyprivate, and approximately efficient. This mechanismis given inAlgorithm 4.10 . The idea is to reduce LINE-1-FAC to a game D-L1F(discrete one-facility on aline) with a small type space, and thento give a private, truthful, and efficient mechanism for D-L1FusingTheorem 4.3 .
12
8/12/2019 Is Privacy Compatible with Truthfulness?
13/31
Input: histogram of player types h. Let n = qj =1 hj .
1. Output the minimal s 1 such that sj =1 hj n2 .
Algorithm 4.6. Truthful and efficient mechanism for D-L1F
4.3.1 The D-L1F game
Denition 4.5. The D-L1F game is dened as follows. Assume that> 0 is such that q = 1 / + 1 is aninteger. The player types aret i [q ]. Output of mechanism is s [q ]. Utility function is v(t, s) = |t s|.Global utility is social welfare: w(t, s ) =
ni =1 v(t i , s).
Theorem 4.7. There is a truthful and perfectly efficientmechanism for D-L1F .
The mechanism is given in Algorithm 4.6 . We may apply Theorem4.3 , we obtain:
Corollary 4.8. For all , > 0, D-L1F has a ( ,, )-PTEmechanism for = O(log( 1 )/ ( )) .
The proof of Theorem 4.7 is a special case of the proof that themedian mechanism is truthful and efficientfor single-peakedpreferences. For completeness, we give a proof in Section B.2 .
4.3.2 Using D-L1F to give a PTE mechanism for LINE-1-FAC
Theorem 4.9. For any , , > 0, the mechanism of Algorithm 4.10is (2, )-differentially private, truthful,and -efficient for theLINE-1-FAC game, where = n + O( 1 log(
1 )) .
As an example setting, pick = n1/ 2 , which implies = O(n1/ 2log(n/ )/ ).
of Theorem 4.9 . (2, )-differential privacy follows immediatelyfrom Theorem 4.3 . Efficiency is also straight-forward, because theoverall error is at most the discretization error, which is boundedby for each player,plus the error from M , which is bounded by O( 1log( 1 )) .
Truthfulness. Truthfulness must be argued more carefully becausethe rounding process might causeunexpected problems. By symmetry,it suffices to consider player 1.
Fix t1 , t1 , and t. We will show that the player can gain noutility from declaring t when his actualtype is t1 . Fix any choiceof random coins used by M . Let h = h(t)+ + 1 and h = h(t1 , t)+ +1.Let s = M (h) and s = M (h). From the proof of truthfulness ofAlgorithm 4.6 , we observe that M has thefollowing property (whichis stronger than truthfulness): either s = s or |t1 s| |t1 s| 1.(Namely,it is impossible for s = s and yet |t1 s| = |t1 s|.)In thecase where s = s then there is clearly no advantage to lying, sosuppose |t1 s| |t1 s| 1.Observe that the rounding processguarantees that for all t [0, 1], |t t| / 2. Therefore we maywrite
|t1 s | |t1 s|+ / 2 (|t1 s| 1) + / 2 |t1 s|
This again implies that there is no advantage to declaring t,and so since for every choice of the mechanismis truthful, itfollows that the overall mechanism is truthful.
13
8/12/2019 Is Privacy Compatible with Truthfulness?
14/31
Input: player types t1 , . . . , t n [0, 1]. Assume forsimplicity that 1/ is an integer.1. Discretize [0, 1] into q = 1 /+ 1 intervals: [0, / 2), [/ 2, (1 + 1 / 2) ), . . . , [( j 1/ 2), (j +1/ 2) ), . . . , [(q 1/ 2), 1].2. Assign player i the proxy typet i = j such that t i falls into the j th interval.
3. Let M denote the mechanism for D-L1F given by Theorem 4.7 .Let M be the correspond-ing (2, )-differentially private, truthful,and efficient mechanism, given by Corollary 4.8 . RunM (t1 , . . ., tn ) to obtain s [q ].
4. Output s.
Algorithm 4.10. (2, )-differentially private, truthful, andefficient mechanism for LINE-1-FAC .
4.4 Application to the VCG mechanismCorollary 2.4 , stating thatall social welfare games with small type space have a PTEmechanism, followsfrom applying Theorem 4.3 to the VCG mechanism(which is truthful and perfectly efficient for all socialwelfaregames).
Observe that the privacy holds with respect to the outcome ofthe game s and the payment function p thatmaps types to payments.In particular, we assume that the payments of individual playersare not revealedpublicly. Clearly, privacy would not hold ifoutside observers learned that, say, player i made payment p(t i).This is unavoidable, but it seems reasonable that the actualpayment of each player can be kept secret e.g.by transmitting thepayment using cryptographic techniques or some other securechannel. One can alsoensure that the player and curator do not tryto underpay/overcharge by using proofs that the mechanismwascomputed correctly and that amount paid is correct by usingtraditional cryptographic techniques ( e.g.NIZK proofs).
5 The value of privacy
We now explore a model that assigns non-negative costs to theinformation leaked by mechanisms aboutthe private types of theplayers. As argued in the introduction, we assume the informationcost to player idepends on the mechanism M , the strategy used byplayer i, and the types of all players t. In additionwe will allowthe information cost with respect to a small approximation factor0, which we motivatebelow. Therefore, the information cost is afunction of the form IC M (,t,i ). We will sometimes write IC M todenote IC 0M . Our formal assumptions about the information costare:
Assumption 5.1. We make the following assumptions about the-approximate information cost:
Players can hide their data: if is independent of its input (i.e. (t) = (t ) for all t, t ), then for alli, t it holds that IC M(,t,i ) = 0 .
Cost reects differential privacy: for the truthful ( i.e.identity) strategy Id :
IC M (Id , t , i ) maxt Q maxB log
Pr[M (ti , t ) B ]Pr[M (ti , t ) B ](1 )
(5.1)
where the maximum of B is taken over all subsets such that Pr[ M(ti , t ) B ] > .The intuition behind these assumptions wasdiscussed in Section 2.3.1 . The formal denition of the
assumption that cost reects differential privacy (Equation 5.1 )intuitively says that the cost is at least howmuch more likely thetrue type t is than any other type t after having observed theoutput of the mechanism.This is precisely the kind of difference inprobability captured by differential privacy. In fact, onenatural
14
8/12/2019 Is Privacy Compatible with Truthfulness?
15/31
denition of information cost in the case where we have nofurther application-specic criteria is preciselythe RHS of Equation5.1 (see Appendix C ).
We now mention the role of . When we study (, )-differentiallyprivate mechanisms, we will set inthe assumption to roughly matchthe in (, )-differential privacy. This is intuitively natural,since withoutthis the mechanisms output may have small uctuationsin probability that create large (but intuitivelyunmeaningful)information costs. For -differential privacy, we set = 0.
To combine the information cost with the value derived byplayers from a game, we use the followingu i (, t ) = E t ( t ) ,sM (t i ,t ) [v(t i , s )] i IC M (,t,i ) (5.2)
Here, we have weighted the information cost with a factor i thatexpresses how much the individual valueshis privacy relative to thevalue of the game.
Remark 5.2. In Equation 5.2 , i models the weight of player isprivacy, and for simplicity we assume thatthe i are xed and known(Ghosh and Roth [ 18] study mechanisms where these valuations areprivate).Intuitively 1/ i represents how many bits must be leakedfor player i to lose a constant amount of utility. i = (1/ log |Q|)is a realistic setting, and would mean a constant cost is incurredif a constant fraction of bits is leaked. Signcantly smaller valuesof i would model a situation in which the player assignssignicantcost only when his type is essentially completely revealedby the mechanism. In particular, we may safelyassume that theweights to satisfy i = 2o(n ) , since otherwise the amount ofutility that the player placeson privacy is so small thatexplicitly modelling the value of privacy loses relevance.
5.1 Releasing histograms for LINE-1-FAC
Recall that Corollary 2.3 says that by applying ourtransformation ( Theorem 4.3 ) to a discretized version of themedian mechanism for the LINE-1-FAC game, we can give a PTEmechanism for the LINE-1-FAC game.An explicit description of thismechanism is given in Algorithm 4.10 , let us call this mechanism M.
Here we show that, on certain databases, no single player canheavily inuence the outcome of M .(2, )-differential privacyimplies that being untruthful can hurt the value of a player by atmost 2 + . Itturns out that for this particular mechanism M , thereexist inputs for which the loss is much smaller.Theorem 5.3. Fixany > 0 and any > 0 such that = 2o( n/ log n ) ( i.e. is nottoo small). Then for n large enough, for all i , there exists ti[0, 1]
n 1 such that for all t i , t i [0, 1], it holds that:E sM ( t )[v(t i , s )] E sM ( t i ,t i ) [v(t i , s )] e(1e
) 2 n (5.3)
Proof. To simplify our notation, suppose that the number ofplayers is n + 1 rather than n. By our choiceof , Algorithm 4.10divides [0, 1] into q = n1/ 2 intervals.
We study the case i = 1, as symmetry will imply that the sameargument works for all choices of i . Thesetting of player types t1is simply to put n players at location 0.
Recall that M functions by building a histogram of the playerslocations, generating noise H,,qwhere = O(log(q/ )/ ), adding + 1to the histogram, and then running the deterministic mechanismM ofAlgorithm 4.6 . Notice that for our choice of t1 , there is norounding necessary. Let us rewrite theLHS of Equation 5.3 as:
E [v(t1 , M (h(t) + + 1)) v(t1 , M (h(t1 , t 1) + + 1))](5.4)The main observation is that for most choices of , M gives thesame output regardless of what player 1
declares as its value. To state this more formally, dene
h1 = h(t1) + + 1 (5.5)n = ( n + 1) +
q
j =1
j + q (5.6)
The value in Equation 5.4 is upper-bounded by the probabilityover that M (h(t)+ + 1) = M (h(t1 , t 1)+ + 1). Call this event B .B occurs only when there exists k [q ] such that
kj =1 (h1) j = n / 2 1.
15
8/12/2019 Is Privacy Compatible with Truthfulness?
16/31
Claim 5.4. Pr[B ] e(1 )2 n
Since we argued above that E [v(t1 , M (h(t) + + 1)) v(t1 , M(h(t1 , t 1) + + 1))] Pr [B ], thisclaim implies the theorem.
of Claim 5.4 . Observe that Pr H,q, [B ] can be written as:
Pr H,q,
k,k
j =1
(h1)j = n / 2 1 = Pr Gq k,k
j =1
(h1) j = n / 2 1(5.7)
Pr Gq k,k
j =1
(h1)j = n / 2 1 (5.8)
q
k=1
Pr Gq
k
j =1
(h1)j = n / 2 1 (5.9)
where Equation 5.7 holds because by denition the distribution ofH,q, is exactly the same as Gqunder the condition .Observe that, bythe denition of h1 and n , we may rewrite Equation 5.9 toobtain:
Pr
[B ] q
k=1
Pr
k
j =1
(h(t1)j + j ) = b +q
j = k +1
(h(t1) j + j ) + ( q 2k) (5.10)
where b = 1 if n is even and b = 0 if n is odd. Let us considerb = 0 (the other case follows by the sameargument). By constructionthere are n players at position 0, so it follows that h1 = n and hj= 0 for all j > 1. Therefore the RHS of Equation 5.10 equals
Pr
n +k
j =1
j =q
j = k+1
j + ( q 2k)
Since G is symmetric therefore j is distributed identically as j, and combined with the above we maydeduce:
Pr
[B ] q
k =1
Pr
q
j =1
j = n (q 2k) (5.11)
We will prove the following lemma.
Lemma 5.5. For all k [q ] and sufficiently large n , it holdsthat
Pr
q
j =1
j = n
(q
2k)
e1.9(1 ) 2 n
Applying this lemma to Equation 5.11 we obtain Pr [B ] qe1.9(1)2 n , which, for large n , is bounded
by e(1 ) 2 n .
We now turn to proving Lemma 5.5 The key point is thecharacterization of the sum of q two-sidedgeometric randomvariables given in Fact 3.3 :
qj =1 j is distributed identically to Y Y where Y, Yareindependent NB q, variables.
16
8/12/2019 Is Privacy Compatible with Truthfulness?
17/31
of Lemma 5.5 . We will prove the following slightly strongerinequality:
Pr
q
j =1
j n (q 2k) e1.9(1 )2 n
By Fact 3.3 it holds that
q
j =1
j is distributed identically to Y
Y as stated in Fact 3.3 . Furthermore,
since both Y, Y are non-negative, Y Y n (q 2k) implies that Y n(q 2k) . Therefore itsuffices to bound Pr[Y n (q 2k) ].Furthermore, it suffices to consider just the case k = 0 , whichisthe worst possible.To summarize, it suffices to bound theprobability Pr[Y n q ] where Y is a NB q, variable. We applythesecond point of fact Fact 3.3 , which says that this probability isequal to the probability Pr[Z q ] whereZ is a binomial randomvariable with n q + q trials and success probability 1 e = 1 . Wecanapply the Hoeffding bound for binomial variables and the factthat q = n and = o( n) (which follows
from our hypothesis that = 2o( n ) / log n ) to conclude that,for sufficiently large n:
Pr[Z q ] e2((1 )( n q )q )2 / (n q + q) e1.9(1 )
2 n (5.12)
Releasing the histogram leaks information Recall that Mdiscretizes the input into q intervals,samples H,,q , computes theperturbed histogram h = h(t) + + 1, and outputs the median pointofh .
We consider a slight modication of this mechanism: in additionto outputting the facility location, italso outputs the perturbedhistogram h. Call this modied mechanism M , and notice that MremainsPTE: privacy holds because the perturbed histogram is (2,)-differentially private, while truthfulness andefficiency remain(with respect just to the game value, before taking into accountthe information cost)because the facility location output is thesame as what M would have output. As mentioned in theintroduction,we believe this represents a common practice: the database curatorgathers the data usingone particular incentive for the individuals,but in addition to the outcome of the game, he publishessomeauxiliary information about the individuals types that may beuseful in the future for some other goal notnecessarily related tothe incentives used for the original database.
Theorem 5.6. , > 0, suppose M is run with (2, )-differentialprivacy. Then there exists such that for any IC
M satisfying Assumption 5.1 , for all inputs t Qn and all i [n],IC
M (Id , t , i ) = ( ).
Proof. M outputs a histogram perturbed by H,,q . Given anydatabase t, construct the histogramh(t). The following Lemma 5.7says that for the setting = Pr[ > ] , for any player i, thereexistst = t i and B such that < log
Pr[ M (t) B ]Pr[ M (ti , t ) B ]
Theorem 5.6 then follows since Assumption 5.1 states that theinformation cost is at least the RHS (up toconstant factors).
Lemma 5.7. Fix any q a positive integer, h
Z q , i
[q ]. Let ek denote the kth standard basis vector.
Suppose is sampled according to the distribution H,,q , wheresatises Pr Gq [ > ] = . Then for all j [q ], j = i, there existsB Z q such that:
logPr[h + ei + B ]
Pr[ h + ej + B ] >
17
8/12/2019 Is Privacy Compatible with Truthfulness?
18/31
Proof. Let B = {h | hi > h i}. Letting = e , we calculatethat:Pr
H,,q[h + ei + B ] = Pr H,,q [ i 0] (5.13)
= Pr Gq
[ > ] + Pr i G
[ i 0] (5.14)
= + 11+
j =0 j (5.15)
> + 11+ e
j =1
j (5.16)
Above, Equation 5.14 holds because by the denition of H,,q (seeSection 3), i 0 can occur one of twoways: either we sampled Gq andgot > so we set = 0 , or else we sampled Gq and got i 0 and weset = . Similarly, we can deduce that:
Pr H,,q
[h + ej + B ] = Pr H,,q [ i 1] e
Combining Theorem 5.3 and Theorem 5.6 , we conclude that thefollowing gives a deviation showing thatM is not truthful when oneuses the tradeoff utility of Equation 5.2 (for reasonable settingsof i ).
Corollary 5.8 (Formalization of Theorem 2.5 ). Fix > 0 and =2o( n/ log n ) , and let M be the (2, )-differentially privatemechanism described above. There exists such that the followingholds for any IC
M
satisfying Assumption 5.1 up to approximation: if there exists aplayer i such that i = (e(1e ) 2 n ).
Let 0 be the strategy that always outputs 0. Then, there existsi [n], ti [0, 1]n 1 such that for all t i [0, 1], t = ( ti , t i )satises u i (Id , t ) < u i (0 , t ).Proof. Fix i such that i =(e(1 )
2 n ). Let ti be the input guaranteed to exist by Theorem 5.3 .Usingthe denition of u i (Equation 5.2 ) and applying Theorem 5.3 ,we have that for all t i [0, 1]:
u i (Id , t ) < E (s,h ) M ( t i ,0) [v(t i , s )] + e(1e ) 2n i
< E (s,h ) M ( t i ,0) [v(t i , s )] i IC M (0 , t , i )= u i(0 , t )
where we used the fact that e(1e ) 2 n i < 0 = IC M (0 , t ,i ) (using Assumption 5.1 ).This proves that, under the hypothesesof Corollary 5.8 , not only is there ti such that player iwouldprefer not to tell the truth on some possible values of ti(which we may view as weakly untruthful), but
there is ti such that player i would always prefer to lie abouthis input for all values of t i (which we mayview as stronglyuntruthful).
5.2 Releasing synopsesSynopsis generators give a summary of thedatabase that is accurate with respect to a specic set ofcountqueries. Let C be a class of predicates on Q, i.e. functionsmapping Q {0, 1}. For F C, t Qn , wedene F (t) = 1n ni=1 F (t i).
18
8/12/2019 Is Privacy Compatible with Truthfulness?
19/31
Denition 5.9. M is a (, )-synopsis generator on n-player inputswith respect to a class C if there is areal-valued function P (s, F) such that, for all t Qn , Pr ( s,p )M (t ) [maxF C|F (t) P (s, F)| ] 1 .Blum et al. [ 3] showed that, if n = O( d log |Q | 3 )where d denotes the VC-dimension of C, then there exists
M that is a (, )-synopsis generator with respect to C and also-differentially private (subsequent work[13, 21] improved theparameters).5.2.1 Synopsis generators reveal information
Intuitively, it makes sense that if the synopsis must beaccurate for a very rich class of predicates, then itmust also bethat the synopsis reveals a lot of information about the database.This is what we formalizenext, by using the VC-dimension as aquantication of the richness of the class of predicates.
Denition 5.10. The VC-dimension of a class of predicates C isthe largest d such that there exist X ={t1 , . . . , t d} Q and D =2 d functions F 1 , . . . , F D such that the F i classify X in allpossible ways, i.e. forall b1 , . . . , bd {0, 1}, there exists j Dsuch that F j (t i ) = bi . We say that X is the shattering set forC, orthat C shatters X .Theorem 5.11. Fix any (0, 15 ), (0, 1).Suppose M is a mechanism that is a (, )-synopsis generator onn-player inputs with respect to
C, which has VC dimension d. Suppose that IC M satisesAssumption 5.1 .
Then for all t Qn , there exists t Qn and i [n] such that t, tdiffer in at most 4n entries and such that IC M (Id , t , i) min((dn ), (1)) .The intuition is the following: dene the ball of radiusinduced by t in the outcome space, B (t) =
{s S | P (s) C (t) }. We use a combinatorial design to constructa set of databases T Qnof size |T | 2( d ) where d = min( d,n ),such that each t T differ from t in at most 4n coordinates,and B (t) B (t ) = for all t, t T . By the pigeon-hole principle, thereexists t T , such that
Pr[M (t) B (t)] 2( d ) . Since Pr[M (t ) B (t )] 1 because M isa (, )-synopsis generator, oneof the hybrid databases between t, tmust exhibit a large jump in the probability of giving an outcomein
B (t ), and this gives a large information cost.This proof isrelated to the packing arguments found in [ 22, 20, 6]; however, itis incomparable, as it gives
quantitatively weaker bounds but it gives the additionalproperty that, given any database, we can producea nearby databasethat leaks a large amount of information. This last property wasnot present in previouslower bounds and is essential in thefollowing applications.
of Theorem 5.11 . By the denition of VC dimension, there existsa shattering set of size d. To simplifynotation, let us name theshattering set [d]. The denition of VC dimension implies that forevery X [d],there exists F X C such that F X (t) = 1 if t X and F X(t) = 0 if t [d] \ X . F X can behave arbitrarilyoutside [d].
Let P (s) = ( P (s, F ))F C be the vector containing allestimates of counts. Let C(t) = ( F (t))F C. LetB (t) = {s S | P(s) C(t) } be the -ball induced by t in the output space of themechanism.Lemma 5.12. There exists an absolute constant K > 0such that for any 1/ 5 > > 0, and for all t Qn ,there existsa set T Qn satisfying:
1. |T | 2d /K where d = min( d, 12n ).
2. For all t T , there are exactly 4n coordinates i such that ti= t i .3. For all t, t T , it holds that B (t) B (t) = .We rstassume the lemma is true to prove the theorem. Let T be a set asguaranteed by Lemma 5.12 .
By the rst and third properties, there exists t T such thatPr[M(t) B (t )] 2d
/K (5.17)
Fix such a t .
19
8/12/2019 Is Privacy Compatible with Truthfulness?
20/31
Let Z denote the set of 4n coordinates on which t and t differ.Now consider the hybrids t(0) , . . . , t (4 n )where t ( i )agrees with t on the rst i coordinates in Z , and agrees with t onthe last 4n i coordinates inZ (and it agrees with both on thecoordinates outsize Z ). Clearly t (0) = t and t (4 n ) = t.
Let wt (i) = log Pr[M (t ( i ) ) B (t)]. We know that wt (0) d/Kby Equation 5.17 , and we knowthat wt (4n ) log 11 O(1) because Mis a (, )-synopsis generator, t = t(4 n ) , and we assume that
is constant. Therefore we have
d K O(1) wt (0) wt (4n ) =
4n
i =1
wt (i 1) wt (i)By an averaging argument, there must exist i suchthat
wt (i 1) wt (i) 14n ( d
K O(1)) = ( d
n ) = min(( dn ), (1))
Furthermore, by the denition of wt and Assumption 5.1 about theinformation cost IC M , it therefore holdsthat IC M (Id , t (i ) ,j i ) (wt (i 1) wt (i)) , where j i on the LHS equals the ithelement of Z and is the onlycoordinate that differs between t ( i ), t ( i1) . Therefore, we deduce that IC M (Id , t ( i ) , j i )min(( dn ), (1)) .
of Lemma 5.12 . Let h(t) be the histogram of t. Let us assumethat h1 h2 . . . hd (for notationalconvenience and without loss ofgenerality, since the names of the coordinates are immaterial andone could just rearrange them to satisfy this property).
Let d d be the largest integer such that d i =1 hi (1 4 )n.Either d = d, or else d < d and wecan deduce that:
n d
i=1
h i =d +1
i =1
h i +d
i = d +2
h i (5.18)
> (1 4 )n + ( d d 1)(1 4 )n
d + 1 (5.19)
d (1 4 )d (5.20)Here we used the denition of d and the fact thatthe h i are non-decreasing, meaning that hi for d i >d + 1 mustsatisfy h i
(1
4 )n/ (d + 1) .
Set d = min( d, 12n ). We rst construct U which is acombinatorial design over [d]. Namely, |U | 2( d ) and each pair X,Y U have small intersection.1. Initially U = , so pick an arbitraryX [d] of size d/ 3. Add X to U .2. If there exists X [d] such that|X Y | < d / 6 for all Y U , then add X to U , otherwise haltandoutput U .
It is clear from the construction that, for all X, Y U , itholds that |X Y | < d / 6. We show that U isexponentiallylarge:|U | e2/ 18
2 d / 3 (5.21)This is a consequence of the Hoeffding inequality.Suppose we have already added i elements to U . We showthat if i< e 2/ 18
2 d / 3 then there exists another subset that can be added. Weuse the probabilistic method
by showing that the probability that a random subset X of [d]with size d/ 3 does not satisfy the desiredproperty is strictlysmaller than 1.
PrX (
[d ]d / 3)
[Y U, |X Y | d/ 6] < e 2/ 182 (d / 3) Pr[ |X Y | d/ 6] <1
where we use the Hoeffding inequality (the version for samplingwithout replacement) in the nal inequality(i.e. sampling d/ 3elements without replacement from among [d], where the elements inY are marked 1and the rest are marked 0).
Let K be the smallest constant so that |U | 2d /K . We nowconstruct T using U . Let X U , thendene tX Qn as follows. Let X 1, . . . , X d / 3 [d] be the elements of X , say sorted inincreasing order.
20
8/12/2019 Is Privacy Compatible with Truthfulness?
21/31
1. Initialize i = 1 and j = 1 . (i will take value between 1, .. . , n and j between 1, . . . d/ 3).
2. Initialize tX = t.
3. Do the following while j d/ 3:(a) Take the rst 12n/dindividuals after and including the ith individual in tX whosevalues lie in
Q \ [d], and change their values to X j .(b) Set i to be theindividual after the last individual modied in the previous step,and increment j .Observe two facts: rst, we never run out ofindividuals to modify, since our choice of d d andEquation 5.20ensure that the number of players with value in Q \ [d] is at least4n . Second, 12nd 1 soin each iteration we modify at least oneplayer.
We prove that T = {tX | X U } satises the properties of thelemma. First, it is clear that if X = Y then tX = tY , andtherefore |T | 2d/K . The second property holds because we modify12n/d individualsin each iteration, and there are d/ 3iterations.To prove the third property, let tX , tY T be twodistinct elements of T . Let F X C be a functionsatisfying F X (x)= 1 if x X and F X (x) = 0 if x [d] \ X (and F X can behavearbitrarily outside [d]).Such F X exists because X [d] [d] and [d]is shattered by C. Let Z [n] be the rst 4n coordinates of t takingvalue in Q \ [d]. Observe that t and tX are identical on allcoordinates outside of Z . It holds that:
|F X (tX ) F X (tY )| = 1n
n
i=1
(F X (( tX ) i ) F X (( tY )i )) (5.22)
= 1n
iZ
F X (( tX )i ) iZ
F X (( tY )i ) (5.23)
= 1n | |Z | 12nd |X Y | | (5.24)> 1n (4n 12nd d
6 ) (5.25)= 2 (5.26)
Suppose now for the sake of contradiction that s B (tX )B (tY ).This means that C (tX )P (s) and
C (tY )
P (s)
. But by the triangle inequality, this would imply that:
2 < |F X (tX ) F X (tY )| |F X (tX ) P (s)|+ |P (s) F X (tY)| 2
which is a contradiction, and therefore B (tX ) B (tY ) = .5.2.2Non-reactive mechanisms
As in Section 5.1 , we would like to use Theorem 5.11 to inferthat if the database owner publishes a synopsisrather than just theoutcome of the game (in the hopes that the synopsis may be usefulfor other purposes),then individuals may prefer to lie becausetheir gain in information cost outweighs their loss in valuederivedfrom the outcome. Intuitively this happens if by deviating,a player cannot lose too much value. We nowformalize this.
Denition 5.13. M is (, )-non-reactive if there exists t Qn suchthat for all t that differ from t in atmost n coordinates, forevery i [n] and t Q, it holds that E [v(ti , M (t))] E [v(ti , M ((t )i , t ))] + .The following is an easy corollary of Theorem 5.11.
Corollary 5.14. Fix any (0, 15 ), (0, 1). If M is a (,)-synopsis generator for C of VC-dimension d. Let = min i i andsuppose that M is also (o( d
n ), 4 )-non-reactive, where d = min( d,n ). Then there exists tQn , i [n] and a strategy (t) that is independent of t such that ui (Id , t ) < u i (, t ).
21
8/12/2019 Is Privacy Compatible with Truthfulness?
22/31
Proof. By the denition of non-reactive, let t Qn be such thatfor all t differing from t in at most 4ncoordinates, for all i [n],t Q, it holds thatE [v(t i , M (t))] E [v(t i , M (( t )i , t ))] +o( dn )
By Theorem 5.11 , one of these t satises IC (Id , t , i) ( dn ).Therefore, if we let be the strategy thatoutputs an arbitraryconstant value in x Q (and therefore by Assumption 5.1 it holdsthat IC M (, t , i ) = 0 ),we may write:
u i (Id , t ) E [v(t i , M (t))] IC (Id , t , i )< E [v(t i ,M (( t )i , x))] + o( dn ) ( dn )< E [v(t i , M (( t )i , x))]IC (, t , i)= ui (, t )
Therefore, M is not truthful.
In particular, Corollary 5.14 holds even if M is differentiallyprivate as long as the VC-dimension of
C is large. Blum et al. [3] prove that it is possible for M tobe -differentially private and still be a(, )-synopsis generatorfor a class of predicates with VC-dimension d = (
3 n
log |Q | log(1 / )). If in addition
|Q| = poly( n) and = (1 / log |Q|) (which by Remark 5.2constitutes a realistic setting of parameters), andM is (o(1/ logn), 4 )-non-reactive, then M cannot be truthful.5.2.3 The1-facility location game on arbitrary bounded metric spaces
In fact, mechanisms may be quite non-reactive becauseintuitively the inuence of a single individual onthe outcome maydiminish rapidly as there are more players. As a concrete exampleof such a class of mechanisms, we show that any efficient mechanismfor a 1-facility location game over an arbitrary boundedmetricspace must be non-reactive. Let (Q, d ) be a general bounded metricspace, normalized so that
maxt,t Q
d (t, t ) 1
The general 1-facility location game is dened similarly toLINE-1-FAC
, except that the type space is Qrather than just [0, 1].
Theorem 5.15. Suppose M is a -efficient mechanism for the1-facility location game over a bounded metric space (Q, d ). Thenfor any (0, 12 ), it holds that M is ( 2(12 )n 2 ,)-non-reactive.
Therefore, we can construct the following deviation showing thatM cannot be truthful if it is efficientfor the 1-facility locationon a metric space game and is also a good synopsis generator.
Corollary 5.16. Let (0, 110 ), (0, 1). Suppose M is a -efficientmechanism for the 1-facility location game on a bounded metricspace, and also M is a (, )-synopsis generator for C ofVC-dimension d. Suppose that IC M satises Assumption 5.1 .Let = mini i . If = o(d ) where d = min( d,n ), then there exists t Qn , i[n] and a strategy (t)that is independent of t such that u i (Id ,t ) < u i (, t ).For example, the above theorem applies for thechoice of parameters d = (
3 nlog |Q | log(1 / ) ), = n
0.99 ,
|Q| = poly( n), and = (1 / log |Q|).Corollary 5.16 applies to amuch broader setting than Corollary 5.8 in terms of the gamesconsid-ered. However, even when applied to LINE-1-FAC , Corollary5.16 gives an incomparable result. WhereasCorollary 5.8 applies tothe specic mechanism ( Algorithm 4.10 ) studied in this paper,Theorem 5.15 holdsfor any efficient mechanism. On the other hand,Corollary 5.8 is better quantitatively, and also applies whenonly ahistogram of the discretization of the player types is released,which may contain less informationthan a synopsis. (One canreconstruct the histogram from a synopsis if C is sufficientlyrich, see for exampleTheorem 4.1 of [12].)
22
8/12/2019 Is Privacy Compatible with Truthfulness?
23/31
of Theorem 5.15 . Let t Qn be the vector where all coordinateshave value x for an arbitrary x Q. Fixt Qn different from t in atmost m < n/ 2 coordinates, i.e. m coordinates of t are not equalto x. Supposefor convenience of notation that these are the rstcoordinates t1 , . . . , t m . We know that, by picking s = x, itispossible to achieve welfare w(t , x)
mi=1
d (x, t i ), and therefore by the -efficiency of themechanism,it holds that
w(t, x)
E s
M (t ) [w(t , s )] (5.27)
m
i=1
d (x, t i ) + E sM (t ) (n m) d (s, x ) +m
i=1
d (s, t i ) (5.28)
= E sM (t ) [(n 2m) d (s, x )] + E sM (t ) m
i=1
(d (s, t i ) + d (s, x ) d (x, t i )) (5.29)
E sM (t ) [(n 2m) d (s, x )] (triangle inequality) (5.30)
E sM (t ) [d (s, x )]
n 2m (5.31)
For any y Q, we may write the following, using the triangleinequality and Equation 5.31 :E sM (t ) [v(y, s )] = E sM (t ) [d(y, s )] (5.32)
E sM (t ) [d (y, x ) d (s, x )] (5.33)= d (y, x ) + E sM (t ) [d(s, x )] (5.34) v(y, x ) + n 2m (5.35)
E sM (t ) [v(y, s )] = E sM (t ) [d (y, s )] (5.36) E sM (t ) [d(y, x ) + d (s, x )] (5.37)= d (y, x ) E sM (t ) [d (s, x )] (5.38)v(y, x ) n 2m (5.39)
If t differs from t in at most n coordinates, then for every i,it holds that ((t)i , t ) differs from t in atmost n +1coordinates. Therefore we can apply Equation 5.35 and Equation 5.39for m = n +1 to obtain:
E [v(ti , M (t ))]
v(ti , x) + (12 )n 2 E [v(ti , M (( t)i , t ))] + 2(12 )n 2
6 Conclusions
In this paper we argued that the study of privacy must becoupled with the study of the incentives thatmotivate people toreveal private data. To study this question, we introduced a modelcombining differentialprivacy with truthfulness and efficiency. Weconstructed a general transformation that takes a truthfulandefficienct mechanism and builds a PTE mechanism. We showed thatwhen privacy is given an explicitnumerical cost, even PTEmechanisms (which at rst may seem to give us everything we want)are notnecessarily sufficient. Our work has already spurred severalfollow-up works [4, 30, 23], and there are manyinterestingremaining open questions. For example, is it always possible foreach problem to create a PTEmechanism that has as good efficiencyas a mechanism that is not private? Another question, moreempirical,is to explore what are good models for information costfunctions and how we may be able to use a betterunderstanding ofthese functions to achieve better parameters.
7 Acknowledgments
Part of this work was done while the author was visitingMicrosoft Research Asia. The author wouldlike to thank Pinyan Luand Yajun Wang for their collaboration at the initial stages ofthis work. The
23
8/12/2019 Is Privacy Compatible with Truthfulness?
24/31
author also thanks Salil Vadhan, Aaron Roth, and Yiling Chen foruseful discussions, and the anonymousreviewers for their comments.The author was supported by the French ANR Des program undercontractANR-08-EMER-012.
References
[1] Noga Alon, Michal Feldman, Ariel D. Procaccia, and MosheTennenholtz. Strategyproof approximationof the minimax on networks.Mathematics of Operations Research , 35(3):513526, 2010.
[2] Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale,Frank Mcsherry, and Kunal Talwar.Privacy, accuracy, and consistencytoo: a holistic solution to contingency table release. In Proc. of26th PODS , pages 273282, 2007.
[3] Avrim Blum, Katrina Ligett, and Aaron Roth. A learningtheory approach to non-interactive databaseprivacy. In Proc. 40thSTOC , pages 609618, 2008.
[4] Yiling Chen, Stephen Chong, Ian A. Kash, Tal Moran, andSalil P. Vadhan. Truthful mechanisms foragents that value privacy.CoRR , abs/1111.5472, 2011.
[5] T. Dalenius. Towards a methodology for statisticaldisclosure control. Statistik Tidskrift , 5:429444,1977.
[6] Anindya De. Lower bounds in differential privacy. In TCC ,pages 321338, 2012.
[7] Irit Dinur and Kobbi Nissim. Revealing information whilepreserving privacy. In In PODS , pages202210. ACM Press, 2003.
[8] Cynthia Dwork. Differential privacy. In In Proc. ICALP ,pages 112. Springer, 2006.
[9] Cynthia Dwork. Differential privacy: A survey of results. InManindra Agrawal, Dingzhu Du, ZhenhuaDuan, and Angsheng Li,editors, Theory and Applications of Models of Computation , volume4978 of Lecture Notes in Computer Science , pages 119. SpringerBerlin / Heidelberg, 2008.
[10] Cynthia Dwork, Krishnaram Kenthapadi, Frank Mcsherry, andMoni Naor. Our data, ourselves: Privacy
via distributed noise generation. In In EUROCRYPT , pages486503. Springer, 2006.[11] Cynthia Dwork, Frank Mcsherry, KobbiNissim, and Adam Smith. Calibrating noise to sensitivity in
private data analysis. In In Proc. of the 3rd TCC , pages265284. Springer, 2006.
[12] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum,and Salil Vadhan. On the complexityof differentially private datarelease: Efficient algorithms and hardness results. In Proc. 41stSTOC ,STOC 09, pages 381390. ACM, 2009.
[13] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan.Boosting and differential privacy. In FOCS ,pages 5160, 2010.
[14] Joan Feigenbaum, Aaron D. Jaggard, and Michael Schapira.Approximate privacy: foundations andquantication (extendedabstract). In Proc. 11th EC , EC 10, pages 167178, New York, NY,USA,
2010. ACM.[15] Dan Feldman, Amos Fiat, Haim Kaplan, and KobbiNissim. Private coresets. In Proc. 41st STOC ,
STOC 09, pages 361370, New York, NY, USA, 2009. ACM.
[16] I. Fellegi. On the question of statistical condentiality.J. of the Amer. Stat. Assoc. , 67:718, 1972.
[17] Lisa K. Fleischer and Yu-Han Lyu. Approximately optimalauctions for selling privacy when costs arecorrelated with data. InProceedings of the 13th ACM Conference on Electronic Commerce , EC12,pages 568585, New York, NY, USA, 2012. ACM.
24
8/12/2019 Is Privacy Compatible with Truthfulness?
25/31
[18] Arpita Ghosh and Aaron Roth. Selling privacy at auction. InProc. 12th EC , EC 11, pages 199208,New York, NY, USA, 2011. ACM.ISBN 978-1-4503-0261-6.
[19] Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan.Universally utility-maximizing privacymechanisms. In Proc. 41stSTOC , STOC 09, pages 351360. ACM, 2009.
[20] Moritz Hardt. A Study of Privacy and Fairness in SensitiveData Analysis . PhD thesis, PrincetonUniversity, 2011.
[21] Moritz Hardt and Guy N. Rothblum. A multiplicative weightsmechanism for privacy-preserving dataanalysis. In Proc. 51st FOCS ,pages 6170, Washington, DC, USA, 2010. IEEE Computer Society.doi:10.1109/FOCS.2010.85.
[22] Moritz Hardt and Kunal Talwar. On the geometry ofdifferential privacy. In Proc. 42nd STOC , pages705714, New York,NY, USA, 2010. ACM. ISBN 978-1-4503-0050-6. doi:10.1145/1806689.1806786.
[23] Zhiyi Huang and Sampath Kannan. The exponential mechanismfor social welfare: Private, truthful, andnearly optimal. In Proc.FOCS 12 , 2012. To appear. Available athttp://arxiv.org/abs/1204.1255 .
[24] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim,Sofya Raskhodnikova, and Adam Smith.What can we learn privately? InProc. 49th FOCS , pages 531540, Washington, DC, USA, 2008.IEEE.
[25] Katrina Ligett and Aaron Roth. Take it or leave it: Runninga survey when privacy comes at a cost.CoRR , abs/1202.4741,2012.
[26] Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu.Asymptotically optimal strategy-proof mechanisms for two-facilitygames. In Proceedings of the 11th ACM conference on Electroniccommerce ,EC 10, pages 315324. ACM, 2010.
[27] Frank McSherry and Kunal Talwar. Mechanism design viadifferential privacy. In Proceedings of the 48th Annual Symposiumon Foundations of Computer Science . Citeseer, 2007.
[28] H. Moulin. On strategy-proofness and single peakedness.Public Choice , 35:437455, 1980.
[29] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smoothsensitivity and sampling in private data
analysis. In Proc. 39th STOC , pages 7584, 2007.[30] KobbiNissim, Claudio Orlandi, and Rann Smorodinsky. Privacy-awaremechanism design. In Proceed-
ings of the 13th ACM Conference on Electronic Commerce , EC 12,pages 774789, New York, NY,USA, 2012. ACM.
[31] Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz.Approximately optimal mechanism de-sign via differential privacy.In Proceedings of the 3rd Innovations in Theoretical ComputerScience Conference , ITCS 12, pages 203213, New York, NY, USA,2012. ACM. ISBN 978-1-4503-1115-1.
[32] Aaron Roth and Grant Schoenebeck. Conducting truthfulsurveys, cheaply. In Proceedings of the 13th ACM Conference onElectronic Commerce , EC 12, pages 826843, New York, NY, USA, 2012.ACM.
[33] J. Schummer and R. V. Vohra. Mechanism design withoutmoney. In N. Nisan, T. Roughgarden,E. Tardos, and V. Vazirani,editors, Algorithmic Game Theory , chapter 10, pages 243266.CambridgeUniversity Press, 2007.
[34] M. R. Spiegel. Theory and Problems of Probability andStatistics . McGraw-Hill, 1992.
[35] David Xiao. Is privacy compatible with truthfulness?Cryptology ePrint Archive, Report 2011/005,2011.http://eprint.iacr.org/ .
25
http://arxiv.org/abs/1204.1255http://arxiv.org/abs/1204.1255http://eprint.iacr.org/http://eprint.iacr.org/http://arxiv.org/abs/1204.1255
8/12/2019 Is Privacy Compatible with Truthfulness?
26/31
Input: histogram h with m coordinates. Let n = mi =1 hi .
1. Select a random permutation : [n] [n].2. For i = 1 to n , sett ( i ) = min { j |
jk =1 hk i}. Let t denote this setting of t1 , . . . , tn .
3. Run M (t1 , . . . , tn ).Algorithm A.1. Converting anarbitrary mechanism to one looking only at histogram.
A Mechanisms only need to consider the histogram
Suppose that G is an anonymous game, i.e. the global utilityfunction is symmetric and all players have thesame private utilityfunctions. Suppose M is an arbitrary mechanism, possibly looking atindividual types.We transform it into a mechanism M that considersonly the histogram according to Algorithm A.1 .
M is efficient because for all it holds that the histogram of tis exactly h. Since the outcome of M isefficient on t , thereforethe outcome is efficient for h .
To see that M is trut

Is Privacy Compatible with Truthfulness? - [PDF Document] (2024)

FAQs

What is post-processing proof of differential privacy? ›

References