Mechanisms that Incentivize Data Sharing in Federated Learning

Sai Praneeth Karimireddy⋄111Equal contribution. Wenshuo Guo⋄1 Michael I.
Jordan⋄,†
---
Department of Electrical Engineering and Computer Sciences⋄
---
Department of Statistics†
University of California, Berkeley

###### Abstract

Federated learning is typically considered a beneficial technology which
allows multiple agents to collaborate with each other, improve the accuracy of
their models, and solve problems which are otherwise too data-intensive /
expensive to be solved individually. However, under the expectation other
agents will share their data, rational agents may be tempted to engage in
detrimental behavior such as _free-riding_ where they contribute no data but
still enjoy an improved model. In this work, we propose a framework to analyze
the behavior of such rational data generators. We first show how a naive
scheme leads to catastrophic levels of free-riding where the benefits of data
sharing are completely eroded. Then, using ideas from contract theory, we
introduce _accuracy shaping_ based mechanisms to maximize the amount of data
generated by each agent. These provably prevent free-riding without needing
any payment mechanism.

###  1 Introduction

Data is a _non-rivalrous good_ —once produced, it can be repeatedly used
multiple times without exhaustion. Thus, multiple firms can simultaneously use
the data produced by any individual firm, increasing societal utility/welfare
(Jones and Tonetti, 2020). To promote such multiple usage, data portability
requirements have been widely legislated, e.g., the GDPR in the EU, CCPA in
California, etc (Mancini, 2021). As a consequence, services are required to
enable a user to download any personal data collected and potentially re-
upload it to a different service. These desiderata form a solid economic and
legal basis for federated learning—a new paradigm in machine learning wherein
multiple data-generating agents collaborate with each other to train a model
on their _combined_ data so that all the agents end up with a better model
than they would have obtained on their own (Kairouz et al., 2021). Such
collaborative data sharing is already common in genomics research (Weinstein
et al., 2013), internet advertisement targeting (Google, 2022), and is also
gaining traction between networks of hospitals (see, e.g., Sheller et al.,
2018; Wen et al., 2019; Rieke et al., 2020; Flores et al., 2021).

It is clear that once a certain amount of data has been produced, privacy
issues aside, societal welfare is maximized by allowing free access to the
data thereby making it a public good. However, under such an expectation, a
rational agent may be tempted to _free-ride_ , i.e., consume the benefits of
the data production by others without contributing any data themselves. This
may lead to a collapse in the data generation with everyone wanting to free-
ride. Such a problem inevitably arises with any public good (Baumol, 2004).
Further, even if no agent actually free-rides and everyone intends to
contribute data out of altruism, the mere perception that others may be free-
riding reduces pro-social behavior and willingness to contribute (Choi and
Robertson, 2019). Thus, the long-term success of federated learning in
particular and data portability in general critically require overcoming free-
riding.

The overall consequence of free-riding to the system is that a lesser amount
of data may be generated. Thus, we can equivalently formulate the problem of
preventing free-riding as that of maximizing the amount of data generated by
the agents. This motivates our main question:

> _How do we design a system which incentivizes rational agents to contribute
> their fair share of data, thereby maximizing the accuracy of the resulting
> model and improving collaboration?_

Maximizing the amount of data generated will arguably lead to the greatest
long-term societal welfare, even if allowing free access to it gives better
short-term welfare.

##### Motivating example.

Autonomous driving is data-intensive, with expensive data generation. Each
data point involves a person physically driving. On the other hand, more data
and more accurate models will potentially lead to reduced accidents and save
lives. The high cost of data collection also means that only a select few
providers will be able to raise capital required to collect enough data,
limiting innovation.

Given that, a government agency may pass legislation requiring autonomous
driving providers to share their data openly with each other with the
following two goals: (i) hoping that each provider would now have access to a
larger pool of data and can train a more accurate model, and (ii) forcing
collaboration between the providers in order to encourage solving more
ambitious problems. However, providers may react to such a data-sharing
regulation by reducing the amount of data they collect and instead free-
riding, defeating the purpose of the legislation. _How should the government
agency formulate its data-sharing legislation in order to maximize the total
amount of data collected and shared?_

####  1.1 Contribution and summary of results

In this work, we formally introduce the _data maximization incentivization
problem_ in federated learning, and design new mechanisms to achieve this
goal. In more detail:

  * •

We formulate a principal-agent model (Laffont and Martimort, 2009) where each
agent has a cost associated with generating a data point and wants to improve
the accuracy of a model while minimizing said costs (Sec. 2). Our formulation
borrows ideas from contract theory while introducing new concepts that are
specific to the federated learning setting.

  * •

Using this framework we show how giving unconditional benefit of the combined
data to all agents (as is standard in federated learning) leads to
catastrophic free-riding where almost none of the agents contribute any data
(Sec. 3) at their optimal responses.

  * •

Accordingly, we propose to tune the accuracy of the model received by an agent
to their contribution. In the full-information setting when the agent’s cost
of data generation is known, we derive an optimal mechanism which overcomes
free-riding and leads to maximal collaboration and data generation (Sec. 4).

  * •

Finally, if the costs of an agent are unknown, we show (in App. B) how to
design truth-revealing accuracy curves at some cost to the principal (i.e.,
information rent) to incentivize the agents to report their true costs.

Our framework can capture free-riding and the need for collaboration when
faced with challenging learning problems. The latter is novel to our
framework—we show that if the learning task is too challenging, then it is not
economically viable for any single agent to tackle the problem. However, using
incentivizing data-sharing mechanisms, it may be possible to share the costs
among participants and solve it collaboratively.

####  1.2 Related Work

##### Free-riding and fairness in federated learning.

Recent work has explored such free-riding behavior in federated learning
schemes, with various incentive models proposed (Sarikaya and Ercetin, 2019;
Lin et al., 2019; Ding et al., 2020; Fraboni et al., 2021). Most of this work
has, however, focused on a taxonomy of free-rider attacks or the detection of
such attacks, instead of proposing mechanisms that incentivize maximal data
contribution. In this work, we consider a mechanism for data sharing under the
standard federated learning setting such that rational agents are incentivized
to contribute their maximal amount of data.

##### Contract theory in federated learning.

Preventing free-riding behavior in federated learning is notoriously hard
because the data collection and costs are private to the agents. This
information asymmetry and the existence of a central server (a “principal”)
suggests connections to contract theory, which studies the design of incentive
mechanisms under a principal-agent model, where the agent possesses private
information about their costs. Recently, there has been an emerging line of
research exploring the application of contract theory for federated learning
(Kang et al., 2019b, c, a; Cong et al., 2020; Zhan et al., 2020; Lim et al.,
2021; Tian et al., 2021). In particular, Tian et al. (2021) proposed a
contract-based aggregator under a multi-dimensional contract model over two
possible types of agents and showed improved model generalization accuracy
under that contract. However, their mechanism focused on eliciting the private
type information instead of maximizing the data contribution. To the best of
our knowledge, our work is the first to use contract theory for data
maximization in federated learning. Further, prior work has focused on how to
design payments to agents, rather than the accuracy-shaping problem that we
focus on here without any payment usage.

##### Mechanism design for collaborative machine learning.

More broadly, this work is related to an active line of research on mechanism
design for collaborative machine learning, which involves multiple parties
each with their own data, jointly training a model or making predictions in a
common learning task (Sim et al., 2020; Xu et al., 2021). In collaborative
machine learning, a major focus has been the design of model rewards (i.e.,
data valuation) in order to ensure certain fairness or accuracy objectives.
Towards that goal, there has been model rewards proposed based on notions from
the cooperative game theory literature such as the Shapley value (Jia et al.,
2019; Wang et al., 2020). However, the guarantees of these model rewards
depend on the assumption that the agents are already willing to contribute the
data they have. In this work, we study a different incentivization task for
data maximization.

Lastly, in this work, we have focused on the data-maximization goal under
individual rationality and accuracy-shaping. More broadly, there are other
objectives which are of interest in federated learning, such as fairness and
welfare objectives, that have been under active study (Donahue and Kleinberg,
2021a, b).

###  2 Modeling an Individual Agent

We begin with modelling the learning task and objective for an individual
agent. We then provide a characterization of the optimal data contribution for
each single agent without participating in a federated learning scheme.

####  2.1 Learning problem

There are $n$ agents all of whom want to solve a _common_ learning problem.
This is often true in federated learning since coalitions form around solving
some particular task. Concretely, we assume that all agents want to maximize
an accuracy function, $a(\mathcal{D}):2^{\mathcal{D}}\rightarrow[0,1]$, for a
dataset $\mathcal{D}$. We also assume each of them has access to the same data
distribution and that we are in an i.i.d. setting. This holds true if the data
is generated by manually labelling a subset of an already public unlabelled
dataset, as is common in machine learning; e.g., Cifar (Krizhevsky et al.,
2009) and ImageNet (Russakovsky et al., 2015). This assumption is arguably
also valid in our autonomous driving example where each data point involves a
random path taken under random external conditions. Thus, every agent wants to
maximize

$a(m):\mathbb{R}_{\geq 0}\rightarrow[0,1]=\max(0,b(m))\,,\ \text{where $b$ is
continuous, non-decreasing and concave.}$ (1)

We also assume w.l.o.g that $a(0)=0$ and $\lim_{m\rightarrow\infty}a(m)>0$. We
will first show how an agent concerned with obtaining high test accuracy on a
learning problem can be modeled by our formulation. are motivated by empirical
observations (Kaplan et al., 2020), and standard generalization guarantees.

######  Example 2.1 (Generalization bounds).

Suppose we want to learn a model $h$ from a hypothesis class $\mathcal{H}$
which minimizes the error over data distribution $\mathcal{D}$, defined to be
$R(h):=\operatorname{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[e(h(x),y)]$, for some
error function $e(\cdot)\in[0,1]$. Let such an optimal model have error
$(1-a_{opt})<1$. Now, given access to $\\{(x_{l},y_{l})\\}_{l\in[m]}$ which
are $m$ i.i.d. samples from $\mathcal{D}$, we can compute the empirical risk
minimizer (ERM) as
$\hat{h}_{m}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\sum_{l\in[m]}e(l(x),y)$.
Then, standard generalization bounds (Mohri et al., 2018, Theorem 11.8) imply
that with probability at least $99\%$ over the sampling of the data, the
accuracy is at least

$1-R(\hat{h}_{m})\geq\Big{\\{}b(m):=a_{opt}-\frac{\sqrt{2k(2+\log(m/k))}+4}{\sqrt{m}}\Big{\\}}\,.$
(2)

Here $k\geq 1$ is the pseudo-dimension of the set of functions
$\\{(x,y)\rightarrow e(h(x),y):h\in\mathcal{H}\\}$, which is a measure of the
_difficulty_ of the learning task. We can then define our accuracy function
$a(m)=\max(0,b(m))$. Note that $a(m)\in[0,1]$ and
$\lim_{m\rightarrow\infty}=a_{opt}>0$. Further, $b(m)\leq 0$ for $m\leq 1$ and
$b(\cdot)$ is concave for any $m\geq 1$, satisfying (1). While (2) does
satisfy our assumptions and can be used to understand our framework, it is too
unwieldy to perform exact analysis. So we will use (2) for simulations, but
use a simplified expression for our analytic analysis:

$b(m):=a_{opt}-2\sqrt{k/{m}}\,.$ (3)

We use the above formulation as a running example in the rest of the paper.
The next example shows a more stylized, but perhaps more realistic setting
where a company derives some abstract value from data but only after a cutoff
due to regulation.

######  Example 2.2 (Starting costs and minimum viability).

Consider an autonomous driving provider who is training large machine learning
models. The dependence of the final accuracy $b(\cdot)$ of such a model
typically scales as a power law in the number of training data points; i.e.,
$b(m)=1-\nicefrac{{\beta}}{{m^{\alpha}}}$ for some $\beta>0$ and
$\alpha\in(0,1]$ (Kaplan et al., 2020). For such a provider, improved accuracy
in their models might directly imply better customer satisfaction and hence
more sales. It might also imply lower downstream costs in term of law-suits,
etc. However, a small number (say ten) data points are not in themselves of
any value. This is because the true value needs to overcome additional fixed
(non data-related) costs, as well as have sufficient accuracy to pass safety
regulation. Thus, in practice, the real value of data is better captured by
$a(m)=\max(0,1-\nicefrac{{\beta}}{{m^{\alpha}}}-\tau)$ for accuracy threshold
$\tau$. Thus, there is a minimum viable dataset
$m^{0}\geq\left(\nicefrac{{\beta}}{{1-\tau}}\right)^{\nicefrac{{1}}{{\alpha}}}$.
The value of the data below this threshold is zero, and its value beyond is
concave and non-decreasing.

####  2.2 Agent’s objective and optimal solution

Each agent $i$ has a marginal fixed cost $c_{i}>0$ for producing a data point.
Their cost for producing a dataset $\mathcal{D}$ with $m$ number of data
points is then:

$cost_{i}(m)=c_{i}m.$ (4)

|  |  |
---|---|---|---
$(a)$ | $(b)$ | $(c)$ | $(d)$
Figure 1: Illustration of the optimal amount of data for a single agent. (a):
Accuracy and cost versus the dataset size.(b)-(d): Utility function of a
low/mid/high-cost agent versus the dataset size.

When manually labelling a dataset or when training an autonomous-driving
model, this cost $c_{i}$ may represent the time spent by researchers/employees
or an amount paid to crowd-sourced workers. The cost $c_{i}m$ may also
represent the risk associated with privacy loss for the agent for revealing
$m$ of their data points. By incurring this cost, they can train a model with
accuracy $a(m)$. We assume that the utility improves linearly with increasing
accuracy $a(\cdot)$. For example, each accurate product recommendation may
lead to a sale or correct digital ad placement may lead to a click and hence
ad revenue. This is also true if each error represents costly consequences.
Each error by a medical diagnostic model, a loan application evaluation model,
or a autonomous driving model may lead to significant suffering. Thus, the
utility of an agent is improve accuracy for the least cost; i.e., to maximize

$u_{i}(m)=a(m)-c_{i}m.$ (5)

######  Theorem 2.3 (Optimal individual generation).

Consider an individual agent $i$ with marginal cost per data point $c_{i}$ and
accuracy function $a$ satisfying (1) working on their own. Then, the optimal
amount of data $m_{i}^{\ast}$ is:

$m_{i}^{\ast}=\begin{cases}0&\text{if ${\max_{m_{i}\geq 0}u_{i}(m_{i})}\leq
0$};\\\ \alpha_{i}^{\ast}\text{, such that
}b^{\prime}(\alpha_{i}^{\ast})=c_{i}&\text{otherwise.}\end{cases}$ (6)

Further, for agents $i,j$ with costs $c_{i}\leq c_{j}$, their utility
satisfies $u_{i}(m_{i}^{\ast})\geq u_{j}(m_{j}^{\ast})$ and $m_{i}^{\ast}\geq
m_{j}^{\ast}$.

As Figure 1 shows, if the learning problem is too hard ($m^{0}$ is large) or
if the marginal cost $c_{i}$ is too high, the problem becomes infeasible for
an individual agent to solve with $m_{i}^{\ast}=0$. Such cases are especially
important in federated learning where we want to enable agents to solve
problems together which they cannot on their own. In other cases, the agent
collects $m_{i}^{\ast}>0$ data points.

Figure 2: Optimal data contribution $m_{i}^{\ast}$ versus the marginal cost
$c_{i}$ for different number of total agents.

######  Example 2.4 (Computing individual contributions).

Consider the accuracy function arising from the generalization guarantees in
Example 2.1, and an agent with marginal cost $c_{i}$. Utilizing the simpler
accuracy definition in (3), we can derive the following. The utility of agent
$i$ becomes $u_{i}(m)=\max(0,a_{opt}-2\sqrt{k/m})-c_{i}m$. For this function,
the minimum amount of data before accuracy starts to improve is
$m^{0}=4a_{opt}^{2}/k$. The maximum cost at which the learning problem is
viable is $c_{i}\leq a_{opt}^{3}/3k$. For any higher cost, the agent does not
attempt to solve the problem with $m_{i}^{\ast}=0$. When the cost is lower
than this threshold, the agent generates data
$m_{i}^{\ast}=k^{1/3}c_{i}^{-2/3}$ and obtains an utility of
$u_{i}(m_{i}^{\ast})=a_{opt}-3(kc_{i})^{1/3}$. As expected, the minimum
viability cost threshold scales inversely with the difficulty of the learning
problem. Beyond this threshold, an agent’s contribution decreases with cost
and increases with the difficulty.

Empirically, we can plot the optimal individual generations using the full
analytic form of the utility function (see Eq (2)). Figure 2 shows the optimal
data contribution $m_{i}^{\ast}$ versus the marginal cost $c_{i}$ for
different number of total agents on a log-log scale. We see that the optimal
contribution decreases with cost as $m_{i}^{\ast}\propto c_{i}^{-2/3}$,
matching the theory. The vertical lines indicate the cutoff for minimum
viability—beyond this, the cost is too high for the problem to be solvable by
an individual. This minimum viability cost is smaller for more harder problems
(larger $k$), but the optimum contribution increases with increasing $k$ once
this threshold is crossed.

###  3 Modeling Multiple Agents and Catastrophic Free-Riding

In this section we will study how agents behave when collaborating with each
other as they do in federated learning. For this, we use a principal-_multi_
-agent framework where the server who sets up the federated learning server is
the principal.

####  3.1 Interaction between agents and server

The interaction between the federated learning server and the agents is
formalized by a mechanism

$\mathcal{M}(\mathbf{m}):\mathbb{R}_{\geq 0}^{n}\rightarrow[0,1]^{n}\,,\text{
which maps agents' contributions to accuracies.}$ (7)

We assume that each agent $i$ generates and transmits $m_{i}$ i.i.d. data
points to the server, ignoring privacy concerns (see Sec. 5). Based on these
contributions, the mechanism assigns accuracies to the models received by the
clients; i.e., if agent $i$ contributes $m_{i}$ data points it receives a
model with accuracy $a_{i}\in[0,1]$, where
$\mathcal{M}(m_{1},\dots,m_{n})=(a_{1},\dots,a_{n})$.

The interaction proceeds in three steps: (i) first the server publishes a
mechanism $\mathcal{M}$, then (ii) each agent generates and transmits some
data $m_{i}$ to the server, and finally (iii) the server returns a trained
model to each agent following the mechanism. Note that the agents decide how
much data to generate adaptively _after_ knowing the mechanism $\mathcal{M}$.
However, they do not have any bargaining power—they cannot re-negotiate the
mechanism—but can only decide if they join or not. We also disallow monetary
compensation or exchanges between the parties since implementing them adds
additional complexity. The only guarantee is that the server truthfully
executes the protocol $\mathcal{M}$.

Given that the server necessarily needs to follow through on the mechanism, we
need to make sure the mechanism is implementable.

######  Definition 3.1 (Feasible mechanism).

A mechanism which returns accuracy $[\mathcal{M}(\mathbf{m})]_{i}$ to agent
$i$ is said to be _feasible_ if for any $i\in[n]$ and any
$\mathbf{m}\in\mathbb{R}_{\geq 0}^{n}$, it satisfies
$[\mathcal{M}(\mathbf{m})]_{i}\leq a(\sum_{j}m_{j})$ .

This is because we can pool together all the agent contributions $\mathbf{m}$
and train a model to accuracy $a(\sum_{j}m_{j})$. Since $a(\cdot)$ is
monotone, this is an upper bound on the accuracy which can be obtained.
However, it is always possible to use a subset of this data, or degrade the
model in a controlled way using noisy perturbations. Thus, this captures
mechanisms which are implementable in practice.

Faced with a potential feasible mechanism $\mathcal{M}$, an agent has to
decide whether to join or simply train on their own. A mechanism which offers
an especially bad accuracy would discourage an agent and they would likely
leave the server and train on their own. We will formalize this next.

######  Definition 3.2 (Individual rationality (IR)).

Given data contributions $\mathbf{m}$ by the $n$ agents with costs
$\mathbf{c}$, the mechanism provides a model with accuracy
$[\mathcal{M}(\mathbf{m})]_{i}$ to agent $i$. Such a mechanism $\mathcal{M}$
is said to satisfy IR if for any agent $i\in[n]$ and any contribution
$\mathbf{m}$,

$[\mathcal{M}(\mathbf{m})]_{i}-c_{i}m_{i}\geq a(m_{i})-c_{i}m_{i}\,.$ (8)

A mechanism which satisfies individual rationality guarantees that for any
agent the accuracy of the model received (and hence their utility) will be no
worse than if they trained on their own. Since IR guarantees that all rational
agents will participate in our mechanism, and participation is key to success
of a federated learning platform, we will restrict our focus henceforth to
mechanisms which satisfy IR. In the context of our running example of data-
sharing legislation for autonomous driving, ensuring the mechanism satisfies
IR means that the legislation is a win-win for all parties encouraging support
and compliance—consumers get safer models and car companies get higher
utilities.

Given any mechanism $\mathcal{M}$, we would like to argue about how rational
agents would respond and how much data they would contribute. For this, we use
the notion of an equilibrium.

######  Theorem 3.3 (Existence of pure equilibrium).

Consider a feasible mechanism $\mathcal{M}$ which can be expressed as:

$[\mathcal{M}(m_{i};\mathbf{m}_{-i})]_{i}=\max\left(0,\nu_{i}(m_{i};\mathbf{m}_{-i})\right)\,,$

for a function $\nu_{i}(m_{i};\mathbf{m}_{-i})$ which is _continuous_ in
$\mathbf{m}$ and _concave_ in $m_{i}$. For any such $\mathcal{M}$, there
exists a pure Nash equilibrium in data contributions
$\mathbf{m}^{eq}(\mathcal{M})$ which for any agent $i$ satisfies,

$[\mathcal{M}(\mathbf{m}^{eq}(\mathcal{M}))]_{i}-c_{i}m_{i}^{\mathcal{M}}\geq[\mathcal{M}(m_{i},\mathbf{m}^{eq}(\mathcal{M})_{-i})]_{i}-c_{i}m_{i}\,,\text{
for all }m_{i}\geq 0\,.$ (9)

Thus, under reasonable conditions on the mechanism $\mathcal{M}$ which are
satisfied for all the mechanisms we consider, an equilibrium always exists.
Note that the mechanism is not concave because of the presence of a
$\max(0,\cdot)$, and the resulting utilities of the agents are not even quasi-
concave. Despite this, our proof uses the specific properties of our setting
to prove existence, and may be more broadly applicable to study non-
concavities arising from “minimum viability” as is captured by the max. The
existence of such an equilibrium allows us to confidently use the data
contributions at this equilibrium to evaluate and compare different
mechanisms.

####  3.2 Standard federated setting

We now examine the behavior of rational agents in the standard federated
learning. Returning a model trained on the combined dataset to everyone
corresponds to the mechanism

$\mathcal{M}(\mathbf{m})=\left(a(\textstyle\sum_{j}m_{j})\,,\forall
i\in[n]\right)\,.$ (10)

Clearly, this mechanism is feasible (Def. 3.1) and also satisfies individual
rationality (Def. 3.2) since the accuracy function $a(\cdot)$ is non-
decreasing and $\sum_{j}m_{j}\geq m_{i}$ for any $i\in[n]$. In fact, given a
data contribution $\mathbf{m}$, this mechanism maximizes utility for all
agents. This observation may at first seem like a strong argument in favor of
this standard scheme. However, recall that the agents choose their
contribution $\mathbf{m}$ _after_ the server publishes the mechanism
$\mathcal{M}$. Thus, we need to first analyze how much data rational agents
would contribute.

######  Theorem 3.4 (Catastrophic free-riding).

Let $\\{m_{i}^{\ast}\\}$ be the equilibrium contributions of agents when
alone, with agent with least cost having a contribution
$m_{i}^{\ast}=:m^{fed}$. The standard federated learning mechanism
corresponding to $[\mathcal{M}(\mathbf{m})]_{i}=a(\sum_{j}m_{j})$ for all
clients $i$ is feasible and IR. Further, the total amount of data collected at
equilibrium remains $m^{fed}$, with only the lowest cost agent contributing:

$m_{i}^{eq}=\begin{cases}m_{i}^{\ast}=:m^{fed}&\text{ if
}i=\operatorname*{arg\,min}_{j}c_{j}\\\ 0&\text{ otherwise.}\end{cases}$ (11)

The agent with the least cost $c_{\min}=\min_{j}c_{j}$ would have collected
$m^{fed}$ amount of data on their own. For any other agent $i$, $c_{i}\geq
c_{\min}$ and so $m_{i}^{\ast}\leq m^{fed}$. Thus, agent $i$ would already
have access to data sufficient to satisfy them. The increase in accuracy
$a(\cdot)$ for collecting an additional data point beyond this is less than
the marginal cost $c_{i}$ incurred. This results in catastrophic free-riding,
with only a single agent collecting data. In the case of our autonomous
vehicle legislation example, this implies that naive data-sharing legislation
will have no effect. The providers would strategically reduce the amount of
data collected so that each of them is using almost the same amount of data as
before.

######  Remark 3.5 (Failure of collaboration).

Consider the case where $m^{\ast}_{i}=0$ for all agents $i$, either because
the learning problem is too hard or because the cost of data collection is too
high for any individual agent. Theorem 3.4 shows that $m^{fed}=0$ and no data
will be collected even with collaboration. Thus, if a problem is too costly to
solve by an individual, it will remain insurmountable when collaborating with
rational self-interested agents. This defeats one of the main motivations of
federated learning.

###  4 Accuracy Shaping with Verifiable Costs

How do we design mechanisms which prevent free-riding? In this section we will
study this question assuming everyone (the server and the agents) know the
costs $\mathbf{c}$ involved in producing the data (we study the unknown costs
setting in Section B), or at the least the costs can be verified; i.e., the
agent cannot incur cost $c$ and report a different cost $\tilde{c}$. This is
sometimes justifiable—the cost of driving a vehicle to generate a data point
by an autonomous-driving provider can be easily estimated by all parties, as
can the cost of labelling a data point by a crowd-worker. We formalize our
goal of data maximization and give a simple optimal mechanism for it. Then, we
look at some implications of the proposed solution—how fairly it distributes
the surplus and potential moral hazards it might induce.

####  4.1 Data maximization using accuracy shaping

A mechanism $\mathcal{M}$ is data-maximizing given costs $\mathbf{c}$ if it
maximizes the data collected at equilibrium.

######  Definition 4.1 (Data Maximization).

Suppose that given a mechanism $\mathcal{M}$, let
$\mathbf{m}^{eq}(\mathcal{M})$ correspond to the amount of data generated by
the agents at equilibrium. $\hat{\mathcal{M}}$ is _data-maximizing_ if it
maximizes the amount of data collected at equilibrium

$\hat{\mathcal{M}}\in\operatorname*{arg\,max}_{\mathcal{M}}\textstyle\sum_{j}[m^{eq}(\mathcal{M})]_{j}\,,\text{subject
to $\mathcal{M}$ being feasible and satisfying IR.}$ (12)

Figure 3: Illustration of the accuracy shaping mechanism. (red curve): model
accuracy returned to agent $i$ by the mechanism; (grey curve): model accuracy
for agent $i$ without participation; (green curve): model accuracy if agent
$i$ receives all the data from the other agents.

Given a mechanism $\mathcal{M}$, we first have to reason about how much each
agent would contribute. As we will see, there is always an equilibrium
contribution $\mathbf{m}^{eq}(\mathcal{M})$ satisfying (9) such that no agent
can improve their utility by unilaterally changing their contribution. If all
players are rational (and such an equilibrium is unique), then such a point is
a natural attractor with all the agents gravitating towards such
contributions. So, a reasonable goal for us as a mechanism designer is to pick
an $\mathcal{M}$ which maximizes the amount of data collected when all players
are contributing such equilibrium amounts.

If we give $\Delta m_{i}$ free data to agent $i$, then at equilibrium they
will reduce the data they generate—they will only generate
$(m_{i}^{\ast}-\Delta m_{i})$ additional data. To prevent this, our key
insight is to condition the amount of extra data $\Delta m_{i}$ on the agent’s
contribution. For given set of costs $\mathbf{c}$ and some small
$\varepsilon>0$, consider the following mechanism:

$[\mathcal{M}(\mathbf{m})]_{i}=\begin{cases}a(m_{i})\quad&\text{for }m_{i}\leq
m_{i}^{\ast}\\\
a(m_{i}^{\ast})+(c_{i}+\varepsilon)(m_{i}-m_{i}^{\ast})\quad&\text{for
}m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]\\\ a(\sum_{j}m_{j})\quad&\text{for
}m_{i}\geq m_{i}^{\max}\,,\end{cases}$ (13)

where $m_{i}^{\max}$ is defined such that $a(m_{i}^{\max}+\sum_{j\neq
i}m_{j})=a(m_{i}^{\ast})+(c_{i}+\varepsilon)(m_{i}^{\max}-m_{i}^{\ast})$. We
illustrate the mechanism in Figure 3. Even without any external
incentivization, agent $i$ will compute $m_{i}^{\ast}$ data points. Thus, for
$m_{i}\leq m_{i}^{\ast}$ (12) returns a model trained on solely their own
data. After $m_{i}^{\ast}$, however, the marginal gain in accuracy becomes
smaller than the additional cost $c_{i}$. Hence, the agent requires active
incentivization here and (12) ensures that for every additional data point
computed, the marginal gain in accuracy is strictly more than the cost
$c_{i}$. However, the mechanism cannot provide unlimited accuracy either and
has to remain feasible, giving us our final constraint.

######  Theorem 4.2 (Data maximization with known costs).

The mechanism $\mathcal{M}$ defined by (13) has an unique Nash equilibrium and
is data-maximizing for $\varepsilon\rightarrow 0^{+}$. At equilibrium, a
rational agent $i$ will contribute $m_{i}^{\max}$ data points where
$m_{i}^{\max}\geq m_{i}^{\ast}$, yielding a total of $\sum_{j}m_{j}^{\max}$
data points.

|  |
---|---|---
$(a)$ | $(b)$ | $(c)$
Figure 4: Equilibrium simulations of our mechanism: the total data collected
at equilibrium (a) increases linearly with the number of agents $n$, (b)
decreases as $c_{i}^{-1}$ with increasing marginal cost per data point, and is
relatively unaffected by the complexity $k$. (c) The number of agents required
to cross the minimum viability threshold (i.e. smallest $n$ for which
$m_{i}^{\max}>0$) increases linearly with both the marginal cost $c_{i}$ and
complexity $k$. Optimal individual contribution for all settings is
$m_{i}^{\ast}=0$; i.e., no data would be generated by standard federated
learning.

For our example of autonomous-driving providers, the state agency can set up a
central repository of the data to which the car providers are required to
contribute. The cost for collecting a data point (say $c$) can easily be
estimated and assumed to be the same for all agents. Using this estimate, the
state agency can compute a threshold. The providers don’t receive any
additional data for contributing up to this threshold. For each data point
contributed beyond the threshold, the providers receive an increasing amount
of additional data. By Theorem 4.2, this would prevent free-riding by the
providers and ensure the best trained model reaches the consumers.

######  Remark 4.3 (Credible threat).

At equilibrium, mechanism $\mathcal{M}$ in (13) ensures all agents contribute
$m_{i}^{\max}\geq m_{i}^{\ast}$; i.e., they generate _more_ data than they
would on their own. Further, every agent receives a model trained on this
combined dataset with accuracy $a(\sum_{j}m_{j}^{\max})$. Thus, we can ensure
that all agents fully utilize the combined data by using a threat that free-
riding will be punished, even though at equilibrium such a threat is never
actually invoked.

Suppose all agents have the same cost $c$. Theorem 4.2 shows that the
mechanism collects $nm^{\max}$ data points in total. However, $m^{\max}$ also
depends on $n$. This is because with a larger pool of data contributions, the
server can more strongly incentivize an individual and extract more data.
There is a natural ceiling to this though—the accuracy caps at
$a_{opt}:=\lim_{m\rightarrow\infty}a(m)\leq 1$. Thus, the absolute maximum
data that can be extracted from an individual agent is $m$ which satisfies
$a(m^{\ast})+c(m-m^{\ast})=a_{opt}$. This gives us the range for the total
data contributions to be
$\left[nm^{\ast},\,n\left(m^{\ast}+\nicefrac{{(a_{opt}-a(m^{\ast}))}}{{c}}\right)\right]$.

######  Remark 4.4 (Overcoming minimum viability).

When $m^{\ast}=0$, i.e., the problem is not solvable by an individual agent,
the net contribution from our mechanism $nm^{\max}$ may still be positive.
Suppose that the cost for all agents is the same $c$. Then, the total data
collected is $m^{\text{tot}}$ which satisfies

$\nicefrac{{c}}{{n}}\cdot m^{\text{tot}}=a(m^{\text{tot}})\,.$

This implies that for sufficiently large $n$, the cost $c$ is successfully
shared and we obtain a positive data contribution. However, note that
$m^{\text{tot}}=0$ is also a valid solution and remains an equilibrium. If all
other agents don’t contribute, there is no extra data to share and so there is
no incentive to compute extra data. In practice, this undesirable equilibrium
is unlikely to be encountered since it has lower utility. It can also be
prevented by the platform itself taking part as an agent and committing to
non-zero data collection.

######  Example 4.5 (Computing maximum contributions).

Consider the accuracy function arising from the generalization guarantees in
Example 2.1, and $n$ agents all with the same marginal cost $c$. For now,
suppose that $m^{\ast}>0$; i.e., the cost satisfies $c\leq a_{opt}^{3}/3k$. In
this case, the data contribution from each agent becomes
$m^{\max}=\max\big{\\{}m\geq 0\text{ s.t. }cm+2\sqrt{k/(nm)}\leq
3(ck)^{1/3}\big{\\}}\,.$ For $n\geq 3$, the contribution can be lower bounded
as $m^{\max}\geq\frac{3}{2}\sqrt[3]{k/c^{2}}$. Further, when
$n\rightarrow\infty$ we have $m^{\max}=3\sqrt[3]{k/c^{2}}$. The total
contribution is thus in the range
$[\frac{3n}{2}\sqrt[3]{k/c^{2}}\,,\,3n\sqrt[3]{k/c^{2}}]$. In contrast, as we
saw in Example 2.4, an individual agent working alone would only collect
$m^{\ast}=\sqrt[3]{k/c^{2}}$ datapoints.

Next, consider the case where $m^{\ast}=0$; i.e., the learning problem is too
difficult for any individual. Using the computation in Remark 4.4, the total
contribution of the agents becomes at least $m^{tot}\geq\frac{a_{opt}n}{2c}$
as soon as we have a minimum number $n\geq 32ck/a_{opt}^{3}$ of participating
agents. The total data collected increases with $n$ and decreases with $c$,
but surprisingly is not affected by the complexity $k$. The complexity $k$
only imposes a constraint on the minimum number of agents required. Thus, in
contrast to the failure of standard data-sharing, agents can successfully
collaborate using our mechanism on otherwise insurmountable learning problems.

Empirically, in Figure 4 we compute the equilibrium under the full utility
function (see Eq (2)) of our mechanism. We assume all agents have the same
cost and see the effect of the equilibrium data contribution as we vary the
cost $c$ and the total number of agents $n$. When not explicitly mentioned, we
used the following default parameters: optimal accuracy of $a_{opt}=0.95$,
marginal cost $c_{i}=0.1$, participants $n=10^{4}$. Under all parameter
configurations of this experiment, the optimal individual contribution is
$m_{i}^{\ast}=0$, while the equilibrium data contributions are significantly
larger as expected, validating our theory.

####  4.2 Incentive compatibility and distribution of surplus

One of our motivating reasons for preventing free-riding was to ensure that
none of the participating agents feel taken advantage of. That is, we wish to
satisfy some notion of fairness. However, there may potentially be new sources
of unfairness in (13). In particular, consider two agents, $i,j\in[n]$, with
different costs: $\text{if }c_{i}\leq c_{j}\text{ then }m_{i}^{\ast}\geq
m_{j}^{\ast}\,.$ Here, an agent $i$ with smaller cost $c_{i}$ faces two
disadvantages under mechanism (13): (i) they have a larger threshold amount of
data $m_{i}^{\ast}$ they have to contribute before receiving any benefit, and
(ii) they receive a smaller increase in accuracy $(c_{i}+\varepsilon)$ for
each additional data point computed.

If the cost for generating each data point is inherently fixed (such as the
cost of driving a vehicle) this is arguably not an issue. However, in many
other settings an agent may innovate and develop new methods to reduce their
cost of collecting a data point. In fact, the business model of large internet
advertising providers is based on systems which can cheaply capture consumer
data in order to show them better advertisements. Would our data-sharing
mechanism (12) disincentivize agents from such innovations? We show this is in
fact not true.

######  Theorem 4.6 (Incentive compatibility).

Under given costs $\mathbf{c}$, consider our optimal mechanism (13) with
equilibrium contributions $\mathbf{m}^{\max}$, and agents working individually
with equilibrium contributions of $\mathbf{m}^{\ast}$. The utility of the
every agent $i$ remains unchanged:

$a(\textstyle\sum_{j}m^{\max}_{j})-c_{i}m^{\max}_{i}=a(m_{i}^{\ast})-c_{i}m_{i}^{\ast}\,.$

Thus, our mechanism does not induce any distortions in the incentive
structure. Further, recall by Theorem 2.3, the utility
$u_{i}(m_{i}^{\ast})\geq u_{j}(m_{j}^{\ast})$ if $c_{i}\leq c_{j}$. This
implies that users with smaller costs continue to receive a higher utility,
encouraging them to innovate and reduce the costs; i.e., our mechanism is
incentive compatible. Of course this is assuming that the costs incurred by an
agent is verifiable. They cannot lie about the true cost, but may be able to
choose between different collection strategies.

######  Remark 4.7 (Distribution of surplus).

One may ask where the additional surplus which is generated by agents
collaborating has disappeared, since the agents receive none of it. Our
mechanism utilizes this surplus in order to extract additional data,
$m_{i}^{\max}-m_{i}^{\ast}$, from the agents. Thus, all the additional surplus
goes into improving the accuracy of the model and hence to the end consumers
of the model.

Finally, in Appendix B, we also show how to extend our framework to the
setting of unverifiable costs. Most of our conclusions translate to this
setting as well.

###  5 Discussion

We have initiated the study of mechanism design for data sharing, where the
goal is to maximize the amount of data collected and the accuracy of the final
model trained. We showed that the standard scheme of sharing each agent’s data
contribution with everyone else will inevitably lead to catastrophic free-
riding where at most a single agent is contributing any data. In particular,
this implies that when a learning problem is too difficult or expensive for a
single agent to solve on their own, it will remain insurmountable under naive
data sharing. Instead, more successful collaboration occurs if the data shared
is tuned to the contributions of each of the agents. Our analysis suggests
using a credible threat—agents receive the full benefit if they honestly
submit data, but free-riding behavior is penalized by reducing the quality of
the model returned. We presented examples of such schemes depending on whether
the costs are verifiable or not. Our framework and results can also be
extended to compensate for additional fixed joining costs, to allow the
accuracy functions $\\{a_{i}(m)\\}$ to be different across the agents, and to
employ general increasing convex cost functions $\\{c_{i}(m)\\}$. However, a
significant limitation is that we needed the data points to be _exchangeable_
; i.e., for an agent $i$, every data point is identical in value and cost. A
more general setting of heterogeneous data may exhibit qualitatively different
behavior. We also assumed that the value function $a(m)$ is known and did not
consider any privacy or data locality constraints. Under such constraints, we
would have to also incorporate data verification into our mechanism design to
prevent agents from submitting fake data points.

Despite such limitations, our proposed framework already yields rich insights
on the design of data-sharing mechanisms, and we believe that it has even
broader implications. The federated learning community has recently been
grappling with questions such as how to compensate the participants for their
contributions (Zhan et al., 2021), incorporating incentives (Zhan et al.,
2021), fairness constraints (Shi et al., 2021), and addressing privacy
concerns (Li et al., 2021). While numerous mechanisms with varying definitions
for each of these goals have been proposed, a principled manner to compare
them is absent. We believe that the data-maximization viewpoint may provide
such a principled framework—the idea is to come up with a mechanism which in
the long-term induces agent behavior that maximizes data (or, more generally,
value) creation.

### References

  * [1] Daron Acemoglu and Asu Ozdaglar.  Lecture notes for course “6.207/14.15 networks”.  https://economics.mit.edu/files/4711.  Accessed: 2022-01-30.
  * Baik [2020] Jeeyun Sophia Baik.  Data privacy against innovation or against discrimination?: The case of the california consumer privacy act (ccpa).  _Telematics and Informatics_ , 52, 2020.
  * Baumol [2004] William J Baumol.  Welfare economics and the theory of the state.  In _The Encyclopedia of Public Choice_ , pages 937–940. Springer, 2004.
  * Bich [2006] Philippe Bich.  Some fixed point theorems for discontinuous mappings.  _Cahiers de la Maison des Sciences Economiques_ , 2006.
  * Bolton and Dewatripont [2004] Patrick Bolton and Mathias Dewatripont.  _Contract Theory_.  MIT Press, 2004.
  * Bonawitz et al. [2019] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al.  Towards federated learning at scale: System design.  _Proceedings of Machine Learning and Systems_ , 1:374–388, 2019.
  * Cheng et al. [2020] Yong Cheng, Yang Liu, Tianjian Chen, and Qiang Yang.  Federated learning for privacy-preserving ai.  _Communications of the ACM_ , 63(12):33–36, 2020\.
  * Choi and Robertson [2019] Taehyon Choi and Peter J Robertson.  Contributors and free-riders in collaborative governance: A computational exploration of social motivation and its effects.  _Journal of Public Administration Research and Theory_ , 29(3):394–413, 2019.
  * Cong et al. [2020] Mingshu Cong, Han Yu, Xi Weng, and Siu Ming Yiu.  A game-theoretic framework for incentive mechanism design in federated learning.  In _Federated Learning_ , pages 205–222. Springer, 2020.
  * Ding et al. [2020] Ningning Ding, Zhixuan Fang, and Jianwei Huang.  Incentive mechanism design for federated learning with multi-dimensional private information.  In _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_ , pages 1–8. IEEE, 2020.
  * Donahue and Kleinberg [2021a] Kate Donahue and Jon Kleinberg.  Model-sharing games: Analyzing federated learning under voluntary participation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 5303–5311, 2021a.
  * Donahue and Kleinberg [2021b] Kate Donahue and Jon Kleinberg.  Optimality and stability in federated learning: A game-theoretic approach.  _Advances in Neural Information Processing Systems_ , 34, 2021b.
  * Flores et al. [2021] Mona Flores, Ittai Dayan, Holger Roth, Aoxiao Zhong, Ahmed Harouni, Amilcare Gentili, Anas Abidin, Andrew Liu, Anthony Costa, Bradford Wood, et al.  Federated learning used for predicting outcomes in SARS-COV-2 patients.  _Research Square_ , 2021.
  * Fraboni et al. [2021] Yann Fraboni, Richard Vidal, and Marco Lorenzi.  Free-rider attacks on model aggregation in federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1846–1854. PMLR, 2021.
  * Google [2022] Google.  Google ads data hub, 2022.  URL https://web.archive.org/web/20220423221048/https://developers.google.com/ads-data-hub/guides/intro.  Accessed on 2022.04.28.
  * Huang et al. [2020] Jiyue Huang, Rania Talbi, Zilong Zhao, Sara Boucchenak, Lydia Y Chen, and Stefanie Roos.  An exploratory analysis on users’ contributions in federated learning.  In _2020 Second IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA)_ , pages 20–29. IEEE, 2020.
  * Jia et al. [2019] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos.  Towards efficient data valuation based on the Shapley value.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1167–1176. PMLR, 2019.
  * Jones and Tonetti [2020] Charles I Jones and Christopher Tonetti.  Nonrivalry and the economics of data.  _American Economic Review_ , 110(9):2819–58, 2020\.
  * Kairouz et al. [2021] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Kang et al. [2019a] Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang.  Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory.  _IEEE Internet of Things Journal_ , 6(6):10700–10714, 2019a.
  * Kang et al. [2019b] Jiawen Kang, Zehui Xiong, Dusit Niyato, Dongdong Ye, Dong In Kim, and Jun Zhao.  Toward secure blockchain-enabled internet of vehicles: Optimizing consensus management using reputation and contract theory.  _IEEE Transactions on Vehicular Technology_ , 68(3):2906–2920, 2019b.
  * Kang et al. [2019c] Jiawen Kang, Zehui Xiong, Dusit Niyato, Han Yu, Ying-Chang Liang, and Dong In Kim.  Incentive design for efficient federated learning in mobile networks: A contract theory approach.  In _2019 IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS)_ , pages 1–5. IEEE, 2019c.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kim et al. [2019] Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong-Lyun Kim.  Blockchained on-device federated learning.  _IEEE Communications Letters_ , 24(6):1279–1283, 2019.
  * Konečnỳ et al. [2016a] Jakub Konečnỳ, H Brendan McMahan, Daniel Ramage, and Peter Richtárik.  Federated optimization: Distributed machine learning for on-device intelligence.  _arXiv preprint arXiv:1610.02527_ , 2016a.
  * Konečnỳ et al. [2016b] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016b.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Laffont and Martimort [2009] Jean-Jacques Laffont and David Martimort.  The theory of incentives.  In _The Theory of Incentives_. Princeton University Press, 2009.
  * Li et al. [2020] Li Li, Yuxi Fan, Mike Tse, and Kuo-Yi Lin.  A review of applications in federated learning.  _Computers & Industrial Engineering_, 149:106854, 2020\.
  * Li et al. [2021] Qinbin Li, Zeyi Wen, Zhaomin Wu, Sixu Hu, Naibo Wang, Yuan Li, Xu Liu, and Bingsheng He.  A survey on federated learning systems: vision, hype and reality for data privacy and protection.  _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * Lim et al. [2021] Wei Yang Bryan Lim, Jianqiang Huang, Zehui Xiong, Jiawen Kang, Dusit Niyato, Xian-Sheng Hua, Cyril Leung, and Chunyan Miao.  Towards federated learning in uav-enabled internet of vehicles: A multi-dimensional contract-matching approach.  _IEEE Transactions on Intelligent Transportation Systems_ , 22(8):5140–5154, 2021.
  * Lin et al. [2019] Jierui Lin, Min Du, and Jian Liu.  Free-riders in federated learning: Attacks and defenses.  _arXiv preprint arXiv:1911.12560_ , 2019.
  * Mancini [2021] James Mancini.  Data portability, interoperability and digital platform competition: Oecd background paper.  _Interoperability and Digital Platform Competition: OECD Background Paper (June 8, 2021)_ , 2021.
  * Maskin [1986] Eric Maskin.  The existence of equilibrium.  _The Review of Economic Studies_ , 53(1):1–26, 1986.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial Intelligence and Statistics_ , pages 1273–1282. PMLR, 2017.
  * Mohri et al. [2018] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of Machine Learning_.  MIT press, 2018.
  * Mohri et al. [2019] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh.  Agnostic federated learning.  In _International Conference on Machine Learning_ , pages 4615–4625. PMLR, 2019.
  * Richardson et al. [2020] Adam Richardson, Aris Filos-Ratsikas, and Boi Faltings.  Budget-bounded incentives for federated learning.  In _Federated Learning_ , pages 176–188. Springer, 2020.
  * Rieke et al. [2020] Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, et al.  The future of digital health with federated learning.  _NPJ Digital Medicine_ , 3(1):1–7, 2020.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3):211–252, 2015.  doi: 10.1007/s11263-015-0816-y.
  * Sarikaya and Ercetin [2019] Yunus Sarikaya and Ozgur Ercetin.  Motivating workers in federated learning: A Stackelberg game perspective.  _IEEE Networking Letters_ , 2(1):23–27, 2019\.
  * Sheller et al. [2018] Micah J Sheller, G Anthony Reina, Brandon Edwards, Jason Martin, and Spyridon Bakas.  Multi-institutional deep learning modeling without sharing patient data: A feasibility study on brain tumor segmentation.  In _International MICCAI Brainlesion Workshop_ , pages 92–104. Springer, 2018.
  * Shi et al. [2021] Yuxin Shi, Han Yu, and Cyril Leung.  A survey of fairness-aware federated learning.  _arXiv preprint arXiv:2111.01872_ , 2021.
  * Sim et al. [2020] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low.  Collaborative machine learning with incentive-aware model rewards.  In _International Conference on Machine Learning_ , pages 8927–8936. PMLR, 2020.
  * Smith [2004] Stephen A Smith.  _Contract Theory_.  OUP Oxford, 2004.
  * Tian et al. [2021] Mengmeng Tian, Yuxin Chen, Yuan Liu, Zehui Xiong, Cyril Leung, and Chunyan Miao.  A contract theory based incentive mechanism for federated learning.  _arXiv preprint arXiv:2108.05568_ , 2021.
  * Voigt and Von dem Bussche [2017] Paul Voigt and Axel Von dem Bussche.  The EU general data protection regulation (gdpr).  _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ , 10(3152676):10–5555, 2017.
  * Wang et al. [2020] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song.  A principled approach to data valuation for federated learning.  In _Federated Learning_ , pages 153–167. Springer, 2020.
  * Weinstein et al. [2013] John N Weinstein, Eric A Collisson, Gordon B Mills, Kenna R Shaw, Brad A Ozenberger, Kyle Ellrott, Ilya Shmulevich, Chris Sander, and Joshua M Stuart.  The cancer genome atlas pan-cancer analysis project.  _Nature genetics_ , 45(10):1113–1120, 2013.
  * Wen et al. [2019] Y Wen, W Li, H Roth, and P Dogra.  Federated learning powered by NVIDIA Clara, 2019.  URL https://web.archive.org/web/20220221070237/https://developer.nvidia.com/blog/federated-learning-clara/.  Accessed on 2022.04.28.
  * Xu et al. [2021] Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low.  Gradient driven rewards to guarantee fairness in collaborative machine learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Zhan et al. [2020] Yufeng Zhan, Peng Li, Zhihao Qu, Deze Zeng, and Song Guo.  A learning-based incentive mechanism for federated learning.  _IEEE Internet of Things Journal_ , 7(7):6360–6368, 2020.
  * Zhan et al. [2021] Yufeng Zhan, Jie Zhang, Zicong Hong, Leijie Wu, Peng Li, and Song Guo.  A survey of incentive mechanism design for federated learning.  _IEEE Transactions on Emerging Topics in Computing_ , 2021.
  * Zhang et al. [2022] Ning Zhang, Qian Ma, and Xu Chen.  Enabling long-term cooperation in cross-silo federated learning: A repeated game perspective.  _IEEE Transactions on Mobile Computing_ , 2022.

## Appendix

###  Appendix A Further Review on the Related Work and Contract Theory
Background

The literature on mechanism design and federated learning is vast. We
discussed the most closely related work in three verticals in the main text;
we include a detailed review of the broader literature in this section.

Over the past decade, federated learning (FL) has emerged as an important
paradigm in modern large-scale machine learning [Konečnỳ et al., 2016a, Kim et
al., 2019, Kairouz et al., 2021, Li et al., 2020, Rieke et al., 2020].
Specifically, FL research has resulted in many applications to overcome
practical challenges such as data silos and data sensitivity: on one side,
since more training data often gives better model performance, data silos
results in scarcity of labeled training data and puts limit on the industrial
performance; on the other side, in high-stakes applications the data may
contain private user information and thus the sharing of data is constrained
by regulations and laws [Voigt and Von dem Bussche, 2017, Baik, 2020, Cheng et
al., 2020, Mancini, 2021]. Given these challenges, FL provides a useful scheme
for different agents / parties to train collaboratively and leverage the
benefit from other agents’ data, while the training data remains distributed
over the agents. Such a framework has been shown to be able to bring improved
model performance to all the participants. Indeed, many prior works have been
devoted to develop more scalable and communication-efficient distributed
optimization algorithms for FL [Konečnỳ et al., 2016b, McMahan et al., 2017,
Bonawitz et al., 2019].

However, one cannot ignore an important aspect in the standard FL scheme,
which is the incentives aspect. The standard FL scheme may incentivize
strategic agents to contribute less data in order to minimize their data
collection cost and maximize the gain from participating in the federated
learning mechanism. Although the participation and contribution of each agent
is often legislated by certain protocols, such free-riding behavior has been
notoriously hard to regulate and prevent in practice [Fraboni et al., 2021,
Huang et al., 2020]. Recently, a few works have started to explore such free-
riding behavior in FL, with various incentive models proposed [Richardson et
al., 2020, Sarikaya and Ercetin, 2019, Lin et al., 2019, Fraboni et al., 2021,
Ding et al., 2020, Zhang et al., 2022]. However, the majority this work has
focused on a taxonomy of free-rider attacks or the detection of attacks under
the existing FL scheme, instead of proposing mechanisms that incentivize
maximal data contribution. In this work, we strive for a mechanism for
information sharing under the standard federated learning setting such that
rational agents are incentivized to contribute their maximal amount of data.

In this work, we focus on the free-riding behavior of FL agents in terms of
data collection. In FL, the data collection happen on the agents’ side before
they join the mechanism for training models. Therefore, the cost of collecting
data is often private information to each agent. Such an information asymmetry
brings difficulty to prevent free-riding, because the agents might simply
report fake costs. This brings the need to design incentive mechanisms for FL,
under which the agents are incentivized to behave truthfully, which is also
guaranteed to lead to the best utility.

Indeed, designing incentive mechanisms under private costs is not new, and has
been a main focus of the contract theory literature Smith [2004], Laffont and
Martimort [2009], Bolton and Dewatripont [2004]. Moreover, the existence of a
central server (a “principal”) in FL brings further convenience to apply a
principle-agent model. An emerging line of recent works have been exploring
the application of contract theory for federated learning [Kang et al., 2019b,
c, a, Lim et al., 2021, Tian et al., 2021, Cong et al., 2020, Zhan et al.,
2020]. In particular, Tian et al. [2021] proposed a contract-based aggregator
under a multi-dimensional contract model over two possible types of agents and
showed improved model generalization accuracy under that contract. However,
their mechanism focused on eliciting the private type information instead of
maximizing the data contribution. To the best of our knowledge, our work is a
first step to use contract theory for data maximization in federated learning.
Further, prior work has focused on how to design payments to agents, rather
than the accuracy-shaping problem that we focus on here.

This work is related to the active line of research on mechanism design for
collaborative machine learning, which involves multiple parties each with
their own data, jointly training a model or making predictions in a common
learning task [Sim et al., 2020, Xu et al., 2021]. In collaborative machine
learning, a major focus has been the design of model rewards (i.e., data
valuation) in order to ensure certain fairness or accuracy objectives. Towards
that goal, there has been model rewards proposed based on notions from the
cooperative game theory literature such as the Shapley value [Jia et al.,
2019, Wang et al., 2020]. However, the guarantees of these model rewards
depend on the assumption that the agents are already willing to contribute the
data they have. In this work, we study a different incentivization task for
data maximization.

More broadly, apart from data maximization, there are other objectives which
are of interest in federated learning, such as fairness and welfare
objectives, that have been under active study [Donahue and Kleinberg, 2021b,
a, Mohri et al., 2019]. We defer a thorough analysis of the tradeoffs among
various objectives to future research.

###  Appendix B Data Maximization under Unverifiable Costs

Until now, we assumed that the cost of all agents is known to everyone
involved, or is atleast verifiable. In some settings where the costs are
universal and outside the control of the agent, this assumption may be
justified. However, in numerous other cases, the exact process of the data
generation may be a trade secret and so there is uncertainty about the cost
incurred by an agent. In this section, we examine how to incorporate such
uncertainties into our mechanism.

We focus on the simplest version of this uncertainty. Suppose that we know
that the cost of each agent can either be low ($\underaccent{\bar}{c}$) or
high ($\bar{c}$). Further, suppose we have some prior knowledge where agent
$i$ has low cost $\underaccent{\bar}{c}$ with probability $p_{i}$ and
$\bar{c}$ with $(1-p_{i})$. Note that there is an inherent _information
asymmetry_ in this setting. The agent knows the realization of their cost,
$c_{i}\in\\{\bar{c},\underaccent{\bar}{c}\\}$, whereas the server only knows
the distribution from which it was drawn. In particular, the server needs to
present a mechanism $\mathcal{M}$ to an agent without knowing their actual
cost.

####  B.1 Mechanism description

Suppose each agent independently selects their cost to be low
$(c_{i}=\underaccent{\bar}{c})$ with probability $p_{i}$. Let an agent with
low cost $\underaccent{\bar}{c}$ generate $\underaccent{\bar}{m}^{\ast}$ data
points at equilibrium on their own (and correspondingly define
$\bar{m}^{\ast}$ for a high-cost agent). Then, for some small $\varepsilon>0$
and $\bar{m}^{\ast}\leq m_{i}^{\uparrow}\leq m_{i}^{\downarrow}$, consider the
following mechanism (illustrated in Figure 5)

$[\mathcal{M}(\mathbf{m})]_{i}=\begin{cases}a(m_{i})\quad&\text{for
}m_{i}\leq\bar{m}^{\ast}\\\
a(\bar{m}^{\ast})+(\bar{c}+\varepsilon)(m_{i}-\bar{m}^{\ast})\quad&\text{for
}m_{i}\in[\bar{m}^{\ast},m_{i}^{\uparrow}]\\\ a(m_{i}^{\downarrow}+\sum_{j\neq
i}m_{j})-(\underaccent{\bar}{c}+\varepsilon)(m_{i}^{\downarrow}-m_{i})\quad&\text{for
}m_{i}\in[m_{i}^{\uparrow},m_{i}^{\downarrow}]\\\
a(\sum_{j}m_{j})\quad&\text{for }m_{i}\geq m_{i}^{\downarrow}\,.\end{cases}$
(14)

Figure 5: Accuracy shaping mechanism under unknown costs. (red curve): model
accuracy returned to agent $i$ by the mechanism; (grey curve): model accuracy
for agent $i$ without participation; (green curve): model accuracy if agent
$i$ receives all the data from the other agents.

Recall from Theorem 2.3 that $\underaccent{\bar}{m}^{\ast}\geq\bar{m}^{\ast}$
since $\underaccent{\bar}{c}\leq\bar{c}$. Thus, agents with either costs do
not need additional incentive to collect data up to $\bar{m}^{\ast}$. Now,
consider a high-cost agent. After $\bar{m}^{\ast}$, they need a marginal gain
in accuracy of at least $\bar{c}$ which they do not get on their own.
Additional supplementary data is provided by (14) until $m_{i}^{\uparrow}$ to
incentivize a high-cost agent. It is now in their best interest to contribute
$m_{i}^{\uparrow}$. For the low-cost agent, the marginal gain in accuracy is
at least $\underaccent{\bar}{c}$ until $m_{i}^{\downarrow}$, making this their
best contribution. The specific values of $m_{i}^{\downarrow}$ and
$m_{i}^{\downarrow}$ (points D and C) can then be chosen to maximize the
expected data contribution
$((1-p_{i})m_{i}^{\uparrow}+p_{i}m_{i}^{\downarrow})$.

For $\Delta m_{\text{-}i}:=\sum_{j\neq i}m_{j}$, let $\bar{m}^{\max}$ be the
maximum amount of data a high-cost agent can be incentivized to contribute as
in (13) i.e. it is defined to be $a(\bar{m}^{\max}+\Delta
m_{\text{-}i})=a(\bar{m}^{\ast})+\bar{c}(\bar{m}^{\max}-\bar{m}^{\ast})$, and
$\underaccent{\bar}{m}^{\max}$ defined correspondingly for the low-cost agent.
Then, we define $m_{i}^{\downarrow}$ (point D) to satisfy

$a^{\prime}(m_{i}^{\downarrow}+\Delta
m_{\text{-}i})=\min\Big{(}\max\Big{(}\underaccent{\bar}{c}-\tfrac{p}{1-p}\bar{c}\
,\ a^{\prime}(\underaccent{\bar}{m}^{\max}+\Delta
m_{\text{-}i}\Big{)}\,,\,a^{\prime}(\bar{m}^{\max}+\Delta
m_{\text{-}i})\Big{)}\ .$ (15)

Then, we can define $m_{i}^{\uparrow}$ (point C) as the intersection of the
two linear curves (starting from A and D in Fig 5):

$a(m_{i}^{\downarrow}+\textstyle\sum_{j\neq
i}m_{j})-(\underaccent{\bar}{c}+\varepsilon)(m_{i}^{\downarrow}-m_{i}^{\uparrow})=a(\bar{m}^{\ast})+(\bar{c}+\varepsilon)(m_{i}^{\uparrow}-\bar{m}^{\ast})\,.$
(16)

Note that our mechanism withholds some data from a high-cost agent resulting
in a lower accuracy model for them. This is necessary to prevent a
contribution level targeted at high-cost agent from becoming attractive to a
low-cost agent.

####  B.2 Analysis

We now analyze the properties of our expected data-maximization algorithm.

######  Theorem B.1 (Expected data maximization).

Mechanism (14) is feasible, satisfies IR, and has a unique Nash equilibrium:
$m_{i}^{\text{eq}}=m_{i}^{\uparrow}$ if $c_{i}=\bar{c}$ and otherwise
$m_{i}^{\text{eq}}=m_{i}^{\downarrow}$. Further, for $\varepsilon\rightarrow
0^{+}$, the mechanism (14) maximizes the expected (over the sampling of the
true costs) amount of data collected with

$\textstyle\sum_{j}(1-p_{j})m_{j}^{\uparrow}+p_{j}m_{j}^{\downarrow}=\max_{\mathcal{M}}\left\\{\textstyle\sum_{j}\operatorname{\mathbb{E}}_{\mathbf{c}}[m_{j}^{\mathcal{M}}]\,,\text{
subject to $\mathcal{M}$ being feasible and IR}\right\\}\,.$

######  Remark B.2 (Decreased data collection).

By construction of our mechanism, the contribution of a high-cost agent would
be $m_{i}^{\uparrow}\in[\bar{m}^{\ast},\bar{m}^{\max}]$ i.e. they contribute
more than they would on their own, but lesser than the max possible under
known costs. Further, our assumption that $a(\cdot)$ is concave means
$a^{\prime}(\cdot)$ is non-increasing. Hence, (15) implies that the data
contributed by a low-cost agent is
$m_{i}^{\downarrow}\in[\bar{m}^{\max},\underaccent{\bar}{m}^{\max}]$. However,
if $p_{i}\geq\frac{\underaccent{\bar}{c}}{\underaccent{\bar}{c}+\bar{c}}$,
(14) always implies that $m_{i}^{\downarrow}=\underaccent{\bar}{m}^{\max}$.

We extract lesser data than if we knew the agent’s true cost i.e.
$m_{i}^{\uparrow}\leq\bar{m}^{\max}$. However, they also receive a model which
has worse accuracy with
$a(\bar{m}^{\ast})+\bar{c}(m_{i}^{\uparrow}-\bar{m}^{\ast})\leq
a(\sum_{j}m_{j})$ i.e. it is not trained on the combined data. This is because
if we offered a full accuracy model to a high-cost agent at
$\bar{m}^{\max}\leq m_{i}^{\downarrow}$ contribution, the low-cost agent can
claim they are actually high-cost and cheat our system. Instead, now the low-
cost agent will contribute $m_{i}^{\downarrow}\geq\bar{m}^{\max}$ and will
receive a model trained on the combined data with accuracy $a(\sum_{j}m_{j})$.

######  Theorem B.3 (Information rent).

Consider our optimal mechanism (14) with equilibrium contributions
$m_{i}^{eq}=m_{i}^{\uparrow}$ for a high-cost agent and
$m_{i}^{eq}=m_{i}^{\downarrow}$ for the low-cost agent. Further, let
$\bar{m}^{\ast}$ and $\underaccent{\bar}{m}^{\ast}$ be the equilibrium
individual contributions. Then, the utility of the high-cost agent remains
unchanged with
$a(\bar{m}^{\ast})+\bar{c}(m_{i}^{\uparrow}-\bar{m}^{\ast})-\bar{c}m_{i}^{\uparrow}=a(\bar{m}^{\ast})-\bar{c}\bar{m}^{\ast}\,.$
The utility of a low-cost agent, however, improves by
$\left(\underaccent{\bar}{c}(\underaccent{\bar}{m}^{\max}-m_{i}^{\downarrow})-a(\underaccent{\bar}{m}^{\max}+\Delta
m_{\text{-}i})+a(m_{i}^{\downarrow}+\Delta m_{\text{-}i})\right)\geq 0$.

Because a low-cost agent can always lie and pretend to be high cost, they hold
some power over the server when
$m_{i}^{\downarrow}<\underaccent{\bar}{m}^{\max}$. This is reflected in the
extra utility they manage to extract and is called information rent. The
utility of the high-cost agent remains unchanged since they hold no such
power.

######  Example B.4 (Computing decreased contributions).

Consider the accuracy function arising from the generalization guarantees in
Example 2.1, and $n$ agents whose marginal cost is chosen uniformly (i.e.
$p_{i}=1/2$) from the set $\\{\underaccent{\bar}{c},\bar{c}\\}$. Also suppose
that $m^{\ast}>0$ i.e. the cost satisfies $c\leq
a_{opt}^{3}/3\underaccent{\bar}{c}$. In this case, we know from Example 2.1
that the individual contribution is $\bar{m}^{\ast}=\sqrt[3]{k/(\bar{c})^{2}}$
and correspondingly
$\underaccent{\bar}{m}^{\ast}=\sqrt[3]{k/\underaccent{\bar}{c}^{2}}$. For
$p_{i}=1/2$, (14) implies that $m^{\downarrow}=\underaccent{\bar}{m}^{\max}$.
Further, the contribution of the high-cost agent is
$m^{\uparrow}=\gamma_{t}\bar{m}^{\ast}+(1-\gamma)\underaccent{\bar}{m}^{\ast}$
for some $\gamma\in[0,1]$. Thus, the high-cost agent’s contribution is in
between the individual contributions, while the low-cost agent contributes the
maximum amount they would have even if we knew their true cost.

###  Appendix C Proofs from Section 2 (Optimal Individual Contributions)

See 2.3

###### Proof.

Recall that the utility function (see Eq. 5) of a single agent is:

$u_{i}(m_{i})=a(m_{i})-c_{i}m_{i}.$

Thus we have,

$u_{i}^{\prime}(m_{i})=a^{\prime}(m_{i})-c_{i}.$

Denote $\operatorname*{arg\,max}_{m}a(m)=0$ as $m^{0}$. By definition,
$\forall m_{i}>m^{0}$, $a(m_{i})=b(m_{i})>0$. Given that $b(\cdot)$ is
concave, $b^{\prime}(m_{i}),m_{i}\geq m^{0}$ (or $u_{i}^{\prime}(m_{i})$) is
maximized when $m_{i}=m^{0}$.

##### Case 1 (high-cost agent): $u_{i}^{\prime}(m^{0})\leq 0$.

Then, for $\forall m_{i}\geq m^{0}$, $u_{i}^{\prime}(m_{i})\leq
u_{i}^{\prime}(m^{0})\leq 0$. On the other hand, $\forall 0\leq m_{i}\leq
m^{0}$, $u_{i}^{\prime}(m_{i})=-c_{i}\leq 0$. Thus $u_{i}(m_{i})$ is non-
increasing, and $m_{i}^{\ast}=0$. The utility function of an agent in this
case is illustrated in Figure 1 (d).

##### Case 2 (mid-cost agent): $u_{i}^{\prime}(m^{0})>0$ and
$\max_{m_{i}}u_{i}(m_{i})\leq 0$.

When $u_{i}^{\prime}(m^{0})>0$, that implies that at $m^{0}$,
$b^{\prime}(m^{0})>c_{i}$. Moreover, for $m_{i}\geq m^{0}$, we have that

$u_{i}^{\prime}(m_{i})=b^{\prime}(m_{i})-c_{i}<b^{\prime}(m^{0})-c_{i}.$

Therefore, since $b(m_{i})$ is concave, it is possible that $u_{i}(m_{i})$
increases first after $m^{0}$. However, as long as
$\max_{m_{i}}u_{i}(m_{i})\leq 0$, we still have that $m_{i}^{\ast}=0$. The
utility function of an agent in this case is illustrated in Figure 1 (c).

##### Case 3 (low-cost agent): $u_{i}^{\prime}(m^{0})>0$ and
$\max_{m_{i}}u_{i}(m_{i})>0$.

Recall that for a mid-cost agent, it is possible that $u_{i}(m_{i})$ increases
first after $m^{0}$. Moreover, given that $a(m_{i})\leq 1$, as
$m_{i}\rightarrow\infty$,

$u_{i}^{\prime}(m_{i})=b^{\prime}(m_{i})-c_{i}\leq 0.$

Therefore, there exists $\alpha_{i}^{\ast}>m^{0}>0$ such that
$b^{\prime}(\alpha_{i}^{\ast})=c_{i}$. The utility function of an agent in
this case is illustrated in Figure 1 (b).

Combining the three cases above completes the first part of the proof.

Next, consider two agents with costs $c_{i}\leq c_{j}$. Note that for any
fixed $m$, $u_{i}(m)\geq u_{j}(m)$. Hence, the inequality also holds after
minimizing both sides. Finally, note that if $j$ is not a low-cost agent, it
is clear that $m_{i}^{\ast}\geq m_{j}^{\ast}=0$. If both $i$ and $j$ are low-
cost agents, note that $m_{i}^{\ast}=b^{\prime-1}(c_{i})$ and
$m_{j}^{\ast}=b^{\prime-1}(c_{j})$. Since $b(\cdot)$ is concave and positive,
$b^{\prime}$ (and hence $b^{\prime-1}$) is non-increasing. This implies that
$m_{i}^{\ast}\geq m_{j}^{\ast}$ finishing the theorem. ∎

###  Appendix D Proofs from Section 3 (Modeling Multiple Agents and
Catastrophic Free-riding)

See 3.3

###### Proof.

For a set of contributions $\mathbf{m}$, define the following best response
mapping:

$[B(\mathbf{m})]_{i}:=\operatorname*{arg\,max}_{\tilde{m}_{i}\geq
0}\left\\{u_{i}(\tilde{m}_{i},\mathbf{m}_{-i}):=[\mathcal{M}(\tilde{m}_{i},\mathbf{m}_{-i})]_{i}-c_{i}\tilde{m}_{i}\right\\}\,,$
(17)

where recall $[\mathcal{M}(\tilde{m}_{i},\mathbf{m}_{-i})]_{i}$ is the
accuracy returned by the mechanism upon agent $i$ submitting $\tilde{m}_{i}$
data points and the rest contributing $\mathbf{m}_{-i}$. Note that the mapping
defined above is a multi-valued function i.e. $B:\mathbb{R}^{n}\rightarrow
2^{\mathbb{R}^{n}}$. This is because the $\operatorname*{arg\,max}$ defined
above may potentially return multiple values. Nevertheless, suppose that there
existed a fixed point to the mapping $B$ i.e. there existed
$\tilde{\mathbf{m}}$ such that $\tilde{\mathbf{m}}\in B(\tilde{\mathbf{m}})$.
Then, $\tilde{\mathbf{m}}$ is the required equilibrium contribution since by
definition of the arg-max we have for any $m_{i}\geq 0$,

$[\mathcal{M}(\tilde{m}_{i},\tilde{\mathbf{m}}_{-i})]_{i}-c_{i}\tilde{m}_{i}\geq[\mathcal{M}(m_{i},\tilde{\mathbf{m}}_{-i})]_{i}-c_{i}m_{i}\,.$

So, we only have to prove that the mapping $B$ has a fixed point. Since the
mechanism $\mathcal{M}$ is feasible, by Definition 3.1 and equation (1) we
have

$[\mathcal{M}(\mathbf{m})]_{i}\leq
a(\textstyle\sum_{j}m_{j})\leq\lim_{m\rightarrow\infty}a(m)\leq 1\,.$

This implies that

$0\geq u_{i}(\tilde{\mathbf{m}})\leq
1-c_{i}\tilde{m}_{i}\Rightarrow\tilde{m}_{i}\leq\nicefrac{{1}}{{c_{i}}}\,.$

Thus, we can restrict our search space to a _convex_ and _compact_ product set
$\mathcal{C}:=\prod_{j}\left[0,\nicefrac{{1}}{{c_{i}}}\right]\subset\mathbb{R}^{n}$
and our mapping is then over $B:\mathcal{C}\rightarrow 2^{\mathcal{C}}$. Next
by assumption on the mechanism $\mathcal{M}$, our utility function can be
written as

$u_{i}(m_{i},\mathbf{m}_{-i})=\max(-c_{i}m_{i}\,,\,\nu(m_{i},\mathbf{m}_{-i})-c_{i}m_{i})\,,$

where $\nu(m_{i},\mathbf{m}_{-i})-c_{i}m_{i}$ is concave in $m_{i}$.
Unfortunately, $u_{i}$ may not be quasi-concave in $m_{i}$ because of the max.
If it was quasi-concave, the mapping $B(\mathbf{m})$ would be continuous in
$\mathbf{m}$ and applying Kakutani’s theorem would yield the existence of the
required fixed point (see Maskin [1986] or Acemoglu and Ozdaglar [, Lecture
11], for details).

######  Lemma D.1 (Kakutani’s fixed point theorem).

Consider a multi-valued function $F:\mathcal{C}\rightarrow 2^{\mathcal{C}}$
over convex and compact domain $\mathcal{C}$ for which the output set
$F(\mathbf{m})$ i) is convex and closed for any fixed $\mathbf{m}$, and ii)
changes continuously as we change $\mathbf{m}$. For any such $F$, there exists
a fixed point $\mathbf{m}$ such that $\mathbf{m}\in F(\mathbf{m})$.

However, our utility function is not quasi-concave and the mapping $B$ may be
discontinuous. While there have been recent extensions of Kakutani’s fixed
point theorem to half-continuous functions (e.g. Bich [2006, Theorem 3.2]),
the mapping $B$ does not satisfy this either. We next study the exact nature
of discontinuity.

######  Lemma D.2.

Consider the best-response mapping $B$ in (17) over convex and compact domain
$\mathcal{C}$. For any $\mathbf{m}$, either the mapping $[B(\mathbf{m})]_{i}$
is convex, closed, and continuous in $\mathbf{m}$, or
$0\in[B(\mathbf{m})]_{i}$.

Figure 6: Utility curves $u(m_{i})$ of some agent $i$, and the corresponding
discontinuous best responses ($\tilde{m}_{i}\geq 0$ which maximizes
$u(m_{i})$). For both $u1$ and $u2$, the best response of the agent is
$\tilde{m}_{i}=0$ (point A), and points B and C are the best responses for
$u3$ and $u4$. A small change in the utility curves (from $u2$ to $u3$) can
result in a large change in the best response (from A to B).

###### Proof.

Figure 6 looks at the best response mapping $B_{i}$ depending on the utility
curve $u_{i}(\cdot,\mathbf{m}_{-i})$. Even if the utility itself is smoothly
varying with the parameters $\mathbf{m}$, the best response may be
discontinuous. In Fig. 6, for a small change in the utility curve between
$u2(m_{i})$ to $u3(m_{i})$, the best response drastically changes from
$\tilde{m}_{i}=0$ (A) to $\tilde{m}_{i}>125$ (B). However, this is the only
source of discontinuity.

Recall that our utility function $u_{i}$ is a max of a decreasing linear
function and a concave function. Thus it has at most two local maxima: either
0, or the maxima of the concave function
$f(m_{i})=\nu_{i}(m_{i};\mathbf{m}_{-i})-c_{i}m_{i}$. The set of maxima of a
continuous concave function is continuous, closed and convex. Hence, either
$0$ is part of the best response, or $[B(\mathbf{m})]_{i}$ is continuous,
closed and convex. ∎

Armed with Kakutani’s fixed point theorem Lemma D.1 and a description of the
discontinuities in the best response mapping Lemma D.2, we can continue with
the proof of existence of a fixed point for $B$. Given any index set
$\mathcal{I}\subseteq[n]$, we can define the following sub-domain
$\mathcal{C}_{\mathcal{I}}:=\prod_{i\in\mathcal{I}}[0,\nicefrac{{1}}{{c_{i}}}]$.
Given any vector $\mathbf{p}\in\mathcal{C}_{\mathcal{I}}$, we can construct
its extension $m(\mathbf{p};\mathcal{I})\in\mathcal{C}$ as

$[m(\mathbf{p};\mathcal{I})]_{i}:=\mathbf{p}_{i}\text{ if
}i\in\mathcal{I}\text{, and }0\text{ otherwise.}$

We will omit the $\mathcal{I}$ dependence and use $m(\mathbf{p})$ when clear
from context. Given this mapping between sub-domain
$\mathcal{C}_{\mathcal{I}}$ and the full domain $\mathcal{C}$, we can define a
mapping:

$B_{\mathcal{I}}(\mathbf{p}):\mathcal{C}_{\mathcal{I}}\rightarrow
2^{\mathcal{C}_{\mathcal{I}}}:=\left([B(m(\mathbf{p}))]_{i}\text{ for
}i\in\mathcal{I}\right)$

Finally, for any $\mathbf{m}\in\mathcal{C}$, define the set of indices
$\mathcal{I}(\mathbf{m})\subseteq[n]$ as

$\mathcal{I}(\mathbf{m}):=\\{i\text{ for which
}0\notin[B(\mathbf{m})]_{i}\,.\\}$

Let us start from $\mathbf{m}=\mathbf{0}$. If
$\mathcal{I}(\mathbf{0})=\emptyset$, we are done since this implies
$\mathbf{0}\in B(\textbf{0})$. Otherwise, Lemma D.2 states that the mapping
$B_{\mathcal{I}(\mathbf{0})}(\mathbf{p})$ over the compact convex domain
$\mathcal{C}_{\mathcal{I}(\mathbf{0})}$ is convex, compact and continuous.
Hence, by Lemma D.1, it has a fixed point such that $\mathbf{p}^{1}\in
B_{\mathcal{I}}(\mathbf{p}^{1})$. We can inductively continue applying the
same argument. If $m(\mathbf{p}^{1})$ is a fixed point of the full mapping $B$
with $m(\mathbf{p}^{1})\in B(m(\mathbf{p}^{1}))$, we are done. Otherwise,
$\mathcal{I}(m(\mathbf{p}^{1}))\supset\mathcal{I}(\mathbf{0})$ and we can
continue repeating the same argument inductively. Since the size of
$\mathcal{I}$ is at most $n$, the recursion will stop and yield a fixed point
$\tilde{\mathbf{m}}\in\mathcal{C}$ such that $\tilde{\mathbf{m}}\in
B(\tilde{\mathbf{m}})$. As we initially proved, this fixed point
$\tilde{\mathbf{m}}$ to the best response dynamics is also the equilibrium of
our mechanism.

∎

See 3.4

###### Proof.

Let $\tilde{i}$ be the agent with the least cost. By Theorem 2.3, it follows
that $m_{j}^{\ast}\leq m_{\tilde{i}}^{\ast}$ for all agents $j\in[n]$.

First, suppose that $m_{\tilde{i}}^{\ast}>0$. In this setting, all other
agents agent $j$ will have access to data contributed by $\tilde{i}$ which is
$m_{\tilde{i}}^{\ast}$. Now given access to this, the marginal gain in
accuracy for an additional data-point for any agent $j$ is less than their
cost i.e. $b^{\prime}(m_{\tilde{i}}^{\ast})=c_{\tilde{i}}\leq c_{j}$. Hence,
it is optimal for agent $j$ to just use $m_{\tilde{i}}^{\ast}$ data-points,
and not generate any additional data-points. Thus, the equilibrium is all
other agents contribute no data, and agent $\tilde{i}$ computes
$m_{\tilde{i}}^{\ast}$ datapoints as if on its own.

Next consider the case where $m_{\tilde{i}}^{\ast}=0$ and hence all
$m_{i}^{\ast}=0$. Suppose all the other agents in total contribute $\Delta m$
datapoints, which is given to all agents unconditionally. With this extra free
data, it is possible that there exists some agent for whom
$m_{\tilde{i}}^{\ast}>0$. However, the incentives of the agents remain
identical and so the agent with the least cost collects the most data. Given
access to this $\Delta m+m_{\tilde{i}}^{\ast}$ amount of data, agent $j$ with
higher cost $c_{j}\geq c_{\tilde{i}}$ has no incentive to collect any
additional data. Hence, only agent $\tilde{i}$ would collect any data and so
$\Delta m=0$. However, if $\Delta m=0$, agent $\tilde{i}$ also has no
incentive to collect any data. This implies that all agents contributing $0$
datapoints is the only Nash equilibrium possible. ∎

###  Appendix E Proofs from Section 4 (Accuracy Shaping under Known Costs)

See 4.2

##### Proof.

We will do the proof in two steps. Consider the best response
$B_{\mathcal{M}}$ of the agents to a mechanism $\mathcal{M}$ similar to the
definition in the proof of Theorem 3.3:

$[B_{\mathcal{M}}(\mathbf{m})]_{i}:=\operatorname*{arg\,max}_{m_{i}\geq
0}[\mathcal{M}(m_{i},\mathbf{m}_{-i})]_{i}-c_{i}m_{i}\,.$

We will first prove that given a fixed contribution $\mathbf{m}$ from other
users, the best response for our mechanism $m_{i}^{\max}$ is higher than that
of any other feasible and IR mechanism. We will then show that this
necessarily implies that the equilibrium contribution of the agent is also
data maximizing.

######  Lemma E.1.

For a given data contribution $\mathbf{m}$ and any feasible and IR mechanism
$\tilde{\mathcal{M}}$, define best responses $B_{\mathcal{M}}(\mathbf{m})$ and
$B_{\tilde{\mathcal{M}}}(\mathbf{m})$ for our mechanism $\mathcal{M}$ (defined
in (13)) and the other mechanism $\tilde{\mathcal{M}}$. Then, for any agent
$i$ and contribution $\mathbf{m}$,

$[B_{\mathcal{M}}(\mathbf{m})]_{i}\geq[B_{\tilde{\mathcal{M}}}(\mathbf{m})]_{i}\,.$

Further, the best response $[B_{\mathcal{M}}(\mathbf{m})]_{i}$ is non-
decreasing in the net contribution from other agents $(\sum_{j\neq
i}\mathbf{m}_{j})$.

For now, we will assume that the above lemma and continue with our proof. As
shown in the proof of Theorem 3.3, the equilibrium of all feasible mechanisms
(if they exist) lie in the range
$\mathcal{C}:=\prod_{i}[0,\nicefrac{{1}}{{c_{i}}}]$. Suppose that
$\tilde{\mathbf{m}}\in\mathcal{M}$ is the equilibrium of mechanism
$\tilde{\mathcal{M}}\in\mathcal{M}$. Note that $\tilde{\mathbf{m}}$ is also
the fixed point of the best response with $\tilde{\mathbf{m}}\in
B_{\tilde{\mathcal{M}}}(\tilde{\mathbf{m}})$. Now, define the following
subspace

$\mathcal{C}_{\geq\tilde{\mathbf{m}}}:=\prod_{j}[\tilde{\mathbf{m}}_{j},\nicefrac{{1}}{{c_{j}}}]\,.$

The set $\mathcal{C}_{\geq\tilde{\mathbf{m}}}$ is compact and convex. Thus, we
can apply Theorem 3.3 to our optimal mechanism $\mathcal{M}$ to prove that
there exists an equilibrium point
$\mathbf{m}\in\mathcal{C}_{\geq\tilde{\mathbf{m}}}$ such that

$[\mathbf{m}]_{i}\in\operatorname*{arg\,max}_{m_{i}\geq\tilde{m}_{i}}[\mathcal{M}(m_{i},\mathbf{m}_{-i})]_{i}-c_{i}m_{i}\,.$

We will next show that the above point $\mathbf{m}$ is in fact a fixed of
$B_{\mathcal{M}}(\mathbf{m})$ and satisfies:

$[\mathbf{m}]_{i}\in\operatorname*{arg\,max}_{m_{i}\geq
0}[\mathcal{M}(m_{i},\mathbf{m}_{-i})]_{i}-c_{i}m_{i}\,.$

Note that the only difference between the two claims is that in the latter the
$\operatorname*{arg\,max}$ is taken over $\geq 0$ where as it was more
constrained in the former. For the sake of contradiction, suppose this is not
true i.e. there exists an agent $i$ such that
$\mathbf{m}_{i}\notin[B_{\mathcal{M}}(\mathbf{m})]_{i}$ and
$[B_{\mathcal{M}}(\mathbf{m})]_{i}<\tilde{\mathbf{m}}_{i}$. However, this
leads to a contradiction:

$\displaystyle\sum_{j\neq i}\mathbf{m}_{j}\geq\sum_{j\neq
i}\tilde{\mathbf{m}}_{j}$ $\displaystyle\Rightarrow$
$\displaystyle[B_{\mathcal{M}}(\mathbf{m})]_{i}\geq[B_{\mathcal{M}}(\tilde{\mathbf{m}})]_{i}\geq[B_{\tilde{\mathcal{M}}}(\tilde{\mathbf{m}})]_{i}=\tilde{\mathbf{m}}_{i}\,.$

The first inequality is because
$\mathbf{m}\in\mathcal{C}_{\geq\tilde{\mathbf{m}}}$. The first inequality in
the second step follows from the latter part of Lemma E.1 while the next
inequality is from the first part. Finally, the last equality follows because
$\tilde{\mathbf{m}}$ is a fixed point of $B_{\tilde{\mathcal{M}}}$. Hence, we
have proven that there exists a fixed point $\mathbf{m}\in
B_{\mathcal{M}}(\mathbf{m})$ such that
$\mathbf{m}\in\mathcal{C}_{\geq\tilde{\mathbf{m}}}$ i.e. the equilibrium
contribution of every agent under $\mathcal{M}$ is at least as much as
$\tilde{\mathcal{M}}$. ∎

##### Proof of Lemma E.1.

Recall the optimal mechanism defined in (13) restated below:

$[\mathcal{M}(\mathbf{m})]_{i}=\begin{cases}a(m_{i})\quad&\text{for }m_{i}\leq
m_{i}^{\ast}\\\
a(m_{i}^{\ast})+(c_{i}+\varepsilon)(m_{i}-m_{i}^{\ast})\quad&\text{for
}m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]\\\ a(\sum_{j}m_{j})\quad&\text{for
}m_{i}\geq m_{i}^{\max}\,.\end{cases}$ (18)

For now, suppose that $m_{i}^{\ast}>0$. Recall, from [case 3, Theorem 2.3],
that this implies $a^{\prime}(m_{i}^{\ast})=b^{\prime}(m_{i}^{\ast})=c_{i}$.

First we show that $m_{i}^{\max}$ is the unique equilibrium contribution for
an agent $i$. The slope of the utility of agent $i$ is

$u_{i}^{\prime}(m_{i};\mathcal{M})=\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial
m_{i}}-c_{i}\,.$

By construction, this slope is $u_{i}^{\prime}(m_{i};\mathcal{M})>0$ for any
$m_{i}<m_{i}^{\max}$. Suppose the contribution of all other agents is fixed to
$\Delta m_{\text{-}i}=\sum_{j\neq i}m_{j}$. The slope of the utility at
$m_{i}^{\max}$ is
$u_{i}^{\prime}(m_{i}^{\max};\mathcal{M})=a^{\prime}(m_{i}^{\max}+\Delta
m_{\text{-}i})-c_{i}$. Again, by construction, $m_{i}^{\max}+\Delta
m_{\text{-}i}\geq m_{i}^{\ast}$. Since $b$ is concave and $b^{\prime}$ is non-
increasing,

$u_{i}^{\prime}(m_{i}^{\max};\mathcal{M})=a^{\prime}(m_{i}^{\max}+\Delta
m_{\text{-}i})-c_{i}=b^{\prime}(m_{i}^{\max}+\Delta m_{\text{-}i})-c_{i}\leq
b^{\prime}(m_{i}^{\ast})-c_{i}=0\,.$

Thus, $m_{i}^{\max}$ is the unique equilibrium contribution of agent $i$.
Next, we have to demonstrate the data-maximizing property. For the sake of
contradiction, suppose there existed some other mechanism
$\tilde{\mathcal{M}}$ such that

$\operatorname*{arg\,max}_{m_{i}}[\tilde{\mathcal{M}}(\mathbf{m})]_{i}-c_{i}m_{i}=:\tilde{m}_{i}>m_{i}^{\max}\,.$

This implies that $u_{i}^{\prime}(m_{i};\tilde{\mathcal{M}})>0$ for any
$m_{i}\leq\tilde{m}_{i}$, i.e.
$\frac{\partial[\tilde{\mathcal{M}}(\mathbf{m})]_{i}}{\partial m_{i}}>c_{i}$.
In particular, this implies that

$\frac{\partial[\tilde{\mathcal{M}}(\mathbf{m})]_{i}}{\partial
m_{i}}>\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial m_{i}}\text{ for
all }m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]\,.$

Further, $\tilde{\mathcal{M}}$ satisfies individual rationality and so at
$m_{i}=m_{i}^{\ast}$ we have

$[\tilde{\mathcal{M}}(m_{i}^{\ast},\mathbf{m}_{\text{-}i})]_{i}\geq
a(m_{i}^{\ast})=[\mathcal{M}(m_{i}^{\ast},\mathbf{m}_{\text{-}i})]_{i}\,.$

Together, these two conditions imply that for all
$m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]$, we have
$[\tilde{\mathcal{M}}(\mathbf{m})]_{i}>[\mathcal{M}(\mathbf{m})]_{i}$. In
particular at $m_{i}=m_{i}^{\max}$, we have

$[\tilde{\mathcal{M}}(m_{i}^{\max},\mathbf{m}_{\text{-}i})]_{i}>a(\textstyle\sum_{j}m_{j})\,.$

This gives us a contradiction since it violates feasibility. Thus,
$m_{i}^{\max}$ is the maximum data which can be extracted from agent $i$.

The proofs for the low and medium cost agents are similar, while noting that
$m_{i}^{\ast}=0$. This finishes the proof of the first part. The second part
of the lemma follows directly from the definition of $\mathcal{M}$ and the
fact that the accuracy function $a(m_{i}+\sum_{j\neq i}m_{j})$ is non-
decreasing in the contributions $\sum_{j\neq i}m_{j}$. ∎

See 4.6

###### Proof.

This statement is true by construction of our mechanism. When
$\varepsilon\rightarrow 0$, the slope of the utility becomes

$u_{i}^{\prime}(m_{i};\tilde{\mathcal{M}})=\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial
m_{i}}-c_{i}=c_{i}+\varepsilon-c_{i}=0\text{ for all
}m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]\,.$

Further, note that at $m_{i}=m_{i}^{\ast}$, we have
$[\mathcal{M}(m_{i}^{\ast},\mathbf{m}_{\text{-}i})]_{i}=a(m_{i}^{\ast})$.
Thus, for all $m_{i}\in[m_{i}^{\ast},m_{i}^{\max}]$, the utility of agent $i$
with our mechanism $\mathcal{M}$ remains constant and equal to the optimal
individual utility $u_{i}(m_{i}^{\ast})$. ∎

###  Appendix F Proofs from Appendix B (Data Maximization with Unverifiable
Costs)

See B.1

###### Proof.

Recall that we had defined the mechanism (14) as

$[\mathcal{M}(\mathbf{m})]_{i}=\begin{cases}a(m_{i})\quad&\text{for
}m_{i}\leq\bar{m}^{\ast}\\\
a(\bar{m}^{\ast})+(\bar{c}+\varepsilon)(m_{i}-\bar{m}^{\ast})\quad&\text{for
}m_{i}\in[\bar{m}^{\ast},m_{i}^{\uparrow}]\\\ a(m_{i}^{\downarrow}+\sum_{j\neq
i}m_{j})-(\underaccent{\bar}{c}+\varepsilon)(m_{i}^{\downarrow}-m_{i})\quad&\text{for
}m_{i}\in[m_{i}^{\uparrow},m_{i}^{\downarrow}]\\\
a(\sum_{j}m_{j})\quad&\text{for }m_{i}\geq m_{i}^{\downarrow}\,.\end{cases}$
(19)

First, we have to show that $m_{i}^{\uparrow}$ and $m_{i}^{\downarrow}$ are
equilibrium for the high and low cost players $\bar{c}$ and
$\underaccent{\bar}{c}$ respectively. For the sake of simplicity, we first
assume that $\bar{m}^{\ast}>0$ and $\underaccent{\bar}{m}^{\ast}>0$. The
proofs directly extend to the other cases. Now, note that
$a^{\prime}(\bar{m}^{\ast})=b^{\prime}(\bar{m}^{\ast})=\bar{c}$. Thus, by
constructions, we have that for a high cost agent,

$u_{i}^{\prime}(m_{i};\mathcal{M})=\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial
m_{i}}-\bar{c}>0\text{ for all }m_{i}\leq m_{i}^{\uparrow}\,.$

where as for $m_{i}>m_{i}^{\uparrow}$, the slope
$u_{i}^{\prime}(m_{i};\mathcal{M})=\underaccent{\bar}{c}+\varepsilon-\bar{c}<0$.
Assuming $\varepsilon$ is small enough, a high cost agent obtains optimal
utility at $m_{i}^{\uparrow}$. Similarly, for the low cost agent,
$u_{i}^{\prime}(m_{i};\mathcal{M})>0$ for all $m_{i}<m_{i}^{\downarrow}$ and
is negative after (similar to Theorem 4.2). Thus, the optimum contribution of
the low cost player is $m_{i}^{\downarrow}$.

Next, recall that we had defined in (15) that $m_{i}^{\downarrow}$ satisfies

$m_{i}^{\downarrow}=\min\Big{(}\max\Big{(}b^{\prime-1}\left(\underaccent{\bar}{c}-\tfrac{p_{i}}{1-p_{i}}\bar{c}\right)-\Delta
m_{\text{-}i}\ ,\
\bar{m}^{\max}\Big{)}\,,\,\underaccent{\bar}{m}^{\max}\Big{)}\ .$ (20)

We will show that $m_{i}^{\downarrow}$ defined this way maximizes the expected
data for agent $i$:

$\max_{m_{i}^{\downarrow}}\left\\{(1-p_{i})m_{i}^{\uparrow}+p_{i}m_{i}^{\downarrow}\right\\}\text{
subject to }m_{i}^{\uparrow},m_{i}^{\downarrow}\text{ are feasible for
}\mathcal{M}\,.$ (21)

Figure 7: Accuracy shaping mechanism under unknown costs. (red curve): model
accuracy returned to agent $i$ by the mechanism; (grey curve): model accuracy
for agent $i$ without participation; (green curve): model accuracy if agent
$i$ receives all the data from the other agents. Point C and D (in red) and
points E and F (in blue) represent two different choices for ($m^{\uparrow}$
and $m^{\downarrow}$) respectively. If we choose a smaller value of
$m^{\downarrow}$ (shown in blue by point F), we would see an increase in
$m^{\uparrow}$ to point E. Thus, the optimum value balances these two
depending on the probability $p_{i}$. Finally, points I and J (in magenta)
represent potential other mechanisms $\tilde{\mathcal{M}}$.

This involves some variational calculus (see Fig. 7). As shown in Fig. 7,
reducing the value of $m_{i}^{\downarrow}$ results in an increase in
$m_{i}^{\uparrow}$. Suppose we push the blue bar vertically by a small value
$dx$. Because the slope of AC is $\bar{c}$, this results in increase of
$\frac{dx}{\bar{c}}$ in $m_{i}^{\uparrow}$. Correspondingly, we can show that
the decrease in $m_{i}^{\downarrow}$ will be
$\frac{dx}{\underaccent{\bar}{c}-a^{\prime}(m_{i}^{\downarrow}+\Delta
m_{\text{-}i})}$. Putting these together, the net expected change in data
contribution is

$(1-p_{i})\frac{dx}{\bar{c}}-\frac{dx}{\underaccent{\bar}{c}-b^{\prime}(m_{i}^{\downarrow}+\Delta
m_{\text{-}i})}\,.$

The local unconstrained maxima can then be derived by setting the above to 0
i.e when

$b^{\prime}(m_{i}^{\downarrow}+\Delta
m_{\text{-}i})=\underaccent{\bar}{c}-\tfrac{p_{i}}{1-p_{i}}\bar{c}\,.$

Of course, we have to respect the constraints that
$m_{i}^{\downarrow}\in[\bar{m}^{\max},\underaccent{\bar}{m}^{\max}]$ giving us
our final result. Thus, the value of $m_{i}^{\downarrow}$ as chosen by (21) is
optimal for these class of mechanisms.

Now, we have to show that any data-maximizing mechanism corresponds to
$\mathcal{M}$ with some choice of $m_{i}^{\downarrow}$. Consider a mechanism
$\tilde{\mathcal{M}}$ whose equilibrium contributions are ($\tilde{m}$,
$\underaccent{\tilde}{m}$) for a high and low-cost agent respectively (see
points I and J in Fig. 7). Now, from the optimality of
$\underaccent{\bar}{m}^{\max}$, we know that
$\underaccent{\tilde}{m}\leq\underaccent{\bar}{m}^{\max}$. Let us connect
$\bar{m}^{\ast}$ (point A) to $\tilde{m}$ (point I) and then to
$\underaccent{\tilde}{m}$ (point J). Recall that we assumed that
$\tilde{\mathcal{M}}$ is different from $\mathcal{M}$ in (14). This means that
the slope AI $\neq\bar{c}$ or IJ $\neq\underaccent{\bar}{c}$. Consider the
latter. Combined with I and J corresponding to equilibria, we have slope of IJ
$>\underaccent{\bar}{c}$. This implies that starting from point I, we could
have instead drawn a line segment of slope $\underaccent{\bar}{c}$ and
increased the data contribution by the low cost agent, while keeping the
contribution of the high-cost agent fixed. Similarly, we can show that the
optimal slope for AI is $\bar{c}$. Together, this implies that any optimal
mechanism $\mathcal{M}$ must be of the form (14), finishing our proof. ∎

See B.3

###### Proof.

For a high cost player, the statement easily follows since
$\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial m_{i}}-\bar{c}=0$ for
all $m_{i}\in[\bar{c}^{\ast},c_{i}^{\uparrow}]$. Thus, a high cost player’s
utility remains constant during this period and is equal to utility at
$m_{i}=\bar{m}^{\ast}$ which is $a(\bar{m}^{\ast})-\bar{c}\bar{m}^{\ast}$.

For a low cost agent, $\frac{\partial[\mathcal{M}(\mathbf{m})]_{i}}{\partial
m_{i}}-\bar{c}=0$ for all $m_{i}\in[m_{i}^{\uparrow},m_{i}^{\downarrow}]$, and
hence their utility is constant in this region. In particular, the difference
in utility with mechanism $\mathcal{M}$ and alone is

$a(m_{i}^{\downarrow}+\Delta
m_{\text{-}i})-\underaccent{\bar}{c}m_{i}^{\downarrow}-a(\underaccent{\bar}{m}^{\max}+\Delta
m_{\text{-}i})+\underaccent{\bar}{c}\underaccent{\bar}{m}^{\max}\,.$

The above quantity is always non-negative since $a^{\prime}(m_{i}+\Delta
m_{\text{-}i})\leq\underaccent{\bar}{c}$ for all
$m_{i}\in[m_{i}^{\downarrow},\underaccent{\bar}{m}^{\max}]$. ∎