Source-linked AI summary
Selling Privacy at Auction
Arpita Ghosh, Aaron Roth
TL;DR
The paper addresses the missing theory for markets in private data, where analysts seek accurate estimates and individuals require compensation for privacy loss. It models privacy through differential privacy and reduces auction design to multi-unit procurement, yielding optimal mechanisms for fixed-accuracy and fixed-budget settings while identifying an impossibility under correlated valuations.
Problem
Markets for private data are already developing, but they lack a theoretical foundation for compensating data owners while obtaining accurate estimates cheaply.
Method
The paper models individuals’ private bits and privacy-cost functions, and uses differential privacy and truthful multi-unit procurement auctions to study analyst payment and accuracy objectives.
Results
The paper gives optimal envy-free auction mechanisms for fixed accuracy and fixed budget objectives, including VCG for minimizing payment and a truthful fixed-price mechanism for maximizing accuracy.
Takeaways & Limitations
Private-data auctions can be analyzed as procurement problems, providing a framework for choosing the smallest affordable privacy level while meeting an analyst’s objective.
Takeaways & Limitations
Generically, no direct-revelation mechanism can compensate individuals for privacy loss caused by unknown correlations between their private data and privacy costs.
Abstract
from arXiv · showhide
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: 1. 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. 2. 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.
1 Introduction
The paper develops a theoretical framework for markets in private data, using differential privacy to model privacy as a commodity and procurement auctions to design truthful mechanisms.
- Motivation: Markets for private information are expanding, but they lack a theoretical foundation for treating privacy as a commodity.The paper introduces a crisp model rather than a complete solution to all problems in private-data sales.
- Motivation: Differential privacy provides a precise way to define and quantify the privacy being bought and sold.Its utility-theoretic interpretation supports assigning individuals a cost for privacy loss.
- Motivation: Because analysts need representative population samples, unknown correlations between private data and privacy valuations make buying from the cheapest sellers unreliable.The paper frames auction design around obtaining representative estimates despite these complementarities.
- Model: The model has n individuals with private bits and privacy-cost functions, while an analyst estimates their aggregate and compensates them through mechanism payments.The analyst either minimizes payments for a fixed accuracy target or maximizes accuracy under a fixed budget.
- Limitations: The paper’s main model compensates for privacy loss in private bits but ignores leakage from correlations between those bits and reported privacy costs.The paper separately establishes that, generically, direct-revelation mechanisms cannot compensate for that correlated valuation privacy loss.
- Results: Private-data auctions can be reduced without loss of generality to multi-unit procurement auctions.Under a fixed accuracy goal, VCG is optimal among envy-free mechanisms; under a fixed budget, a truthful fixed-price mechanism is instance-by-instance optimal.
2 Preliminaries
The paper models private-data markets using differential privacy, with individuals compensated for privacy loss and analysts receiving noisy estimates under truthful, individually rational mechanisms.
- Model: Each individual has a verifiable private bit and a private value parameterizing the cost of privacy loss.Individuals cannot misreport their bits but may misreport their privacy valuations.
- Differential privacy: Differential privacy limits how much one individual can affect an algorithm’s output distribution and therefore limits information revealed about that individual.The paper also uses Laplacian noise as a primitive for producing differentially private outputs.
- Mechanism: A mechanism takes privacy-cost parameters and private bits, then outputs an estimate and a payment collected from the data analyst.In the insensitive-value model, reported costs determine a randomized differentially private algorithm and participant payments.
- Utilities: A participant whose data is used with ε_i-differential privacy receives utility p_i − c(v_i, ε_i).The cost function is normalized by c(v_i, 0) = 0 and is assumed continuous.
- Mechanism requirements: Individual rationality guarantees non-negative utility from truthful participation, while truthfulness prevents utility gains from misreporting privacy costs.For randomized mechanisms, individual rationality is ex post and truthfulness is evaluated in expectation over internal randomness.
- Valuing differential privacy: The paper justifies privacy costs through future-event utilities and motivates cost functions c(v_i, ε_i) = (exp(ε_i) − 1)v_i and c(v_i, ε_i) = ε_iv_i.The linear form is motivated as an approximation for small ε_i.
3 Characterizing Accurate Mechanisms
Accurate mechanisms must purchase sufficient privacy from enough individuals, independent of truthfulness requirements. Matching upper and lower bounds reduce accurate private-data mechanisms to multi-unit procurement auctions up to small constant factors.
- The lower bound quantifies a privacy–accuracy trade-off: αn/4-accuracy requires at least a 1/αn privacy loss for at least a (1−α) fraction of the population.The corresponding payment lower bound follows for individually rational mechanisms.
- An individually rational αn-accurate mechanism must pay at least the stated benchmark, though achieving it generally requires knowing all players’ cost functions.No truthful mechanism can generally match this omniscient benchmark.
- A differentially private mechanism achieves (1/2 + ln 3)α·n accuracy while selecting individuals with privacy levels matching the sufficient conditions up to constants.The construction selects a set H with positive privacy loss for members and zero privacy loss for nonmembers.
- Together, the bounds permit restricting attention to procurement auctions that buy exactly 1/αn privacy units from exactly (1−α)n individuals.This quantity suffices to run the Laplace mechanism, up to small constant factors in the error term.
- Random sampling does not evade the lower bounds because every individual with nonzero selection probability incurs positive privacy cost when the sampled algorithm has ε > 0.Sampling and other randomization procedures remain within the class covered by the lower bounds.
4 Deriving Truthful Mechanisms in the Insensitive Value Model
The paper reduces private-data auctions to multi-unit procurement auctions and develops truthful, individually rational mechanisms for fixed-budget and fixed-accuracy settings. FairQuery is optimal for accuracy under a budget among truthful, envy-free fixed-purchase mechanisms, while MinCostAuction minimizes payment for a fixed accuracy goal.
- Fixed budget: FairQuery maximizes estimate accuracy subject to budget B among truthful, individually rational, envy-free fixed-purchase mechanisms.It is instance-by-instance optimal within the stated comparison class.
- Fixed budget: FairQuery is truthful, individually rational, and never exceeds the analyst’s budget B.Its proof checks individual rationality, the budget constraint, and truthfulness through four deviation cases.
- Benchmark: Envy-free fixed-purchase mechanisms pay every selected individual the same fixed price.This fixed-price interpretation provides the benchmark used to evaluate FairQuery.
- Fixed accuracy: The VCG-based MinCostAuction truthfully obtains the target accuracy while minimizing total payment among envy-free fixed-purchase auctions.Its total payment is k · w_k+1, and no comparable auction guaranteeing k purchases can pay less.
- Reduction to procurement auctions: The analysis models privacy purchases as a multi-unit procurement auction, with accuracy determining how many equal privacy units must be bought.Each individual supplies a single privacy good, and the accuracy constraint specifies the required number of units.
5 Truthful Mechanisms in the Sensitive Value Model
The sensitive-value model asks whether an auction can protect and compensate privacy valuations that may correlate with individuals’ private data. The paper proves a generic impossibility when valuations are unbounded and nontrivial accuracy is required.
- Sensitive-value model: The sensitive-value model includes privacy leakage from correlations between individuals’ private bits and their reported privacy costs.The earlier insensitive-value analysis compensated only for privacy loss involving the private bits themselves.
- Impossibility result: If privacy valuations are arbitrarily large, no individually rational direct-revelation mechanism can protect those valuations while promising k-accuracy for any k < n/2.The impossibility applies to every nontrivial accuracy level covered by the theorem.
- Proof strategy: The proof uses linear privacy costs and differential privacy to show that individual rationality would require payments large enough to conflict with privacy protection.The argument lower-bounds total privacy loss and then applies differential privacy across database inputs.
- Impossibility result: The impossibility means the mechanism cannot charge a finite price for any input when valuations are unbounded.This is the paper’s stated conclusion for protecting and compensating reported privacy valuations.
- Workaround and limitation: Restricting valuations to a bounded range is a partial workaround, but may exclude high-valuation bidders and systematically skew the resulting estimate.The paper characterizes this workaround as unsatisfying because it reintroduces sampling bias.
6 Conclusion and Future Directions
The paper formalizes auctions for private data by reducing their design to multi-unit procurement auctions, while identifying unresolved questions about benchmarks, privacy of valuations, unverifiable data, market structure, and repeated access.
- Contributions: The paper’s main contribution is formalizing private-data auctions and reducing their design space to multi-unit procurement auctions.The conclusion presents this reduction as available without loss of generality.
- Open questions: The choice of fixed-price or envy-free mechanisms as the benchmark remains open to revision.The paper asks whether a more natural benchmark exists for these auctions.
- Open questions: No direct-revelation mechanism can generically compensate privacy loss caused by correlations between private data and reported privacy costs.The conclusion calls for restricted models that might protect and compensate valuation privacy.
- Open questions: The framework assumes users’ private bits are already known to or verifiable by a database administrator.The paper leaves open mechanisms for settings where individuals can lie about their private data.
- Open questions: Future work includes two-sided markets with multiple analysts and populations, and online mechanisms for repeated data-access requests.These extensions would address market-clearing prices and the value of marginal privacy loss over time.