Selling privacy at auction

By Arpita Ghosh, Aaron Roth. 2010

425 citations recorded by the source corpus.

We initiate the study of markets for private data, through the lens of differential privacy. Although the purchase and sale of private data has already begun on a large scale, a theory of privacy as a commodity is missing. In this paper, we propose to build such a theory. Specifically, we consider a setting in which a data analyst wishes to buy information from a population from which he can estimate some statistic. The analyst wishes to obtain an accurate estimate cheaply, while the owners of the private data experience some cost for their loss of privacy, and must be compensated for this loss. Agents are selfish, and wish to maximize their profit, so our goal is to design truthful mechanisms. Our main result is that such problems can naturally be viewed and optimally solved as variants of multi-unit procurement auctions. Based on this result, we derive auctions which are optimal up to small constant factors for two natural settings: When the data analyst has a fixed accuracy goal, we show that an application of the classic Vickrey auction achieves the analyst's accuracy goal while minimizing his total payment. When the data analyst has a fixed budget, we give a mechanism which maximizes the accuracy of the resulting estimate while guaranteeing that the resulting sum payments do not exceed the analyst's budget. In both cases, our comparison class is the set of envy-free mechanisms, which correspond to the natural class of fixed-price mechanisms in our setting. In both of these results, we ignore the privacy cost due to possible correlations between an individual's private data and his valuation for privacy itself. We then show that generically, no individually rational mechanism can compensate individuals for the privacy loss incurred due to their reported valuations for privacy. This is nevertheless an important issue, and modeling it correctly is one of the many exciting directions for future work.

Subfields: Artificial Intelligence, Computer Science Applications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Management Science and Operations Research

Citations in the corpus

Differential Privacy: An Economic Method for Choosing Epsilon (2014, background): “While there has been work on using auctions to discover costs related to privacy [11], [18], [2], [5], [24],”
Towards Statistical Queries over Distributed Private User Data (2012, methodology): “One way to leverage the privacy deficit would be to charge analysts accordingly, as suggested in [24].”
A Marketplace for Data: An Algorithmic Solution (2018, methodology): “revenue gain are modeled [16, 22]; (iii) there is a feedback eect between data sellers and data buyers and incentives for individuals to provide data when they know the information will be used to adjust prices for goods they consume in the future are modeled [9] (e.”
Too Much Data: Prices and Inefficiencies in Data Markets (2019, neutral): “…[2007], Horner and Skrzypacz [2016], Bergemann et al. [2018], and Eliaz et al. [2019] consider either static or dynamic mechanisms for selling data, Ghosh and Roth [2015] uses differential privacy framework of Dwork et al. [2014] and study mechanism design with privacy constraints, and Admati and…”
The Algorithmic Foundations of Differential Privacy (2014, background): “3–4 (2013) 1–277 c© 2014 C. Dwork and A. Roth DOI: 10.1561/0400000042 The Algorithmic Foundations of Differential Privacy Cynthia Dwork Microsoft Research, USA dwork@microsoft.com Aaron Roth University of Pennsylvania, USA aaroth@gmail.com Contents Preface 2”
GUPT: privacy preserving data analysis made easy (2012, positive): “Alternative approaches such as auctioning of privacy budget [9] can also be used.”
The Long-Standing Privacy Debate: Mobile Websites vs Mobile Apps (2017, background): “To deliver effective advertisements to the enduser, third party ad-networks request from app developers to embed in their apps external third party ad-libraries, also known as in-app libraries [13].”
Provably Confidential Language Modelling (2022, background): “Moreover, it is more informative to define ε as a function of each specific x, which is different from DP (it resembles personalized DP (Ghosh and Roth, 2015)).”