Selling Privacy at Auction
Arpita Ghosh, Aaron Roth
[arXiv]
We initiate the study of markets for private data, though 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.
On the other hand, 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 auctions can naturally be viewed and
optimally solved as variants of multi-unit procurement auctions. Based
on this result, we derive auctions for two natural settings which are
optimal up to small constant factors:
- In the setting in which 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.
- In the setting in which 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
analysts 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 individuals 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.