We study markets for private data using differential privacy. 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. Agents are rational and we wish to design truthful mechanisms.We show that such problems can naturally be viewed and solved as variants of multi-unit procurement auctions. We derive auctions for two natural settings:
In both results, we treat each agent's cost for privacy as insensitive information. We then show that no individually rational mechanism can compensate individuals for the privacy loss incurred due to their reported valuations for privacy.