DECEMBER 2017 | VOL. 60 | NO. 12 | COMMUNICATIONS OF THE ACM 85
was proposed by Ghosh et al., in which the ε budget is determined by the budget of the data analyst. 12
5. 3. Balanced pricing frameworks: Synthesis
Call (ε, µ, W) semi-balanced if all micro-payment functions
are arbitrage free and compensating w.r.t. K; that is, we leave
out the pricing function π and the cost-recovering requirement. The first step is to design a semi-balanced set of
Proposition 21. Let L be the Laplace Mechanism, and let the
contract functions be linear, Wi(ε) = ci ⋅ ε, where ci > 0 is a fixed
constant, fori = 1, ..., n. Define the micro-payment functions
for i = 1, .. ., n. Then (ε, µ, W) is semi-balanced.
The proposition defines the micro-payment associated to
linear contracts Wi, which requires infinite payment for total
loss of privacy. In practice, data owners are willing to sell their
raw data at some high (but finite) price. We show next how to
derive new semi-balanced micro-payments by applying sub-additive functions to other micro-payments.
Proposition 22. Fix k semi-balanced pricing frameworks,
(ε, µj , Wj ), j = 1, . . ., k. Define , and
, for each i = 1, . . ., n, where each function
fi : , i = 1, . . ., n, is non-decreasing, sub-additive, and
satisfies fi(0) = 0. Then, (ε, µ, W) is also semi-balanced, where
µ = (µ1, . . ., µn) and W = ( W1, . . ., Wn).
Finally, we choose a payment function such as to ensure
that the micro-payments are cost-recovering.
Proposition 23. Suppose that (ε, µ, W) is semi-balanced, and
define π(Q) = ∑i µi(Q). Then, (π, ε, µ, W) is balanced.
To summarize, the synthesis procedure for a pricing
framework proceeds as follows. Start with the simple micro-payment functions given by Proposition 21, which ensure
linear compensation for each user. Next, modify both the
micro-payment and the contract functions using Proposition 22, as desired, in order to adjust to the preferences of
individual users (e.g. in order to allow a user to set a price for
her true data). Finally, define the query price to be the sum
of all micro-payments (Proposition 23), then increase this
price freely, by using any method in Section 3. 4.
A number of issues deserve further attention if we are to
achieve a fully-functional marketplace for private data.
First, we have made two restrictions which limit the
prevention of arbitrage in our market. We require the mar-
ket maker to answer queries using an unbiased estimator
(Definition 5) and therefore arbitrage-freeness only pre-
vents an adversary from deriving an unbiased estimator of
a query using cheaper queries (Definition 6). In addition, we
have considered a restricted notion of answerability, limit-
ing our attention to adversaries who only consider queries
computed by linear functions of other queries. Both of these
Definition 19. We say that the micro-payment functions µi,
i = 1, . . ., n are cost-recovering for a pricing function π if, for any
query Q, π(Q) ≥ ∑i µi(Q).
Fix a query answering mechanism K. We say that a micro-payment function µi is compensating for a contract function
Wi, if for any query Q, µi (Q) ≥ Wi (ε (KQ) ).
The market maker will insist that the micro-payment
functions are cost-recovering: otherwise, he will not be
able to pay the data owners from the buyer’s payment. In
addition, a data owner will insist that the micro-payment
function is compensating: this enforces the contract
between her and the market maker, guaranteeing that she
will be compensated at least Wi(ε), in the event of a privacy
Fix a query answering mechanism K. We denote a pricing
framework (π, ε, µ, W), where π(Q), µi(Q) are the buyer’s price
and the micro-payments, ε = (ε1, ..., εn) where εi(KQ) is the
privacy loss corresponding to the mechanism K, and Wi(ε) is
the contract with the data owner i.
Definition 20. A pricing framework (π, ε, µ, W) is balanced
if ( 1) π is arbitrage-free and ( 2) the micro-payment functions µ
are arbitrage-free, cost-recovering for π, and compensating for W.
We explain how the contract between the data owner and
the market maker differs from that in privacy-preserving
mechanisms. Let ε > 0 be a small constant. A mechanism
K is called differentially private7 if, for any measurable set S,
any database vector x and for any entry j of x:
In differential privacy, the basic contract between the
mechanism and the data owner is the promise to every user
that her privacy loss is no larger than ε. In our framework
for pricing private data we turn this contract around. Now,
privacy is lost, and Definition 18 quantifies this loss. The
contract requires that the users are compensated according to their privacy loss. At an extreme, if the mechanism is
ε-differentially private for a tiny ε, then each user will receive
only a tiny micro-payment Wi(ε); as her privacy loss increases,
she will be compensated more.
The micro-payments circumvent a common limitation
of differentially-private mechanisms. In differential privacy,
the data analyst typically has a fixed budget, ε, granted by the
data curator, for all queries that he may ever ask. In order to
issue N queries, he needs to divide the privacy budget among
these queries, and, as a result, each query will be perturbed
with greater noise. After issuing these N queries, he can no
longer query the database, because otherwise the contract
with the data owner would be breached.
In our pricing framework there is no such hard limitation because the buyer simply pays for each query. The budget is now a real financial quantity, and the buyer can ask as
many query as he wants, with as high accuracy as he wants,
as long as he has money to pay for them. As a consequence,
it is the analyst-buyer, rather than the data owner, who ultimately determines the actual privacy loss. A similar model