Source-linked AI summary
A Theory of Pricing Private Data
Chao Li, Daniel Yang Li, Gerome Miklau, Dan Suciu
TL;DR
Existing privacy mechanisms restrict the number and accuracy of query answers, while practical data markets often monetize personal information without directly compensating data owners. The paper develops a pricing framework for noisy queries that combines differential privacy and data-market principles, characterizes arbitrage-free prices and privacy-loss-based micro-payments, and identifies challenges surrounding private valuations and user-facing choices.
Problem
Perturbation-based privacy mechanisms have not seen wide practical deployment and impose strict limits on accurately released queries, while growing data monetization motivates direct compensation for data owners.
Method
The paper prices linear queries according to their requested noise and compensates each data owner according to the privacy loss caused by the query.
Results
The framework characterizes arbitrage-free pricing and balances buyer charges with micro-payments that compensate owners for their privacy loss.
Takeaways & Limitations
Monetizing private data gives individuals financial control over disclosure while allowing buyers to purchase queries with accuracy and price chosen together.
Takeaways & Limitations
Privacy valuations correlated with the underlying data can themselves reveal sensitive information when prices are disclosed.
Abstract
from arXiv · showhide
Personal data has value to both its owner and to institutions who would like to analyze it. Privacy mechanisms protect the owner's data while releasing to analysts noisy versions of aggregate query results. But such strict protections of individual's data have not yet found wide use in practice. Instead, Internet companies, for example, commonly provide free services in return for valuable sensitive information from users, which they exploit and sometimes sell to third parties. As the awareness of the value of the personal data increases, so has the drive to compensate the end user for her private information. The idea of monetizing private data can improve over the narrower view of hiding private data, since it empowers individuals to control their data through financial means. In this paper we propose a theoretical framework for assigning prices to noisy query answers, as a function of their accuracy, and for dividing the price amongst data owners who deserve compensation for their loss of privacy. Our framework adopts and extends key principles from both differential privacy and query pricing in data markets. We identify essential properties of the price function and micro-payments, and characterize valid solutions.
1 Introduction
The paper frames private-data pricing as a financial alternative to strict perturbation-based privacy mechanisms, enabling compensation tied to disclosure and query accuracy. It proposes a framework connecting differential privacy, data markets, arbitrage-free pricing, and personalized privacy-loss payments.
- Motivation: Perturbation-based privacy mechanisms impose a strict privacy budget because repeated queries can reduce noise and eventually reveal private data.The paper notes that such mechanisms have rarely been deployed in practice.
- Framework: The framework lets buyers trade accuracy for price: more perturbation lowers cost, while unperturbed answers require compensating contributors for substantial privacy loss.The relationship between accuracy and cost depends on the query and the preferences of contributing data owners.
- Framework: The paper formalizes arbitrage for noisy queries, preventing buyers from reconstructing a more accurate answer more cheaply through repeated lower-accuracy purchases.Its motivating example reduces variance from 10 to 1 by buying the noisy query ten times and averaging the results.
- Framework: It also relates personalized privacy loss to micro-payments, allowing data owners to value their losses differently rather than accepting one universal privacy bound.The framework permits high payments for low-variance or exact answers when those queries impose greater privacy loss.
- Motivation: Pricing private data shifts the market maker’s task from guarding query volume to ensuring every disclosure properly compensates contributing individuals.If queries can reveal most of the database, their price must approach the total cost of the database.
- Open challenges: The paper identifies honest privacy valuation and incentives for data owners as future challenges for pricing private data.These challenges concern disclosures arising from privacy valuations themselves and truthful reporting of those valuations.
2 Basic Concepts
The framework lets buyers purchase noisy answers to linear aggregate queries, with prices tied to tolerated variance and payments distributed to data owners for privacy loss. It requires prices to cover owner compensation while preventing indirect information from multiple queries from undermining pricing.
- Framework architecture: The market maker collects owner data, answers buyers’ linear aggregation queries, adds noise, returns results, and distributes individual payments.The market maker may retain part of the price as profit.
- Queries and pricing: Buyers may issue multiple queries, so pricing must account for information they can derive indirectly from cheaper query combinations.This requirement motivates addressing arbitrage across priced queries.
- Balance conditions: The framework tracks payment π, privacy loss εi, and micro-payment µi, requiring each owner’s privacy loss to be compensated and total payments to be covered by the buyer’s price.The formal coverage condition is ∑i µi(Q) ≤ π(Q).
- Queries and pricing: A buyer submits Q = (q, v), where q is a linear query and v ≥0 bounds answer variance; increasing v can lower the price.The market maker computes q(x) and adds mean-zero noise with variance at most v.
- Balance conditions: Pricing based only on variance requires agreement on a reasonable noise distribution because the distribution affects privacy loss and therefore owner payments.The framework later restricts noise to the Laplace distribution to connect privacy loss explicitly to variance.
- Balance conditions: The framework excludes noise choices with high variance but extremely accurate outputs, because they can create large privacy losses and micro-payments that exceed recovered costs.The example distribution has mean 0 and variance 2m, yet returns an accurate answer with extremely high probability.
3 Pricing Queries
The paper defines priced, noisy query answering and characterizes when query combinations permit arbitrage. It gives polynomial-time tests for linear answerability and derives structural conditions for arbitrage-free prices.
- Pricing Queries: Arbitrage-free pricing prevents buyers from reconstructing a query more cheaply from other purchased queries, ensuring prices can cover the resulting owner payments.Repeated-query exploitation is a motivating example: averaging independent noisy answers can reduce variance while spreading cost across cheaper purchases.
- Pricing Queries: A price function maps a query and permitted variance to a nonnegative price, while the answering mechanism returns an unbiased result with variance at most the specified bound.The buyer pays for a requested variance and is assumed indifferent to other perturbation properties.
- Answerability and Determinacy: A query is linearly answerable from S exactly when its query vector is a linear combination of S and the resulting weighted variance does not exceed the target variance.For coefficients c_i, the conditions are c_1q_1 + ... + c_mq_m = q and c_1^2v_1 + ... + c_m^2v_m ≤ v.
- Answerability and Determinacy: The framework restricts arbitrage analysis to linear combinations of previously purchased queries, called linear answerability.General answerability may involve nonlinear estimators, especially when the noise is not Gaussian.
- Answerability and Determinacy: Determining whether S determines Q can be done in polynomial time through a quadratic program that minimizes attainable variance subject to query-vector equality.The verification runs in PTIME(m, n).
- Arbitrage-free Price Functions: Arbitrage-free prices decrease with variance, charge the most for zero variance, and equal zero at infinite noise under continuity.They also satisfy π(q, v) = Ω(1/v) for linear queries.
- Arbitrage-free Price Functions: For prices of the form π(q, v) = f(q)^2/v, arbitrage-freeness is equivalent to f being a semi-norm.Subadditive non-decreasing combinations of arbitrage-free price functions remain arbitrage-free, including norm-based constructions.
- Arbitrage-free Price Functions: Corollary 20 shows that applying atan, tanh, or π/ to an arbitrage-free price function preserves arbitrage-freeness and boundedness.The supplied statement lists these transformations as valid bounded arbitrage-free functions.
4 Privacy Loss
The paper defines individual privacy loss by comparing a mechanism's outputs with and without one person's data, then develops bounds and payment-relevant properties under data-independent mechanisms.
- Privacy Loss: Privacy loss for individual i is the maximum output-probability ratio between retaining and removing that individual's data, bounded by e^ε in differential privacy.The paper adapts this comparison to a buyer-dependent loss rather than imposing one population-wide bound in advance.
- Privacy Loss: For linear combinations of mechanisms, privacy loss equals the sum of each mechanism's loss weighted by the absolute value of its coefficient.A deterministic mechanism has zero loss when independent of x_i and infinite loss otherwise.
- Data-Independent Mechanisms: The framework restricts mechanisms to data-independent noise added to the true query answer, so the noise depends on requested variance rather than the database instance.This restriction ensures users with zero query coefficient incur no privacy loss.
- Data-Independent Mechanisms: If query component q_i equals zero, individual i has privacy loss ε_i(K_Q) = 0.The mechanism produces identical random outputs on the database with and without that individual's data.
- Sensitivity and the Laplacian Mechanism: Because direct privacy-loss computation is difficult, the paper derives an upper bound using query sensitivity over a bounded data domain.The domain examples include binary values and ages in [0, 150].
- Sensitivity and the Laplacian Mechanism: The Laplacian mechanism answers q with additive Laplace noise whose scale is selected from the query and requested variance, and Proposition 28 bounds each individual's privacy loss.The paper introduces personalized sensitivity and the Laplacian density as components of this analysis.
5 Micro-Payments to Data Owners
Micro-payments compensate each data owner for privacy loss caused by answering a buyer’s query. They must be fair and micro-arbitrage-free so payments cover queried data and cannot be circumvented through alternative queries.
- Payment framework: The market maker pays each owner µi(Q) for data item xi according to the privacy loss εi caused by mechanism KQ.Payments are funded by the buyer’s payment π.
- Required properties: Fairness requires µi(q, v) = 0 whenever the owner’s data is not included in the query.Unqueried data owners do not receive payment.
- Required properties: Micro-arbitrage-freeness requires each owner’s payment function to remain arbitrage-free across alternative query combinations.This prevents buyers from avoiding compensation by deriving answers through other queries.
6 Balanced Pricing Frameworks
The paper defines balanced pricing by connecting buyer prices, individualized privacy loss, owner contracts, and micro-payments. It then gives construction rules for semi-balanced payments and converts them into balanced frameworks.
- Contracts: A contract Wi guarantees owner i at least µi ≥ Wi(εi) when privacy loss εi occurs.Each Wi is non-decreasing and satisfies Wi(0) = 0.
- Balanced frameworks: Micro-payments are cost-recovering when the buyer’s price π(Q) covers the sum of all owner payments, and compensating when µi(Q) covers Wi(εi(KQ)).These conditions protect both the market maker’s ability to pay owners and owners’ contractual guarantees.
- Balanced frameworks: A pricing framework is balanced when π is arbitrage-free and micro-payments are fair, micro-arbitrage-free, cost-recovering, and compensating.Compensation is measured relative to the owner contracts W.
- Construction: For Laplacian mechanisms with linear contracts Wi(εi) = ci · εi, the construction µi(Q) = γ·ci√(v/2|qi|) yields semi-balanced micro-payments.The construction ensures fairness, micro-arbitrage-freeness, and compensation.
- Construction: Non-decreasing sub-additive functions fi can combine existing semi-balanced payment functions into new semi-balanced payments.The resulting payment is µi = fi(µ1_i, ..., µk_i), with fi(0) = 0.
- Personalization: The framework can personalize contracts so one owner rejects total disclosure while another accepts it for a bounded maximum payment.For the less privacy-concerned voter, the payment is bounded by d and reaches d under total disclosure.
- Construction: Setting π(Q) = Σi µi(Q) converts a semi-balanced framework into a balanced one, while any higher arbitrage-free π′ also preserves balance.The query price is therefore constructed from owner payments and may be increased without violating the framework’s conditions.
7 Discussion
The discussion addresses truthful reporting of privacy valuations and the privacy risks of revealing those valuations. It proposes menu-based contracts but identifies valuation disclosure as an unresolved limitation.
- Truthfulness: Truthful participation is difficult because users may report extremely high prices even for tiny privacy losses.The paper frames this as a mechanism-design problem involving each owner’s contract function Wi.
- Truthfulness: Instead of eliciting exact valuations, the framework offers users a fixed menu of contract options.Users choose among understandable alternatives rather than directly reporting their privacy valuations.
- Truthfulness: Risk-tolerant users typically choose Option A, while risk-averse users choose Option B.Option A concentrates payment in larger privacy losses; Option B pays for small losses but caps large-loss payments lower.
- Truthfulness: Designing more than two easily understandable contract options remains a difficult task left for future work.The options were originally designed for sampling-based answering but also work with the paper’s perturbation-based mechanism.
- Private valuations: If privacy valuations correlate with data values, revealing a query price can itself disclose sensitive information.The paper gives HIV status as an example: differing valuations could let a buyer infer status without purchasing the query.
- Private valuations: When prices are private, both query answers and prices must be randomized, and total privacy loss includes εi(K) + εi(K′).For linear contracts, expected micro-payments must cover ci · (εi(K) + εi(K′)).
8 Related Work
Related work spans differential privacy, mechanism-design approaches to truthful valuation reporting, economic markets for personal information, and data-pricing systems. The paper distinguishes its framework by quantifying privacy loss and compensating owners across multiple privacy levels.
- Differential privacy: Differential-privacy research seeks accurate statistics with individual privacy, but does not consider compensating individuals for privacy loss.This paper uses an interactive model in which queries arrive online and the market maker charges for them.
- Mechanism design: Mechanism-design work studies truthful reporting of private valuations, whereas this paper addresses repeated pricing of private data with a different perspective.The cited prior work focuses on a single query and private valuations.
- Information markets: Earlier proposals for personal-information markets and approximate-query compensation did not use a rigorous measure of privacy loss or protection.The paper positions its framework as combining economic compensation with quantified privacy loss.
- Data pricing: Prior data-pricing methods based on explicit view prices did not consider the potential privacy risks of their pricing method.Their query determinacy was instance-based, allowing worst-case information leakage.
- Positioning: Compared with all-or-nothing exposure models, this framework supports different privacy levels, quantifies privacy loss, and compensates owners accordingly.The cited approaches either expose data entirely or leave it unused, with prices ultimately determined by buyers.
9 Conclusions
The framework supports selling perturbed linear queries while compensating data owners according to their privacy loss. It provides arbitrage-free, balanced pricing, but whether truthfulness and arbitrage-freeness can coexist remains open.
- Buyers can purchase linear queries with arbitrary perturbation, while data owners receive compensation based on the privacy loss each query causes.
- The framework permits arbitrarily many queries and ensures arbitrage-free prices for information buyers may extract from them.
- Buyer payments cover data-owner micro-payments, and each micro-payment compensates users according to their privacy loss.
- Whether truthfulness and arbitrage-freeness can both be achieved when pricing private data remains an open question.
A Proof of Corollary 20
Lemma 18 reduces the proof to verifying derivative signs over the nonnegative domain. The required conditions are nonnegative first derivatives and nonpositive second derivatives.
- Lemma 18 makes it sufficient to check the relevant derivative conditions.
- All first derivatives must be nonnegative.
- All second derivatives must be nonpositive for every x ≥0.
B Proof of Prop. 36
The proof establishes that each individual’s micro-payment satisfies fairness, micro-arbitrage-freeness, cost recovery, and compensation in expectation. It then lifts these properties to aggregate pricing where stated.
- Each micro-payment is fair in expectation for an individual.
- Each micro-payment is micro-arbitrage-free in expectation.
- The expected micro-payment is arbitrage-free, and the corresponding aggregate pricing is also arbitrage-free in expectation.
- The micro-payments are cost recovering.
- Each micro-payment compensates the individual for privacy loss in expectation.