∎

11institutetext:  Zicun Cong 22institutetext: Simon Fraser University,
Burnaby, Canada
22email<EMAIL_ADDRESS>33institutetext: Xuan Luo 44institutetext: Simon
Fraser University, Burnaby, Canada
44email<EMAIL_ADDRESS>55institutetext: Jian Pei 66institutetext: Simon
Fraser University, Burnaby, Canada
66email<EMAIL_ADDRESS>77institutetext: Feida Zhu 88institutetext: Singapore
Management University, Singapore
88email<EMAIL_ADDRESS>99institutetext: Yong Zhang 1010institutetext:
Huawei Technologies Canada, Burnaby, Canada
1010email<EMAIL_ADDRESS>
#  Data Pricing in Machine Learning Pipelines

Zicun Cong  Xuan Luo  Pei Jian  Feida Zhu  Yong Zhang

(Received: date / Accepted: date)

###### Abstract

Machine learning is disruptive. At the same time, machine learning can only
succeed by collaboration among many parties in multiple steps naturally as
pipelines in an eco-system, such as collecting data for possible machine
learning applications, collaboratively training models by multiple parties and
delivering machine learning services to end users. Data is critical and
penetrating in the whole machine learning pipelines. As machine learning
pipelines involve many parties and, in order to be successful, have to form a
constructive and dynamic eco-system, marketplaces and data pricing are
fundamental in connecting and facilitating those many parties. In this
article, we survey the principles and the latest research development of data
pricing in machine learning pipelines. We start with a brief review of data
marketplaces and pricing desiderata. Then, we focus on pricing in three
important steps in machine learning pipelines. To understand pricing in the
step of training data collection, we review pricing raw data sets and data
labels. We also investigate pricing in the step of collaborative training of
machine learning models, and overview pricing machine learning models for end
users in the step of machine learning deployment. We also discuss a series of
possible future directions.

###### Keywords:

Data Assets Data Pricing Data Products Machine Learning AI

##  1 Introduction

The disruptive success of machine learning in many applications has led to an
explosion in demand (Tramèr et al., 2016; Agarwal et al., 2019). Recent
research predicts that the global machine learning market is expected to reach
20.83 billion dollars in 2024 (Louis, 2020). To succeed in building a machine
learning application, one party is far from enough. Many parties have to
collaborate in one way or another. For example, one party may have to acquire
raw data and data labeling services from some other parties to construct
training data, multiple parties may need to collaborate in building a machine
learning model, and one party may want to use some other parties’ models to
solve its business problems. Machine learning applications are indeed
pipelines connecting many parties.

Data is critical for machine learning. Machine learning models, especially
deep models, rely on large amounts of data for training and testing. Deploying
machine learning services also needs data – machine learning models consume
users’ data as input, and return insights and recommend possible actions.
Maintaining and updating machine learning models still need data. The
importance of data for machine learning cannot be over emphasized. Data
penetrates the whole machine learning pipelines.

Obtaining data for machine learning is far from easy (Liu et al., 2021). For a
party that wants to build a machine learning model, the challenges come from
multiple aspects. First, within the party, in order to develop a training data
set, more often than not it is costly to collect data, create proper labels
and ensure data quality. Second, the party may realize that it does not have
the necessary data to train the target model. Thus, the party may have to
explore external sources for the data needed. This involves acquiring external
data. Last, to build or strengthen business edges, the party may want to
provide machine learning services to other parties. Then, the party has to
exchange data with other parties, such as accessing data from end users and
providing end users model output.

Connecting many parties in an eco-system in scale requires a general and
principled mechanism. As data and models are essential in machine learning
pipelines and data and model exchanges are the most fundamental interactions
among different parties, data and model marketplaces become a natural choice
for machine learning pipelines and eco-systems, and pricing becomes the core
mechanism in machine learning pipelines.

In response to the massive and diversified demands for various data, data
products become valuable assets for purchase and sale. Here, _data products_
refer to data sets as products and information services derived from data sets
(Pei, 2020). Data commoditization motivates data owners to share their data
products in exchange of rewards and thus helps data buyers to access data
products of high quality and large quantities.

To enable tradings between data owners and data buyers, data must be priced.
Pricing data, however, is far from trivial. Agarwal et al. (2019) summarize
five properties making data a unique asset. First, data can be replicated at
zero marginal cost. Second, the value of data is inherently combinatorial.
Third, the value of data varies widely among different buyers. Last, the
usefulness of data lies in the value of information derived from it, which is
difficult to verify a priori. Due to those properties, pricing models for
physical goods cannot be directly applied or straightforwardly extended to
data products, and thus new principles, theories, and methods need to be
developed.

Figure 1: Steps and pricing tasks in machine learning pipelines

Based on an extensive survey on existing research, we identify and focus on
three steps in data and model supply tasks in the manufacturing pipeline of
machine learning models (Fung and Beschastnikh, 2019). The steps and their
corresponding tasks are illustrated in Figure 1. In the step of training data
collection, raw data is collected and the associated labels are annotated. We
review the research on pricing for raw data sets and data labels. In the step
of collaborative training of machine learning models, we investigate how to
price different participants’ contributions through their data. In the model
deployment step, we overview pricing machine learning models for end users. We
focus on the four pricing tasks in machine learning pipelines as follows.

  * •

_Pricing raw data sets_. To build a machine learning model, the first step is
collecting training data. Monetizing and trading raw data sets provide people
with a convenient and efficient way to acquire a large amount of training
data. A key challenge in pricing raw data sets is how to set the price
reflecting the usefulness of a data set. Moreover, pricing models may be
optimized towards different objectives, such as revenue maximization,
arbitrage-freeness, and truthfulness. Achieving those optimization goals
introduces additional challenges in the design and implementation of pricing
models.

  * •

_Pricing data labels._ In the training data collection step, in addition to
collecting raw data, obtaining data labels is critical. Crowdsourcing is a
popular way for this purpose (Vaughan, 2017). Unfortunately, spammers may
commit no efforts in their assigned tasks and produce random answers, which
leads to data sets of poor quality. Thus, a key challenge in pricing data
labels is how to estimate label accuracy and compensate crowdworkers
correspondingly, such that they are motivated and driven to invest high
efforts and report accurate data labels (Vaughan, 2017). This task only
appears in machine learning pipelines where supervised machine learning models
are produced.

  * •

_Revenue allocation in collaborative machine learning._ Collaborative machine
learning is an emerging paradigm, where multiple data owners collaboratively
train machine learning models on their aggregate data, and share the revenues
of using/selling these models. Data sets from different owners may have
different contributions to the learned models. Evenly distributing the
revenues is not fair to data owners, particularly for those who contribute
more valuable data, and thus may discourage future collaborations. To this
end, a key challenge is how to fairly reward data owners’ contributions.

  * •

_Pricing machine learning models._ Machine learning as a service (MLaaS)
(Tramèr et al., 2016; Chen et al., 2020) is a rapidly growing industry.
Customers may purchase well-trained machine learning models or build models on
top of those well-trained rather than building models from scratch by
themselves. For example, one may use Google prediction API to classify an
image for only $0.0015 (Chen et al., 2020). While machine learning models and
raw data sets share a series of common ideas in pricing, the pricing models of
raw data sets cannot be trivially adapted to price machine learning models.
How to version machine learning models and avoid arbitrage among multiple
versions is a key challenge in this task.

The four tasks are related to each other. They share some core ideas, that is,
linking prices of data products to their utilities to customers. But as the
tasks have different application scenarios and pricing goals, they are solved
by orthogonal techniques.

The existing models in the first two tasks aim at pricing training data sets
with absolute utility functions, that is, the utility of a data product only
depends on the properties of the product. One important difference between the
first two tasks is about the utility functions. The utility (e.g., accuracy)
of data labels is very hard to compute due to the lack of ground-truth
verifications. The third task evaluates the utility of a data set by its
marginal contribution to a machine learning model. Thus, the utility of a data
set also depends on the utility of other data sets used to jointly build the
model. The existing methods in the last task also employ absolute utility
functions. But as machine learning models and data sets have different
properties, new pricing models are developed.

The four tasks are connected when machine learning models and data sets are
priced in an end-to-end manner. On the one hand, the price of a machine
learning model limits the budget of training data procurement and the revenue
that can be split among data owners (Agarwal et al., 2019). On the other hand,
the costs of data procurement and model training also influence the selling
price of machine learning models, as they are part of the manufacturing cost
(Liu et al., 2021). Figure 1 shows the connections of the four tasks.

There are some previous surveys related to data pricing (Liang et al., 2018;
Fricker and Maksimov, 2017; Zhang and Beltran, 2020). This article covers a
substantially deeper and more focused scope than those. In this article, we
try to present a comprehensive survey on data pricing in machine learning
pipelines. Very recently, Pei (2020) presents a survey connecting economics,
digital product pricing, and data product pricing. He identifies a series of
desirable properties in data pricing and reviews the techniques achieving
those properties. But Pei (2020) does not focus on machine learning pipeline
and does not cover the studies of pricing data labels.

The rest of this survey is organized as follows. Section 2 reviews basic
concepts and essential principles in data product pricing. Section 3 reviews
pricing raw data sets. Pricing data labels is discussed in Section 4. In
Section 5, we review the recent progress in revenue allocation in
collaborative machine learning. Section 6 is about how to price machine
learning models. We conclude this survey and discuss some future directions in
Section 7.

##  2 Data Marketplaces and Pricing

In this section, we briefly review data marketplaces and pricing in general.
We first discuss the basic structures of data marketplaces. Then, we discuss
some major pricing strategies in general. Third, we discuss different types of
data markets in terms of competition and dominance. Last, we discuss the
desiderata of data pricing.

###  2.1 Data Marketplaces

A data marketplace is a platform that allows people to buy and sell data
products (Schomm et al., 2013). Some examples of data marketplaces include
Dawex (Dawex, 2021), Snowflake data marketplace (Snowflake, 2021), and BDEX
(BDEX, 2021). Muschalle et al. (2012) identify seven categories of
participants in data marketplaces, namely analysts, application vendors, data
processing algorithm developers, data providers, consultants, licensing and
certification entities, and data market owners.

(a) General data marketplace.

(b) Sell-side marketplace.

(c) Buy-side marketplace.

Figure 2: Architectures of data marketplace.

Figure 2a shows the conceptual architecture of data marketplaces. A data
marketplace mainly consists of three major entities, namely data sellers, an
arbiter (also known as data vendor (Schomm et al., 2013) and data broker (Niu
et al., 2018)), and data buyers. Data sellers own data products and are
willing to share those products with the arbiter in exchange for rewards. Data
buyers want to obtain data products to solve their problems. The function of
an arbiter is to facilitate transactions between data sellers and data buyers.
The arbiter collects data products from data sellers and sells them to data
buyers. After collecting the payments from buyers, the arbiter distributes the
payments to data sellers. In general, arbiters are modeled as non-profit
participants in data marketplaces.

Some studies simplify the architecture of data marketplaces to sell-side
marketplaces and buy-side marketplaces. A sell-side marketplace (Zhang and
Beltran, 2020), as shown in Figure 2b, has a single data provider and multiple
data buyers. In a sell-side marketplace, the arbiter is operated by a monopoly
data seller to sell the single seller’s data products. In literature, sell-
side marketplaces are considered by pricing models of both general data sets
(Heckman et al., 2015) and specific types of data products, such as XML
documents (Tang et al., 2014) and data queries on a relational database (Deep
and Koutris, 2017b).

A buy-side marketplace (Zhang and Beltran, 2020), as shown in Figure 2c, has
multiple data providers and a single consumer/data buyer. In a buy-side
marketplace, the arbiter is operated by the single data buyer for purchasing
data products from providers. Buy-side marketplaces are considered in many
existing studies (Ghorbani and Zou, 2019; de Alfaro et al., 2016; Jia et al.,
2019a). For instance, de Alfaro et al. (2016) study a buy-side marketplace,
where a single consumer pays crowdsource workers for labeling the single
buyer’s data set.

###  2.2 Pricing Strategies

Many pricing strategies have been developed in pricing theory. Cost-based
pricing, customer value-based pricing, and competition-based pricing are three
important categories (De Toni et al., 2017).

Cost-based pricing considers that the price of a product is determined by
adding a specific amount of markup to the cost. This strategy is adopted in
personal data pricing, where the cost is the total privacy compensation to
data owners (Niu et al., 2018). A disadvantage of the cost-based pricing
strategy is that it only considers internal factors in determining the selling
price. External factors, such as competition and demands, are not included
(Luong et al., 2016).

Customer value-based pricing determines the price of a product primarily based
on how much the target customers believe a product is worth (De Toni et al.,
2017). To apply customer value-based pricing, a seller needs to estimate
customers’ demands for a product through their willingness and affordability
(Luong et al., 2016). Customer value-based pricing is the most popularly used
strategy for data pricing.

Competition-based pricing determines the price of a product strategically
based on competitors’ price levels and behavior expectations (De Toni et al.,
2017). Game theory provides a powerful tool to implement the strategy. In a
non-cooperative game, every seller is selfish and sets the price that
maximizes the seller’s profit independently (Luong et al., 2016). The
competition result, that is the asking price of each seller, is the Nash
equilibrium (Nash, 1950).

There are some other major pricing strategies in literature (Dibb et al.,
2005; Nagle, 2010; Brennan et al., 2013; Neumeier, 2015; Irvin, 1978), such as
operation-oriented pricing, revenue-oriented pricing, and relationship-
oriented pricing. The remarkably rich body of studies in economics and
marketing research on pricing tactics is far beyond the scope and capacity of
this survey.

###  2.3 Four Types of Data Markets

Similar to physical goods, the prices of data products are also influenced by
the dominance and diversity of supplies and demands in the market.

Fricker and Maksimov (2017) identify four types of data markets. First, in a
_monopoly_ , a supplier holds enough market power to set prices to maximize
profits. Second, in an _oligopoly_ , a small number of suppliers dominate the
market. Third, in _strong competition markets_ , individual suppliers do not
have enough market powers to set profit-maximizing prices, and prices tend to
align with marginal costs. Last, in a _monopsony_ , a single buyer controls
the market as the only consumer of products provided by sellers.

Most studies assume explicitly or implicitly a monopoly (monopsony) market
structure where the data seller (data buyer) does not care about competing
with others. Data pricing in oligopoly market is considered by Balasubramanian
et al. (2015). Jiang et al. (2015) study a perfect competition market where
participants can directly trade with each other.

###  2.4 Desiderata of Data Pricing

There are some desiderata perferred by most pricing models. In this section,
we briefly review the six desiderata suggested by Pei (2020). In addition, we
complement the existing study by an important desideratum, effort elicitation.

#### Truthfulness

Truthfulness is an important economic property of robust markets (Zhou and
Zheng, 2009). In a truthful market, all participants are selfish and only
offer prices that maximize their utility values. Participants may have their
own valuations on the same product, but a truthful market guarantees that for
each participant, offering the real valuation is an individual’s best
strategy. In other words, no participants will lie about their valuations.
Truthfulness simplifies all participants’ strategies and ensures basic market
fairness (Fernandez et al., 2020).

Reverse auction is a common tool to implement truthful data markets. In a
reverse auction, $N$ sellers $D=\\{s_{1},\ldots,s_{N}\\}$ compete for a
buyer’s deal by submitting their asking prices $\\{b_{1},\ldots,b_{N}\\}$. An
auction mechanism takes as input the submitted bids, selects a subset of
sellers as winners, and determines the payment $p_{i}$ to each winner $s_{i}$,
where $p_{i}\geq b_{i}$. In a truthful reverse auction, the best strategy
(dominant strategy) for a seller $s_{i}$ to maximize the expected utility is
submitting the individual’s real valuation, no matter what others submit.

In his seminal paper on optimal mechanism design, Myerson (1981) shows that a
sealed-bid reverse auction mechanism is truthful if and only if (1) The
selection rule is monotone, that is, if a seller $s_{i}$ wins the auction by
bidding $b_{i}$, it also wins by bidding $b^{\prime}_{i}\leq b_{i}$; and (2)
Each winner is paid the critical value, that is, seller $s_{i}$ would not win
the auction if $s_{i}$ bids higher than this value.

#### Revenue Maximization

Revenue maximization is a strategy to increase a seller’s customer base by
having low prices. This strategy is widely adopted by sellers in an emerging
market to build market share and reputations. For traditional physical goods,
the curves of marginal cost are U-shaped with respect to manufacturing level.
The revenue of a seller is maximized when the manufacturing level is set such
that the marginal revenue is zero (Burkett, 2006). Since data products can be
re-produced at almost zero costs (Agarwal et al., 2019), the revenue
maximization techniques for data products and physical products are quite
different (Pei, 2020).

#### Fairness

In some scenarios, sellers need to cooperatively participate in a transaction.
A data market is fair to the contributors in a coalition if the revenue
generated by the coalition is fairly divided among the sellers.

Suppose a set of sellers $D=\\{s_{1},\ldots,s_{N}\\}$ cooperatively
participate in a transaction that leads to a payment $v$. Shapley (1953) lays
out four axioms for a fair allocation.

  * •

Balance: The payment $v$ should be fully distributed to the sellers in $D$.

  * •

Symmetry: Sellers making the same contribution to the payment should be paid
the same. For a set of sellers $S$ and two additional sellers $s$ and
$s^{\prime}$, if $S\cup\\{s\\}$ and $S\cup\\{s^{\prime}\\}$ lead to the same
payment, sellers $s$ and $s^{\prime}$ should get the same payment.

  * •

Zero element: If a seller’s data does not contribute to the payment of any
coalitions, the seller should receive no payment.

  * •

Additivity: If the data of a group of sellers can be used for two tasks
$t_{1}$ and $t_{2}$ with payments $v_{1}$ and $v_{2}$, respectively, then the
payment to solve both tasks $t_{1}+t_{2}$ should be $v_{1}+v_{2}$.

It is proved that Shapley value $\psi(s)$ is the unique allocation method that
satisfies the four axioms, which is defined as the average marginal
contribution of $s_{i}$ to all possible subsets of sellers $S\subseteq
D\setminus\\{s_{i}\\}$

$\psi(s)=\frac{1}{N}\sum_{S\subseteq
D\setminus\\{s\\}}\frac{\mathcal{U}(S\cup\\{s\\})-\mathcal{U}(S)}{{N-1\choose|S|}},$
(1)

where $\mathcal{U}(\cdot)$ is the utility function (Shapley, 1953). For
example, in the context of collaborative machine learning, $\mathcal{U}(S)$ is
the performance score of the machine learning model trained on the data sets
of $S$, such as precision.

Equation 1 can be rewritten to

$\psi(s)=\frac{1}{N!}\sum_{\pi\in\prod(D)}(\mathcal{U}(P_{s}^{\pi}\cup\\{s\\}-\mathcal{U}(P_{s}^{\pi}))),$
(2)

where $\pi\in\prod(D)$ is a permutation of sellers and $P_{s}^{\pi}$ is the
set of sellers that precede seller $s$ in $\pi$.

The fact that Shapley value uniquely possesses Shapley fairness, combined with
its flexibility to support different utility functions, makes it a popular
tool to implement fair data marketplaces.

#### Arbitrage-free Pricing

Arbitrage is the activities that take advantage of price differences between
multiple markets. In a data marketplace, a data seller may offer multiple
versions of products. As a consequence, a critical concern is that a data
buyer may circumvent the advertised price of a product through buying a bundle
of cheaper ones, which negatively affects the seller’s revenue. For example,
consider a data seller selling noisy queries to the seller’s database (Niu et
al., 2018; Pei, 2020), and the seller perturbs each query answer independently
with random noise. An answer with a variance of $5$ is sold at $$5$ and with a
variance of $1$ is sold at $$50$. A data buyer wants to obtain an answer of
variance $1$. The buyer can purchase the cheaper answer $5$ times and compute
their average. Since the noises are added independently, the aggregated
average has variance $1$. Thus the customer saves $25 by arbitrage. A
desirable pricing function should guarantee that no arbitrage is possible, in
which case we call it arbitrage-free.

#### Privacy-preservation

Privacy protection during the transactions of data raises more and more
concerns. In data marketplaces, the privacy of buyers, sellers, and involved
third parties are highly vulnerable, and might be disclosed in many different
ways (Pei, 2020). Many different solutions have been proposed for privacy
protection in data markets (Fernandez et al., 2020; Li et al., 2013; Hynes et
al., 2018). In this survey, we focus on the studies along the line of privacy
compensation (Li et al., 2013; Niu et al., 2018; Nget et al., 2017), which
investigate how to provide compensations for the privacy disclosure of data
owners. For the purpose of privacy protection, sensitive data sets are usually
traded with injected random noise (Nget et al., 2017). A data set with less
random noise is more accurate, but may leak more privacy and thus more
compensations should be made to the data owner.

#### Computational Efficiency

The numbers of transactions, sellers and buyers may be huge in a data
marketplace. Therefore, it is a fundamental requirement for a pricing model to
compute prices efficiently with respect to a large number of goods and
participants. Prices should be computed in polynomial time with respect to the
number of participants (Agarwal et al., 2019) or the number of data products
(Chen et al., 2019). In some application scenarios, however, it takes
exponential time to compute the pricing functions with desirable properties,
such as Shapley fairness (Ghorbani and Zou, 2019), arbitrage-freeness (Koutris
et al., 2012), and revenue maximization (Chen et al., 2019). For example,
Koutris et al. (2012) show that computing arbitrage-free prices of join
queries on a relational database is in general NP-hard. How to efficiently
determine prices with desirable properties presents technical challenges.

#### Effort Elicitation

In addition to the above six desiderata, here we propose a new one, effort
elicitation.

In a data marketplace, a data buyer may purchase training data labels via
crowdsourcing. Crowdworkers are presented with unlabeled data instances (for
instance, images) and are asked to provide labels (for instance, a binary
label indicating whether or not the image contains pedestrains). A major
challenge in label collection is to ensure that workers invest their efforts
and provide accurate answers. A poorly designed pricing model may result in
labels with very low quality (Shah and Zhou, 2015). For example, if each task
has a fixed price, an obvious strategy that maximizes a worker’s profit is to
just provide arbitrary answers without even solving the tasks (Vaughan, 2017).
Many techniques have been developed to post-process noisy answers in order to
improve their quality. However, when the inputs to these algorithms are highly
erroneous, it is difficult to guarantee that the processed answers will be
reliable enough for downstream machine learning tasks (Shah and Zhou, 2015).
In order to avoid the troubles of “garbage in, garbage out”, a desirable
approach is to design proper rewards for crowdsourcing tasks that incent
workers to invest efforts and provide higher quality answers (Vaughan, 2017).

##  3 Pricing Raw Data Sets

In this section, we review the existing studies focusing on pricing raw data
sets. The existing studies consider four types of scenarios. The most
traditional methods price data sets as indivisible units and do not consider
supplier competitions. The intrinsic properties of data sets, such as volumes,
are factors determining prices. In the second scenario, how to price
indivisible data sets in a competitive market is studied. In the third
scenario, data consumers can purchase just a fraction of an entire data set,
which is more flexible to consumers but may have the issue of arbitrage. The
last scenario addresses pricing personal data by privacy compensation.

###  3.1 Pricing General Data

Machine learning and statistical models are vulnerable to poor quality
training data, thus high quality data is valuable to data buyers (Vaughan,
2017). Pricing data sets based on quality becomes a natural choice.

Heckman et al. (2015) identify a list of factors to assess the quality of a
data set, such as age of data, accuracy of data, and volume of data. A linear
model is proposed to set the price of a data set as

$\text{price }=\text{Fixed cost}+\sum_{i}w_{i}\cdot\text{factor}_{i}.$

Estimating the model parameters $w_{i}$ is a difficult task, as many data sets
may not have public prices associated with them. A more comprehensive list of
quality criteria is proposed in (Stahl and Vossen, 2016).

Yu and Zhang (2017) study the problem of trading multiple versions of a data
set, constructed by different data quality factors. They assume customers’
demands and maximum acceptable prices of different versions are public. A bi-
level programming model is established to address the problem. At the first
level, the data seller determines versions and their prices to maximize the
total revenue. At the second level, a group of buyers select data products to
maximize their utilities. Solving the bi-level programming model is NP-hard.
Yu and Zhang (2017) propose a heuristic genetic algorithm to approach it
numerically.

###  3.2 Pricing Crowdsensing Data

Crowdsensing is a powerful tool to quickly and cheaply obtain vast amounts of
training data for machine learning models (Vaughan, 2017; Zhang et al., 2016).
In a crowdsensing marketplace, a task requester initiates a data collection
task and compensates participating workers according to their reported costs.
As workers may exaggerate their costs, pricing models should incentivize
workers to truthfully reveal their costs.

Yang et al. (2012) design a reverse auction mechanism for mobile sensing data,
that is truthful, individually rational, and profitable. A pricing model is
truthful if all sellers truthfully report their data collection costs. A model
is individually rational if all sellers have non-negative net profits, and
profitable if the data buyer has non-negative net profits. The authors assume
that a buyer has a set $\Gamma=\\{\tau_{1},\ldots,\tau_{n}\\}$ of sensing
tasks, where each task $\tau_{i}$ has a value $v_{i}$ to the buyer. Each
seller $s_{i}$ chooses a subset of tasks $\Gamma_{i}\subseteq\Gamma$ and has a
private cost $c_{i}$ for performing the tasks. Seller $s_{i}$ decides a price
$b_{i}$ for the sensed data and submits the task-bid pair $(\Gamma_{i},b_{i})$
to the buyer. After collecting all bids, the buyer selects a subset of sellers
$S$ as winners and determines the payment $p_{i}$ to each winner $s_{i}$.

The proposed auction mechanism, MSensing, selects winners $S$ in a greedy
manner. Starting with $S=\emptyset$, it iteratively chooses the seller that
brings the largest non-negative net marginal profit. Each winner $s_{i}\in S$
is paid the critical value $p_{i}$ of $s_{i}$, that is, seller $s_{i}$ would
not win the auction if $s_{i}$ bids higher than $p_{i}$. Specifically,
MSensing runs the winner selection algorithm over users
$S^{\prime}=U\setminus\\{s_{i}\\}$. The payment $p_{i}$ is the largest price
$s_{i}$ can bid, such that $s_{i}$ can replace a user in $S^{\prime}$. Please
note that $p_{i}\geq b_{i}$, this is because due to incomplete cost
information, the buyer provides extra compensations to sellers on top of their
bids to motivate them to reveal actual costs. MSensing satisfies Myerson’s
characterization of truthful auction mechanisms (Myerson, 1981).

The follow-up work by Jin et al. (2015) considers the situation where a data
buyer has a data quality requirement $Q_{j}$ for each sensing task $t_{j}$.
The authors propose a Vickrey-Clarke-Groves mechanism (Ausubel et al., 2006)
like truthful reverse combinatorial auction. They assume that the data quality
$q_{i}$ of each seller $s_{i}$ is public and $q_{i}$ is the same for all
sensing tasks. The authors first consider the scenario where each seller only
bids for one bundle of sensing tasks $\Gamma_{i}$. The auction winners $S$
must satisfy the quality requirement for each task $t_{j}$, that is,
$\sum_{s_{i}\in S,\text{ if }t_{j}\in\Gamma_{i}}q_{i}\geq Q_{j}$. The
objective of the auction is to maximize the total utility of the buyer and the
sellers. The authors prove that winner determination under the setting is NP-
hard and propose a greedy winner selection algorithm with a guaranteed
approximation ratio to the optimal total utility. Each winner is paid by the
winner’s critical payment. The authors further study the total utility
maximization problem in a more general scenario, where each seller can bid for
multiple bundles of tasks. They propose an iterative descending algorithm that
achieves close-to-optimal total utility. However, the auction is not truthful.

Koutsopoulos (2013) considers a similar setting as Jin et al. (2015) do, but
assumes that a data buyer has only one sensing task. The author proposes a
truthful reverse auction that minimizes the expected cost of the buyer while
guaranteeing the data quality requirement. The author assumes that the data
buyer has prior knowledge about the distribution of each seller $s_{i}$’s unit
participation cost $c_{i}$. The units of participation $x_{i}$ of $s_{i}$ is a
positive real value indicating how much data is purchased from $s_{i}$. Given
the sellers’ bids, the data buyer determines the auction winners and their
participation units by solving a linear programming model, which minimizes the
total expected payment under the data quality constraint. Critical payments
are made to the selected winners. All sellers bidding truthfully forms a
Bayesian Nash equilibrium (Leyton-Brown and Shoham, 2008).

###  3.3 Pricing Data Queries

Query-based pricing models tailor the purchase of data to users’ needs.
Customers can purchase their interested parts of a data set through data
queries, and are charged according to their issued queries. While such a
marketplace mechanism provides greater flexibility to buyers, a less carefully
designed pricing model may open the loophole for arbitrage, which allows
buyers to obtain a query result in a cost less than the advertised prices.

Given a database $D$ and a multi-set of query bundles
$\mathbf{S}=\\{\mathbf{Q}_{1},\ldots,\mathbf{Q}_{m}\\}$, a query bundle
$\mathbf{Q}$ is determined by $\mathbf{S}$, if the answer to $\mathbf{Q}$ can
be computed only from the answers to the query bundles in $\mathbf{S}$. A
pricing function is arbitrage-free if the advertised price
$\pi(\mathbf{Q})\leq\sum_{i=1}^{m}\pi(\mathbf{Q_{i}})$, that is, the answer to
a query bundle $\mathbf{Q}$ cannot be obtained more cheaply from an
alternative set of query bundles.

The first formal framework for arbitrage-free query-based data pricing was
introduced by Koutris et al. (2012). The major idea is that a data seller can
first specify the prices of a few views $\mathbf{V}$ over a database, and then
the price of a query bundle $\mathbf{Q}$ is decided algorithmically.
Theoretically, the authors show that if there are no arbitrage situations
among the views in $\mathbf{V}$, there exists a unique arbitrage-free and
discount-free pricing function $\pi(\mathbf{Q})$. Specifically,
$\pi(\mathbf{Q})$ is the total price of the cheapest subset of $\mathbf{V}$
that determines $\mathbf{Q}$, which is found by query determinacy (Nash et
al., 2007). They also show the complexity of evaluating the price functions.
Unfortunately, the pricing model is NP-hard for a large class of practical
queries. They develop polynomial time algorithms for specific classes of
conjunctive queries, chain queries, and cyclic queries.

Subsequently, Koutris et al. (2013) develop a prototype pricing system,
QueryMarket, based on the idea (Koutris et al., 2012). They formulate the
pricing model as an integer linear program (ILP) with the objective to
minimize the total cost of purchased views $\mathbf{V}_{p}$. The purchased
views $\mathbf{V}_{p}$ must satisfy the following requirements. For a tuple
$t$ in the query answer $\mathbf{Q}(D)$, there must exist a subset of views in
$\mathbf{V}_{p}$ that can produce $t$ and for each relation $R$ in
$\mathbf{Q}$, at lease one view on $R$ should be purchased. For a tuple $t$
not in $\mathbf{Q}(D)$, there must exist a subset of views in $\mathbf{V}_{p}$
that can indicate $t\notin\mathbf{Q}(D)$. Although the pricing problem in the
setting is in general NP-hard, QueryMarket shows that a large class of queries
can be priced in practice, albeit for small data sets. To handle the case that
a query $\mathbf{Q}$ may require databases from multiple sellers, they
introduce a revenue sharing policy among sellers. Specifically, each seller
gets a share of the query price $\pi(\mathbf{Q})$, which is proportional to
the maximum revenue that the seller can get among all minimum-cost solutions
to the ILP.

The problem of designing arbitrage-free pricing models for linear aggregation
queries is studied by Li et al. (2013). Given a data set of $n$ real values
$\mathbf{x}=\langle x_{1},\ldots,x_{n}\rangle$, a linear query over
$\mathbf{x}$ is a real-valued vector $\mathbf{q}=\langle
w_{1},\ldots,w_{n}\rangle$, and the answer is
$\mathbf{q}(\mathbf{x})=\sum_{i=1}w_{i}x_{i}$. The authors propose a
marketplace, where a data buyer can purchase a single linear query
$\mathbf{q}$ with a variance constraint $v$ defined by the buyer. The query
$\mathbf{Q}=(\mathbf{q},v)$ is answered by an unbiased estimator of
$\mathbf{q}(\mathbf{x})$ with a variance smaller than or equal to $v$. The
authors first develop a proposition that the pricing function $\pi$ cannot
decrease faster than $\frac{1}{v}$, that is,
$\pi(\mathbf{q},v)=\Omega(\frac{1}{v})$. Then, they propose a family of
arbitrage-free pricing functions,
$\pi(\mathbf{q},v)=\frac{f^{2}(\mathbf{q})}{v}$, where the function $f(\cdot)$
is semi-norm. Last, they provide a general framework to synthesize new
arbitrage-free pricing functions from the existing ones. For any arbitrage-
free pricing functions $\pi_{1},\ldots,\pi_{k}$, the pricing function
$\pi(\mathbf{Q})=f(\pi_{1}(\mathbf{Q}),\ldots,\pi_{k}(\mathbf{Q}))$ is also
arbitrage-free if $f(\cdot)$ is a subadditive and nondecreasing function. A
comprehensive list of celebrated arbitrage-free pricing functions are listed
by Niu et al. (2018). In addition to synthesized pricing functions, Li et al.
(2013) also study a similar view-based pricing framework as Koutris et al.
(2012) do. By adapting the theoretical results in (Koutris et al., 2012), the
authors show that the view-based pricing model for linear aggregation queries
is NP-hard.

Lin and Kifer (2014) study arbitrage-free pricing for general data queries.
They propose three pricing schemes, namely instance-independent pricing, up-
front dependent pricing, and delayed pricing. The authors further summarize
five forms of arbitrages, namely price-based arbitrage, separate account
arbitrage, post-processing arbitrage, serendipitous arbitrage, and almost-
certain arbitrage. The authors point out that the model by Koutris et al.
(2012) has pricing-based arbitrage, that is, the computed prices may leak
information about $D$. Theoretically, they propose an instance-independent
pricing function and a delayed pricing function that are arbitrage-free across
all forms. The major idea is to tackle the pricing problem from a
probabilistic view. Queries that are more likely to reveal the true database
instance are priced higher.

In the same vein, Deep and Koutris (2017a) characterize the structure of
pricing functions with respect to information arbitrage and bundle arbitrage,
where information arbitrage covers both post-processing arbitrage and
serendipitous arbitrage defined by Lin and Kifer (2014). For both instance-
independent pricing and answer-dependent pricing of a query, an arbitrage-free
pricing function should be monotone and subadditive with respect to the amount
of information revealed by asking the query. Several examples of arbitrage-
free pricing functions are presented, including the weighted coverage function
and the Shannon entropy function.

Deep and Koutris (2017b) later implement the theoretical framework (Deep and
Koutris, 2017a) into a real time pricing system, QIRANA, which computes the
price of a query bundle $\mathbf{Q}$ from the view of uncertainty reduction.
They assume that a buyer is facing a set of all possible database instances
$S$ with the same schema as the true database instance $D$. After receiving
the query answer $E=\mathbf{Q}(D)$, the buyer can rule out some database
instances $D_{i}\in S$ that cannot be $D$ by checking whether
$\mathbf{Q}(D_{i})=E$. A query bundle that eliminates more database instances
is priced higher, as it reveals more information about $D$. The authors
propose an arbitrage-free answer-dependent pricing function, which assigns a
weight $w_{i}$ to each database $D_{i}\in S$, and computes the price of a
query bundle by

$\pi(\mathbf{Q})=\sum_{i\in\\{i|D_{i}\in
S\\},\mathbf{Q}(D)\neq\mathbf{Q}(D_{i})}w_{i}.$ (3)

By default, the same weight $w_{i}=\frac{P}{|S|}$ is assigned to each possible
database instance $D_{i}$, where $P$ is a parameter set by the data owner. The
data owner can also provide QIRANA with some example query bundles and their
corresponding prices. Then, QIRANA will automatically learn instance weights
$w_{i}$ from the given examples by solving an entropy maximization problem.
Choosing $S$ to be the complete set of possible database instances leads to a
$\\#P$-hard problem. To make the pricing function tractable, QIRANA uses a
random sample of database instances as $S$.

Chawla et al. (2019) extend the pricing function in Equation 3 to maximize
seller revenue. They consider the setting that the supply is unlimited and the
buyers are single-minded, that is, a buyer only wants to buy a single query
bundle $\mathbf{Q}$. A buyer will purchase $\mathbf{Q}$ if the advertised
price $\pi(\mathbf{Q})$ is smaller than or equal to the buyer’s valuation
$v_{\mathbf{Q}}$. The authors take a training data set consisting of some
query bundles and their customer valuations. Three pricing schemes are
investigated. The major idea of the pricing schemes is that, according to
Equation 3, a query can be priced as a bundle of items (database instances).
Uniform bundle pricing sets the same price for all query bundles. Item pricing
sets the price of a query bundle using Equation 3, where the weights $w_{i}$
are learned from the training data. XOS pricing learns $k$ weights
$w_{i}^{1},\ldots,w_{i}^{k}$ for each item $D_{i}$ and sets the price of
$\mathbf{Q}$ as $\pi(\mathbf{Q})=\text{max}_{j=1}^{k}\sum_{i\in\\{i|D_{i}\in
S\\},\mathbf{Q}(D)\neq\mathbf{Q}(D_{i})}w_{i}^{j}$. Theoretically, the
approximation rate of each pricing scheme to the optimal revenue is studied.
Although XOS pricing scheme enjoys the best approximation rate, the authors
show that item pricing usually achieves larger revenue in practice.

Miao et al. (2020) study the problem of pricing selection-projection-natural
join queries over incomplete databases. An arbitrage-free pricing function is
proposed based on the idea of data provenance, which describes the origins of
a piece of data and its processing history (Buneman and Tan, 2007; Tang et
al., 2013). Let $t$ be a tuple in a query answer $\mathbf{Q}(D)$. The lineage
$L(t,D)$ of $t$ is defined as the set of tuples in the database $D$ that
contribute to $t$. The authors assume that each tuple $t$ has a base price
$p(t)$. The price of $\mathbf{Q}$ is set to the weighted aggregation of the
costs of all tuples in $M(\mathbf{Q},D)=\cup_{t\in\mathbf{Q}(D)}L(t,D)$.
Specifically, $\pi^{UCA}(\mathbf{Q})=\sum_{i\in\\{i|t_{i}\in
M(\mathbf{Q},D)\\}}\mu_{i}p(t_{i})$, where $\mu_{i}$ is the percentage of
attributes of $t_{i}$ that are not missing. The authors also propose an answer
quality aware pricing function,
$\pi^{QUCA}(\mathbf{Q})=\frac{\Delta}{n}\pi^{UCA}(\mathbf{Q})\kappa(\mathbf{Q},D)$,
where $\kappa(\mathbf{Q},D)$ is the answer quality and $\Delta$ is a constant.
However, $\pi^{QUCA}$ is not arbitrage-free.

Purchasing data is usually not a one-shot deal. A customer may purchase
multiple queries from the same data seller. A history-aware pricing function
will not charge the customer twice for already purchased information.
QueryMarket (Koutris et al., 2013) tracks the purchased views of a customer
and avoids charging those views when pricing future queries of the customer.
Both (Deep and Koutris, 2017b) and (Miao et al., 2020) support history-aware
pricing in the same vein as (Koutris et al., 2013). One drawback of these
history-based approaches is that the seller must provide reliable storage to
keep users’ query history (Upadhyaya et al., 2016).

Upadhyaya et al. (2016) propose an optimal history-aware pricing function,
that is, a buyer is only charged once for purchased data. The key idea is to
allow buyers to ask for refunds of already purchased data. In their setting, a
query is priced according to its output size. The seller computes an
identifier (coupon) for each tuple in the query answer $\mathbf{Q}(D)$. Both
$\mathbf{Q}(D)$ and the corresponding coupons are sent to the buyer. If the
buyer receives the same tuple $t$ from two queries, the buyer can ask for a
refund of $t$ by presenting the two coupons associated with $t$ in the two
corresponding queries. To prevent buyers from borrowing coupons from others
and receiving unconscionable refunds, each coupon is uniquely associated with
a buyer. By tracking coupon status, the data seller guarantees that each
coupon will be used only once. However, the pricing function has no arbitrage-
free guarantee (Deep and Koutris, 2017b).

###  3.4 Privacy Compensation

Machine learning models in many areas, like recommendation systems (Dandekar
et al., 2012) and personalized medical treatments (Ma et al., 2020), require a
large amount of personal data. However, trading and sharing personal data may
leak the privacy of data providers. Therefore, how to measure and properly
compensate data providers for their privacy loss is an important concern in
designing marketplaces of personal data.

Differential privacy (Dwork, 2008) is a mathematical framework rigorously
providing privacy protection and plays an essential role in personal data
pricing. Following the principle of differential privacy, random noises are
injected into a data set, such that data buyers can learn useful information
about the whole data set but cannot learn specifics accurately about an
individual. The magnitude of random noise impacts data providers’ privacy loss
and the data price. A data set with less injected random noise may leak more
privacy and is priced higher. Pricing models of personal data routinely adopt
cost-plus pricing strategy, where sellers first compensate data providers for
their privacy loss, and then scale up the total privacy compensation to
determine the price for data buyers (Niu et al., 2018).

Ghosh and Roth (2011) initiate the study of pricing privacy by auction. They
propose a truthful marketplace to sell single counting queries on binary data.
In their settings, a data seller has a data set consisting of personal data
$d_{i}\in\\{0,1\\}$ of individual $i$. The data seller sells an estimator
$\widehat{s}$ of the sum $s=\sum_{i}d_{i}$ and compensates data providers for
their privacy loss. Under the framework of differential privacy, the authors
treat privacy as a commodity to be traded. In particular, if a provider’s data
is used in an $\epsilon-$differentially private manner, $\epsilon$ privacy
units should be purchased from the provider. Thus, the privacy compensation
problem can be transformed into variants of multi-unit reverse auction. The
authors assume that each data provider $i$ has a privacy cost function

$c_{i}(\epsilon)=v_{i}*\epsilon,$ (4)

representing the cost for using the data in an $\epsilon$-differentially
private manner, where $v_{i}$ is the unit privacy cost of $i$. In an auction,
data providers are asked to submit their asking prices $b_{i}$ for the use of
their data. Ghosh and Roth (2011) consider two situations. In the first
situation, a buyer has an accuracy requirement on $\widehat{s}$, that is,
$\text{Pr}[|\widehat{s}-s|\geq k]\leq\frac{1}{3}$. The authors establish an
observation that they only need to purchase data from $m$ individuals and use
them in an $\epsilon$-dfferential privacy manner, where $m$ and $\epsilon$
only depend on the accuracy goal. It’s shown that the classic Vickrey-Clarke-
Groves auction minimizes the buyer’s payment and guarantees the accuracy goal.
The major idea is to select $m$ individuals with the cheapest bids and provide
each winner with a uniform compensation $\epsilon\cdot b$, where $b$ is the
$(m+1)$-th smallest bid. In the second situation, a buyer has a budget
constraint and wants to maximize the accuracy of $\hat{s}$. The authors
propose a greedy-based approximation algorithm to solve the problem.

The value of personal data and privacy valuation may be correlated. For
example, a patient may assign a higher price to the patient’s medical report
than the healthy people ask for. Ghosh and Roth (2011) show a negative result
that in the situations having such correlations, no individually rational
direct mechanism can protect privacy.

In a follow-up study, Dandekar et al. (2012) consider the scenario of selling
linear aggregate queries $\mathbf{q}=\langle w_{1},\ldots,w_{n}\rangle$ over
real-valued personal data $D=\langle d_{1},\ldots,d_{n}\rangle$. They assume
data providers have the same privacy cost function as Equation 4, and propose
a truthful reverse auction mechanism to maximize the accuracy of estimators
for budget-constraint buyers. The error of an estimator $\widehat{s}$ of the
true answer $s=\sum_{i}w_{i}d_{i}$ is its squared error $(\widehat{s}-s)^{2}$.
It is shown that an $\widehat{s}$ computed from more providers with large
corresponding weights in $\mathbf{q}$ is more accurate. Therefore, the problem
is transformed into a knapsack reverse auction (Singer, 2010) that maximizes
the total weights of the selected providers under budget constraints.
Specifically, the authors treat the budget as the capacity of the knapsack,
the privacy cost of a data entry $d_{i}$ as its weight in the knapsack, and
$w_{i}$ as the value of $d_{i}$. A greedy-based algorithm with an
approximation ratio of $5$ is proposed to solve the problem.

The aforementioned studies (Ghosh and Roth, 2011; Dandekar et al., 2012)
assume that data buyers can purchase an arbitrary amount of privacy from each
data provider. However, a conservative individual may not want to sell the
individual’s data if the privacy loss is too large. Nget et al. (2017) study
the same problem as Dandekar et al. (2012) do in a more realistic situation,
that is, an individual $i$ can refuse to participate in an estimator if the
privacy loss of $i$ is larger than a threshold $\epsilon_{i}$. They assume
that the privacy cost function of each data provider is public and propose a
heuristic method to determine query price. The model first randomly samples a
subset of data providers. Then, it uses the data from each sampled individual
$i$ in an $\epsilon_{i}$-differentially private manner, and computes the
compensations correspondingly. If the total compensation is larger than the
budget, the model decreases the differential privacy levels of the high cost
providers, such that the budget goal is met. Last, they generate the perturbed
query answers by personalized differential privacy (Jorgensen et al., 2015),
which guarantees the differential privacy for each selected individual $i$.
They repeat the above steps several times and return the perturbed answer with
the smallest squared error.

Later, Zhang et al. (2020) propose a truthful personal data marketplace, where
each data provider $i$ can specify the personal maximum tolerable privacy loss
$\epsilon_{i}$. They first show that the accuracy of query answers is
proportional to the total amount of purchased privacy. Under the assumption
that the distributions of privacy costs of all individuals are public, they
design a variant of Bayesian optimal knapsack procurement (Ensthaler and
Giebe, 2014), which maximizes the expected total purchased privacy under the
constraint of a data buyer’s expected budget. The authors solve the problem by
adopting the algorithm in (Ensthaler and Giebe, 2014). The noisy query answer
is generated using personalized differential privacy (Jorgensen et al., 2015),
which guarantees $\epsilon_{i}$-differential privacy for each selected
individual $i$.

The models proposed by Dandekar et al. (2012); Ghosh and Roth (2011) may be
attacked by arbitrage. Li et al. (2013) consider the situation where a data
buyer has a variance constraint $v$ on the purchased noisy query answers. They
assume that the privacy costs of individuals are public, and propose a
theoretical framework for assigning arbitrage-free prices to linear aggregate
queries $\mathbf{q}$. A perturbed answer is generated from the true answer by
adding Laplace noise with the expectation $0$ and variance
$\sqrt{\frac{v}{2}}$. Measured by differential privacy, the privacy loss of an
individual $i$ is upper-bounded by $\epsilon=\frac{w}{\sqrt{\frac{v}{2}}}$ if
the individual is involved in the query, and $0$ otherwise, where $w$ is the
largest absolute weight in $\mathbf{q}$. Several privacy compensation
functions are proposed, such as $p_{i}(\epsilon)=c_{i}\epsilon$, where $c_{i}$
is the unit privacy cost of individual $i$. The price of a query is the sum of
the privacy compensations, which is proved to be arbitrage-free.

Li et al. (2013) only compensate individuals involved in queries. However, as
two individuals’ data may be correlated, the privacy of a not-involved
individual may be leaked due to the revelation of the other individual’s data.
To fairly compensate individuals for their privacy, Niu et al. (2018) extend
the model by Li et al. (2013), and propose a pricing model that is arbitrage-
free and dependency fair. Dependent fairness requires that a data provider
should receive a privacy compensation as long as some data of other providers
that is correlated to the data of this provider is involved in a query.
Employing dependent differential privacy (Liu et al., 2016), the privacy loss
of a data provider $i$ caused by a query is upper-bounded by
$\epsilon_{i}=\frac{ds_{i}}{\sqrt{\frac{v}{2}}}$, where $ds_{i}$ is the
dependent sensitivity of the query at provider $i$’s data. The authors propose
a bottom-up mechanism and a top-down mechanism to determine privacy
compensations and query prices. The bottom-up mechanism computes compensations
in the same way as Li et al. (2013) do and determines query prices as a
multiple of the total compensations. The top-down mechanism first determines
the query price using a user-defined arbitrage-free pricing function and
spares some fraction of a buyer’s payment for privacy compensation. Each data
provider receives a division of the compensation proportional to the
provider’s privacy loss.

All of the privacy compensation methods discussed above assume a trustworthy
platform/agent to trade data providers’ privacy with data buyers. Data
providers, however, cannot control the usage of their own data.

In this concern, Jin et al. (2019) develop a truthful crowdsensing
marketplace, where data owners can determine how much privacy to disclose. In
their marketplace, obfuscated geo-locations of data owners are traded by
auctions. Data owners first inject random noise to their data based on their
own privacy preferences. Then, each data owner bids with the cost as well as
the mean and variance of the injected random noise. The buyer determines
auction winners to maximize data accuracy with respect to the buyer’s budget
constraint. The authors show that the optimization problem is NP-hard and
develop a greedy heuristic solution. The major idea is to iteratively select
data owners that bring the largest marginal utility contributions until the
budget is used up.

In this section, we review representative pricing models of raw data sets in
four types of scenarios, where different desiderata are considered. A
limitation of the discussed pricing models is that data sets are priced
without considering their down-stream applications. Fernandez et al. (2020)
argue that the value of a data set to customers is usually task dependent and
cannot be evaluated by the intrinsic properties of the data set alone. As the
pricing models of raw data sets are agnostic to the down-stream applications
of raw data sets, these pricing models can be used in machine learning
pipelines of building both supervised and unsupervised machine learning
models.

##  4 Pricing Data Labels

Crowdsourcing is a popular method for collecting large-scale labeled training
data for machine learning tasks (Shah and Zhou, 2015). Unfortunately,
crowdsourced data often suffers from quality issues. This is mainly due to the
existence of lazy and spamming workers, who submit low quality labels. Those
workers can be discouraged from participating in the tasks by rewarding them
with a performance-based payment (Radanovic et al., 2016). However, due to a
lack of ground-truth verification of the collected labels, how to evaluate
label quality and price the labels correspondingly is a challenging task. In
this section, we review two types of label pricing models, which are designed
to motivate workers to exert efforts and submit accurate data labels.

###  4.1 Gold Task-based Pricing Models

A gold task is one for which the answer is known to the data buyer a priori.
Gold tasks can be uniformly mixed at random within the tasks for workers to
evaluate workers’ performance, which determines the payments to workers. Since
workers cannot distinguish gold tasks from others, this strategy can motivate
workers to provide accurate labels.

Shah and Zhou (2015) consider a crowdsourcing setup where workers perform
binary labeling tasks. The authors propose a multiplicative pricing model
using gold tasks. The model allows a worker to skip an assigned task if the
worker is not confident about the answer. The total payment to a worker $u$ is
computed based on $u$’s performance on the answered tasks. The workers are
selfish and want to maximize their individual expected payments. The authors
assume that each worker has a private belief $\text{Pr}(y_{t}=l)$ about how
likely the true label $y_{t}$ of a task $t$ is $l$. The pricing model is
designed to incentivize workers to only report high-confidence labels with
beliefs greater than a threshold $p$. The total reward starts at $\beta$. For
each correct answer in the gold tasks, the reward will be multiplied by
$\frac{1}{p}$. However, if any of these gold tasks are answered incorrectly,
the reward will drop to zero, that is,

$\pi(u)=\beta\cdot\frac{1}{p^{c}}\cdot\mathbf{1}(r=0),$ (5)

where $\mathbf{1}(\cdot)$ is an indicator function, and $c$ and $r$ are the
number of correct and wrong answers, respectively. This pricing model
motivates workers to only answer tasks that they are sufficiently confident
about. The pricing model is incentive compatible, that is, a worker receives
the maximum expected payment if and only if the worker exerts efforts to
report accurate labels. The pricing model also satisfies the “no-free-lunch”
axiom, that is, workers who only provide wrong answers will receive no
payments. In their setting, the proposed method is the unique incentive
compatible model that satisfies the “no-free-lunch” axiom.

Shah et al. (2015) further generalize the model (Shah and Zhou, 2015) to
multi-label tasks. For each task, a worker can submit multiple answers
$\widehat{Y}$ that the worker believes is most likely to be correct. This
multi-selection system provides workers more flexibility to express their
beliefs, which can use the expertise of workers with partial knowledge more
effectively than single-selection systems. The authors assume that the
workers’ beliefs for any label being the true label for a task lie in the set
$\\{0\\}\cup(p,1]$, where $p$ is fixed and known. The authors want to
encourage workers to only report the set of labels with positive beliefs. The
reward of a worker for a gold task is $(1-p)^{(|\widehat{Y}|-1)}$ if one of
the worker’s answers is correct and $0$ if otherwise. The total payment to a
worker is determined by the product of the worker’s rewards on all gold tasks.

In a later study, Shah and Zhou (2016) propose a two-stage multiplicative
pricing model to motivate workers to self-correct their answers. In the first
stage, a worker answers the assigned tasks. In the second stage, if the
worker’s answer to a task $t$ does not agree with the answer from the peer
workers, the worker has an opportunity to change the answer. The worker $u$
receives a high reward for a gold task $t$ if the initial answer to the task
is correct, a low reward if the updated answer is correct, and $0$ reward if
the final answer is wrong. The total payment is determined by the product of
the worker’s rewards from gold tasks. Theoretically, the authors prove that
the proposed method is the unique incentive compatible model that satisfies
the no-free-lunch axiom. Empirically, they show in a simulation that the self-
correction setting can significantly improve the data quality compared to the
standard single-stage settings.

To reduce the variance in payoffs, the aforementioned methods (Shah and Zhou,
2016; Shah et al., 2015; Shah and Zhou, 2015) require each worker to solve a
sufficient number of gold tasks. This leads to a waste of procurement budget,
as the answers to the gold tasks are already known.

de Alfaro et al. (2016) address the limitation by combining the ideas from
peer prediction and gold tasks. They arrange the workers in a hierarchy, where
every worker shares one common task with each of its children. A few gold
tasks are used to incentivize high efforts from the workers at the top level
of the hierarchy. Assuming these workers exert sufficient efforts to provide
high quality answers, their answers can be used as pseudo gold tasks for
workers in the second layer, who can in turn provide pseudo gold tasks for the
next level, and so forth. A worker will be punished if the worker does not
agree with the parent on the task shared between them. As the workers at the
top level are evaluated by the true gold tasks, they are evaluated more
accurately than the other workers, which is not fair to workers at lower
layers.

The follow-up work by Goel and Faltings (2019) considers fair payment among
workers, that is, the expected reward of a worker is directly proportional to
the accuracy of the worker’s answers and independent of the strategy and
proficiency of the worker’s random peers. The key idea is to estimate the
proficiency of workers, which is the probability that a worker can solve the
tasks correctly. Goel and Faltings (2019) start by estimating the proficiency
of a small group of workers with gold tasks. Then, the answers by the small
group of workers to non-gold tasks are used as contributed gold tasks, where
the workers’ proficiencies are used as the trustworthy degree of those tasks.
The contributed gold tasks are used to estimate the proficiency of more
workers. Finally, the payoff of each worker is proportional to the worker’s
estimated proficiency, such that workers with good proficiency receive high
payments. The model guarantees that exerting high efforts to provide accurate
labels is a dominant strategy for each worker.

###  4.2 Peer Prediction-based Pricing Models

Peer prediction-based pricing model can incentivize efforts and accurate data
labels without access to gold tasks. Those models take advantage of the
stochastic correlation of answers to the same tasks, and set up a game among
workers, called a mechanism in game theory. The game is designed such that
workers who exert effort in solving the tasks can achieve high expected
rewards, whereas spammers providing random answers on average receive no
payments. A pricing model is incentive compatible if it admits exerting high
efforts and truthful reporting as an equilibrium.

Dasgupta and Ghosh (2013) initiate the study of effort elicitation and propose
the DG model to price binary labels. A data buyer assigns a set of data
labeling tasks to a group of workers, such that each task is labeled by
multiple workers and each worker labels multiple tasks. They assume that a
worker $u_{i}$ either invests no effort and thus provides a random label, or
invests full effort with a cost $c_{i}$ and provides a true label with
probability $p_{i}$. Here, $p_{i}$ is called the proficiency of $u_{i}$. The
workers are self-interested, who want to maximize their payoffs.

The DG model pays a worker $u_{i}$ on an assigned task $t$ based on how
surprisingly $u_{i}$’s report is consistent with that of the peer worker
$u_{p}$. Denote by $\widehat{y}$ and $\widehat{y}_{p}$ the answers from
$u_{i}$ and $u_{p}$ to a task, respectively. The model pays $u_{i}$ with a
constant reward subtracting the probability $\text{Pr}(u_{i},u_{p})$ that
$u_{i}$ and $u_{p}$ have the same answer to a random task, that is,

$\pi(u_{i},t)=\beta\cdot(\mathbf{1}(\widehat{y}=\widehat{y}_{p})-\text{Pr}(u_{i},u_{p})),$
(6)

where $\beta$ is a non-negative payment scaling parameter that is chosen to
cover workers’ effort costs, and $\text{Pr}(u_{i},u_{p})$ is approximated from
the submitted labels. The total payment to a worker $u_{i}$ is the sum of
$u_{i}$’s payment for each task.

The pricing model incentivizes efforts, as the expected payment for spammers
who do not solve their tasks and report random/constant labels is exactly
zero. Under the assumption that the proficiency of all workers are better than
random guess, it is shown that the DG model is incentive compatible. Even
though the pricing model also has non-informive equilibria, such as all
workers reporting the same label, those equilibria are less profitable to the
workers, and thus are not attractive to the workers.

In a multi-label situation, two labels $l_{1}$ and $l_{2}$ may be positively
correlated. Shnayder et al. (2016a) show that under the DG model (Dasgupta and
Ghosh, 2013), workers can achieve more profits by misreporting $l_{1}$ by
$l_{2}$. The correlated agreement (CA) mechanism (Shnayder et al., 2016a)
extends the DG model to multi-label tasks. In the CA mechanism, knowledge
about label correlation is required. A label correlation matrix $\Delta$ is
learned from workers’ submissions, where an element
$\Delta_{i,j}=\text{Pr}(l_{i},l_{j})-\text{Pr}(l_{i})\text{Pr}(l_{j})$ is the
correlation degree between labels $l_{i}$ and $l_{j}$. Denote by $S(\cdot)$
the sign function of $\Delta$, that is, $S(l_{i},l_{j})=1$ if
$\Delta_{i,j}>0$, and $0$ otherwise. A worker $u$ will be rewarded for a task
$t$ if $u$’s report is positively correlated with that of peer $u_{p}$. To
penalize the case where all workers blindly report the same label, a worker
$u$ will be penalized if $u$ is likely to be consistent with worker $u_{p}$ on
random tasks. In particular, the payment to worker $u$ for reporting $\hat{y}$
is

$\pi(u,t)=\beta\cdot(S(\widehat{y},\widehat{y}_{p})-S(\widehat{y}_{a},\widehat{y}_{b})),$

where $\hat{y}_{p}$ is the answer to task $t$ by worker $u_{p}$,
$\widehat{y}_{a}$ is the answer to a random task by worker $u$, and
$\widehat{y}_{b}$ is the answer to another random task by worker $u_{p}$. When
the number of tasks is large, such that label correlations $\Delta$ can be
accurately learned, the CA mechanism is incentive compatible with the highest
payment. However, the mechanism fails if two labels $l_{1}$ and $l_{2}$ are
not distinguishable with respect to $S(\cdot)$, that is, $\forall l_{i}\in Y$,
$S(l_{1},l_{i})=S(l_{2},l_{i})$. In this situation, workers may misreport
$l_{1}$ by $l_{2}$ and still receive the same payoffs.

Radanovic et al. (2016) provide complementary theoretical results on pricing
multi-label tasks. They assume that the labels only have limited correlations,
that is, $\text{Pr}(o_{p}=l_{2}|o=l_{1})<\text{Pr}(o_{p}=l_{2}|o=l_{2})$,
where $o$ and $o_{p}$ are the observed labels of worker $u$ and worker
$u_{p}$, respectively. The mechanism pays the report $\widehat{y}$ by worker
$u$ on a task $t$ by

$\pi(u,t)=\frac{\mathbf{1}(\widehat{y}=\widehat{y}_{p})}{\text{R}(\widehat{y})}-1,$

where $\text{R}(\widehat{y})$ is the empirical frequency of $\widehat{y}$,
which is computed from all submissions. It is shown that exerting high efforts
and truthful reporting is strictly more profitable than any other equilibria.
However, their assumptions on label correlations may not hold in some
applications (Shnayder et al., 2016a).

The aforementioned methods (Dasgupta and Ghosh, 2013; Shnayder et al., 2016a;
Radanovic et al., 2016) require that each task must be completed by at least
two workers, which leads to duplicate answers, and thus does not use the crowd
efficiently. For a setting with binary labels, Liu and Chen (2017a) propose to
learn a classifier $\mathcal{M}$ from workers’ reports, and use the
classifier’s predictions $\mathcal{M}(t)$ as peer reports. Since workers’
submitted labels are noisy, the classifier is trained by the techniques of
learning with noisy labels (Natarajan et al., 2013). Specifically, they first
estimate the error rates of submitted labels. Then, the classifier is
optimized by an error rate calibrated loss function $\varphi(\cdot)$ proposed
by Natarajan et al. (2013). A report $\widehat{y}$ to a task $t$ is priced
based on $-\varphi(\mathcal{M}(t),\widehat{y})$, such that labels with large
loss are priced lower. Under the assumption that $\mathcal{M}$ is better than
random guess, exerting efforts to find the truth labels is the highest-paying
equilibrium.

Liu and Chen (2017b) study the problem of sequential label collection, where
labeling tasks are published in multiple rounds. In their settings, an
accurately labeled task has a fixed reward to a data buyer, whereas a
mistakenly labeled task has no value to a data buyer. They propose an
incentive compatible pricing model that maximizes the expected utility for a
data buyer, which is the difference between the total rewards and the total
payment.

They develop a multi-armed bandit algorithm to extend the DG model (Dasgupta
and Ghosh, 2013), which dynamically adjusts the parameter $\beta$ in Equation
6. A larger $\beta$ encourages more accurate labels but costs more money. As
the bandit algorithm requires a static environment, this method may fail to
learn the optimal $\beta$ if adversarial workers adjust their strategies
according to their interactions with the mechanism (Hu et al., 2018; Gur et
al., 2014). Hu et al. (2018) solve the problem by reinforcement learning,
which is more robust to strategic behaviors of workers.

In practice, peer prediction-based models need to adjust payments to avoid
negative payments. The adjustment may lead to an issue that spammers may
receive positive and high rewards. Radanovic and Faltings (2016) address the
issue by proposing a reputation system PropeRBoost to adjust the payments.
PropeRBoost publishes tasks to workers in multiple rounds, and computes a
reputation score for each worker based on the worker’s past submissions. In
each round $r$, it first applies the DG model (Dasgupta and Ghosh, 2013) to
compute workers’ payments, and then re-scales the payments by the reputations
of the corresponding workers. It is shown that the average payment of a
spammer converges to $0$ as $r$ approaches infinity.

In this section, we review gold task-based and peer prediction-based pricing
models for data labels. The developed pricing models guarantee that exerting
efforts to report accurate data labels is the most profitable strategy of all
workers. A major concern of gold task-based methods is that these methods
require a sufficient number of gold tasks to obtain good performance. In some
scenarios, however, gold tasks are very expensive to obtain. For peer
prediction-based methods, the existence of multiple equilibria is a major
limitation, as workers may converge to an uninformative equilibrium, where
workers do not exert full efforts (Shnayder et al., 2016b).

##  5 Pricing in Collaborative Training of Machine Learning Models

Collaborative machine learning is an appealing paradigm where multiple data
owners collaboratively build high-quality machine learning models by
contributing their data. As the data sets from different data owners may have
different contributions to the trained machine learning models, data owners
who contribute more valuable data should receive more rewards (Sim et al.,
2020). In this section, we review contribution evaluation and revenue
allocation techniques in collaborative machine learning.

###  5.1 Revenue Allocation by Shapley Value

Shapley fairness is widely adopted as the foundation of fair revenue
allocation in collaborative machine learning. It guarantees that each
participant receives a payment proportional to the participant’s marginal
contribution to the performance of the trained machine learning model. The
challenge in adopting Shapley value lies in its exponential computational
cost.

Maleki et al. (2013) tackle the efficiency issue of Shapley value by proposing
a permutation sampling algorithm for bounded utility functions. By Equation 2,
the Shapley value of a seller is the marginal utility contribution averaged
over all possible subsets of sellers, which can be estimated by sample mean.
Denote by $\widehat{\psi}(s)$ an $(\epsilon,\delta)$-approximator of a
seller’s Shapley value, that is,
$\text{Pr}(|\widehat{\psi}(s)-\psi(s)|\leq\epsilon)\geq 1-\delta$. To compute
the estimators for all sellers, by Hoeffding’s inequality (Hoeffding, 1994),
we need $O(\frac{2r^{2}N}{\epsilon^{2}}\log\frac{2N}{\delta})$ samples and
evaluate the utility function $O(N^{2}\log N)$ times, where $N$ is the number
of sellers and $r$ is the range of the utility function. Evaluating the
utility function itself, such as computing testing accuracy, is
computationally expensive, as it requires training a machine learning model.
Therefore, the method is not scalable to a large number of sellers.

Ghorbani and Zou (2019) extend the Monte-Carlo method by Maleki et al. (2013)
to price individual data point in supervised learning, and propose truncated-
based and gradient-based approximation methods. Their truncated-based method
reduces the number of utility evaluations by ignoring coalitions of large
size. The authors argue that it is sufficient to estimate Shapley values up to
the intrinsic noise in the prediction performance $\mathcal{U}$ on the test
data set, which can be measured as the bootstrap variance of $\mathcal{U}$. In
addition, the performance change by adding one more training data point $s$ to
a large training data set $S$ is ignorably small. Therefore, if the utility of
$S$ is close to the utility of the whole data set $D$, the marginal
contribution of $s$ to $S$ can be regarded as $0$ in practice, and thus its
computation can be truncated. Their gradient-based method speeds up the
evaluation of utility functions by reducing training time, where a model is
trained with only one pass through the training data. They update the model by
performing gradient descent on one data point $s$ at a time and the marginal
contribution of $s$ is the change in the model performance. The two
approximation methods introduce estimation bias into the approximated Shapley
values, and have no guarantees on the approximation error.

Jia et al. (2019b) propose two approximation algorithms with provable error
bounds for Shapley value that significantly reduce the number of utility
evaluations. The first algorithm adopts the idea of group testing in feature
selection (Zhou et al., 2014). Denote by $\beta_{i}$ a Boolean random variable
indicating whether a seller $s_{i}$ is in a random sample of sellers. A
sampling distribution of $\beta_{1},\ldots,\beta_{N}$ is designed such that
the difference in Shapley values between a seller $s_{i}$ and a seller $s_{j}$
is

$\displaystyle\psi(s_{i})-\psi(s_{j})$
$\displaystyle=\frac{1}{N-1}\sum_{S\subseteq
D\setminus\\{s_{i},s_{j}\\}}\frac{\mathcal{U}(S\cup\\{s_{i}\\})-\mathcal{U}(S\cup\\{s_{j}\\})}{{N-2\choose|S|}}$
$\displaystyle=\text{E}[(\beta_{i}-\beta_{j})\mathcal{U}(\beta_{1},\ldots,\beta_{N})],$

where $\mathcal{U}(\beta_{1},\ldots,\beta_{N})$ is the utility evaluated on
the appearing sellers and $D$ are all sellers. The Shapley value of sellers
can be derived from the estimated Shapley differences between all datum pairs
by solving a feasibility problem. They demonstrate that the algorithm returns
an $(\epsilon,\delta)$-approximation with $O(N(logN)^{2})$ utility
evaluations. The second algorithm is based on their observation that Shapley
values are approximately sparse, that is, most values are around the mean.
Exploiting this property, they apply the idea of sparse signal recovering in
compressive sensing (Rauhut, 2010), and develop an algorithm that produces an
$(\epsilon,\delta)$-approximation with only $O(N\log(\log(N)))$ utility
evaluations.

Jia et al. (2019a) further discover that Shapley values for data points used
in unweighted kNN classifiers can be computed exactly only in $O(N\log N)$
time. Given a testing point $x_{test}$ with label $y_{test}$, they define the
utility of a kNN classifier as the likelihood of $y_{test}$, that is,

$\mathcal{U}(S)=\frac{1}{k}\sum_{i=1}^{\text{min}(k,|S|)}\mathbf{1}(y_{\alpha_{i}(S)}=y_{test}),$

where $\alpha_{i}(S)$ is the index of the training data that is the $i$-th
closest to $x_{test}$ in the set of data points $S$. The special utility
function enables efficient computation of Shapley differences between two data
points $x_{\alpha_{i}(S)}$ and $x_{\alpha_{i+1}(S)}$, that is,

$\psi(x_{\alpha_{i}(S)})-\psi(x_{\alpha_{i+1}(S)})=\frac{\mathbf{1}(y_{\alpha_{i}(S)}=y_{test})-\mathbf{1}(y_{\alpha_{i+1}(S)}=y_{test})}{k}\frac{\text{min}(i,k)}{i}.$
(7)

They start by computing
$\psi(x_{\alpha_{N}(S)})=\frac{\mathbf{1}(y_{\alpha_{N}(S)}=y_{test})}{N}$ and
then exploiting Equation 7 to recursively compute the Shapley values in the
order of $x_{\alpha_{N}(S)},\ldots,x_{\alpha_{1}(S)}$. They further develop an
$(\epsilon,\delta)$-approximation algorithm based on Locality Sensitive
Hashing (Datar et al., 2004) with only sublinear complexity. The major idea is
to only compute Shapley values for the retrieved
$k^{*}=\text{max}(k,\frac{1}{\epsilon})$ nearest neighbors of $x_{test}$ and
ignore the rest data points, as their Shapley values are too small. Moreover,
they present a Monte-Carlo approximation algorithm with
$O(\frac{N}{\epsilon^{2}}\log(k)\log(\frac{k}{\delta}))$ time complexity for
weighted kNN classifiers.

The aforementioned studies (Jia et al., 2019a, b; Ghorbani and Zou, 2019)
evaluate the utility of a model by its performance on a validation data set.
Sim et al. (2020) consider the situation where no validation data sets are
available, and propose to use information gain on model parameters as the
utility function. Denote by $\theta$ the model parameters. After training on
data $D$, the information gain $\text{IG}(\theta)=H(\theta)-H(\theta|D)$ is
the reduction in the uncertainty of $\theta$, where $H(\cdot)$ is the entropy
function. In addition to Shapley fairness, three additional incentive
conditions for revenue allocation are proposed, namely individual rationality,
stability of the grand coalition, and group welfare. They also present
$p$-Shapley fairness, which assigns a reward $\pi(s_{i})=k\psi(s_{i})^{p}$ to
a seller $s_{i}$. By tuning parameter $p\in[0,1]$, they can trade off between
achieving different incentive conditions. Rather than monetary incentives,
each participant receives a machine learning model as a reward. To realize
different levels of rewards, the models are trained by injecting different
levels of noise into training labels.

Federated Learning (Brendan and Daniel, 2017; McMahan et al., 2017) enables
multiple decentralized participants to collaboratively train a machine
learning model while keeping their training data locally. The data sets
contributed by the participants are used in a sequential order determined by a
central server. Evaluating participants’ contributions using Shapley value
incurs high communication costs among the decentralized participants.
Moreover, Shapley value neglects the order of data sources. To accommodate the
challenges, Wang et al. (2020) propose federated Shapley value. Denote by
$\mathcal{U}(s_{i}+s_{j})$ the utility of the model, which is trained on
$s_{i}$’s data first, then on $s_{j}$’s data. Let $I_{t}$ be the set of
selected participants in round $t$ of the federated learning process. The
federated Shapley value of participant $s_{i}$ at round $t$ is defined as
follows.

$\psi_{t}(s_{i})=\begin{cases}\frac{1}{|I_{t}|}\sum_{S\subseteq
I_{t}\setminus\\{s_{i}\\}}\frac{\mathcal{U}(I_{1:t-1}+(S\cup\\{s_{i}\\}))-\mathcal{U}(I_{1:t-1}+S)}{{|I_{t}|-1\choose|S|}}&\text{if
$s_{i}\in I_{t}$}\\\ 0&\text{if $s_{i}\notin I_{t}$}\\\ \end{cases}$ (8)

The federated Shapley value of $s_{i}$ is
$\psi(s_{i})=\sum_{t=1}^{T}\psi(s_{i})$, where $T$ is the total rounds in
federated learning. The authors show that federated Shapley values satisfy the
balance and additivity axioms of Shapley fairness. The other two axioms,
symmetry and zero element, are satisfied in each round. They extend the
permutation sampling and group testing approximation methods (Jia et al.,
2019b) to compute federated Shapley values.

Participants in federated learning spend some costs for contributing their
data sets, such as privacy cost Hu and Gong (2020) and energy costs Kang et
al. (2019). Yu et al. (2020a) propose a fair revenue allocation mechanism for
federated learning that jointly considers the costs and contributions of
participants. At round $t$, each participant $s_{i}$ has a public cost
$c_{i}(t)$ and receives a reward $\pi_{i}(t)$. The regret $r_{i}(t)$ of
$s_{i}$ is a function of the difference between the total cost and total
reward of $s_{i}$. A large value of $r_{i}(t)$ indicates that $s_{i}$ is not
well compensated for the costs incurred to $s_{i}$. The authors argue that the
payments of participants at each round should achieve contribution fairness
and regret fairness. Contribution fairness requires that the payment
$\pi_{i}(t)$ and the Shapley value $\psi_{t}(s_{i})$ of each participant
$s_{i}$ should be positively correlated, that is,
$\sum_{i}\pi_{i}(t)\psi_{t}(s_{i})$ should be maximized. Regret fairness
requires that the participants should have similar regrets, that is, the
difference of the regrets among participants should be minimized. The payments
of participants are determined by solving an optimization problem with respect
to a budget constraint. Theoretically, they show that the time-averaged regret
of participants is upper-bounded by a constant value as $t\rightarrow\infty$.

Shapley value is vulnerable to data-replication attacks. A data provider may
replicate his/her data with zero cost and acts as an additional provider to
get extra unconscionable rewards. Agarwal et al. (2019) address the issue by
penalizing similar data sets to disincentivize replication, that is, the
replication-robust Shapley value is defined as

$\psi_{r}(s_{i})=\psi(s_{i})e^{-\lambda\sum_{s_{j}\in
D\setminus\\{s_{i}\\}}\text{SM}(s_{i},s_{j})},$

where SM is a similarity metric and $\lambda$ is a constant. However, the
proposed replication-robust Shapley value no longer satisfies the balance
axiom in Shapley fairness.

Han et al. (2020) study the replication attack in data markets with submodular
utility functions. They show that the total reward received by an attacker
increases monotonically with respect to the number of the attacker’s
replications. They discover that the extra reward to the attacker mainly comes
from the marginal contributions to small seller groups by the attacker’s
replication. To fix the issue, the authors propose to down-weigh those
contributions when computing Shapley values. Their method guarantees that
attackers receive smaller rewards with more replications.

Ohrimenko et al. (2019) design a replication robust collaborative data market,
where each participant is asked to pay a participation fee. This method
discourages replication, as the extra reward received by an attacker cannot
cover the attacker’s participation cost.

###  5.2 Other Revenue Allocation Methods

There are some other revenue allocation methods in collaborative machine
learning other than Shapley value.

Leave-one-out (Cook and Weisberg, 1980) is a commonly used method to evaluate
data importance. It compares the performance of a model trained on the full
data set with the performance trained on the full set minus one point. The
performance drop is defined as the value of the data point, that is,
$\pi(s_{i})=\mathcal{U}(D)-\mathcal{U}(D\setminus\\{s_{i}\\})$. Leave-one-out
is often approximated by influence function (Cook and Weisberg, 1980; Koh and
Liang, 2017), which measures how the model changes as the weight of a training
point is changed without retraining the model. Richardson et al. (2020) apply
an influence function to reward participants in federated learning for their
contributed data points. It is shown that the pricing model is incentive
compatible. Applying influence functions to price data points are also
investigated in (Richardson et al., 2019; Jia et al., 2019b). Comparing with
Shapley value, leave-one-out methods, in general, are more efficient as they
do not require model retraining. However, leave-one-out methods may not
accurately assess the values of data points. The methods may assign a low
value to one of the two exactly equivalent data points, regardless of how
important the datum is, as high performance may still be achieved by including
the other datum (Yoon et al., 2020).

Yan and Procaccia (2021) design a data pricing model based on core (Gillies,
1959), which is a celebrated revenue allocation solution in cooperative game
theory. The solution seeks to achieve maximum stability of how participants
team up with each other. Core requires that the total reward of each coalition
$S$ should be at least equal to the utility $\mathcal{U}(S)$, that is,
$\forall S\subseteq D,\sum_{s_{i}\in S}\pi(s_{i})\geq\mathcal{U}(S)$, where
$\pi(s_{i})$ is the reward of participant $s_{i}$ and $D$ is the set of all
participants. When such a reward cannot be achieved, least core relaxes the
constraints by allowing a minimum difference $\epsilon$ between the utility of
$S$ and the total reward of $S$. In particular, least core computes the
payment to each participant by solving the following linear program.

$\displaystyle\begin{split}\text{min}\ &\epsilon\\\ \text{s.t.
}&\sum_{s_{i}\in D}\pi(s_{i})=\mathcal{U}(D),\\\ &\sum_{s_{i}\in
S}\pi(s_{i})+\epsilon\geq\mathcal{U}(S)\ \forall S\subseteq D.\end{split}$ (9)

The number of constraints in Equation 9 grows exponentially with respect to
the number of participants. Yan and Procaccia (2021) tackle the efficiency
issue by proposing a Monte Carlo approximation algorithm with guaranteed
approximation errors. Their approximation method samples a relatively small
number of coalitions and solves Equation 9 on the sampled coalitions. If
Equation 9 has multiple solutions, the solution with the smallest $l_{2}$-norm
is chosen. Their revenue allocation satisfies the balance, symmetry, and zero
element axioms of Shapley fairness.

Yoon et al. (2020) propose a reinforcement learning algorithm to value data
points. They learn a data value estimator that estimates data values and
selects the most valuable samples to train a target classifier. They jointly
learn the data value estimator and the corresponding classifier, which enables
the classifier and the data value estimator to improve the performance of each
other. However, this method cannot guarantee fair revenue distribution among
participants.

Most of the existing revenue allocation methods are developed in the settings
that supervised machine learning models are jointly trained. The participants
are rewarded based on the contributions of their data sets to the utility of
the jointly trained machine learning model. To adapt existing pricing models
to scenarios where unsupervised machine learning models are jointly trained,
the major challenge is to develop a utility function that participants can all
agree on. For some traditional unsupervised machine learning models, there are
some widely accepted performance metrics that can serve as the utility
functions. For example, Silhouette Coefficient Rousseeuw (1987) and Calinski-
Harabasz index Caliński and Harabasz (1974) are widely used to evaluate the
performance of clustering algorithms when ground-truth clusters are unknown.
However, developing a utility function for some unsupervised models, such as
pre-trained deep language models Devlin et al. (2019); Brown et al. (2020),
may be challenging, as they are evaluated differently in many down-stream
machine learning tasks.

In this section, we review pricing models in collaborative training of machine
learning models. The major idea is to price each participant’s data set based
on its contribution to the performance of the jointly trained machine learning
model. Shapley value-based methods guarantee fair revenue distribution among
participants, but suffer from poor computational efficiency and scalability.
Some alternative methods (Yoon et al., 2020; Yan and Procaccia, 2021) enjoy
better efficiency or coalition stability, but lose fairness guarantee.

##  6 Pricing Machine Learning Models

Machine learning models are needed in many different applications and
scenarios. Rather than building machine learning models from scratch, many
users and companies turn to purchase well-trained machine learning models, due
to their lack of expertise and computation resources (Yu et al., 2020b; Chen
et al., 2019). In this section, we review pricing models for machine learning
models and discuss the differences between pricing machine learning models and
raw data sets.

###  6.1 Pricing Models

Pricing machine learning models is an emerging research area. To the best of
our knowledge, the existing studies mainly focus on arbitrage-free and revenue
maximization pricing.

Chen et al. (2019) propose an arbitrage-free and revenue maximization machine
learning model marketplace. In their setting, a model owner sells multiple
versions of a machine learning model to different buyers. The seller first
trains an optimal model on the whole raw data set. Then, the seller produces
different versions of the optimal model by adding Gaussian noises with
different variances to the parameters of the optimal model. The expected error
rates of the generated model instances are monotonically increasing with
respect to the variance of the injected noise. An arbitrage-free pricing
function guarantees that a buyer cannot derive a high performance model by
paying less. Under their mechanism, a pricing function is arbitrage-free if
and only if the function is monotone and subadditive with respect to the
inverse of the noise variance. Unfortunately, their pricing model only works
for machine learning models trained with strictly convex objective functions.

Chen et al. (2019) further study revenue maximization in pricing machine
learning models with respect to the demands and valuations of a set of buyers.
They show that determining the optimal prices is coNP-hard. To overcome the
computational hardness, they relax the subadditive constraints
$\pi(x+y)\leq\pi(x)+\pi(y)$ by
$\frac{\widehat{\pi}(x)}{x}\leq\frac{\widehat{\pi}(y)}{y}$, where $x\leq y$
and $\widehat{\pi}$ is an approximation of the optimal pricing function $\pi$.
They show that $\widehat{\pi}$ is arbitrage-free and $\forall x>0$,
$\pi(x)/2\leq\widehat{\pi}(x)\leq\pi(x)$. They propose a dynamic programming
algorithm to compute $\widehat{\pi}$ in $O(n^{2})$ time, where $n$ is the
number of model versions.

Liu et al. (2021) present an end-to-end model marketplace, which jointly
considers data owners’ privacy costs and model buyers’ demands. A broker
collects data from data owners, and produces multiple versions of a machine
learning model for sale with different subsets of training data and different
differential privacy levels $\epsilon$. The revenues are fully distributed to
data owners. Objective perturbation (Chaudhuri et al., 2011) is used to train
models with required differential privacy levels, which injects quantified
random noise into the objective function of a model. Each data owner $s_{i}$
requests a minimum compensation for using the owner’s data to train a model
with $\epsilon$-differential privacy, that is

$\pi(s_{i},\epsilon)=b_{i}\cdot c_{i}(\epsilon),$

where $b_{i}$ is proportional to the Shapley value of $s_{i}$ with regard to
all sellers’ data sets and $c_{i}(\epsilon)$ is the privacy cost of $s_{i}$. A
desirable pricing model should guarantee revenue maximization, arbitrage-
freeness with respect to differential privacy levels, and covers the
compensations to data owners. Computing the optimal pricing function is coNP-
hard, and thus they propose a dynamic programming algorithm to solve the
problem approximately. A limitation of the pricing model is that it cannot
adjust prices with respect to dynamic customer demands, which may limit the
broker’s revenue.

Agarwal et al. (2019) consider an online auction for machine learning model
market, which is truthful and revenue maximizing. They assume buyers come one
at a time, and each wants to purchase a machine learning model for the buyer’s
prediction task. Denote by $\mathcal{G}(\widehat{Y}_{i},Y_{i})$ the quality of
a model’s prediction $\widehat{Y}_{i}$ on buyer $i$’s validation data set
$Y_{i}$. The reward that buyer $i$ receives from the model is
$\mu_{i}\cdot\mathcal{G}(\widehat{Y}_{i},Y_{i})$, where $\mu_{i}$ is buyer
$i$’s private valuation on unit performance. Denote by $p_{i}$ and $b_{i}$,
respectively, the asking price of the broker and the bid of buyer $i$ for unit
performance. The broker produces a noisy machine learning model for buyer $i$
based on the price difference $p_{i}-b_{i}$. Specifically, the model is
trained on a data set with quantified injected random noise, such that the
model’s performance is degraded proportionally to $p_{i}-b_{i}$. Buyer $i$ is
charged by a function $RF(p_{i},b_{i},Y_{i})$, which is designed following
Myerson’s payment function rule (Myerson, 1981). The utility that buyer $i$
receives by bidding $b_{i}$ is

$\mathcal{U}(b_{i})=\mu_{i}\cdot\mathcal{G}(\widehat{Y}_{i},Y_{i})-RF(p_{i},b_{i},Y_{i}),$

where $\widehat{Y}_{i}$ is the prediction of the returned noisy model. It is
shown that truthfully bidding the buyer’s valuation $\mu_{i}$ can maximize
buyer $i$’s utility. The authors apply a Multiplicative Weights method (Arora
et al., 2012) to compute the price $p_{i}$ from historical revenues. They show
that the pricing mechanism achieves maximum revenue.

###  6.2 Pricing Raw Data Products Versus Machine Learning Models

At a high level, pricing machine learning models and raw data sets share a
series of common desiderata and techniques. But their pricing models are
essentially different from each other on at least four aspects.

First, the pricing units of machine learning models are often well defined and
fixed. A machine learning model is usually priced and sold as a whole.
Customers can purchase either a machine learning model or the usage of a
machine learning model via API calls, where each call has a fixed price. In
contrast, a raw data set can be consumed in multiple granularities. For
example, a customer may be interested in the sales information of American
customers in the last year. Another customer, however, may want to purchase
the sales information during the Christmas season. Such flexibility makes it
easier to version raw data products, and enables more flexible pricing
mechanisms. For example, according to how much information is revealed,
different prices can be assigned to different queries on the same database
(Deep and Koutris, 2017b).

Second, versioning in model markets is harder than that in data markets. As
data sets have strong and flexible aggregateability, different versions of a
data set can be easily produced by aggregating along different dimensions.
Producing different versions of a machine learning model requires more
sophisticated techniques (Chen et al., 2019), since it is challenging to
accurately control the differences between multiple versions.

Third, the value of raw data sets to customers is generally harder to measure
than that of machine learning models. Often, raw data sets are used to train
machine learning models. The ultimate value of a data set dependents not only
on its intrinsic properties but also on the specific task that the data set is
used for and the analyzing methods (Fernandez et al., 2020). Therefore, it is
usually hard for customers to understand the value of a data set. Many machine
learning models are designed for specific tasks and are directly used by
people to support decision making (Agarwal et al., 2019). It is easier for
people to verify and understand the value of such machine learning models. For
example, customers can value a classification model based on its prediction
accuracy.

Last, preventing arbitrage is usually harder in model market than in raw data
market. As shown by Tramèr et al. (2016); Yu et al. (2020b), machine learning
models may be stolen by adversaries via a reasonable number of API calls. A
customer with a large number of query instances may first purchase some
predictions from a target machine learning model. Then, the customer can train
a local model with near-equivalent outputs as the target model and use the
local model to predict the remaining query instances with almost no cost.

In this section, we review pricing machine learning models. We first revisit
arbitrage-free and revenue maximization pricing models. Then, we discuss
several major differences between machine learning model products and raw data
set products, including pricing units, versioning, arbitrage prevention, and
customer valuation.

##  7 Conclusions and Future Directions

In this paper, we survey data pricing in end-to-end machine learning
pipelines. We consider three important steps in machine learning pipelines
where pricing may be substantially involved, namely raw data collection and
labeling, collaborative training machine learning models, and machine learning
model marketplaces. We systematically review representative studies in those
steps, discuss the pricing principles and review the existing methods. End-to-
end machine learning pipelines are playing a more and more important role in
the current big data and AI economics era. To the best of our knowledge, this
is the first survey on data pricing in machine learning pipelines.

Data pricing is still in its early stage. There are many research challenges
for future works. We list some of them here.

First, the existing studies focus on designing proper rewarding models in each
separate stage of machine learning pipelines. There is a lack of systematic
study of an end-to-end revenue allocation solution. As presented in our
survey, the manufacturing process of machine learning models involves multiple
parties, including data owners, data processors, machine learning model
designers, and other possible participants. Each party provides value-added
contributions at one stage of the pipeline and receives a reward. A natural
question is how to allocate manufacturing budgets among different parties. To
answer the question, we need a mechanism to measure and compare the
contributions of different parties in different stages. We also need a system
that can dynamically adjust the budget allocations in response to the changes
in supply and demand.

Second, almost all pricing models of collaborative model training formulate
revenue allocation as a cooperative game, and use Shapley value to carry out
the allocation. They justify the usage of Shapley value through the four
axioms, namely balance, symmetry, zero element, and additivity. However, Yan
and Procaccia (2021) argue that the necessity of additivity for data valuation
is debatable. Except for the additivity axiom, many other celebrated
allocation solutions in cooperative game theory can also satisfy the other
three axioms. Comparing with Shapley value, the other solutions have their
advantages and limitations. For example, normalized Banzhaf value
(Chalkiadakis et al., 2011) computes the payment to each player as the
player’s average marginal contribution towards all coalitions of other
players. Even though normalized Banzhaf value does not satisfy the additivity
axiom, it is more robust to data replication attacks than Shapley value (Han
et al., 2020). In a marketplace where robustness is more important than
additivity, normalized Banzhaf value is more preferable than Shapley value.
Different types of data marketplaces may have different goals (Fernandez et
al., 2020), and thus require different axioms. Therefore, we need a better
understanding about the necessary axioms in different marketplaces and explore
revenue allocation solutions in specific marketplaces.

Third, fine-grained data procurement for machine learning tasks is not fully
explored. In practice, data sets from two sellers may have similar or
overlapping parts. A data buyer with a limited budget may not want to purchase
many similar data points, as the diversity of training data sets is critical
to the performance of machine learning models (Fernandez et al., 2020). Query-
based pricing models (Koutris et al., 2012) allow data buyers to only purchase
their interested parts of a data set. However, the existing query-based
pricing models are only designed for relational data sets in monopoly markets.
Supporting query-based pricing in marketplaces of general data sets with
competing sellers brings new challenges and opportunities. For example, it is
interesting for data buyers to explore how to distribute their budgets among
data sellers to maximize the utility of purchased data sets. For data sellers,
it is important to assign prices to different parts of their data sets based
on supply and demand, such that the data sellers and their data sets can
remain competitive in the market.

Last, rigorous evaluation methods for data pricing models need to be
developed. Many existing pricing models are only evaluated in oversimplified
experimental environments, where many assumptions are made on the behaviors of
market participants. A theoretically sound model, however, may not work in
practice, as some model assumptions may break. For example, in a real-world
market, participants can have adversarial, ignorant, or coalition-building
behaviors. However, the effects of those behaviors on the performance of
pricing models are largely dismissed in detailed analysis. Therefore, as
suggested by Fernandez et al. (2020), a simulation platform that can simulate
different behaviors of market participants should be developed. The platform
can help us study the advantages and limitations of pricing models in target
environments, and choose the best one to deploy.

## References

  * Agarwal et al. (2019) Agarwal A, Dahleh MA, Sarkar T (2019) A marketplace for data: An algorithmic solution. In: Karlin A, Immorlica N, Johari R (eds) Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, ACM, pp 701–726, DOI 10.1145/3328526.3329589, URL https://doi.org/10.1145/3328526.3329589
  * de Alfaro et al. (2016) de Alfaro L, Faella M, Polychronopoulos V, Shavlovsky M (2016) Incentives for truthful evaluations. CoRR abs/1608.07886, URL http://arxiv.org/abs/1608.07886, 1608.07886
  * Arora et al. (2012) Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: a meta-algorithm and applications. Theory Comput 8(1):121–164, DOI 10.4086/toc.2012.v008a006, URL https://doi.org/10.4086/toc.2012.v008a006
  * Ausubel et al. (2006) Ausubel LM, Milgrom P, et al. (2006) The lovely but lonely vickrey auction. Combinatorial auctions 17:22–26
  * Balasubramanian et al. (2015) Balasubramanian S, Bhattacharya S, Krishnan VV (2015) Pricing information goods: A strategic analysis of the selling and pay-per-use mechanisms. Marketing Science 34(2):218–234
  * BDEX (2021) BDEX (2021) Bdex. https://www.bdex.com, accessed: 2021-05-09
  * Brendan and Daniel (2017) Brendan M, Daniel R (2017) Federated learning: Collaborative machine learning without centralized training data. Google AI Blog URL https://ai.googleblog.com/2017/04/federated-learning-collaborative.html, accessed: 2021-07-02
  * Brennan et al. (2013) Brennan R, Canning L, Mcdowell R (2013) Business-to-business marketing. Sage Publications, DOI 10.4135/9781446276518
  * Brown et al. (2020) Brown TB, Mann B, Ryder N, Subbiah M, Kaplan J, Dhariwal P, Neelakantan A, Shyam P, Sastry G, Askell A, Agarwal S, Herbert-Voss A, Krueger G, Henighan T, Child R, Ramesh A, Ziegler DM, Wu J, Winter C, Hesse C, Chen M, Sigler E, Litwin M, Gray S, Chess B, Clark J, Berner C, McCandlish S, Radford A, Sutskever I, Amodei D (2020) Language models are few-shot learners. In: Larochelle H, Ranzato M, Hadsell R, Balcan M, Lin H (eds) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, URL https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html
  * Buneman and Tan (2007) Buneman P, Tan WC (2007) Provenance in databases. In: Chan CY, Ooi BC, Zhou A (eds) Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007, ACM, pp 1171–1173, DOI 10.1145/1247480.1247646, URL https://doi.org/10.1145/1247480.1247646
  * Burkett (2006) Burkett JP (2006) Microeconomics: Optimization, Experiments, and Behavior. OUP Catalogue, Oxford University Press, New York
  * Caliński and Harabasz (1974) Caliński T, Harabasz J (1974) A dendrite method for cluster analysis. Communications in Statistics-theory and Methods 3(1):1–27
  * Chalkiadakis et al. (2011) Chalkiadakis G, Elkind E, Wooldridge MJ (2011) Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, DOI 10.2200/S00355ED1V01Y201107AIM016, URL https://doi.org/10.2200/S00355ED1V01Y201107AIM016
  * Chaudhuri et al. (2011) Chaudhuri K, Monteleoni C, Sarwate AD (2011) Differentially private empirical risk minimization. J Mach Learn Res 12:1069–1109, URL http://dl.acm.org/citation.cfm?id=2021036
  * Chawla et al. (2019) Chawla S, Deep S, Koutris P, Teng Y (2019) Revenue maximization for query pricing. Proc VLDB Endow 13(1):1–14, DOI 10.14778/3357377.3357378, URL http://www.vldb.org/pvldb/vol13/p1-chawla.pdf
  * Chen et al. (2019) Chen L, Koutris P, Kumar A (2019) Towards model-based pricing for machine learning in a data marketplace. In: Boncz PA, Manegold S, Ailamaki A, Deshpande A, Kraska T (eds) Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, ACM, pp 1535–1552, DOI 10.1145/3299869.3300078, URL https://doi.org/10.1145/3299869.3300078
  * Chen et al. (2020) Chen L, Zaharia M, Zou JY (2020) Frugalml: How to use ml prediction apis more accurately and cheaply. Advances in Neural Information Processing Systems 33
  * Cook and Weisberg (1980) Cook RD, Weisberg S (1980) Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics 22(4):495–508, DOI 10.1080/00401706.1980.10486199, URL https://www.tandfonline.com/doi/abs/10.1080/00401706.1980.10486199, https://www.tandfonline.com/doi/pdf/10.1080/00401706.1980.10486199
  * Dandekar et al. (2012) Dandekar P, Fawaz N, Ioannidis S (2012) Privacy auctions for recommender systems. In: Goldberg PW (ed) Internet and Network Economics - 8th International Workshop, WINE 2012, Liverpool, UK, December 10-12, 2012. Proceedings, Springer, Lecture Notes in Computer Science, vol 7695, pp 309–322, DOI 10.1007/978-3-642-35311-6“˙23, URL https://doi.org/10.1007/978-3-642-35311-6_23
  * Dasgupta and Ghosh (2013) Dasgupta A, Ghosh A (2013) Crowdsourced judgement elicitation with endogenous proficiency. In: Schwabe D, Almeida VAF, Glaser H, Baeza-Yates R, Moon SB (eds) 22nd International World Wide Web Conference, WWW ’13, Rio de Janeiro, Brazil, May 13-17, 2013, International World Wide Web Conferences Steering Committee / ACM, pp 319–330, DOI 10.1145/2488388.2488417, URL https://doi.org/10.1145/2488388.2488417
  * Datar et al. (2004) Datar M, Immorlica N, Indyk P, Mirrokni VS (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Snoeyink J, Boissonnat J (eds) Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004, ACM, pp 253–262, DOI 10.1145/997817.997857, URL https://doi.org/10.1145/997817.997857
  * Dawex (2021) Dawex (2021) Dawex. https://www.dawex.com/en/, accessed: 2021-05-09
  * De Toni et al. (2017) De Toni D, Milan GS, Saciloto EB, Larentis F (2017) Pricing strategies and levels and their impact on corporate profitability. Revista de Administração (São Paulo) 52(2):120–133
  * Deep and Koutris (2017a) Deep S, Koutris P (2017a) The design of arbitrage-free data pricing schemes. In: Benedikt M, Orsi G (eds) 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs, vol 68, pp 12:1–12:18, DOI 10.4230/LIPIcs.ICDT.2017.12, URL https://doi.org/10.4230/LIPIcs.ICDT.2017.12
  * Deep and Koutris (2017b) Deep S, Koutris P (2017b) QIRANA: A framework for scalable query pricing. In: Salihoglu S, Zhou W, Chirkova R, Yang J, Suciu D (eds) Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, ACM, pp 699–713, DOI 10.1145/3035918.3064017, URL https://doi.org/10.1145/3035918.3064017
  * Devlin et al. (2019) Devlin J, Chang M, Lee K, Toutanova K (2019) BERT: pre-training of deep bidirectional transformers for language understanding. In: Burstein J, Doran C, Solorio T (eds) Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), Association for Computational Linguistics, pp 4171–4186, DOI 10.18653/v1/n19-1423, URL https://doi.org/10.18653/v1/n19-1423
  * Dibb et al. (2005) Dibb S, Simkin L, Pride WM, Ferrell O (2005) Marketing: Concepts and Strategies. 5th Edition. Houghton Mifflin, Abingdon, UK
  * Dwork (2008) Dwork C (2008) Differential privacy: A survey of results. In: Agrawal M, Du D, Duan Z, Li A (eds) Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi’an, China, April 25-29, 2008. Proceedings, Springer, Lecture Notes in Computer Science, vol 4978, pp 1–19, DOI 10.1007/978-3-540-79228-4“˙1, URL https://doi.org/10.1007/978-3-540-79228-4_1
  * Ensthaler and Giebe (2014) Ensthaler L, Giebe T (2014) Bayesian optimal knapsack procurement. Eur J Oper Res 234(3):774–779, DOI 10.1016/j.ejor.2013.09.031, URL https://doi.org/10.1016/j.ejor.2013.09.031
  * Fernandez et al. (2020) Fernandez RC, Subramaniam P, Franklin MJ (2020) Data market platforms: Trading data assets to solve data problems. Proc VLDB Endow 13(12):1933–1947, DOI 10.14778/3407790.3407800
  * Fricker and Maksimov (2017) Fricker SA, Maksimov YV (2017) Pricing of data products in data marketplaces. In: Ojala A, Holmström Olsson H, Werder K (eds) Software Business, Springer International Publishing, Cham, pp 49–66
  * Fung and Beschastnikh (2019) Fung C, Beschastnikh I (2019) Brokered agreements in multi-party machine learning. In: Proceedings of the 10th ACM SIGOPS Asia-Pacific Workshop on Systems, pp 69–75
  * Ghorbani and Zou (2019) Ghorbani A, Zou JY (2019) Data shapley: Equitable valuation of data for machine learning. In: Chaudhuri K, Salakhutdinov R (eds) Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, PMLR, Proceedings of Machine Learning Research, vol 97, pp 2242–2251, URL http://proceedings.mlr.press/v97/ghorbani19c.html
  * Ghosh and Roth (2011) Ghosh A, Roth A (2011) Selling privacy at auction. In: Shoham Y, Chen Y, Roughgarden T (eds) Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011, ACM, pp 199–208, DOI 10.1145/1993574.1993605, URL https://doi.org/10.1145/1993574.1993605
  * Gillies (1959) Gillies DB (1959) Solutions to general non-zero-sum games. Contributions to the Theory of Games 4:47–85
  * Goel and Faltings (2019) Goel N, Faltings B (2019) Deep bayesian trust: A dominant and fair incentive mechanism for crowd. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, AAAI Press, pp 1996–2003, DOI 10.1609/aaai.v33i01.33011996, URL https://doi.org/10.1609/aaai.v33i01.33011996
  * Gur et al. (2014) Gur Y, Zeevi AJ, Besbes O (2014) Stochastic multi-armed-bandit problem with non-stationary rewards. In: Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ (eds) Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp 199–207, URL https://proceedings.neurips.cc/paper/2014/hash/903ce9225fca3e988c2af215d4e544d3-Abstract.html
  * Han et al. (2020) Han D, Tople S, Rogers A, Wooldridge MJ, Ohrimenko O, Tschiatschek S (2020) Replication-robust payoff-allocation with applications in machine learning marketplaces. CoRR abs/2006.14583, URL https://arxiv.org/abs/2006.14583, 2006.14583
  * Heckman et al. (2015) Heckman JR, Boehmer EL, Peters EH, Davaloo M, Kurup NG (2015) A pricing model for data markets. iConference 2015 Proceedings
  * Hoeffding (1994) Hoeffding W (1994) Probability inequalities for sums of bounded random variables. In: The Collected Works of Wassily Hoeffding, Springer, pp 409–426
  * Hu and Gong (2020) Hu R, Gong Y (2020) Trading data for learning: Incentive mechanism for on-device federated learning. In: IEEE Global Communications Conference, GLOBECOM 2020, Virtual Event, Taiwan, December 7-11, 2020, IEEE, pp 1–6, DOI 10.1109/GLOBECOM42002.2020.9322475, URL https://doi.org/10.1109/GLOBECOM42002.2020.9322475
  * Hu et al. (2018) Hu Z, Liang Y, Zhang J, Li Z, Liu Y (2018) Inference aided reinforcement learning for incentive mechanism design in crowdsourcing. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R (eds) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp 5512–5522, URL https://proceedings.neurips.cc/paper/2018/hash/f2e43fa3400d826df4195a9ac70dca62-Abstract.html
  * Hynes et al. (2018) Hynes N, Dao D, Yan D, Cheng R, Song D (2018) A demonstration of sterling: A privacy-preserving data marketplace. Proc VLDB Endow 11(12):2086–2089, DOI 10.14778/3229863.3236266, URL http://www.vldb.org/pvldb/vol11/p2086-hynes.pdf
  * Irvin (1978) Irvin G (1978) Modern Cost-Benefit Methods. Macmillan Publishers Limited, London, DOI 10.1007/978-1-349-15912-3
  * Jia et al. (2019a) Jia R, Dao D, Wang B, Hubis FA, Gürel NM, Li B, Zhang C, Spanos CJ, Song D (2019a) Efficient task-specific data valuation for nearest neighbor algorithms. Proc VLDB Endow 12(11):1610–1623, DOI 10.14778/3342263.3342637, URL http://www.vldb.org/pvldb/vol12/p1610-jia.pdf
  * Jia et al. (2019b) Jia R, Dao D, Wang B, Hubis FA, Hynes N, Gürel NM, Li B, Zhang C, Song D, Spanos CJ (2019b) Towards efficient data valuation based on the shapley value. In: Chaudhuri K, Sugiyama M (eds) The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, PMLR, Proceedings of Machine Learning Research, vol 89, pp 1167–1176, URL http://proceedings.mlr.press/v89/jia19a.html
  * Jiang et al. (2015) Jiang C, Gao L, Duan L, Huang J (2015) Economics of peer-to-peer mobile crowdsensing. In: 2015 IEEE Global Communications Conference (GLOBECOM), IEEE, pp 1–6
  * Jin et al. (2015) Jin H, Su L, Chen D, Nahrstedt K, Xu J (2015) Quality of information aware incentive mechanisms for mobile crowd sensing systems. In: Shen SX, Sun Y, Chen J, Zhang J, Zussman G (eds) Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2015, Hangzhou, China, June 22-25, 2015, ACM, pp 167–176, DOI 10.1145/2746285.2746310, URL https://doi.org/10.1145/2746285.2746310
  * Jin et al. (2019) Jin W, Xiao M, Li M, Guo L (2019) If you do not care about it, sell it: Trading location privacy in mobile crowd sensing. In: 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019, IEEE, pp 1045–1053, DOI 10.1109/INFOCOM.2019.8737457, URL https://doi.org/10.1109/INFOCOM.2019.8737457
  * Jorgensen et al. (2015) Jorgensen Z, Yu T, Cormode G (2015) Conservative or liberal? personalized differential privacy. In: Gehrke J, Lehner W, Shim K, Cha SK, Lohman GM (eds) 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015, IEEE Computer Society, pp 1023–1034, DOI 10.1109/ICDE.2015.7113353, URL https://doi.org/10.1109/ICDE.2015.7113353
  * Kang et al. (2019) Kang J, Xiong Z, Niyato D, Xie S, Zhang J (2019) Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet Things J 6(6):10700–10714, DOI 10.1109/JIOT.2019.2940820, URL https://doi.org/10.1109/JIOT.2019.2940820
  * Koh and Liang (2017) Koh PW, Liang P (2017) Understanding black-box predictions via influence functions. In: Precup D, Teh YW (eds) Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, PMLR, Proceedings of Machine Learning Research, vol 70, pp 1885–1894, URL http://proceedings.mlr.press/v70/koh17a.html
  * Koutris et al. (2012) Koutris P, Upadhyaya P, Balazinska M, Howe B, Suciu D (2012) Query-based data pricing. In: Benedikt M, Krötzsch M, Lenzerini M (eds) Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, ACM, pp 167–178, DOI 10.1145/2213556.2213582, URL https://doi.org/10.1145/2213556.2213582
  * Koutris et al. (2013) Koutris P, Upadhyaya P, Balazinska M, Howe B, Suciu D (2013) Toward practical query pricing with querymarket. In: Ross KA, Srivastava D, Papadias D (eds) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, ACM, pp 613–624, DOI 10.1145/2463676.2465335, URL https://doi.org/10.1145/2463676.2465335
  * Koutsopoulos (2013) Koutsopoulos I (2013) Optimal incentive-driven design of participatory sensing systems. In: Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14-19, 2013, IEEE, pp 1402–1410, DOI 10.1109/INFCOM.2013.6566934, URL https://doi.org/10.1109/INFCOM.2013.6566934
  * Leyton-Brown and Shoham (2008) Leyton-Brown K, Shoham Y (2008) Essentials of Game Theory: A Concise Multidisciplinary Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, DOI 10.2200/S00108ED1V01Y200802AIM003, URL https://doi.org/10.2200/S00108ED1V01Y200802AIM003
  * Li et al. (2013) Li C, Li DY, Miklau G, Suciu D (2013) A theory of pricing private data. In: Tan W, Guerrini G, Catania B, Gounaris A (eds) Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22, 2013, ACM, pp 33–44, DOI 10.1145/2448496.2448502, URL https://doi.org/10.1145/2448496.2448502
  * Liang et al. (2018) Liang F, Yu W, An D, Yang Q, Fu X, Zhao W (2018) A survey on big data market: Pricing, trading and protection. IEEE Access 6:15132–15154
  * Lin and Kifer (2014) Lin B, Kifer D (2014) On arbitrage-free pricing for general data queries. Proc VLDB Endow 7(9):757–768, DOI 10.14778/2732939.2732948, URL http://www.vldb.org/pvldb/vol7/p757-lin.pdf
  * Liu et al. (2016) Liu C, Chakraborty S, Mittal P (2016) Dependence makes you vulnberable: Differential privacy under dependent tuples. In: 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21-24, 2016, The Internet Society, URL http://wp.internetsociety.org/ndss/wp-content/uploads/sites/25/2017/09/dependence-makes-you-vulnerable-differential-privacy-under-dependent-tuples.pdf
  * Liu et al. (2021) Liu J, Lou J, Liu J, Xiong L, Pei J, Sun J (2021) Dealer: An end-to-end model marketplace with differential privacy. Proc VLDB Endow 14(6):957–969, DOI 10.14778/3447689.3447700, URL https://doi.org/10.14778/3447689.3447700
  * Liu and Chen (2017a) Liu Y, Chen Y (2017a) Machine-learning aided peer prediction. In: Daskalakis C, Babaioff M, Moulin H (eds) Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, ACM, pp 63–80, DOI 10.1145/3033274.3085126, URL https://doi.org/10.1145/3033274.3085126
  * Liu and Chen (2017b) Liu Y, Chen Y (2017b) Sequential peer prediction: Learning to elicit effort using posted prices. In: Singh SP, Markovitch S (eds) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, AAAI Press, pp 607–613, URL http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14970
  * Louis (2020) Louis C (2020) Roundup of machine learning forecasts and market estimates, 2020\. Forbes URL https://www.forbes.com/sites/louiscolumbus/2020/01/19/roundup-of-machine-learning-forecasts-and-market-estimates-2020, accessed: 2021-06-28
  * Luong et al. (2016) Luong NC, Hoang DT, Wang P, Niyato D, Kim DI, Han Z (2016) Data collection and wireless communication in internet of things (iot) using economic analysis and pricing models: A survey. IEEE Communications Surveys & Tutorials 18(4):2546–2590
  * Ma et al. (2020) Ma L, Zhang C, Wang Y, Ruan W, Wang J, Tang W, Ma X, Gao X, Gao J (2020) Concare: Personalized clinical feature embedding via capturing the healthcare context. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, AAAI Press, pp 833–840, URL https://aaai.org/ojs/index.php/AAAI/article/view/5428
  * Maleki et al. (2013) Maleki S, Tran-Thanh L, Hines G, Rahwan T, Rogers A (2013) Bounding the estimation error of sampling-based shapley value approximation with/without stratifying. CoRR abs/1306.4265, URL http://arxiv.org/abs/1306.4265, 1306.4265
  * McMahan et al. (2017) McMahan B, Moore E, Ramage D, Hampson S, y Arcas BA (2017) Communication-efficient learning of deep networks from decentralized data. In: Singh A, Zhu XJ (eds) Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, PMLR, Proceedings of Machine Learning Research, vol 54, pp 1273–1282, URL http://proceedings.mlr.press/v54/mcmahan17a.html
  * Miao et al. (2020) Miao X, Gao Y, Chen L, Peng H, Yin J, Li Q (2020) Towards query pricing on incomplete data. IEEE Transactions on Knowledge and Data Engineering
  * Muschalle et al. (2012) Muschalle A, Stahl F, Löser A, Vossen G (2012) Pricing approaches for data markets. In: International workshop on business intelligence for the real-time enterprise, Springer, pp 129–144
  * Myerson (1981) Myerson RB (1981) Optimal auction design. Mathematics of operations research 6(1):58–73
  * Nagle (2010) Nagle J TT & Hogan (2010) The Strategy and Tactics of Pricing: A Guide to Growing More Profitably. Prentice Hall
  * Nash et al. (2007) Nash A, Segoufin L, Vianu V (2007) Determinacy and rewriting of conjunctive queries using views: A progress report. In: Schwentick T, Suciu D (eds) Database Theory - ICDT 2007, 11th International Conference, Barcelona, Spain, January 10-12, 2007, Proceedings, Springer, Lecture Notes in Computer Science, vol 4353, pp 59–73, DOI 10.1007/11965893“˙5, URL https://doi.org/10.1007/11965893_5
  * Nash (1950) Nash JF (1950) Equilibrium points in $n$-person games. Proc of the National Academy of Sciences 36:48–49
  * Natarajan et al. (2013) Natarajan N, Dhillon IS, Ravikumar P, Tewari A (2013) Learning with noisy labels. In: Burges CJC, Bottou L, Ghahramani Z, Weinberger KQ (eds) Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp 1196–1204, URL https://proceedings.neurips.cc/paper/2013/hash/3871bd64012152bfb53fdf04b401193f-Abstract.html
  * Neumeier (2015) Neumeier M (2015) The brand flip : why customers now run companies–and how to profit from it. New Riders,, San Francisco :
  * Nget et al. (2017) Nget R, Cao Y, Yoshikawa M (2017) How to balance privacy and money through pricing mechanism in personal data market. In: Degenhardt J, Kallumadi S, de Rijke M, Si L, Trotman A, Xu Y (eds) Proceedings of the SIGIR 2017 Workshop On eCommerce co-located with the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, eCOM@SIGIR 2017, Tokyo, Japan, August 11, 2017, CEUR-WS.org, CEUR Workshop Proceedings, vol 2311, URL http://ceur-ws.org/Vol-2311/paper_15.pdf
  * Niu et al. (2018) Niu C, Zheng Z, Wu F, Tang S, Gao X, Chen G (2018) Unlocking the value of privacy: Trading aggregate statistics over private correlated data. In: Guo Y, Farooq F (eds) Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, ACM, pp 2031–2040, DOI 10.1145/3219819.3220013, URL https://doi.org/10.1145/3219819.3220013
  * Ohrimenko et al. (2019) Ohrimenko O, Tople S, Tschiatschek S (2019) Collaborative machine learning markets with data-replication-robust payments. CoRR abs/1911.09052, URL http://arxiv.org/abs/1911.09052, 1911.09052
  * Pei (2020) Pei J (2020) A survey on data pricing: from economics to data science. IEEE Transactions on Knowledge and Data Engineering PP:1–1, DOI 10.1109/TKDE.2020.3045927
  * Radanovic and Faltings (2016) Radanovic G, Faltings B (2016) Learning to scale payments in crowdsourcing with properboost. In: Ghosh A, Lease M (eds) Proceedings of the Fourth AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2016, 30 October - 3 November, 2016, Austin, Texas, USA, AAAI Press, pp 179–188, URL http://aaai.org/ocs/index.php/HCOMP/HCOMP16/paper/view/14033
  * Radanovic et al. (2016) Radanovic G, Faltings B, Jurca R (2016) Incentives for effort in crowdsourcing using the peer truth serum. ACM Trans Intell Syst Technol 7(4):48:1–48:28, DOI 10.1145/2856102, URL https://doi.org/10.1145/2856102
  * Rauhut (2010) Rauhut H (2010) Compressive sensing and structured random matrices. Theoretical foundations and numerical methods for sparse recovery 9:1–92