Privacy Auctions for Inner Product Disclosures

Details Privacy Auctions for Inner Product Disclosures Privacy Auctions for Inner Product Disclosures

2011-11-11

arxiv.org/abs/1111.2885v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study a market for private data in which a data analyst wishes to publicly release a statistic computed over a database of private information. The statistic we focus on is the inner product of the database entries with a publicly known weight vector. Individuals that own the data incur a cost for their loss of privacy quantified in terms of the differential-privacy guarantee given by the analyst at the time of the release. To properly incentivize individuals, the analyst must compensate them for the cost they incur. This gives rise to a \emph{privacy auction}, in which the analyst decides how much privacy to purchase from each individual, in order to \emph{cheaply} obtain an accurate estimate of the inner product. The individuals are profit-maximizing, so we would like to design a truthful auction. First, we formalize the trade-off between privacy and accuracy in this setting; we show that obtaining an accurate estimate of the inner product necessitates providing poor privacy guarantees to individuals that have a significant effect on the estimate. We show that a simple, natural class of estimates achieves an order-optimal trade-off between privacy and accuracy, and, consequently, it suffices to focus on auction mechanisms that output such estimates. These estimates guarantee privacy to individuals in proportion to their effect on the accuracy of the estimate. We use this observation to design a truthful, individually rational, proportional-purchase mechanism under the constraint that the analyst has a fixed budget. We show that our mechanism is 5-approximate in terms of accuracy compared to the optimal mechanism, and that no truthful mechanism can achieve a $2-\ve$ approximation, for any $\ve > 0$.

Affiliated with

Also associated with

No associations

Rating

Privacy Auctions for Inner Product Disclosures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Privacy Auctions for Inner Product Disclosures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Privacy Auctions for Inner Product Disclosures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2851