# Unravelling in Collaborative Learning

Aymeric Capitaine1
&Etienne Boursier2
Antoine Scheid1
&Eric Moulines1
&Michael I. Jordan3
&El-Mahdi El-Mhamdi1
Alain Durmus1

###### Abstract

Collaborative learning offers a promising avenue for leveraging decentralized
data. However, collaboration in groups of strategic learners is not a given.
In this work, we consider strategic agents who wish to train a model together
but have sampling distributions of different quality. The collaboration is
organized by a benevolent aggregator who gathers samples so as to maximize
total welfare, but is unaware of data quality. This setting allows us to shed
light on the deleterious effect of adverse selection in collaborative
learning. More precisely, we demonstrate that when data quality indices are
private, the coalition may undergo a phenomenon known as _unravelling_ ,
wherein it shrinks up to the point that it becomes empty or solely comprised
of the worst agent. We show how this issue can be addressed without making use
of external transfers, by proposing a novel method inspired by probabilistic
verification. This approach makes the grand coalition a Nash equilibrium with
high probability despite information asymmetry, thereby breaking unravelling.

1 Centre de Mathématiques Appliquées – CNRS – École polytechnique – Palaiseau,
91120, France
2 INRIA Saclay, Université Paris Saclay, LMO - Orsay, 91400, France
3 Inria, Ecole Normale Supérieure, PSL Research University - Paris, 75, France

##  1 Introduction

Collaborative learning is a framework in which multiple agents share their
data and computational resources to address a common learning task (Blum et
al., 2017; Kairouz et al., 2021). A significant challenge arises when the
quality of these distributions is unknown centrally and agents are strategic.
Indeed, participants may be tempted to withhold or misrepresent the quality of
their data to gain a competitive advantage. These strategic behaviors and
their consequences have been studied extensively in the literature on
information economics (Mas-Colell et al., 1995; Laffont and Martimort, 2001).
In particular, information asymmetry is known to result in adverse selection,
whereby low-quality goods end up dominating the market. In the current paper
we study collaborative learning from the perspective of information economics.

A vivid illustration of adverse selection is found in Akerlof’s seminal work
on the market for lemons (second-hand cars of low quality, Akerlof, 1970).
Because buyers cannot properly assess the quality of cars on the second-hand
market, their inclination to pay decreases. As a consequence, sellers with
high-quality cars withdraw from the market, since the proposed price falls
below their reservation price. This in turn lowers the buyers’ expectation
regarding the average quality of cars on the market, so their willingness to
pay decreases even more, which de facto crowds out additional cars. The market
may therefore enter a death spiral, up to the point where only low-quality
cars are exchanged in any competitive Nash equilibrium. This phenomenon is
known as unravelling. The insurance market serves as another poignant example
of this effect (Rothschild and Stiglitz, 1976; Einav and Finkelstein, 2011;
Hendren, 2013). In insurance, information asymmetry arises due to the fact
that insurees possess private knowledge about their individual risk profiles,
which insurers lack. Individuals with higher risk are more inclined to
purchase policy, while those with lower risk opt out. Consequently, insurers
are left with a pool of policyholders skewed towards higher risk, leading to
increased premiums to cover potential losses. This, in turn, prompts low-risk
individuals to exit the market, exacerbating adverse selection further—a cycle
reminiscent of the unravelling described by Akerlof.

We study the problem of whether collaborative learning could also fall victim
to unravelling. We consider strategic agents who have access to sampling
distributions of varying quality and wish to jointly train a model. They
delegate the training process to a central authority who collects samples so
as to maximize total welfare. We ask whether adverse selection can arise when
data quality is private information. In particular, the presence of a low-
quality data owner may harm the model, prompting high-quality owner to leave
the collaboration and train a model entirely on their own. Their departure
would decrease the average data quality even more, and create a vicious
circle. In the worst case, the coalition of learners would reduce to the
lowest data quality owner alone. This question is of prime importance from a
practical point of view, because unravelling could jeopardize the long-run
stability of collaborative models deployed at large scale.

Our contribution is threefold:

  1. 1.

We provide a rigorous framework for analyzing collaborative learning with
strategic agents having data distributions of varying quality. On the one
hand, we leverage tools from domain adaptation to capture a notion of data
quality formally. On the other hand, collaboration is modeled as a principal-
agent problem, where the principal is an aggregator in charge of collecting
samples so as to maximize social welfare. This setup allows us to derive the
benchmark welfare-maximizing collaboration scheme when data quality is public
information.

  2. 2.

We show that when data quality is private, a naive aggregation strategy which
consists in asking agents to declare their quality type and applying the
optimal scheme results in a complete unravelling. More precisely, the set of
agents willing to collaborate is either empty or made of the lowest-quality
data owner alone at any pure Nash equilibrium.

  3. 3.

We present solutions to unravelling. When transfers are allowed, the VCG
mechanism suffices to re-establish optimality. When transfers are not
possible, we leverage probabilistic verification techniques to design a
mechanism which breaks unravelling. More precisely, we ensure that the
optimal, grand coalition ranks with high probability among the Nash equilibria
of the game induced by our mechanism. We demonstrate how to implement our
mechanism practically in the setting of classification.

#### Related work.

The issue of information asymmetry in machine learning has been an area of
recent activity. Several learning settings have been considered, including
bandits (Wei et al., 2024), linear regression (Donahue and Kleinberg, 2021a,
b), classification (Blum et al., 2021) and empirical risk minimization (Dorner
et al., 2023; Liu et al., 2023) in a federated context (Tu et al., 2022).

Most of these studies focus on the sub-problem of moral hazard, where agents
take actions that are unobserved by others. This situation usually results in
under-provision of effort and inefficiency at the collective scale (Laffont
and Martimort, 2001). This issue appears naturally in federated learning,
because model updates are performed locally. For instance, Karimireddy et al.
(2022) show that heterogeneity in sampling costs results in total free-riding
without a proper incentive scheme. Huang et al. (2022) show that under-
provision of data points in federated learning arises from privacy concerns.
Yan et al. (2023) consider a federated classification game where agents can
reduce the noise in their data distribution but incur a costly effort to do
so. In the same vein, Huang et al. (2023) study the case of agents who are
interested in different models, and may skew their sampling measure
accordingly. Saig et al. (2023) and Ananthakrishnan et al. (2023) study hidden
actions when a principal delegates a predictive task to another agent, and
show that thresholds or linear contracts are able to approximate the optimal
contracts.

Adverse selection is another type of information asymmetry, where preferences
of agents are unobserved rather than actions. This issue also naturally arises
in collaborative learning, because the data distributions from which agents
sample or about which they care may not be public. While data heterogeneity is
a widely explored topic in federated learning (see for instance Gao et al.
2022 for a general survey, and Fu et al. 2023 for the specific problem of
client selection), the strategic aspect has been rarely considered. Most
studies doing so focus on hidden sampling costs (see, e.g., Karimireddy et al.
2022, or Wei et al. 2024 in a bandit context), but few address the fundamental
problem of distribution shift. Ananthakrishnan et al. (2023) mentions the
issue of adverse selection when a principal delegates a predictive task to an
agent, and provide qualitative insights about the optimal contract. However,
they consider a single agent and leave aside the question of participation.
Finally, Werner et al. (2024) and Tsoy and Konstantinov (2023) study the
question of the stability of collaborative learning between competing agents.
However, their analysis relies on ad-hoc market structures rather than
information asymmetry per se. As such, our work is the first to demonstrate
the effect of imperfect information on the sustainability of collaborative
learning.

#### Organization.

Section 2 presents our model and assumptions. Section 3 studies a full
information benchmark, which allows us to derive the welfare-maximizing
contribution scheme. In Section 4, we turn to the more realistic case where
data quality is private information. We first show that in this case, a naive
aggregation method leads to total unravelling. Second, we introduce a
mechanism which breaks unravelling by inducing a game where the grand
coalition is a pure strategy Nash equilibrium with high probability.

##  2 Model

#### Statistical framework.

Let $(\mathsf{X},\mathcal{X})$ and $(\mathsf{Y},\mathcal{Y})$ be two
measurable spaces and denote by $\mathcal{P}$ a family of probability measures
on $(\mathsf{X}\times\mathsf{Y},\mathcal{X}\otimes\mathcal{Y})$. We consider
$\mathopen{}\mathclose{{}\left[J}\right]=\\{1,\ldots,J\\}$ agents who aim to
perform a prediction task associated with a hypothesis class
$\mathscr{G}\subset\\{g:\mathsf{X}\to\mathsf{Y}\\}$, a loss function
$\ell:\mathsf{Y}\times\mathsf{Y}$ and a probability measure
$P_{0}\in\mathcal{P}$. Each agent seeks to minimize
$g\in\mathscr{G}\mapsto\mathcal{R}_{P_{0}}\mathopen{}\mathclose{{}\left(g}\right)$
where for any probability distribution $P\in\mathcal{P}$,
$\mathcal{R}_{P}\mathopen{}\mathclose{{}\left(g}\right)=\int\ell(g(x),y)\mathrm{d}P(x,y)$
is the risk associated to $g\in\mathscr{G}$ with respect to $P$.

We leverage tools and results from statistical learning theory. Denote by
$\\{(X_{i},Y_{i})\\}_{i\geqslant 1}$ the canonical process on
$\mathsf{X}\times\mathsf{Y}$ and denote by $\mathbb{P}_{P}$ and
$\mathbb{E}_{P}$ the canonical probability and expectation under which
$\\{(X_{i},Y_{i})\\}_{i\geqslant 1}$ are i.i.d. random variables with
distribution $P\in\mathcal{P}$. With this notation, we can introduce our
assumptions on $\mathscr{G}$ and $\mathcal{P}$.

######  H 1.

For $\delta\in(0,1)$, there exist $\alpha_{\delta}>0$, $\beta>0$ and
$\gamma>0$ such that for any distribution $P\in\mathcal{P}$, hypothesis
$g\in\mathcal{G}$ and $n\geqslant 1$

$\mathbb{P}_{P}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left|\mathcal{R}_{P}\mathopen{}\mathclose{{}\left(g}\right)-\frac{1}{n}\sum_{i=1}^{n}\ell(g(X_{i}),Y_{i})}\right|\leqslant\frac{\alpha_{\delta}}{(1+n)^{\gamma}}+\beta}\right)\geqslant
1-\delta\;.$

This assumption covers a wide range of situations. For instance in the
classification case where
$\mathsf{Y}=\mathopen{}\mathclose{{}\left\\{-1,1}\right\\}$ and
$\ell:(y,\tilde{y})\mapsto\mathbbm{1}_{\\{y\tilde{y}\leqslant 0\\}}$,
$\alpha_{\delta}=\sqrt{\ln(1/\delta)/2}$, $\beta=2\textsc{Rad}(\mathscr{G})$
and $\gamma=1/2$ where $\textsc{Rad}(\mathscr{G})$ is the empirical Rademacher
complexity of $\mathscr{G}$ (Bousquet et al., 2003). Similarly, the Bayesian
PAC approach in the linear regression context with bounded loss leads to
$\alpha_{\delta}=\operatorname{KL}(\rho\|\pi)+\ln(1/\delta),\,\beta=\mathopen{}\mathclose{{}\left\|\ell}\right\|^{2}_{\infty}/8$
and $\gamma=1$ where $\rho$ and $\pi$ are any distributions on $\mathscr{G}$
(Shalaeva et al., 2019, Corollary 4).

For ease of notation, we let
$\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)$ serve as a shorthand
for $\mathcal{R}_{P_{j}}\mathopen{}\mathclose{{}\left(g}\right)$. It is
moreover assumed that agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$
cannot directly sample from $P_{0}$, but has instead access to a distribution
$P_{j}\in\mathcal{P}$ which deviates from $P_{0}$ according to the
$\mathscr{G}$-divergence:

######  H 2.

For any $j\in[J]$, $P_{j}\in\mathcal{P}$ has finite $\mathscr{G}$-divergence:
$\theta_{j}=\sup_{g\in\mathscr{G}}|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)|<+\infty$
.

Intuitively, for any
$j\in\mathopen{}\mathclose{{}\left[J}\right],\,\theta_{j}\geqslant 0$ models
the bias incurred by having access to samples from $P_{j}$ instead of the
target distribution $P_{0}$. More precisely, the risk excess associated with
empirical risk minimization (ERM) based on samples from $P_{j}$ is in the
worst case at least $\theta_{j}$. A poor sampling distribution $P_{j}$—which
corresponds to a high $\theta_{j}$ in the previous expression—might be the
consequence of low-quality sensors or degraded experimental conditions
resulting in noisier data points.

The class of discrepancies appearing in H 2 has been considered in the domain
adaptation literature (see, e.g., Ben-David et al., 2010; Kifer et al., 2004;
Konstantinov and Lampert, 2019). It provides a natural framework to analyze
the behavior of models trained on diverse distributions, and is practically
appealing since it can be easily estimated in the context of classification
(Ben-David et al., 2010).

We make the following assumptions on the quality indexes
$(\theta_{1},\ldots,\theta_{J})$, hereafter referred to as types.

######  H 3.

There exists $(\underline{\theta},\bar{\theta})\in\mathbb{R}_{+}^{2}$ such
that
$\underline{\theta}\leqslant\theta_{1}<\theta_{2}<\ldots<\theta_{J}\leqslant\bar{\theta}$.

H 3 The ordering assumption is just for ease of exposition but is neither used
by the aggregator nor the agents. Our condition that types are strictly
different is for convenience in simplifying the proofs.

#### Collaborative learning framework.

We further suppose that agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$
can fit a model $g\in\mathscr{G}$ based on i.i.d. samples
$\\{(X^{j}_{1},Y^{j}_{1}),\ldots,(X^{j}_{n_{j}},Y^{j}_{n_{j}})\\}$ of size
$n_{j}\geqslant 0$ from $P_{j}\in\mathcal{P}$ in one of two ways: they can
compute on their own, or collaborate. This is captured by the two following
options:

  1. Option 1)

Agent $j$ performs ERM on their own samples:

$\textstyle\widehat{g}_{j}=\operatorname*{\arg\\!\min}_{g\in\mathscr{G}}\widehat{\mathcal{R}}_{j}(g)\;,\qquad\widehat{\mathcal{R}}_{j}(g)=n^{-1}_{j}\sum_{i=1}^{n_{j}}\ell(g(X^{j}_{i}),Y^{j}_{i})\;.$
(1)

This non-collaborative procedure is referred to as the _outside option_.

  2. Option 2)

Agent $j$ can take part in a coalition orchestrated by a central data
aggregator, encoded as
$\mathsf{B}=(B_{1},\ldots,B_{J})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$,
where $B_{j}=1$ means that agent $j$ is member of the coalition. We also write
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>B_{j}=1}\right\\}$.
In exchange for their samples, agent $j$ gains access to the collaborative
model trained over the concatenation of samples:

$\displaystyle\widehat{g}_{\mathsf{B}}$
$\displaystyle=\operatorname*{\arg\\!\min}_{g\in\mathscr{G}}\widehat{\mathcal{R}}_{\mathsf{B}}(g)\;,$
(2) $\displaystyle\text{ where }\quad\widehat{\mathcal{R}}_{\mathsf{B}}(g)$
$\displaystyle=N^{-1}\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\sum_{i=1}^{n_{j}}\ell(g(X^{j}_{i}),Y^{j}_{i})\quad\text{
and }\quad N=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}n_{j}\;.$

#### Agent utilities.

We assume that agents incur a unitary cost for sampling from their
distribution and dislike statistical risk. Therefore, a baseline model for
measuring the preferences associated with a model $g\in\mathcal{G}$ and a
number of samples $n$ is based on a linear map:
$(g,n)\mapsto-a\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)-cn$ for
$a,c>0$. In practice, however,
$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)$ is typically unknown
so agents instead can use a PAC bound of the form
$\mathbb{P}(\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\hat{g}_{n}}\right)\leqslant\mathcal{R}^{\star}_{0}+\varepsilon)\geqslant
1-\delta$ to a assess a model $\hat{g}_{n}\in\mathscr{G}$ trained over their
samples, where $\varepsilon>0$, $\delta\in(0,1)$ and
$\mathcal{R}^{\star}_{0}=\inf_{g\in\mathscr{G}}\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)$.
Our next result shows that H 1 and H 2 allow each agent to pin down such an
$\varepsilon>0$, under either Option 1) or Option 2). Assuming H 1, define the
function $\varepsilon$ for any $(\theta,n)\in\Theta\times\mathbb{R}_{+}$ by

$\varepsilon(\theta,n)=2\mathopen{}\mathclose{{}\left[\alpha_{\delta}(1+n)^{-\gamma}+\beta+\theta}\right]\;.$
(3)

######  Lemma 1.

Assume H 1 and H 2.

  1. (i)

Any agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$ picking the outside
Option 1) obtains a model $\widehat{g}_{j}\in\mathscr{G}$ achieving

$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)\leqslant\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},n_{j})\quad\text{with
probability }1-\delta\;.$

  2. (ii)

Any coalition $\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$
drawing $\mathbf{n}=(n_{1},\ldots,n_{J})\in\mathbb{R}_{+}^{J}$, samples
obtains a model $\widehat{g}_{\mathsf{B}}\in\mathscr{G}$ achieving

$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{\mathsf{B}}}\right)\leqslant\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta,N)\quad\text{with
probability }1-\delta\;,$

where $N$ is the total of samples and $\vartheta$ is the weighted average type
within the coalition:

$N(B,\mathbf{n})=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}n_{j}\;,\qquad\vartheta(\mathsf{B},\mathbf{n})=N^{-1}\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}n_{j}\theta_{j}\;.$
(4)

When the context is clear, we write
$\varepsilon(\mathsf{B},\mathbf{n})=\varepsilon(\vartheta(\mathsf{B},\mathbf{n}),N(\mathsf{B},\mathbf{n}))$
to lighten notation. Based on Lemma 1, we define the utility of agent
$j\in\mathopen{}\mathclose{{}\left[J}\right]$ as

$u_{j}:(\mathsf{B},\mathbf{n})\mapsto-a\mathopen{}\mathclose{{}\left[\,\mathcal{R}^{\star}_{0}+(1-B_{j})\varepsilon(\theta_{j},n_{j})+B_{j}\varepsilon(\mathsf{B},\mathbf{n})\,}\right]-cn_{j}\;.$
(5)

Note that for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$, we take
$n_{j}\geqslant 0$ to be a real number for ease of presentation. In (5),
$a/c>0$ captures the trade-off between sampling burden and model quality.

For any $j\in\mathopen{}\mathclose{{}\left[J}\right]$ and
$\mathsf{B}_{-j}=(B_{1},\ldots,B_{j-1},B_{j+1},\ldots,B_{J})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J-1}$,
we denote by a slight abuse of notation
$(B,\mathsf{B}_{-j})=(B_{1},\ldots,B_{j-1},B,B_{j+1},\ldots,B_{J})$ for any
$B\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}$. Similarly for
$\mathbf{n}_{-j}=(n_{1},\ldots,n_{j-1},n_{j+1},\ldots,n_{j})\in\mathbb{R}_{+}^{J-1}$,
we write $(n,\mathbf{n}_{-j})=(n_{1},\ldots,n_{j-1},n,n_{j+1},\ldots,n_{j})$
for any $n\geqslant 0$. We can then characterize the optimal behavior of any
agent picking the outside option as follows.

######  Proposition 1.

Assume H 1 and H 2. For any $j\in\mathopen{}\mathclose{{}\left[J}\right]$,
$\mathsf{B}_{-j}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J-1}$ and
$\mathbf{n}_{-j}\in\mathbb{R}_{+}^{J-1}$, the optimal number of samples to
draw under Option 1) is $\operatorname{argmax}_{n\geq
0}u_{j}((0,\mathsf{B}_{-j}),(n,\mathbf{n}_{-j})\,;\,\theta_{j})=\underline{n}$
where

$\underline{n}=(2ac^{-1}\gamma\alpha_{\delta})^{1/(\gamma+1)}-1\;.$ (6)

In what follows, we assume $2a/c>(\gamma\alpha_{\delta})^{-1}$ to exclude the
pathological case where no agent is willing to sample data points. From now
on, we denote by

$\underline{u}_{j}=u_{j}((0,\mathsf{B}_{-j}),(\underline{n},\mathbf{n}_{-j}))\;$
(7)

the best achievable utility under the outside option. Note that
$\underline{n}$ does not depend on $\theta_{j}\in\Theta$ (but
$\underline{u}_{j}$ does) so all agents outside of the coalition draw a same
number of data points $\underline{n}>0$. This result, which may be surprising
at first glance, comes from the fact that all agents have the same accuracy-
to-sampling-cost ratio $a/c$ in their utility.

#### Aggregator.

We finally assume that the aggregator acts benevolently to set up a Pareto-
optimal collaboration, by maximizing the total welfare under individual
rationality. In other words, they solve:

$\displaystyle\text{maximize}\quad
W:\>(\mathsf{B},\mathbf{n})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\mathbb{R}_{+}^{J}\mapsto\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}(\mathsf{B},\mathbf{n})$
(8) $\displaystyle\text{subject
to}\quad\min_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}((1,\mathsf{B}_{-j}),\mathbf{n})-\underline{u}_{j}\geqslant
0\;.$

In the Social Choice literature, $W$ is referred to as the utilitarian social
welfare function. The participation constraint ensures that no agent within
the coalition finds it beneficial to switch to their outside option. Note that
$\mathbf{n}\in\mathbb{R}_{+}^{J}$ is required to have non-negative entries,
which prevents the aggregator from giving away data points to agents.

##  3 Full-Information Benchmark: First-Best Collaboration

#### Exact solution.

In this section, we assume that the profile of types
$(\theta_{1},\ldots,\theta_{J})\in\Theta^{J}$ is public and study how the
aggregator can implement an optimal collaboration among agents. For any
$\mathsf{B}\in\\{0,1\\}^{J}$ and $\mathbf{n}\in\mathbb{R}_{+}^{J}$, denote by

$\displaystyle\overline{n}_{j}(\mathsf{B},\mathbf{n})$
$\displaystyle=\max\\{n\geqslant
0:\,u_{j}\mathopen{}\mathclose{{}\left((1,\mathsf{B}_{-j}),(n,\mathbf{n}_{-j})\,;\,\theta_{j}}\right)\geqslant\underline{u}_{j}\\}$
$\displaystyle=\underline{n}-(a/c)[\varepsilon(\mathsf{B},\mathbf{n})-\varepsilon(\theta_{j},\underline{n})]\;,$
(9)

the maximum number of samples that agent $j$ can be asked to provide within
the coalition under its participation constraint, where $\underline{n}$ is
defined as in (6), and $\underline{u}_{j}$ as in (7). With this notation,
problem (8) rewrites

$\text{maximize}\quad W(\mathsf{B},\mathbf{n})\quad\text{subject
to}\quad\min_{j\in\mathcal{B}}\overline{n}_{j}(\mathsf{B},\mathbf{n})-n_{j}\geqslant
0\;.$ (10)

######  Theorem 1.

Assume H 1, H 2, H 3. Problem (8) admits a unique solution
$(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\mathbb{R}_{+}^{J}$.
Moreover,

  1. (i)

$\mathsf{B}^{\mathrm{opt}}={\bf 1}=(1,\ldots,1)$,

  2. (ii)

Denoting
$\mathbf{n}^{\mathrm{opt}}(\bm{\theta})=(n^{\mathrm{opt}}_{1}(\bm{\theta}),\ldots,n^{\mathrm{opt}}_{J}(\bm{\theta}))$,
there exists $L^{\mathrm{opt}}\in\mathopen{}\mathclose{{}\left[J}\right]$ such
that for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$,

$n^{\mathrm{opt}}_{j}(\bm{\theta})\begin{cases}=\overline{n}_{j}({\bf
1},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))&\text{if }j<L^{\mathrm{opt}},\\\
\in[\,0\,,\,\overline{n}_{j}({\bf
1},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))\,]&\text{if }j=L^{\mathrm{opt}},\\\
=0&\text{otherwise}.\end{cases}$ (11)

The couple $(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}})$ is referred
to as the optimal contribution scheme. Although implicit, the condition (11)
provides insights about the optimal scheme. The aggregator makes everyone
enter the coalition, but only asks the $L^{\mathrm{opt}}>0$ first-best agents
to contribute. This allows to obtain the best possible collaborative model
while sparing any sampling cost to other agents. Moreover, the number of
required samples $n^{\mathrm{opt}}_{j}(\bm{\theta})$ slightly differs from
$\underline{n}$ according to the relative performance of the collaborative
model with respect to agent $j$’s one: if the agent gets a better accuracy by
collaborating, the aggregator can ask them for more data; if on the other hand
the agent gets a worse model by collaborating (i.e., they are a contributor
with very high quality data), the aggregator can only ask less data because of
the participation constraint.

#### Relaxed solution.

Working with the optimal scheme
$(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}})$ is difficult because
$\overline{n}_{j}({\bf 1},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))$ has no
explicit expression. To make the analysis tractable, we consider the
simplified optimal contribution scheme
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$ where
$\mathsf{B}^{\star}=\mathsf{B}^{\mathrm{opt}}=(1,\ldots,1)$ and for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$,

$\displaystyle n^{\star}_{j}(\bm{\theta})=\mathbbm{1}_{\\{j\leqslant
L^{\star}\\}}\overline{n}_{j}({\bf 1},\mathbf{n}^{\star}(\bm{\theta}))\quad$
$\displaystyle\text{and}\quad
L^{\star}=\min\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>\sum_{k\leqslant
j}\overline{n}_{k}({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))\geqslant\bar{N}\\}\;,$ (12)
$\displaystyle\text{with}\quad\bar{N}=(\underline{n}+1)J^{\frac{1}{1+\gamma}}-1\;.$

Note that $(\mathsf{B}^{\star},\mathbf{n}^{\star})$ only differs from
$(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}})$ in two ways. First, in
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$ all contributors’ participation
constraint bind, while in
$(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}})$ the
$L^{\mathrm{opt}}$-th one could be slack. Second, the total number of data
points required from the coalition is fixed and equal to
$\bar{N}=\Theta(J^{\frac{1}{1+\gamma}})$. The alternative scheme
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$ that we consider come from a natural
relaxation of the original problem Equation 10 which is described in Appendix
A.

The following proposition shows that $\mathbf{n}^{\star}(\bm{\theta})$ admits
a workable expression.

######  Corollary 1.

Assume H 1, H 2 and H 3. Then $L^{\star}=\Theta(J^{\frac{1}{1+\gamma}})$ and
for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$,

$n^{\star}_{j}(\bm{\theta})=\mathbbm{1}_{\\{j\leq
L^{\star}\\}}\mathopen{}\mathclose{{}\left[\frac{\bar{N}}{L^{\star}}+\frac{2a}{c}\mathopen{}\mathclose{{}\left(\theta_{j}-\frac{1}{L^{\star}}\sum_{\ell=1}^{L^{\star}}\theta_{\ell}}\right)}\right]\;.$

Applying $(\mathsf{B}^{\star},\mathbf{n}^{\star})$ instead of
$(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}})$ may come at a
negligible welfare cost, as illustrated by the following result when types are
sufficiently evenly spaced.

######  Lemma 2.

Assume H 1, H 2 and $\theta_{j}-\theta_{j-1}=\mathcal{O}(1/J)$ for any
$j\in\\{2,\ldots,J\\}$. Then,

$W(\mathsf{B}^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))=W(\mathsf{B}^{\star},\mathbf{n}^{\star}(\bm{\theta}))+\mathcal{O}(J^{\frac{1}{1+\gamma}})\;.$

Since $(\mathsf{B}^{\star},\mathbf{n}^{\star})$ correctly approximates the
optimal scheme while being more tractable, we work with it in the remainder to
lighten proofs.

######  H 4.

The aggregator applies the simplified contribution scheme
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$.

##  4 Hidden information

The welfare-maximizing contribution scheme described in (12) depends
explicitly on $\bm{\theta}\in\Theta^{J}$, so it is implementable only if types
are public. This often unrealistic, either for legal or competitive reasons.
We therefore turn to the problem of setting up a collaboration when types are
private.

###  4.1 Naive aggregation and unravelling

A naive solution to coping with the private nature of
$\bm{\theta}\in\Theta^{J}$ is for the aggregator to ask agents to disclose
their types, and apply the contribution scheme defined in (12). In this
setting, however, agents may declare a type $\tilde{\theta}_{j}$ different
from their true type $\theta_{j}$.

This approach corresponds to a direct-revelation mechanism
$\Gamma:(\mathsf{B},\widetilde{\bm{\theta}})\mapsto\mathbf{n}^{\star}(\widetilde{\bm{\theta}})$
which unfolds as follows.

  1. 1.

Any agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$ declares a tuple
$(B_{j},\widetilde{\theta}_{j})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}\times\Theta\cup\mathopen{}\mathclose{{}\left\\{\dagger}\right\\}$.
If $B_{j}=1$, then agent $j$ picks Option 2), and enters the coalition with
type $\widetilde{\theta}_{j}$. If $B_{j}=0$, then agent $j$ picks Option 1),
their declared type $\widetilde{\theta}_{j}$ is $\dagger$ by convention.

  2. 2.

Setting $\mathsf{B}=(B_{1},\ldots,B_{J})$ and
$\tilde{\bm{\theta}}\in(\Theta\cup\\{\dagger\\})^{J}$, then the aggregator
applies the contribution scheme defined in (12), so the vector of number of
contributions within the coalition is
$\mathbf{n}^{\star}(\widetilde{\bm{\theta}})$.

$\Gamma$ induces a direct revelation game
$(\mathopen{}\mathclose{{}\left[J}\right],\mathscr{S}^{J},(v_{j})_{j\in\mathopen{}\mathclose{{}\left[J}\right]})$
where the action space is
$\mathscr{S}=\\{(1,\widetilde{\theta})\,:\;\widetilde{\theta}\in\Theta\\}\cup\mathopen{}\mathclose{{}\left\\{(0,\dagger)}\right\\}$
and payoffs are for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$ and
$\mathbf{s}\in\mathscr{S}^{J}$,

$v_{j}(s_{j},\mathbf{s}_{-j})=u_{j}(\mathsf{B},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))=B_{j}\mathopen{}\mathclose{{}\left[-a\mathopen{}\mathclose{{}\left(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))}\right)-cn^{\star}_{j}(\widetilde{\bm{\theta}})}\right]+(1-B_{j})\underline{u}_{j}\;.$

This mechanism is obviously vulnerable to strategic manipulation, since it
disregards incentive compatibility. This has severe consequences for the
coalition, as shown by the following proposition.

######  Theorem 2 (Unravelling).

Assume H 1, H 2, H 3, and H 4. Let $\mathscr{E}\subset\mathscr{S}^{J}$ be the
set of pure-strategy Nash equilibria of the game induced by $\Gamma$. We have

  1. (i)

$\mathscr{E}\neq\emptyset$

  2. (ii)

at any $s^{\star}\in\mathscr{E}$, $\mathsf{B}=(0,\ldots,0)$ or
$\mathsf{B}=(0,\ldots,0,1)\;.$

Theorem 2 shows that under $\Gamma$, the coalition undergoes a full
unravelling: agent strategies result in a pure Nash equilibrium where the
coalition is either empty or comprised solely of the worst agent. Thus,
collaborative learning is not immune to adverse selection, and may suffer from
unravelling as any market characterized by information asymmetry.

###### Sketch of proof.

The profile of actions $((0,\dagger),\ldots,(0,\dagger))$ corresponding to
$\mathsf{B}=(0,\ldots,0)$ is a pure Nash equilibrium, since forming a lone
coalition cannot bring more utility than picking the outside option.
Conversely, consider a pure-strategy Nash equilibrium ${\bf s}\in\mathcal{E}$
such that $\mathsf{B}\neq(0,\ldots,0)$. Denote by
$\mathcal{C}=\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>B_{j}=1\text{
and }n^{\star}_{j}(\widetilde{\bm{\theta}})>0\\}$ the set of contributors
under this equilibrium. It can be shown that (i) for any
$(j,k)\in\mathcal{C}^{2}$,
$\theta_{j}-\widetilde{\theta}_{j}=\theta_{k}-\widetilde{\theta}_{k}$, and
(ii) For any $j\in\mathcal{C}$, $(1,\widetilde{\theta}_{j})$ with
$\widetilde{\theta}_{j}>\underline{\theta}$ is strictly dominated by
$(1,\underline{\theta})$ so $\widetilde{\theta}_{j}=\underline{\theta}$ at the
equilibrium. As a consequence, $\theta_{j}=\theta_{k}$ for any
$(j,k)\in\mathcal{C}^{2}$, which implies by H 3 that
$\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|=1$. From the definition of
the contribution scheme (12), we can deduce that
$\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}=\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|=1$,
because $\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|>1$ would entail
$\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|>1$. Finally, $B_{J}=1$
because $v_{J}((1,\underline{\theta}),{\bf s}_{-J})>v_{J}((0,\dagger),{\bf
s}_{-J})$ and ${\bf s}$ is a Nash equilibrium. This leads to
$\mathsf{B}=(0,\ldots,0,1)$. ∎

###  4.2 Breaking unravelling

The previous results motivate the design of a more sophisticated aggregation
scheme that addresses adverse selection. In this section, we discuss how to
design such a procedure.

#### Is VCG available in our framework?

Unravelling occurs under $\Gamma$ because agents do not find it beneficial to
declare their true type and eventually opt for their outside option. This
could be avoided by modifying $\Gamma$ to make it

  1. (i)

individually rational, that is $v_{j}((1,\theta_{j}),\mathbf{s}_{-j})\geqslant
v_{j}((0,\dagger),\mathbf{s}_{-j})$ for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$,
$\mathbf{s}_{-j}\in\mathscr{S}^{J-1}$,

  2. (ii)

and incentive compatible, that is
$v_{j}((1,\theta_{j}),\mathbf{s}_{-j})\geqslant
v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-j})$ for any
$\widetilde{\theta}_{j}\in\Theta$.

Under these conditions, the truthful, optimal profile of actions
$((1,\theta_{1}),\ldots,(1,\theta_{J}))$ would emerge as a Nash equilibrium.
Since the aggregator seeks to minimize the utilitarian function $W$, one
option would be to rely on the VCG mechanism (Vickrey, 1961; Clarke, 1971;
Groves, 1973), which is the direct-revelation mechanisms fulfilling these
desiderata (Green and Laffont, 1977; Holmstrom, 1979). Formally, the VCG
mechanism writes
$\Gamma^{\textsc{vcg}}:\widetilde{\bm{\theta}}\mapsto(\mathbf{n}^{\star}(\widetilde{\bm{\theta}}),\mathbf{t}(\widetilde{\bm{\theta}}))$
where
$\mathbf{t}(\widetilde{\bm{\theta}})=(t_{1}(\bm{\theta}),\ldots,t_{J}(\bm{\theta}))\in\mathbb{R}^{J}$
is a set of transfers satisfying for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$:

$t_{j}(\widetilde{\bm{\theta}})=\sum_{k\neq j}u_{k}((0,{\bf
1}_{-j}),\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))-\sum_{k\neq j}u_{k}({\bf
1},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))\;.$

It re-establishes truthfulness as a dominant strategy by aligning individual
payoffs $v_{j}^{\textsc{VCG}}(\widetilde{\bm{\theta}})=u_{j}({\bf
1},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))-t_{j}(\widetilde{\bm{\theta}})$
with total social welfare. Unfortunately, the VCG approach is unavailable in
our framework, because of the following observation.

######  Lemma 3.

There exists $j\in\mathopen{}\mathclose{{}\left[J}\right]$ such that
$-t_{j}(\widetilde{\bm{\theta}})>0$.

Lemma 3 shows that some agent would need to receive a strictly positive
transfer. This is impossible without a monetary payment (utility can only be
decreased by the aggregator, for instance through accuracy shaping
(Karimireddy et al., 2022)), which we exclude here.

#### A probabilistic verification-based mechanism.

We now show how to design a mechanism that recovers the optimal collaboration
as a Nash equilibrium in high probability without the need for transfers.
Inspired by the probabilistic verification approach (Caragiannis et al., 2012;
Ferraioli and Ventre, 2018; Ball and Kattwinkel, 2019), we assume that the
aggregator can approximately estimate $\theta_{j}$ with few samples from
$P_{j}$ for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$:

######  H 5.

There exists a decreasing function
$\eta_{\delta}:\>\mathbb{R}_{+}^{\star}\rightarrow\mathbb{R}_{+}^{\star}$,
with $\delta\in(0,1)$ defined in H 1, such that for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$ and i.i.d samples
$(X^{j}_{1},Y^{j}_{1}),\ldots,(X^{j}_{q},Y^{j}_{q})$ of size $q>0$ from
$P_{j}$, there exists a measurable estimator $\widehat{\theta}_{j}$ of
$(X^{j}_{1},Y^{j}_{1}),\ldots,(X^{j}_{q},Y^{j}_{q})$ satisfying

$\mathbb{P}(|\widehat{\theta}_{j}-\theta_{j}|\leqslant\eta_{\delta}(q))\geqslant
1-\delta\;.$

In Section 4.2, we show how the aggregator can design such estimators. H 5
allows us to consider a new mechanism
$\widehat{\Gamma}:\>\mathsf{B}\mapsto\mathbf{m}(\mathsf{B})$ as follows:

  1. 1.

any agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$ declares
$B_{j}\in\\{0,1\\}$. If $B_{j}=1$, the principal asks for
$\underline{q}\leqslant\underline{n}-2(a/c)(\bar{\theta}-\underline{\theta})$
i.i.d samples from $P_{j}$ and estimates types as
$\widehat{\bm{\theta}}=(\widehat{\theta}_{j})_{j\in\mathcal{B}}$ following H
5.

  2. 2.

Based on the estimated types
$\widehat{\bm{\theta}}=(\widehat{\theta}_{j})_{j\in\mathcal{B}}$, the
aggregator asks for
$[\,n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})-\underline{q}\,]_{+}$
additional samples from $P_{j}$, where $\mathbf{n}^{\star}(\,\bm{\cdot}\,)$ is
defined as in (12) and

$\bm{\eta}_{j}=\eta_{\delta/J}(\underline{q}){\bf
1}-2\bm{\delta}_{j}\eta_{\delta/J}(\underline{q}),\quad\text{with}\quad\bm{\delta}_{j}=(0,\ldots,0,1,0,\ldots,0)^{\operatorname{T}}\;.$

Thus, the number of draws required from agent $j$ is
$\max[\underline{q}\,,\,n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})]$.

  3. 3.

The aggregator keeps
$m_{j}(\widehat{\bm{\theta}})=\text{1}\\{n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})>0\\}\max[\underline{q}\,,\,n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})]$
samples from agent $j$, and trains a collaborative model with these pooled
samples.

$\hat{\Gamma}$ induces a game
$(\mathopen{}\mathclose{{}\left[J}\right],\\{0,1\\}^{J},(\hat{v}_{j})_{j\in\mathopen{}\mathclose{{}\left[J}\right]})$
where any agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$ faces a payoff
function

$\hat{v}_{j}:(B_{j},\mathsf{B}_{-j})\mapsto
B_{j}\mathopen{}\mathclose{{}\left[-a\mathopen{}\mathclose{{}\left(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B},\mathbf{m}(\widehat{\bm{\theta}}))}\right)-c\max[\underline{q}\,,\,n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})]}\right]+(1-B_{j})\underline{u}_{j}\;.$

The rationale behind this mechanism is fairly intuitive: since
$\widehat{\bm{\theta}}$ is a correct estimate of $\bm{\theta}$,
$n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})\approx
n^{\star}_{j}(\widehat{\bm{\theta}})$ correctly approximates the optimal
contribution $n^{\star}_{j}(\bm{\theta})$ for any contributor
$j\in\mathcal{B}$. Note that type estimates are purposely biased by
$\bm{\eta}_{j}$ when asking for samples. This is a safeguard against over-
estimated types, which would lead to asking to many data points and could
deter agents from participating in the coalition.

Critically, $\mathbf{m}(\widehat{\bm{\theta}})$ does not depend on declared
type, so agents are no longer able to strategically manipulate the mechanism.
Observe that the number of data points asked to estimate types $\underline{q}$
is low enough to never deter agents from participating in the coalition.

######  Theorem 3.

Assume H 1, H 2, H 3, H 4 and H 5.
$\mathsf{B}^{\star}=(1,\ldots,1)^{\operatorname{T}}$ is a Nash equilibrium
under $\hat{\Gamma}$ with probability $1-\delta$.

Theorem 3 shows that the optimal coalition is a sustainable equilibrium under
$\hat{\Gamma}$, which effectively breaks unravelling: the set of (approximate)
Nash equilibria is no more reduced to profiles of actions where the coalition
is empty, or reduced to the worst agent.

#### Practical implementation.

We now explain how to practically implement $\widehat{\Gamma}$ in a
collaborative learning setting. This requires defining estimators
$(\widehat{\theta}_{j})_{j}$ satisfying H 5. To this end, we assume that few
samples from the target distribution are available.

######  H 6.

There are $q^{\prime}>0$ i.i.d samples
$\mathopen{}\mathclose{{}\left\\{(X^{0}_{1},Y^{0}_{1}),\ldots,(X^{0}_{q^{\prime}},Y^{0}_{q^{\prime}})}\right\\}$
from $P_{0}$ available to the aggregator and agents.

This assumption is reasonable when the statistical phenomenon under study is
not entirely new to agents. Under H 6, define
$\widehat{\mathcal{R}}_{0}(g)=q^{\prime-1}\sum_{i=1}^{q^{\prime}}\ell(g(X^{0}_{i}),Y^{0}_{i})$
for $g\in\mathscr{G}$. This allows us to devise suitable estimators
$\widehat{\theta}_{j}$ as follows.

######  Proposition 2.

Assume H 1, H 2 and H 6. For any $j\in\mathopen{}\mathclose{{}\left[J}\right]$
the estimator

$\widehat{\theta}^{\textsc{erm}}_{0,j}=\sup_{g\in\mathscr{G}}|\widehat{\mathcal{R}}_{j}(g)-\widehat{\mathcal{R}}_{0}(g)|\;,$

satisfies H 5 with

$\eta_{\delta}(q)=\alpha_{\delta/4}\mathopen{}\mathclose{{}\left[(q+1)^{-\gamma}+(q^{\prime}+1)^{-\gamma}}\right]+2\beta\;.$
(13)

Proposition 2 shows that the empirical version of the $\mathscr{G}$-divergence
defined in H 2 correctly estimate types. Note that the tighter the PAC bound
in H 1, the better the approximation term in (13). The type estimator
$\widehat{\theta}_{j}^{\textsc{ERM}}$ defined in H 5 can easily be computed in
the classification case, as shown with the following example.

######  H 7 (Classification setting).

$\mathcal{Y}=\mathopen{}\mathclose{{}\left\\{-1,1}\right\\}$,
$\ell=\ell_{0,1}:(y,y^{\prime})\in\mathcal{Y}\times\mathcal{Y}\mapsto\mathbbm{1}_{\\{yy^{\prime}<0\\}}$,
and $\mathscr{G}$ is a symmetric ($g\in\mathscr{G}$ if and only if
$-g\in\mathscr{G}$) class of classifiers.

######  Example 4.

Assume H 1, H 2, H 6 and H 7.

  1. (i)

Denoting
$\widehat{\mathcal{R}}_{j^{-}}(g)=n_{j}^{-1}\sum_{i=1}^{n_{j}}\ell_{0,1}(g(X^{j}_{i}),-Y^{j}_{i})$,
we have

$\widehat{\theta}^{\textsc{erm}}_{0,j}=1-\inf_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left\\{\widehat{\mathcal{R}}_{0}(g)+\widehat{\mathcal{R}}_{j^{-}}(g)}\right\\}\;.$

  2. (ii)

In H 1, assume $\alpha_{\delta}=\ln(1/\delta)^{1/2}$,
$\beta=2\textsc{RAD}(\mathscr{G})$ and $\gamma=1$ (Bousquet et al., 2003).
With $\widehat{\theta}_{0,j}^{\textsc{erm}}$ defined in Proposition 2, we have

$\displaystyle\eta_{\delta/J}(q)=\ln(4J/\delta)^{1/2}[(1+q)^{-\gamma}+(1+q^{\prime})^{-\gamma}]+2\mathrm{Rad}(\mathscr{G})\;.$

Example 4 shows that in the classification case, it is sufficient to flip the
labels of the data received from each contributor, merge these samples with
those from $P_{0}$, and perform an empirical risk minimization to compute
$\widehat{\theta}_{0,j}^{\textsc{erm}}$. The approximation error grows no more
than logarithmically with the number of agents, while decreasing at rate
$\gamma$ with the number of samples used in the estimation.

##  5 Conclusion

In this work, we show that information asymmetry has deleterious consequences
when strategic agents try to learn a collaborative model. More precisely,
under a naive aggregation procedure, the ignorance of others’ data quality
leads the coalition of learners to be either empty or reduced to the lowest-
quality agent. We introduce a transfer-free mechanism based on estimation of
types. This effectively counteracts unravelling by letting the grand coalition
ranks among the approximate Nash equilibria with high probability.

There are several possible extensions that can be considered. First, we have
assumed that agents know their type $\theta_{j}\in\Theta$. The model could be
made more realistic by letting the agents learn it in an online fashion.
Second, the mechanism presented in Section 4 aims for individual rationality.
A more desirable, yet difficult to achieve, property would be core stability,
to ensure that no group of agents would benefit from a coordinated deviation,
i.e., forming an alternative coalition. Finally, it would be interesting to
check whether there exist mechanisms where the optimal collaboration not only
emerges as a Nash equilibrium, but as a dominant equilibrium under imperfect
information.

## Acknowledgements

Funded by the European Union (ERC, Ocean, 101071601). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Research Council Executive
Agency. Neither the European Union nor the granting authority can be held
responsible for them.

## References

  * Akerlof [1970] George A. Akerlof.  The market for lemons: Quality uncertainty and the market mechanism.  _The Quarterly Journal of Economics_ , 84(3):488–500, 1970.  URL https://ideas.repec.org/a/oup/qjecon/v84y1970i3p488-500..html.
  * Ananthakrishnan et al. [2023] Nivasini Ananthakrishnan, Stephen Bates, Michael Jordan, and Nika Haghtalab.  Delegating data collection in decentralized machine learning, 2023.
  * Ball and Kattwinkel [2019] Ian Ball and Deniz Kattwinkel.  Probabilistic verification in mechanism design.  September 2019.
  * Ben-David et al. [2010] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan.  A theory of learning from different domains.  _Machine Learning_ , 79:151–175, 05 2010.  doi: 10.1007/s10994-009-5152-4.
  * Blum et al. [2017] Avrim Blum, Nika Haghtalab, Ariel Procaccia, and Mingda Qiao.  Collaborative PAC learning.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_. Curran Associates, 2017.
  * Blum et al. [2021] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao.  One for one, or all for all: Equilibria and optimality of collaboration in federated learning.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 1005–1014. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/blum21a.html.
  * Bousquet et al. [2003] Olivier Bousquet, Stéphane Boucheron, Gábor Lugosi, Ulrike Luxburg, and Gunnar Rätsch.  Introduction to statistical learning theory.  _Advanced Lectures on Machine Learning, 169-207 (2004)_ , 01 2003.  doi: 10.1007/978-3-540-28650-9_8.
  * Caragiannis et al. [2012] Ioannis Caragiannis, Edith Elkind, Mario Szegedy, and Lan Yu.  Mechanism design: From partial to probabilistic verification.  _Proceedings of the ACM Conference on Electronic Commerce_ , 06 2012.  doi: 10.1145/2229012.2229035.
  * Clarke [1971] Edward Clarke.  Multipart pricing of public goods.  _Public Choice_ , 11(1):17–33, September 1971.  doi: 10.1007/BF01726210.  URL https://ideas.repec.org/a/kap/pubcho/v11y1971i1p17-33.html.
  * Donahue and Kleinberg [2021a] Kate Donahue and Jon Kleinberg.  Optimality and stability in federated learning: A game-theoretic approach, 06 2021a.
  * Donahue and Kleinberg [2021b] Kate Donahue and Jon Kleinberg.  Model-sharing games: Analyzing federated learning under voluntary participation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35:5303–5311, 05 2021b.  doi: 10.1609/aaai.v35i6.16669.
  * Dorner et al. [2023] Florian E. Dorner, Nikola Konstantinov, Georgi Pashaliev, and Martin T. Vechev.  Incentivizing honesty among competitors in collaborative learning and optimization.  _ArXiv_ , abs/2305.16272, 2023.  URL https://api.semanticscholar.org/CorpusID:258887502.
  * Einav and Finkelstein [2011] Liran Einav and Amy Finkelstein.  Selection in insurance markets: Theory and empirics in pictures.  _Journal of Economic Perspectives_ , 25(1):115–38, March 2011.  doi: 10.1257/jep.25.1.115.  URL https://www.aeaweb.org/articles?id=10.1257/jep.25.1.115.
  * Ferraioli and Ventre [2018] Diodato Ferraioli and Carmine Ventre.  Probabilistic verification for obviously strategyproof mechanisms, 2018.
  * Fu et al. [2023] Lei Fu, Huanle Zhang, Ge Gao, Mi Zhang, and Xin Liu.  Client selection in federated learning: Principles, challenges, and opportunities, 2023.
  * Gao et al. [2022] Dashan Gao, Xin Yao, and Qiang Yang.  A survey on heterogeneous federated learning.  _arXiv preprint arXiv:2210.04505_ , 2022.
  * Green and Laffont [1977] Jerry Green and Jean-Jacques Laffont.  Characterization of satisfactory mechanisms for the revelation of preferences for public goods.  _Econometrica_ , 45(2):427–38, 1977.  URL https://EconPapers.repec.org/RePEc:ecm:emetrp:v:45:y:1977:i:2:p:427-38.
  * Groves [1973] Theodore Groves.  Incentives in teams.  _Econometrica_ , 41:617–631, 1973.  URL https://api.semanticscholar.org/CorpusID:264740987.
  * Hendren [2013] Nathaniel Hendren.  Private Information and Insurance Rejections.  _Econometrica_ , 81(5):1713–1762, September 2013.  doi: ECTA10931.  URL https://ideas.repec.org/a/ecm/emetrp/v81y2013i5p1713-1762.html.
  * Holmstrom [1979] Bengt Holmstrom.  Groves’ scheme on restricted domains.  _Econometrica_ , 47(5):1137–44, 1979.  URL https://EconPapers.repec.org/RePEc:ecm:emetrp:v:47:y:1979:i:5:p:1137-44.
  * Huang et al. [2023] Baihe Huang, Sai Praneeth Karimireddy, and Michael I. Jordan.  Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning.  Papers 2306.05592, arXiv.org, June 2023.  URL https://ideas.repec.org/p/arx/papers/2306.05592.html.
  * Huang et al. [2022] Chao Huang, Shuqi Ke, Charles Kamhoua, Prasant Mohapatra, and Xin Liu.  Incentivizing data contribution in cross-silo federated learning, 2022.
  * 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, Rafael G. L. D’Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konevcný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.  Advances and open problems in federated learning, 2021.
  * Karimireddy et al. [2022] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I. Jordan.  Mechanisms that incentivize data sharing in federated learning, 2022.
  * Kifer et al. [2004] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  pages 180–191, 04 2004.
  * Konstantinov and Lampert [2019] Nikola Konstantinov and Christoph Lampert.  Robust learning from untrusted sources, 2019.
  * Laffont and Martimort [2001] Jean-Jacques Laffont and David Martimort.  _The Theory of Incentives: The Principal-Agent Model_.  Princeton University Press, Princeton, NJ, USA, 2001.
  * Liu et al. [2023] Shutian Liu, Tao Li, and Quanyan Zhu.  Game-theoretic distributed empirical risk minimization with strategic network design.  _IEEE Transactions on Signal and Information Processing over Networks_ , 9:542–556, 2023.  doi: 10.1109/TSIPN.2023.3306106.
  * Mas-Colell et al. [1995] Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green.  _Microeconomic Theory_.  Number 9780195102680 in OUP Catalogue. Oxford University Press, 1995.  ISBN ARRAY(0x516030e0).  URL https://ideas.repec.org/b/oxp/obooks/9780195102680.html.
  * Rothschild and Stiglitz [1976] Michael Rothschild and Joseph Stiglitz.  Equilibrium in competitive insurance markets: An essay on the economics of imperfect information.  _The Quarterly Journal of Economics_ , 90(4):629–649, 1976.  URL https://EconPapers.repec.org/RePEc:oup:qjecon:v:90:y:1976:i:4:p:629-649.
  * Saig et al. [2023] Eden Saig, Inbal Talgam-Cohen, and Nir Rosenfeld.  Delegated classification, 2023.
  * Shalaeva et al. [2019] Vera Shalaeva, Alireza Fakhrizadeh Esfahani, Pascal Germain, and Mihály Petreczky.  Improved pac-bayesian bounds for linear regression.  In _AAAI Conference on Artificial Intelligence_ , 2019.  URL https://api.semanticscholar.org/CorpusID:208857400.
  * Tsoy and Konstantinov [2023] Nikita Tsoy and Nikola Konstantinov.  Strategic data sharing between competitors, 2023.  URL https://arxiv.org/abs/2305.16052.
  * Tu et al. [2022] Xuezhen Tu, Kun Zhu, Nguyen Cong Luong, Dusit Niyato, Yang Zhang, and Juan Li.  Incentive mechanisms for federated learning: From economic and game theoretic perspective.  _IEEE Transactions on Cognitive Communications and Networking_ , 8(3):1566–1593, 2022.  doi: 10.1109/TCCN.2022.3177522.
  * Vickrey [1961] William Vickrey.  Counterspeculation, auctions, and competitive sealed tenders.  _Journal of Finance_ , 16(1):8–37, 1961.  URL https://EconPapers.repec.org/RePEc:bla:jfinan:v:16:y:1961:i:1:p:8-37.
  * Wei et al. [2024] Zhepei Wei, Chuanhao Li, Tianze Ren, Haifeng Xu, and Hongning Wang.  Incentivized truthful communication for federated bandits, 2024.
  * Werner et al. [2024] Mariel Werner, Sai Praneeth Karimireddy, and Michael I. Jordan.  Defection-free collaboration between competitors in a learning system, 2024.  URL https://arxiv.org/abs/2406.15898.
  * Yan et al. [2023] Yizhou Yan, Xinyu Tang, Chao Huang, and Ming Tang.  Price of stability in quality-aware federated learning.  In _GLOBECOM 2023 - 2023 IEEE Global Communications Conference_ , pages 734–739, 2023.  doi: 10.1109/GLOBECOM54140.2023.10437743.

##  Appendix A Relaxation of the optimal aggregation problem.

Let $\mathsf{B}\in\\{0,1\\}^{J}$ and the associated coalition
$\mathcal{B}=\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>B_{j}=1\\}$ be
fixed. We present in this appendix a natural relaxation of problem Equation 10
which motivates the choice
$\sum_{j\in\mathcal{B}}n^{\star}_{j}(\bm{\theta})=\bar{N}=(\underline{n}+1)\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|^{\frac{1}{1+\gamma}}-1$
in the simplified contribution scheme
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$. The optimal aggregation problem
with $\mathsf{B}$ fixed is

$\quad\text{maximize}\quad\mathbf{n}\in\mathbb{R}^{J}\,\mapsto\,\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}(\mathsf{B},\mathbf{n})\quad\text{subject
to}\quad\begin{cases}\max_{j\in\mathcal{B}}n_{j}-\overline{n}(\mathsf{B},\mathbf{n})\leqslant
0\\\ \max_{j\in\mathopen{}\mathclose{{}\left[J}\right]}-n_{j}\leqslant
0\;,\end{cases}$

Since agents outside of the coalition maximize their utility, the problem can
equivalently be stated as

$(\mathcal{T}_{\mathsf{B}}):\quad\text{maximize}\quad\mathbf{n}\in\mathbb{R}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}\,\mapsto\,\sum_{j\in\mathcal{B}}u_{j}(\mathsf{B},\mathbf{n})+\zeta_{\mathsf{B}}\quad\text{subject
to}\quad\mathbf{n}\in\Xi_{\mathsf{B}}\;,$

where

$\Xi_{\mathsf{B}}=\mathopen{}\mathclose{{}\left\\{\mathbf{n}_{\mathcal{B}}\in\mathbb{R}_{+}^{\mathcal{B}}:\>\begin{array}[]{cc}\max_{j\in\mathcal{B}}\mathopen{}\mathclose{{}\left\\{n_{j}-\overline{n}_{j}(\mathsf{B},\mathbf{n})}\right\\}\leqslant
0\\\ \max_{j\in\mathcal{B}}-n_{j}\leqslant
0\end{array}}\right\\}\quad\text{and}\quad\zeta_{\mathsf{B}}=\sum_{j\notin\mathcal{B}}\underline{u}_{j}\;.$
(14)

We start by rewriting $(\mathcal{T}_{\mathsf{B}})$ in a more convenient way.
Instead of working with
$\mathbf{n}\in\mathbb{R}_{+}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$
directly, we make appear (i) the total number of samples and (ii) the sharing
out of samples between agents. Formally, for any
$\mathbf{n}\in\mathbb{R}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}_{+}$
consider $N=\mathbf{n}^{\operatorname{T}}\mathsf{B}$ and
$\bm{\lambda}=N^{-1}\mathbf{n}\in\Delta_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$,
where $\Delta_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$ is the
simplex of dimension $\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|$.
First,
$\vartheta(\mathsf{B},\mathbf{n})=\bm{\lambda}^{\operatorname{T}}\bm{\theta}$
and second, the welfare evaluated in $(\mathsf{B},\mathbf{n})$ rewrites

$\displaystyle\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}(\mathsf{B},\mathbf{n})$
$\displaystyle=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\mathopen{}\mathclose{{}\left[-a\mathopen{}\mathclose{{}\left(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B},\bm{\lambda}N)}\right)-cn_{j}}\right]+\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}(1-B_{j})\underline{u}_{j}$
$\displaystyle=-a\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|\mathopen{}\mathclose{{}\left(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B},\bm{\lambda}N)}\right)-cN+\zeta_{\mathsf{B}}\;,$
$\displaystyle=-a\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left(\alpha_{\delta}(1+N)^{-\gamma}+\beta+\bm{\lambda}^{\operatorname{T}}\bm{\theta}}\right)}\right]-cN+\zeta_{\mathsf{B}}$
$\displaystyle=\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)\;.$

We denote by
$\widetilde{\Xi}_{\mathsf{B}}=\mathopen{}\mathclose{{}\left\\{(\bm{\lambda},N)\in\Delta_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}\times\mathbb{R}_{+}:\>\bm{\lambda}N\in\Xi_{\mathsf{B}}}\right\\}$
and $\widetilde{\mathcal{T}}_{\mathsf{B}}$ the problem:

$(\widetilde{\mathcal{T}}_{\mathsf{B}}):\quad\text{minimize}\quad-\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)\quad\text{subject
to}\quad(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}\;.$ (15)

By definition, any solution to $\widetilde{\mathcal{T}}_{\mathsf{B}}$ is a
solution to $\mathcal{T}_{\mathsf{B}}$. We can further decompose
$\widetilde{\mathcal{T}}_{\mathsf{B}}$ by observing that

$-\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)=f(N)+g(\bm{\lambda})\;,$

with

$f(N)=a\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|(\mathcal{R}^{\star}_{0}+2\alpha_{\delta}(1+N)^{-\gamma}+2\beta)+cN+\zeta_{\mathsf{B}}\quad\text{and}\quad
g(\bm{\lambda})=2a\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|\bm{\lambda}^{\operatorname{T}}\bm{\theta}\;.$

Finally, we denote a slice of $\widetilde{\Xi}_{\mathsf{B}}$ along $N\geqslant
0$ as
$\widetilde{\Xi}_{\mathsf{B}}(N)=\\{\bm{\lambda}\in\Delta_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}:\>(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}\\}$
and $\mathcal{N}=\\{N\geqslant
0:\>\widetilde{\Xi}_{\mathsf{B}}(N)\neq\emptyset\\}$.
$\widetilde{\mathcal{T}}_{\mathsf{B}}$ comes down to

$\min_{(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}}\\{f(N)+g(\bm{\lambda})\\}=\min_{N\in\mathcal{N}}\\{f(N)+\min_{\bm{\lambda}\in\widetilde{\Xi}_{\mathsf{B}}(N)}g(\bm{\lambda})\\}\;.$
(16)

A strategy to solve Equation 45 is to (i) address the innermost problem
$\min_{\bm{\lambda}\in\widetilde{\Xi}_{\mathsf{B}}(N)}g(\bm{\lambda})$ with
$N\geqslant 0$ fixed, and denoting
$\bm{\lambda}^{(N)}\in\widetilde{\Xi}_{\mathsf{B}}(N)$ its solution, (ii)
solve

$\min_{N\in\mathcal{N}}\\{f(N)+g(\bm{\lambda}^{(N)})\\}\;.$ (17)

Point (i) is done in the proof of Theorem 1. However, the resulting problem in
(ii) is hard to tackle because $\bm{\lambda}^{(N)}$ has no simple form.
Therefore, we leave aside the term $g(\bm{\lambda}^{(N)})$ (which can be
easily controlled, as shown in Lemma 2) to determine $N$ and only consider the
problem

$\min_{N\geqslant 0}\,f(N)\;.$ (18)

Since $f$ is differentiable and strictly convex, its minimizer is uniquely
defined by $f^{\prime}(\bar{N})=0$, which gives

$\bar{N}=(\underline{n}+1)\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|^{\frac{1}{1+\gamma}}-1\;,$
(19)

where $\underline{n}$ is defined in Proposition 1. As the solution of the
relaxed problem (18), we take
$\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}n^{\star}_{j}(\bm{\theta})=\bar{N}$
is the simplified contribution scheme
$(\mathsf{B}^{\star},\mathbf{n}^{\star})$.

##  Appendix B Proofs

See 1

###### Proof.

  1. (i)

Let $\\{(X^{j}_{1},Y^{i}_{1}),\ldots,(X^{j}_{n_{j}},Y^{j}_{n_{j}})\\}$ be
$n_{j}>0$ i.i.d samples from $P_{j}\in\mathcal{P}$ and
$\widehat{g}_{j}=\inf_{g\in\mathscr{G}}\widehat{\mathcal{R}}_{j}(g)$. First,
observe that

$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)\leqslant\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)}\right|=\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)+\theta_{j}\;.$
(20)

Let $\upsilon>0$ and $g_{j}^{\upsilon}\in\mathscr{G}$ such that
$\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g^{\upsilon}_{j}}\right)\leqslant\inf_{g\in\mathscr{G}}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)+\upsilon$.
Then with probability at least $1-\delta$,

$\displaystyle\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)$
$\displaystyle=\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)-\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g_{j}^{\upsilon}}\right)+\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g_{j}^{\upsilon}}\right)$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\widehat{\mathcal{R}}_{j}(g^{\upsilon}_{j})-\widehat{\mathcal{R}}_{j}(\widehat{g}_{j})}\right)+\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)-\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g_{j}^{\upsilon}}\right)+\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g_{j}^{\upsilon}}\right)$
$\displaystyle\leqslant
2\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\widehat{\mathcal{R}}_{j}(g)}\right|+\inf_{g\in\mathscr{G}}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)+\upsilon$
$\displaystyle\leqslant
2\mathopen{}\mathclose{{}\left(\frac{\alpha_{\delta}}{(n+1)^{\gamma}}+\beta}\right)+\inf_{g\in\mathscr{G}}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)\;,$
(21)

where the last inequality holds taking the limit $\upsilon\rightarrow 0$ and
using H 1. Finally, observing that
$\inf_{g\in\mathscr{G}}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)\,-\,\mathcal{R}^{\star}_{0}=\inf_{g\in\mathscr{G}}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\inf_{g\in\mathscr{G}}\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)\leqslant\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|=\theta_{j}$,
and combining Equation 20 and Equation 21 yields

$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{j}}\right)\leqslant\mathcal{R}^{\star}_{0}+2\theta_{j}+2\mathopen{}\mathclose{{}\left(\frac{\alpha_{\delta}}{(n+1)^{\gamma}}+\beta}\right)=\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},n)\;,$
(22)

with probability at least $1-\delta$.

  2. (ii)

Let $\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$ and
$\mathbf{n}=(n_{1},\ldots,n_{j})\in\mathbb{R}_{+}^{J}$. For any
$j\in\mathsf{B}$, let
$\\{(X^{j}_{1},Y^{i}_{1}),\ldots,(X^{j}_{n_{j}},Y^{j}_{n_{j}})\\}$ be a
collection of $n_{j}>0$ i.i.d samples from $P_{j}\in\mathcal{P}$. Denote by
$N=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}n_{j}$ and consider
$\bm{\lambda}=(\lambda_{1},\ldots,\lambda_{J})$ such that
$\lambda_{j}=B_{j}n_{j}/N$. Note that $\bm{\lambda}$ belongs to the
$J$-dimensional simplex. For any $g\in\mathscr{G}$, the empirical risk over
contributions is

$\widehat{\mathcal{R}}_{\mathsf{B}}(g)=\frac{1}{N}\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\sum_{i=1}^{n_{j}}\ell(h(X^{j}_{i}),Y^{j}_{i})=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\widehat{\mathcal{R}}_{j}(g)\;,$
(23)

and the population risk is

$\mathcal{R}_{\mathsf{B}}(g)=\mathbb{E}\mathopen{}\mathclose{{}\left[\widehat{\mathcal{R}}_{\mathsf{B}}(g)}\right]=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\mathbb{E}\mathopen{}\mathclose{{}\left[{\widehat{\mathcal{R}}_{j}(g)}}\right]=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)\;.$
(24)

The collaborative model $\widehat{g}_{\mathsf{B}}\in\mathscr{G}$ defined by
$\widehat{\mathcal{R}}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})=\inf_{g\in\mathscr{G}}\widehat{\mathcal{R}}_{\mathsf{B}}(g)$
verifies

$\displaystyle\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{\mathsf{B}}}\right)\leqslant\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{\mathsf{B}}(g)}\right|$
$\displaystyle\leqslant\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left\\{\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|}\right\\}$
$\displaystyle\leqslant\mathcal{R}_{\mathsf{B}}\mathopen{}\mathclose{{}\left(\widehat{g}_{\mathsf{B}}}\right)+\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|$
$\displaystyle=\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})+\vartheta(\mathsf{B},\mathbf{n})\;,$
(25)

with
$\vartheta(\mathsf{B},\mathbf{n})=N^{-1}\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\mathrm{n}_{j}\theta_{j}=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}\lambda_{j}\theta_{j}$.
Now, let $\upsilon>0$ and $g^{\upsilon}\in\mathscr{G}$ such that
$\mathcal{R}_{\mathsf{B}}(g^{\upsilon})\leqslant\inf_{g\in\mathscr{G}}\mathcal{R}_{\mathsf{B}}(g)+\upsilon$.
We also have

$\displaystyle\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})$
$\displaystyle=\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})-\mathcal{R}_{\mathsf{B}}(g^{\upsilon})+\mathcal{R}_{\mathsf{B}}(g^{\upsilon})$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\widehat{\mathcal{R}}_{\mathsf{B}}(g^{\upsilon})-\widehat{\mathcal{R}}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})}\right)+\mathcal{R}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})-\mathcal{R}_{\mathsf{B}}(g^{\upsilon})+\mathcal{R}_{\mathsf{B}}(g^{\upsilon})$
$\displaystyle\leqslant
2\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{\mathsf{B}}(g)-\widehat{\mathcal{R}}_{\mathsf{B}}(g)}\right|+\inf_{g\in\mathscr{G}}\mathcal{R}_{\mathsf{B}}(g)+\upsilon$
$\displaystyle\leqslant
2\mathopen{}\mathclose{{}\left(\frac{\alpha_{\delta}}{(N+1)^{\gamma}}+\beta}\right)+\inf_{g\in\mathscr{G}}\mathcal{R}_{\mathsf{B}}(g)\quad\text{with
probability at least }1-\delta\;,$ (26)

where the first inequality comes from
$\widehat{\mathcal{R}}_{\mathsf{B}}(\widehat{g}_{\mathsf{B}})=\inf_{g\in\mathscr{G}}\widehat{\mathcal{R}}_{\mathsf{B}}(g)\leqslant\widehat{\mathcal{R}}_{\mathsf{B}}(g^{\upsilon})$,
and the last is obtained by taking $\upsilon\rightarrow 0$ and applying
assumption H 1. Now, observe that
$\inf_{g\in\mathscr{G}}\mathcal{R}_{\mathsf{B}}(g)-\mathcal{R}^{\star}_{0}=\inf_{g\in\mathscr{G}}\mathcal{R}_{\mathsf{B}}(g)-\inf_{g\in\mathscr{G}}\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)\leqslant\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{\mathsf{B}}(g)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|\leqslant\sum_{j}B_{j}\lambda_{j}\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|=\vartheta(\mathsf{B},\mathbf{n})$.
Combining this observation with Item (ii) and Equation 26 gives with
probability $1-\delta$

$\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(\widehat{g}_{\mathsf{B}}}\right)\leqslant\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left(\frac{\alpha_{\delta}}{(N+1)^{\gamma}}+\beta}\right)+2\vartheta(\mathsf{B},\mathbf{n})=\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\mathsf{B},\mathbf{n}),N)\;.$
(27)

∎

See 1

###### Proof.

For any $j\in\mathopen{}\mathclose{{}\left[J}\right]$ and $n\geq 0$, Lemma 1
gives that

$-u_{j}\mathopen{}\mathclose{{}\left((0,\mathsf{B}_{-j}),(n,\mathbf{n}_{-j}),\theta_{j}}\right)=a[\mathcal{R}^{\star}_{0}+2(\alpha_{\delta}(n+1)^{-\gamma}+\beta+\theta_{j})]+cn=f(n)\;.$

Since $f$ is strictly convex and differentiable, it admits a unique maximizer
$\underline{n}\geqslant 0$ determined by $f^{\prime}(\underline{n})=0$. Simple
algebra leads to $\underline{n}=(2a\gamma
c^{-1}\alpha_{\delta})^{1/\gamma+1}-1$. ∎

See 1

###### Proof.

Recall that the optimal aggregation problem reads

$\displaystyle\text{maximize}\quad
W(\mathsf{B},\mathbf{n})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\mathbb{R}^{J}_{+}\mapsto\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}(\mathsf{B},\mathbf{n})$
(28) $\displaystyle\text{subject
to}\quad\min_{j\in\mathopen{}\mathclose{{}\left[J}\right]}u_{j}((1,\mathsf{B}_{-j}),\mathbf{n})-\underline{u}_{j}\geqslant
0\;.$

Define for any
$j\in\mathopen{}\mathclose{{}\left[J}\right],\mathsf{B}_{-j}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J-1}$,
and $\mathbf{n}_{-j}\in\mathbb{R}_{+}^{J-1}$, the maximum number of samples
agent $j\in\mathopen{}\mathclose{{}\left[J}\right]$ having $B_{j}=1$ may be
asked given their participation constraint:

$\overline{n}_{j}(\mathsf{B},\mathbf{n})=\max\\{n\geqslant
0:\,u_{j}\mathopen{}\mathclose{{}\left((1,\mathsf{B}_{-j}),(n,\mathbf{n}_{-j})}\right)\geqslant\underline{u}_{j}\\}\;.$

Given Equation 5 and Proposition 1, we obtain

$\overline{n}_{j}(\mathsf{B},\mathbf{n})=\underline{n}-ac^{-1}(\varepsilon(\mathsf{B},\mathbf{n})-\varepsilon(\theta_{j},\underline{n}))\;,$
(29)

where
$N=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}B_{j}n_{j}=\mathbf{n}^{\operatorname{T}}\mathsf{B}$.
Problem (28) rewrites in canonical form

$\text{minimize}\quad-W(\mathsf{B},\mathbf{n})\quad\text{subject
to}\quad\begin{cases}\max_{j\in\mathcal{B}}n_{j}-\overline{n}(\mathsf{B},\mathbf{n})\leqslant
0\\\ \max_{j\in\mathopen{}\mathclose{{}\left[J}\right]}-n_{j}\leqslant
0\;,\end{cases}$ (30)

where
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>B_{j}=1}\right\\}$.
We first show that it admits a unique minimum.

Fix a $\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$ and
consider problem (30) with respect to $\mathbf{n}\in\mathbb{R}^{J}_{+}$ only.
We call this subproblem $\mathcal{T}_{\mathsf{B}}$. First, we show that it is
enough to focus on $(n_{j})_{j\in\mathcal{B}}$ in $\mathcal{T}_{\mathsf{B}}$.
With $\mathbf{n}_{\mathcal{B}}=(\mathrm{n}_{j})_{j\in\mathcal{B}}$ and
$\mathbf{n}_{\mathcal{B}^{c}}=(\mathrm{n}_{j})_{j\notin\mathcal{B}}$, note
that $W(\mathsf{B},\mathbf{n})$ is decomposable in $\mathbf{n}_{\mathcal{B}}$
and $\mathbf{n}_{\mathcal{B}^{c}}$:

$W(\mathsf{B},\mathbf{n})=W(\mathsf{B},\mathbf{n}_{\mathcal{B}})+W(\mathsf{B},\mathbf{n}_{\mathcal{B}^{c}})\;,$

where, by a slight abuse of notation
$W(\mathsf{B},\mathbf{n}_{\mathcal{B}})=\sum_{j\in\mathsf{B}}u_{j}(\mathsf{B},\mathbf{n})$
and
$W(\mathsf{B},\mathbf{n}_{\mathcal{B}^{c}})=\sum_{j\in\mathcal{B}^{c}}u_{j}(\mathsf{B},\mathbf{n})$.
With

$\Xi_{\mathsf{B}}=\mathopen{}\mathclose{{}\left\\{\mathbf{n}_{\mathcal{B}}\in\mathbb{R}_{+}^{\mathcal{B}}:\>\begin{array}[]{cc}\max_{j\in\mathcal{B}}\mathopen{}\mathclose{{}\left\\{n_{j}-\overline{n}_{j}(\mathsf{B},\mathbf{n})}\right\\}\leqslant
0\\\ \max_{j\in\mathcal{B}}-n_{j}\leqslant 0\end{array}}\right\\}\;,$ (31)

problem $\mathcal{T}_{\mathsf{B}}$ is equivalent to

$\min_{\mathbf{n}_{\mathcal{B}}\in\Xi_{\mathsf{B}}}-W(\mathsf{B},\mathbf{n}_{\mathcal{B}})+\min_{\mathbf{n}_{\mathcal{B}^{c}}\in\mathbb{R}_{+}^{J-\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}}-W(\mathsf{B},\mathbf{n}_{\mathcal{B}^{c}})=\min_{\mathbf{n}_{\mathcal{B}}\in\Xi_{\mathsf{B}}}-W(\mathsf{B},\mathbf{n}_{\mathcal{B}})+\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}(1-B_{j})\underline{u}_{j}\;,$
(32)

by Proposition 1. Since
$\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}(1-B_{j})\underline{u}_{j}$
is constant, by Equation 32 it is enough to focus on
$\min_{\mathbf{n}_{\mathcal{B}}\in\Xi_{\mathsf{B}}}-W(\mathsf{B},\mathbf{n}_{\mathcal{B}})$.
On the one hand, $\Xi_{\mathsf{B}}$ is bounded. Indeed for any
$j\in\mathcal{B}$, by Equation 29 and Lemma 1

$\displaystyle\overline{n}_{j}(\mathsf{B},\mathbf{n}_{\mathcal{B}})$
$\displaystyle=\underline{n}-\frac{a}{c}\mathopen{}\mathclose{{}\left[\varepsilon(\mathsf{B},\mathbf{n}_{\mathcal{B}})-\varepsilon(\theta_{j},\underline{n})}\right]$
$\displaystyle=\underline{n}-\frac{a}{c}\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left[\frac{\alpha_{\delta}}{(1+\mathbf{n}_{\mathcal{B}}^{\operatorname{T}}\mathsf{B})^{\gamma}}+\beta+\vartheta(\mathsf{B},\mathbf{n})}\right]-\mathcal{R}^{\star}_{0}-2\mathopen{}\mathclose{{}\left[\frac{\alpha_{\delta}}{(1+\underline{n})^{\gamma}}-\beta-\theta_{j}}\right]}\right]$
$\displaystyle=\underline{n}-\frac{2a}{c}\mathopen{}\mathclose{{}\left[\alpha_{\delta}\mathopen{}\mathclose{{}\left((1+\mathbf{n}_{\mathcal{B}}^{\operatorname{T}}\mathsf{B})^{-\gamma}-(1+\underline{n})^{-\gamma}}\right)+\mathopen{}\mathclose{{}\left(\vartheta(\mathsf{B},\mathbf{n})-\theta_{j}}\right)}\right]$
$\displaystyle\leqslant\underline{n}-\frac{2a}{c}\mathopen{}\mathclose{{}\left[\alpha_{\delta}\mathopen{}\mathclose{{}\left(1-(1+\underline{n})^{-\gamma}}\right)+\max_{j\in\mathcal{B}}\theta_{j}}\right]$
$\displaystyle=M$ (33)

Thus,
$\Xi_{\mathsf{B}}\subset[0,M]^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$.
Moreover, $\Xi_{\mathsf{B}}$ is closed and convex. For any $j\in\mathcal{B}$,
rewrite

$\displaystyle\overline{n}_{j}(\mathsf{B},\mathbf{n}_{\mathcal{B}})$
$\displaystyle=\underline{n}-\frac{2a}{c}\mathopen{}\mathclose{{}\left[\alpha_{\delta}\mathopen{}\mathclose{{}\left((1+\mathbf{n}_{\mathcal{B}}^{\operatorname{T}}\mathsf{B})^{-\gamma}-(1+\underline{n})^{-\gamma}}\right)+\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\mathbf{n}_{\mathcal{B}}^{\operatorname{T}}\mathsf{B}}\right)^{-1}\mathbf{n}_{\mathcal{B}}^{\operatorname{T}}\bm{\theta}-\theta_{j}}\right)}\right]$
$\displaystyle=g_{j}(\mathbf{n}_{\mathcal{B}})\;,$

and define
$h_{j}:\mathbf{n}_{\mathcal{B}}\mapsto\mathrm{n}_{\mathcal{B},j}-g_{j}(\mathbf{n}_{\mathcal{B}})$.
Observe that
$\Xi_{\mathsf{B}}=\\{\mathbf{n}_{\mathcal{B}}\in\mathbb{R}_{+}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}:\>\forall
j\in\mathcal{B},\,n_{\mathcal{B},j}\geqslant 0\>\text{ and
}\>h_{j}(\mathbf{n}_{\mathcal{B}})\leqslant 0\\}$, that is
$\Xi_{\mathsf{B}}=A\,\cap\,B$ with
$A=\mathbb{R}_{+}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$ and
$B=h^{-1}_{1}((-\infty,0])\cap\ldots\cap
h^{-1}_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}((-\infty,0])$. For
any $j\in\mathcal{B}$, $h^{-1}_{j}((-\infty,0])$ is convex, because so is
$h_{j}$. Additionally, $h^{-1}_{j}((-\infty,0])$ is closed as the inverse
image of a closed set by a continuous function. It follows that
$\Xi_{\mathsf{B}}$ is convex and closed as the intersection of convex and
closed sets.

As a consequence $\Xi_{\mathsf{B}}$ is compact and convex, and
$-W(\mathsf{B},\,\bm{\cdot}\,)$ is strictly convex so
$\mathcal{T}_{\mathsf{B}}$ admits a unique minimizer
$\mathbf{n}_{\mathcal{B}}^{\mathrm{opt}}\in\Xi_{\mathsf{B}}$.

Since there are finitely many
$\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$,
$\min\\{-W(\mathsf{B},\mathbf{n}_{\mathcal{B}}^{\mathrm{opt}})+\sum_{j\in\mathcal{B}^{c}}\underline{u}_{j},\,\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\\}>0$
exists and coincide with the minimum of problem
$\eqref{master_problem_canonical}$. We show later in the proof that the
optimal
$\mathsf{B}^{\mathrm{opt}}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$
is unique (see part 1), so the minimizer of Equation 30 is unique. This
establishes the point (i) of the result.

The remainder of the proof proceeds as follows: we first characterize the
optimal
$\mathsf{B}^{\mathrm{opt}}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}$,
and then prove that the solution
$\mathbf{n}^{\mathrm{opt}}_{\mathcal{B}^{\mathrm{opt}}}\in\mathbb{R}_{+}^{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}$
of $\mathcal{T}_{\mathsf{B}^{\mathrm{opt}}}$ satisfies point (ii).

_Part 1: Optimal
$\mathsf{B}\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{\mathopen{}\mathclose{{}\left[J}\right]}$_

We show that $\mathsf{B}^{\mathrm{opt}}=(1,\ldots,1)^{\operatorname{T}}$. By
contradiction, assume there exists
$\mathsf{B}^{\prime}\neq(1,\ldots,1)^{\operatorname{T}}$ and
$\mathbf{n}^{\prime}\in\mathbb{R}^{J}_{+}$ such that for any
$(\mathsf{B},\mathbf{n})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\mathbb{R}^{J}_{+}$

$-W(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\leqslant-W(\mathsf{B},\mathbf{n})\;.$
(34)

Denote by $j\in\mathopen{}\mathclose{{}\left[J}\right]$ an agent such that
$B^{\prime}_{j}=0$, and first assume
$\theta_{j}\geqslant\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})$.
Consider the alternative allocation
$(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})=((1,\mathsf{B}^{\prime}_{-j}),(0,\mathbf{n}^{\prime}_{-j}))$.
Observe that
$B^{\prime}_{j}n^{\prime}_{j}=B^{\prime\prime}_{j}n^{\prime\prime}_{j}=0$, so

$N^{\prime}=\mathsf{B}^{\prime\operatorname{T}}\mathbf{n}^{\prime}=\mathsf{B}^{\prime\prime\operatorname{T}}\mathbf{n}^{\prime\prime}=N^{\prime\prime}\quad\text{and}\quad\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})=\vartheta(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})\;.$
(35)

This in particular implies

$\displaystyle\varepsilon(\mathsf{B}^{\prime},\mathbf{n}^{\prime})$
$\displaystyle=2\mathopen{}\mathclose{{}\left[\alpha_{\delta}(1+N^{\prime})^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime},N^{\prime})}\right]$
$\displaystyle=2\mathopen{}\mathclose{{}\left[\alpha_{\delta}(1+N^{\prime\prime})^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime\prime},N^{\prime\prime})}\right]=\varepsilon(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})\;.$
(36)

Thus by (36)

$\displaystyle-
u_{j}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})=\underline{u}_{j}$
$\displaystyle=a(\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},\underline{n}))+c\underline{n}>a(\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},\underline{n}))$
$\displaystyle\geqslant
a(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B}^{\prime},\mathbf{n}^{\prime}))=a(\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime}))=-u_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})\;,$
(37)

where the second inequality results from
$\theta_{j}\geqslant\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})$ and
$N^{\prime}\geqslant\underline{n}$. Finally by definition of
$(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$, (35) and (36), for
any $k\neq j$ such that $B^{\prime\prime}_{k}=1$:

$\displaystyle-u_{k}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$
$\displaystyle=a\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left(\alpha_{\delta}(1+N^{\prime\prime})^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})}\right)}\right]+cn_{k}^{\prime\prime}$
$\displaystyle=a\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left(\alpha_{\delta}(1+N^{\prime})^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})}\right)}\right]+cn_{k}^{\prime}=-u_{k}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;.$
(38)

Hence, (38) together with (37) give

$\displaystyle-W(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})=-\sum_{k\neq
j}u_{k}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})-u_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$
$\displaystyle=-\sum_{k\neq
j}u_{i}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})-u_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$
$\displaystyle<-\sum_{k\neq
j}u_{i}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})-u_{j}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})=-W(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;.$
(39)

This contradicts (34). Now assume
$\theta_{j}<\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})$, and let
$R\in\mathopen{}\mathclose{{}\left[J}\right]$ be such that
$\theta_{R}=\max\\{\theta_{k},\,k\in\mathcal{B}\\}$. Consider
$(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\mathbb{R}^{J}_{+}$
where

$\displaystyle\mathsf{B}^{\prime\prime}$
$\displaystyle=(B^{\prime}_{1},\ldots,B^{\prime}_{j-1},\,1\,,B^{\prime}_{j+1},\ldots,B^{\prime}_{J})^{\operatorname{T}}$
$\displaystyle\text{and }\mathbf{n}^{\prime\prime}$
$\displaystyle=(n^{\prime}_{1},\ldots,n^{\prime}_{j-1},\,\overline{n}_{j}\,,n^{\prime}_{j+1},\ldots,n^{\prime}_{R-1},\,\max(0,n^{\prime}_{R}-\overline{n}_{j})\,,n^{\prime}_{R+1},\ldots,n^{\prime}_{J})^{\operatorname{T}}\;.$

which is feasible. Observe on the one hand that

$N^{\prime\prime}=N^{\prime}\quad\text{
and}\quad\vartheta(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})\leqslant\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})+\frac{\overline{n}_{j}}{N^{\prime}}\mathopen{}\mathclose{{}\left(\theta_{j}-\theta_{R}}\right)<\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;,$

because
$\theta_{j}<\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\leqslant\theta_{R}$.
In particular

$\displaystyle\varepsilon(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$
$\displaystyle=\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left[\alpha_{\delta}(N^{\prime\prime}+1)^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})}\right]$
$\displaystyle<\mathcal{R}^{\star}_{0}+2\mathopen{}\mathclose{{}\left[\alpha_{\delta}(N^{\prime}+1)^{-\gamma}+\beta+\vartheta(\mathsf{B}^{\prime},\mathbf{n}^{\prime})}\right]=\varepsilon(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;.$
(40)

(40) in turn implies that for any $k\neq j$ such that
$B^{\prime\prime}_{k}=1$:

$-u_{k}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})=a\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})}\right]+cn^{\prime\prime}_{k}<a\mathopen{}\mathclose{{}\left[\mathcal{R}^{\star}_{0}+\varepsilon(\mathsf{B}^{\prime},\mathbf{n}^{\prime})}\right]+cn^{\prime}_{k}=-u^{\prime}_{k}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;.$
(41)

because $n^{\prime}_{k}=n^{\prime\prime}_{k}$ for
$k\in\mathcal{B}\setminus\\{j,R\\}$ and $n^{\prime\prime}_{R}<n^{\prime}_{R}$.
On the other hand, we have

$u_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})=\underline{u}_{j}=u_{j}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;,$
(42)

by definition (29) of
$\overline{n}_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$. (41)
and (42) together yield

$\displaystyle-W(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})=-\sum_{k\neq
j}u_{k}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})-u_{j}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})$
$\displaystyle=-\sum_{k\neq
j}u_{k}(\mathsf{B}^{\prime\prime},\mathbf{n}^{\prime\prime})-u_{j}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})$
$\displaystyle<-\sum_{k\neq
j}u_{k}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})-u_{j}(\mathsf{B}^{\prime},\mathbf{n}^{\prime})=-W(\mathsf{B}^{\prime},\mathbf{n}^{\prime})\;,$

which once again violates (34). Thus, we obtain
$\mathsf{B}^{\mathrm{opt}}=(1,\ldots,1)^{\operatorname{T}}$, that is
$\mathcal{B}^{\mathrm{opt}}=\mathopen{}\mathclose{{}\left[J}\right]$.

_Part 2: Characterization of
$\mathbf{n}^{\mathrm{opt}}_{\mathopen{}\mathclose{{}\left[J}\right]}\in\mathbb{R}_{+}^{J}$_

We now focus on the problem $\mathcal{T}_{\mathsf{B}^{\mathrm{opt}}}$. To
lighten notations, we write $\mathbf{n}^{\mathrm{opt}}\in\mathbb{R}_{+}^{J}$
instead of $\mathbf{n}^{\mathrm{opt}}_{\mathcal{B}^{\mathrm{opt}}}$, and drop
the $\mathrm{opt}$ superscript in $\mathsf{B}^{\mathrm{opt}}$. We first
reformulate $\mathcal{T}_{\mathsf{B}}$ in a more convenient way. Recall that
$\mathcal{T}_{\mathcal{B}}$ reads

$(\mathcal{T}_{\mathsf{B}}):\quad\text{minimize}\quad-W(\mathsf{B},\mathbf{n})\quad\text{subject
to}\quad\mathbf{n}\in\Xi_{\mathsf{B}}\;,$ (43)

where $\Xi_{\mathsf{B}}$ is defined in (31). As explained in Appendix A, this
problem can equivalently be stated as

$(\widetilde{\mathcal{T}}_{\mathsf{B}}):\quad\text{minimize}\quad-\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)\quad\text{subject
to}\quad(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}\;,$ (44)

where

$-\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)=f(N)+g(\bm{\lambda})\;,$

with

$f(N)=aJ(\mathcal{R}^{\star}_{0}+2\alpha_{\delta}(1+N)^{-\gamma})+cN\quad\text{and}\quad
g(\bm{\lambda})=2aJ\bm{\lambda}^{\operatorname{T}}\bm{\theta}\;,$

and

$\widetilde{\Xi_{\mathsf{B}}}=\mathopen{}\mathclose{{}\left\\{(\bm{\lambda},N)\in\Delta_{\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|}\times\mathbb{R}_{+}:\>\bm{\lambda}N\in\Xi_{\mathsf{B}}}\right\\}\;.$

Writing
$\widetilde{\Xi}_{\mathsf{B}}(N)=\\{\bm{\lambda}\in\Delta_{J}:\>(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}\\}$
for $N\geqslant 0$ and $\mathcal{N}=\\{N\geqslant
0:\>\widetilde{\Xi}_{\mathsf{B}}(N)\neq\emptyset\\}$,
$\widetilde{\mathcal{T}}_{\mathsf{B}}$ comes down to

$\min_{(\bm{\lambda},N)\in\widetilde{\Xi}_{\mathsf{B}}}\\{f(N)+g(\bm{\lambda})\\}=\min_{N\in\mathcal{N}}\\{f(N)+\min_{\bm{\lambda}\in\widetilde{\Xi}_{\mathsf{B}}(N)}g(\bm{\lambda})\\}\;.$
(45)

In this proof, we address the innermost problem. Let $N\geqslant 0$ such that
$\widetilde{\Xi}_{\mathsf{B}}(N)\neq\emptyset$, which exists because
$\Xi_{\mathsf{B}}\neq\emptyset$ (for instance,
$((1,0,\ldots,0),(\underline{n},0,\ldots,0))\in\Xi_{\mathsf{B}}$). By
definition of $\widetilde{\Xi}_{\mathsf{B}}$, it reads

$(\widetilde{\mathcal{T}}^{(N)}):\quad\text{minimize}\quad\bm{\lambda}\in\Delta_{J}\mapsto
2aJ\bm{\lambda}^{\operatorname{T}}\bm{\theta}\quad\text{subject
to}\quad\begin{cases}\forall j\in\mathcal{B}:\lambda_{j}\geqslant 0\\\ \forall
j\in\mathcal{B}:\>\lambda_{j}N\leqslant\overline{n}_{j}(\mathsf{B},\bm{\lambda}N)\\\
\sum_{j\in\mathcal{B}}\lambda_{j}=1\;,\end{cases}$ (46)

The following lemma provides a necessary condition for any solution to problem
(46).

######  Lemma 4.

Let
$\bm{\lambda}^{(N)}=(\lambda^{(N)}_{1},\ldots,\lambda^{N}_{J})\in\Delta_{J}$
be a solution to (46). If there exists $r\in\mathcal{B}$ such that
$\lambda^{(N)}_{r}>0$, then
$\lambda_{k}^{(N)}=N^{-1}\overline{n}_{k}(\mathsf{B},N\bm{\lambda}^{(N)})$ for
any $k<r$.

###### Proof.

We denote by
$\bar{\mathbf{n}}(\mathsf{B},\mathbf{n})=(\overline{n}_{1}(\mathsf{B},\mathbf{n}),\ldots,\overline{n}_{J}(\mathsf{B},\mathbf{n}))^{\operatorname{T}}$
for any $\mathbf{n}\in\mathbb{R}_{+}^{J}$. The Lagrangian associated to
problem (46), with $\bm{\mu},\bm{\rho}$ and $\nu$ the associated dual
variables, reads:

$\displaystyle\mathcal{L}(\bm{\lambda},\bm{{\mu}},\bm{\rho},\nu)$
$\displaystyle=2aJ\bm{\lambda}^{\operatorname{T}}\bm{\theta}-\bm{{\mu}}^{\operatorname{T}}\bm{\lambda}+\nu\mathopen{}\mathclose{{}\left(1-\bm{\lambda}^{\operatorname{T}}{\bf
1}}\right)+\bm{\rho}^{\operatorname{T}}\mathopen{}\mathclose{{}\left[N\bm{\lambda}-\bar{\mathbf{n}}(\mathsf{B},N\bm{\lambda})}\right]$
$\displaystyle=2aJ\bm{\lambda}^{\operatorname{T}}\bm{\theta}+cN-\bm{{\mu}}^{\operatorname{T}}\bm{\lambda}+\nu\mathopen{}\mathclose{{}\left(1-\bm{\lambda}^{\operatorname{T}}{\bf
1}}\right)$
$\displaystyle+\bm{\rho}^{\operatorname{T}}(N\bm{\lambda}-\underline{n}{\bf
1}+\frac{2a}{c}\mathopen{}\mathclose{{}\left[\alpha_{\delta}\mathopen{}\mathclose{{}\left((N+1)^{-\gamma}-(\underline{n}+1)^{-\gamma}}\right){\bf
1}+\mathopen{}\mathclose{{}\left((\bm{\lambda}^{\operatorname{T}}\bm{\theta}){\bf
1}-\bm{\theta}}\right)}\right])\;.$

Since the objective and the constraints are convex, $\mathcal{L}$ admits a
saddle point
$(\bm{\lambda}^{(N)},\bm{{\mu}},\bm{\rho},\nu)\in\Delta\times\mathbb{R}^{J}\times\mathbb{R}^{J}\times\mathbb{R}$
which is solution to problem (46) and verifies the following KKT conditions:

$\displaystyle\forall k\leqslant
J:\>2aJ\theta_{k}-\mu_{k}+\rho_{k}(N+2ac^{-1}\theta_{k})=\nu$ (47)
$\displaystyle\forall k\leqslant
J:\>\mu_{k}\lambda^{(N)}_{k}=0,\quad\mu_{k}\geqslant 0$ (48)
$\displaystyle\forall k\leqslant
J:\>\rho_{k}\mathopen{}\mathclose{{}\left(\lambda^{(N)}_{k}\,N-\overline{n}_{{}_{k}}(\mathsf{B},\bm{\lambda}^{(N)}N)}\right)=0,\quad\rho_{k}\geqslant
0$ (49) $\displaystyle\sum_{k\in\mathcal{B}}\lambda^{(N)}_{k}=1\;.$ (50)

Assume there exists $r\in\mathcal{B}$ such that $\lambda^{(N)}_{r}>0$. By
complementary slackness (48), $\mu_{r}=0$, and (47) gives for any $k<r$:

$2aJ\theta_{k}-\mu_{k}+\rho_{k}(N+2ac^{-1}\theta_{k})=2aJ\theta_{r}+\rho_{r}(N+2ac^{-1}\theta_{r})\;,$
(51)

That is

$\rho_{k}=\frac{2aJ(\theta_{r}-\theta_{k})+\mu_{k}}{N+2ac^{-1}\theta_{k}}+\rho_{r}\frac{N+2ac^{-1}\theta_{r}}{N+2ac^{-1}\theta_{k}}\;.$

By assumption $\theta_{r}>\theta_{k}$, and since $\mu_{k}\geqslant 0$ as well
as $\rho_{r}\geqslant 0$, we have $\rho_{k}>0$. It follows from (49) for agent
$k$ that
$\lambda^{\mathrm{opt}}_{k}N=\overline{n}(\mathsf{B},N\bm{\lambda}^{(N)})$.

∎

Now, define

$M_{j}=\sum_{k\leqslant
j}\overline{n}_{k}(\mathsf{B},\bm{\lambda}^{(N)}N)\quad\text{and}\quad
L=\min\mathopen{}\mathclose{{}\left\\{j\in\mathcal{B}\,:\;M_{j}\geqslant
N}\right\\}\;.$ (52)

We show that

$\lambda^{(N)}_{k}=\overline{n}_{k}(\mathsf{B},N\bm{\lambda}^{(N)})N^{-1}\text{
for any }k<L\quad\text{ and }\quad\lambda^{(N)}_{k}=0\text{ for any }k>L\;.$
(53)

To prove the first point, assume by contradiction that there exists $\ell<L$
such that
$\lambda^{(N)}_{\ell}<\overline{n}_{\ell}(\mathsf{B},\bm{\lambda}^{(N)}N)N^{-1}$.
By the contrapositive of Lemma 4,
$\lambda^{\mathrm{opt}}_{\ell+1}=\ldots=\lambda^{\mathrm{opt}}_{J}=0$. Thus

$\sum_{k\leqslant
J}\lambda^{(N)}_{k}=\sum_{k\leqslant\ell}\lambda^{(N)}_{k}\leqslant\sum_{k\leqslant\ell}\overline{n}_{k}(\mathsf{B},\bm{\lambda}^{(N)}N)N^{-1}=M_{\ell}N^{-1}<1\;,$

by definition of $L$ Equation 52 and $\ell<L$. This violates the third
constraint of problem (46). For the second point, assume there exists $\ell>L$
such that $\lambda^{(N)}_{\ell}>0$. By Lemma 4,
$\lambda^{(N)}_{k}=\overline{n}_{k}(\mathsf{B},\bm{\lambda}^{(N)}N)N^{-1}$ for
any $k\leqslant L<\ell$, so

$\displaystyle\sum_{k\leqslant J}\lambda^{(N)}_{k}\geqslant\sum_{k\leqslant
L}\lambda^{(N)}_{k}+\lambda^{(N)}_{\ell}$ $\displaystyle=\sum_{k\leqslant
L}\overline{n}_{k}(\mathsf{B},\bm{\lambda}^{(N)}N)N^{-1}+\lambda^{(N)}_{\ell}$
$\displaystyle=M_{L}N^{-1}+\lambda^{(N)}_{\ell}$ $\displaystyle\geqslant
1+\lambda^{(N)}_{\ell}>1\;,$

which once again violates the constraints of the problem. Finally by (53),

$\lambda^{(N)}_{i_{L}}=1-\sum_{k<L}\lambda^{(N)}_{k}-\sum_{k>L}\lambda^{(N)}_{k}=1-M_{L-1}N^{-1}\;,$
(54)

by (53). By (53) and (54) we obtain for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$:

$\lambda_{j}^{(N)}=N^{-1}\overline{n}_{j}(\mathsf{B},N\bm{\lambda}^{(N)})\mathbbm{1}_{\\{j<L\\}}+(1-N^{-1}M_{j-1})\mathbbm{1}_{\\{j=L\\}}\;,$
(55)

Now, consider the solution
$\mathbf{n}^{\mathrm{opt}}(\bm{\theta})\in\mathbb{R}^{J}$ to the initial
problem (46), and define

$\begin{cases}N^{\mathrm{opt}}&=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}n_{j}^{\mathrm{opt}}(\bm{\theta})\\\
\bm{\lambda}^{\mathrm{opt}}(\bm{\theta})&=\frac{1}{N^{\mathrm{opt}}}\mathbf{n}^{\mathrm{opt}}(\bm{\theta})\\\
L^{\mathrm{opt}}&=\min\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>\sum_{k\leqslant
j}\overline{n}_{k}(\mathsf{B},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))\geqslant
N^{\mathrm{opt}}\\}\;.\end{cases}$

$\bm{\lambda}^{\mathrm{opt}}(\bm{\theta})$ satisfies (55), and multiplying by
$N^{\mathrm{opt}}$ yields

$n_{j}^{\mathrm{opt}}(\bm{\theta})=\overline{n}_{j}(\mathsf{B},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))\mathbbm{1}_{\\{j<L^{\mathrm{opt}}\\}}+(N^{\mathrm{opt}}-\sum_{k\leqslant
j}n_{j}^{\mathrm{opt}}(\bm{\theta}))\mathbbm{1}_{\\{j=L^{\mathrm{opt}}\\}}\;,$
(56)

which concludes the proof.

∎

See 1

###### Proof.

By definition of the simplified scheme (12),
$n^{\star}_{j}(\bm{\theta})=\mathbbm{1}_{\\{j\leqslant
L^{\star}\\}}\overline{n}_{j}({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))=\mathbbm{1}_{\\{j\leqslant
L^{\star}\\}}[\underline{n}-(2a/c)(\varepsilon({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))-\varepsilon(\theta_{j},\underline{n}))]$
for any $j\leqslant L^{\star}$. Since
$\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}n^{\star}_{j}(\bm{\theta})=\bar{N}$,
we get

$\displaystyle\bar{N}$
$\displaystyle=L^{\star}\underline{n}-\frac{a}{c}\mathopen{}\mathclose{{}\left[L^{\star}\varepsilon({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))-\sum_{j\leqslant
L^{\star}}\varepsilon(\theta_{j},\underline{n})}\right]$
$\displaystyle=L^{\star}\mathopen{}\mathclose{{}\left[\underline{n}-\frac{2a}{c}\mathopen{}\mathclose{{}\left[\alpha_{\delta}\mathopen{}\mathclose{{}\left((1+\bar{N})^{-\gamma}-(1+\underline{n})^{-\gamma}}\right)+(\vartheta({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))-\bar{\theta}_{L^{\star}})}\right]}\right]\;,$

By Lemma 1 and denoting $\bar{\theta}_{L^{\star}}=L^{\star-1}\sum_{j\leqslant
L^{\star}}\theta_{j}$. This yields

$\vartheta({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))=\bar{\theta}_{L^{\star}}-\alpha_{\delta}((1+\bar{N})^{-\gamma}-(1+\underline{n})^{-\gamma})+(c/2a)(\underline{n}-\bar{N}/L^{\star})\;.$

Plugging back this value in $\overline{n}^{\star}_{j}({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))=\underline{n}-(2a/c)[\alpha_{\delta}\mathopen{}\mathclose{{}\left((1+\bar{N})^{-\gamma}-(1+\underline{n})^{-\gamma}}\right)+\mathopen{}\mathclose{{}\left(\vartheta({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))-\theta_{j}}\right)]$ gives for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$:

$n^{\star}_{j}(\bm{\theta})=\mathbbm{1}_{\\{j\leqslant
L^{\star}\\}}\mathopen{}\mathclose{{}\left[\frac{\bar{N}}{L^{\star}}-\frac{2a}{c}(\bar{\theta}_{L^{\star}}-\theta_{j})}\right]\;.$
(57)

We now determine the order of magnitude of $L^{\star}\in\\{1,\ldots,J\\}$.
Recall on the one hand that by (33), there exists $M>0$ such that $0\leqslant
n^{\star}_{j}(\bm{\theta})\leqslant M$ for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$, and on the other hand that
$\bar{\theta}_{L^{\star}}-\theta_{j}\leqslant\bar{\theta}-\underline{\theta}=\text{diam}(\Theta)<\infty$.
Therefore by (57),

$\frac{2a}{c}\text{diam}(\Theta)\leqslant\frac{\bar{N}}{L^{\star}}\leqslant
M+\frac{2a}{c}\text{diam}(\Theta)\quad\text{so}\quad\frac{\bar{N}}{L^{\star}}=\Theta(1)\;.$
(58)

Since
$\bar{N}=(\underline{n}+1)\mathopen{}\mathclose{{}\left|\mathcal{B}^{\star}}\right|^{\frac{1}{1+\gamma}}-1$
and $\mathcal{B}^{\star}=\mathopen{}\mathclose{{}\left[J}\right]$, (58)
results in $L=\Theta(J^{\frac{1}{1+\gamma}})$.

∎

See 2

###### Proof.

Recall that for any admissible $\mathbf{n}\in\Xi_{\mathsf{B}}$, we can define
$N={\bf 1}^{\operatorname{T}}\mathbf{n}$ and $\bm{\lambda}=N^{-1}\mathbf{n}$
so that the social cost rewrites

$-W(\mathsf{B},\mathbf{n})=-\widetilde{W}_{\mathsf{B}}(\bm{\lambda},N)=f(N)+g(\bm{\lambda})\;,$

with

$f(N)=aJ(\mathcal{R}^{\star}_{0}+2\alpha_{\delta}(1+N)^{-\gamma})+cN\quad\text{and}\quad
g(\bm{\lambda})=2aJ\bm{\lambda}^{\operatorname{T}}\bm{\theta}\;.$

By definition,
$N^{\star}=\sum_{j\in\mathopen{}\mathclose{{}\left[J}\right]}n^{\star}_{j}(\bm{\theta})=\bar{N}$
where
$\bar{N}=(\underline{n}+1)J^{\frac{1}{1+\gamma}}-1=\operatorname*{\arg\\!\min}_{N\geqslant
0}f(N)$. Hence,

$\displaystyle
W(B^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))-W(\mathsf{B}^{\star},\mathbf{n}^{\star}(\bm{\theta}))$
$\displaystyle=\widetilde{W}_{\mathsf{B}}(\bm{\lambda}^{\mathrm{opt}},N^{\mathrm{opt}})-\widetilde{W}_{\mathsf{B}}(\bm{\lambda}^{\star},\bar{N})$
$\displaystyle=f(\bar{N})+g(\bm{\lambda}^{\star})-f(N^{\mathrm{opt}})-g(\bm{\lambda}^{\mathrm{opt}})$
$\displaystyle\leqslant
g(\bm{\lambda}^{\star})-g(\bm{\lambda}^{\mathrm{opt}})=2aJ(\bm{\lambda}^{\star}-\bm{\lambda}^{\mathrm{opt}})^{\operatorname{T}}\bm{\theta}$
Since $\theta_{j}\leqslant\theta_{L^{\star}}$ for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$ such that
$\lambda^{\star}_{j}>0$, and $\theta_{j}\geqslant\theta_{1}$ for any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$ such that
$\lambda^{\mathrm{opt}}_{j}>0$: $\displaystyle
W(B^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))-W(\mathsf{B}^{\star},\mathbf{n}^{\star}(\bm{\theta}))$
$\displaystyle\leqslant 2aJ(\theta_{L^{\star}}-\theta_{1})\;,$ By assumption,
for any $j\in\\{2,\ldots,J\\}$ $\theta_{j}-\theta_{j-1}=\mathcal{O}(1/J)$ so
there exists $k_{j}>0$ and $R_{j}\geqslant 0$ such that
$\theta_{j}-\theta_{j-1}\leqslant k_{j}J^{-1}$ for $J\geqslant R_{j}$.
Denoting $R=\max_{j\in\mathopen{}\mathclose{{}\left[J}\right]}R_{j}$ and
$k=\max_{j\in\mathopen{}\mathclose{{}\left[J}\right]}k_{j}$, for any
$J\geqslant R$: $\displaystyle
W(B^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))-W(\mathsf{B}^{\star},\mathbf{n}^{\star}(\bm{\theta}))$
$\displaystyle\leqslant 2aJ\frac{kL^{\star}}{J}=2akL^{\star}\;,$

so
$W(B^{\mathrm{opt}},\mathbf{n}^{\mathrm{opt}}(\bm{\theta}))-W(\mathsf{B}^{\star},\mathbf{n}^{\star}(\bm{\theta}))=\mathcal{O}(L^{\star})=\mathcal{O}(J^{\frac{1}{1+\gamma}})$
by Corollary 1.

∎

See 2

###### Proof.

First, we show that the situation where the coalition is empty is a Nash
equilibrium. Consider
$\mathbf{s}=((0,\dagger),\ldots,(0,\dagger))\in\mathscr{S}^{N}$. For any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$ and deviation
$(1,\widetilde{\theta}_{j})$,
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j}\right\\}$ so
$\widehat{g}_{\mathsf{B}}=\widehat{g}_{j}$ and
$v_{j}((0,\dagger),\mathbf{s}^{\star}_{-j})=\underline{u}_{j}\geqslant
v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-j})$ by Proposition 1. Thus,
$s^{\star}\in\mathscr{E}$.

Now, consider a pure-strategy Nash equilibrium $s^{\star}\in\mathscr{E}$ such
that
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j\in\mathopen{}\mathclose{{}\left[J}\right]\,:\;B_{j}=1}\right\\}\neq\emptyset$.
Denote by
$\mathcal{C}=\\{j\in\mathcal{B}:\>n^{\star}_{j}(\widetilde{\bm{\theta}})>0\\}$
the set of contributors. We start with two technical lemmas:

######  Lemma 5.

There exists $\Delta\in\mathbb{R}$ such that for any $(j,k)\in\mathcal{C}^{2}$

$\theta_{j}-\widetilde{\theta}_{j}=\theta_{k}-\widetilde{\theta}_{k}=\Delta\;.$

###### Proof.

Consider $j\in\mathcal{C}$. To lighten notation, we write in this proof

$\vartheta(\widetilde{\bm{\theta}})=N^{-1}\sum_{j\in\mathcal{C}}n^{\star}_{j}(\widetilde{\bm{\theta}})\,\theta_{j}\quad\text{and}\quad\widetilde{\vartheta}(\widetilde{\bm{\theta}})=N^{-1}\sum_{j\in\mathcal{C}}n^{\star}_{j}(\widetilde{\bm{\theta}})\,\widetilde{\theta}_{j},\quad\text{where}\quad
N=\sum_{k\in\mathcal{C}}n^{\star}_{k}(\widetilde{\bm{\theta}})\;.$

By Corollary 1 and H 4,
$n^{\star}_{j}(\widetilde{\bm{\theta}})=\overline{n}_{j}(\mathsf{B},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))=\underline{n}-\frac{a}{c}(\varepsilon(\widetilde{\vartheta}(\widetilde{\bm{\theta}}),N)-\varepsilon(\widetilde{\theta}_{j},\underline{n}))$,
so their payoff reads

$\displaystyle v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-{j}})$
$\displaystyle=-a(\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\widetilde{\bm{\theta}}),N)-c\mathopen{}\mathclose{{}\left[\underline{n}-\frac{a}{c}\mathopen{}\mathclose{{}\left(\varepsilon(\widetilde{\vartheta}(\widetilde{\bm{\theta}}),N)-\varepsilon(\widetilde{\theta}_{j},\underline{n})}\right)}\right]$
$\displaystyle=-a(\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},\underline{n}))-c\underline{n}$
$\displaystyle+a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\varepsilon(\theta_{j},\underline{n})-\varepsilon(\widetilde{\theta}_{j},\underline{n})}\right)-\mathopen{}\mathclose{{}\left(\varepsilon(\vartheta(\widetilde{\bm{\theta}}),N)-\varepsilon(\widetilde{\vartheta}(\widetilde{\bm{\theta}}),N)}\right)}\right]$
$\displaystyle=\underline{u}_{j}+2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\mathopen{}\mathclose{{}\left(\vartheta(\widetilde{\bm{\theta}})-\widetilde{\vartheta}(\widetilde{\bm{\theta}})}\right)}\right]\;.$
(59)

Since $\mathbf{s}$ is a Nash equilibrium and
$\underline{u}_{j}=v_{j}((0,\dagger),\mathbf{s}_{-j})$, we have in particular
that

$2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\mathopen{}\mathclose{{}\left(\vartheta(\widetilde{\bm{\theta}})-\widetilde{\vartheta}(\widetilde{\bm{\theta}})}\right)}\right]\geqslant
0$

that is
$\theta_{j}-\widetilde{\theta}_{j}=\Delta_{j}\geqslant\Delta=\vartheta(\widetilde{\bm{\theta}})-\widetilde{\vartheta}(\widetilde{\bm{\theta}})$
for any $j\in\mathcal{C}$. We now show that this holds with strict equality
for any $j\in\mathcal{C}$. By contradiction, assume there exists
$r\in\mathcal{C}$ such that $\Delta_{r}=\Delta+\chi$ with $\chi>0$. Then

$\displaystyle\Delta=\vartheta(\widetilde{\bm{\theta}})-\widetilde{\vartheta}(\widetilde{\bm{\theta}})=\sum_{j\in\mathcal{C}}\lambda^{\star}_{j}(\widetilde{\bm{\theta}})\Delta_{j}$
$\displaystyle=\sum_{j\in\mathcal{C}\setminus\\{r\\}}\lambda^{\star}_{j}(\widetilde{\bm{\theta}})\Delta_{j}+\lambda^{\star}_{r}(\widetilde{\bm{\theta}})(\Delta+\chi)$
$\displaystyle\geqslant\Delta+\lambda^{\star}_{r}(\widetilde{\bm{\theta}})\chi>\Delta\;,$

because $\lambda^{\star}_{r}(\widetilde{\bm{\theta}})>0$ as $r\in\mathcal{C}$.
This is a contradiction, and establishes the result. ∎

######  Lemma 6.

For any $j\in\mathcal{C}$, $\widetilde{\theta}_{j}=\underline{\theta}\;.$

###### Proof.

Let $j\in\mathcal{C}$, by (59):

$\displaystyle v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-j})$
$\displaystyle=\underline{u}_{j}+2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\mathopen{}\mathclose{{}\left(\vartheta(\widetilde{\bm{\theta}})-\widetilde{\vartheta}(\widetilde{\bm{\theta}})}\right)}\right]$
$\displaystyle=\underline{u}_{j}+2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(1-\lambda_{j}^{\star}(\widetilde{\bm{\theta}})}\right)\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\sum_{k\in\mathcal{C}\setminus\\{j\\}}\lambda_{k}^{\star}(\widetilde{\bm{\theta}})\mathopen{}\mathclose{{}\left(\theta_{k}-\widetilde{\theta}_{k}}\right)}\right]$
$\displaystyle=\underline{u}_{j}+2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\sum_{k\in\mathcal{C}\setminus\\{j\\}}\lambda^{\star}_{k}(\widetilde{\bm{\theta}})}\right)\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\sum_{k\in\mathcal{C}\setminus\\{j\\}}\lambda^{\star}_{k}(\widetilde{\bm{\theta}})\mathopen{}\mathclose{{}\left(\theta_{k}-\widetilde{\theta}_{k}}\right)}\right]$
$\displaystyle=\underline{u}_{j}+2aq_{j}(\widetilde{\theta}_{j},\widetilde{\bm{\theta}}_{-j})\;,$

where

$q_{j}(\widetilde{\theta}_{j},\widetilde{\bm{\theta}}_{-j})=\sum_{k\in\mathcal{C}\setminus\\{j\\}}\lambda^{\star}_{k}(\widetilde{\bm{\theta}})[(\theta_{j}-\widetilde{\theta}_{j})-(\theta_{k}-\widetilde{\theta}_{k})]\;.$
(60)

We prove that $v_{j}((1,\,\bm{\cdot}\,),\mathbf{s}_{-j})$ is strictly
decreasing in $\widetilde{\theta}_{j}$ for $j\in\mathcal{C}$, by showing that
$\partial\hat{v}_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-{i_{j}}})/\partial\widetilde{\theta}_{j}<0$
For any $j\in\mathcal{C}$. For $v_{j}$ to be differentiable, we need $q_{j}$
to be differentiable, that is
$\lambda^{\star}_{j}(\widetilde{\bm{\theta}})=(\sum_{k\in\mathcal{C}}n^{\star}_{k}(\widetilde{\bm{\theta}}))^{-1}n^{\star}_{j}(\widetilde{\bm{\theta}})$
to be differentiable for any $j\in\mathcal{C}$. We re-index $\mathcal{C}$ as
$\\{i_{1},\ldots,i_{\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|}\\}$ so
that
$\widetilde{\theta}_{i_{1}}<\ldots<\widetilde{\theta}_{i_{\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|}}$.
Observe that for $0<h<\delta$ for $\delta>0$ sufficiently small,
$\widetilde{\theta}_{i_{j-1}}<\widetilde{\theta}_{j}+h<\widetilde{\theta}_{i_{j+1}}$
because
$\widetilde{\theta}_{i_{j-1}}<\widetilde{\theta}_{j}<\widetilde{\theta}_{i_{j+1}}$
by Lemma 5 and H 3. Hence, the bid ordering does not change for any
infinitesimal variation $\mathrm{d}\widetilde{\theta}_{j}>0$, nor does the
indicator $\text{1}\\{i_{j}\leqslant
i_{\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|}\\}$. Consequently by
Corollary 1, $n^{\star}_{j}(\bm{\theta})$ is differentiable in
$\widetilde{\theta}_{j}$. We have for any $j\in\mathcal{C}$:

$\displaystyle\frac{\partial
v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{k})}{\partial\widetilde{\theta}_{j}}$
$\displaystyle=2a\frac{\partial
q_{j}(\widetilde{\theta}_{j},\widetilde{\bm{\theta}}_{-j})}{\partial\widetilde{\theta}_{j}}$
$\displaystyle=2a\sum_{k\in\mathcal{C}\setminus\\{j\\}}\mathopen{}\mathclose{{}\left[\frac{\partial\lambda^{\star}_{k}(\widetilde{\bm{\theta}})}{\partial\widetilde{\theta}_{j}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\theta_{j}-\widetilde{\theta}_{j}}\right)-\mathopen{}\mathclose{{}\left(\theta_{k}-\widetilde{\theta}_{k}}\right)}\right)-\lambda^{\star}_{k}(\widetilde{\bm{\theta}})}\right]$
$\displaystyle=\sum_{k\in\mathcal{C}\setminus\\{j\\}}\frac{\partial\lambda^{\star}_{k}(\widetilde{\bm{\theta}})}{\partial\widetilde{\theta}_{j}}\mathopen{}\mathclose{{}\left(\Delta-\Delta}\right)-\sum_{k\in\mathcal{C}\setminus\\{j\\}}\lambda^{\star}_{k}(\widetilde{\bm{\theta}})$
(61) $\displaystyle<0\;.$ (62)

where we have used Lemma 5 at the third line. This implies

$\widetilde{\theta}_{j}=\underline{\theta}\qquad\text{for any
}j\in\mathcal{C}\;.$ (63)

To see why, assume by contradiction that there exists $j\in\mathcal{C}$ such
that $s_{j}=(1,\widetilde{\theta}_{j})$ with
$\widetilde{\theta}_{j}>\underline{\theta}$. Then for any
$h\in(0,\widetilde{\theta}_{j}-\underline{\theta}]$, by (62):

$\displaystyle
v_{j}((1,\widetilde{\theta}_{j}-h),\mathbf{s}_{-j})=v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{-j})-\int_{\widetilde{\theta}_{j}-h}^{\widetilde{\theta}_{j}}\frac{\partial
v_{j}((1,t),\mathbf{s}_{k})}{\partial
t}dt>v_{j}((1,\widetilde{\theta}_{j}),\mathbf{s}_{k})\;,$

which contradicts $\mathbf{s}$ being a Nash equilibrium.∎

Combining Lemma 5 and Lemma 6 gives for any $(j,k)\in\mathcal{C}^{2}$:

$\theta_{j}=\theta_{k}\;.$ (64)

Recall that by H 3, $\theta_{m}=\theta_{n}$ if and only if $m=n$, so (64)
implies $\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|=1$. This in turn
implies $\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|=1$. Indeed, assume
by contradiction $\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|=1$ and
$\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|\geqslant 2$. Denote
$r\in\mathcal{B}$ the only contributing agent. They are asked
$n^{\star}_{r}(\widetilde{\bm{\theta}})=\overline{n}_{r}(\widetilde{\bm{\theta}})=\underline{n}$.
Moreover by (19)
$\bar{N}=\mathopen{}\mathclose{{}\left|\mathcal{B}}\right|^{1/1+\gamma}(\underline{n}+1)-1>\underline{n}$,
so by definition of the contribution scheme (12), there exists
$k\in\mathcal{B}\setminus\mathopen{}\mathclose{{}\left\\{r}\right\\}$ such
that $n^{\star}_{k}(\widetilde{\bm{\theta}})>0$. This contradicts
$\mathopen{}\mathclose{{}\left|\mathcal{C}}\right|=1$.

We now show that $\mathcal{B}=\mathopen{}\mathclose{{}\left\\{J}\right\\}$. By
contradiction, assume
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j}\right\\}$ with $j<J$. In
particular, $s_{J}=(0,\dagger)$. Consider a deviation
$s^{\prime}_{J}=(1,\widetilde{\theta}_{J})$ with
$\widetilde{\theta}_{J}\in\Theta$, so
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{j,J}\right\\}$ under
$(s^{\prime}_{J},\mathbf{s}_{-J})$. By Lemma 6,
$\widetilde{\theta}_{j}=\widetilde{\theta}_{J}=\underline{\theta}$, so (59)
rewrites:

$v_{k}((1,\widetilde{\theta}_{k}),\mathbf{s}_{-k})=\underline{u}_{k}+2a(\theta_{k}-\vartheta(\mathsf{B},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))\;,$
(65)

for any $k\in\mathopen{}\mathclose{{}\left\\{j,J}\right\\}$. Since
$\theta_{j}<\vartheta(\mathsf{B},\mathbf{n}^{\star}(\widetilde{\bm{\theta}}))<\theta_{J}$
by H 3, we have

$v_{J}((1,\widetilde{\theta}_{J}),\mathbf{s}_{-J})>\underline{u}_{J}=v_{J}((0,\dagger),\mathbf{s}_{-J})\;,$

which contradicts $\mathbf{s}$ begin a Nash equilibrium. Hence,
$\mathcal{B}=\mathopen{}\mathclose{{}\left\\{J}\right\\}$. This concludes the
proof. ∎

See 3

###### Proof.

Let
$(\mathsf{B},\widetilde{\bm{\theta}})\in\mathopen{}\mathclose{{}\left\\{0,1}\right\\}^{J}\times\Theta^{N}$
be an equilibrium of the game induced by $\Gamma^{\textsc{VCG}}$. Since the
VCG mechanism is strategyproof in dominant strategy,
$\widetilde{\bm{\theta}}=\bm{\theta}$. For any
$j\in\mathopen{}\mathclose{{}\left[J}\right]$, the VCG payment is

$\displaystyle t_{j}(\widetilde{\bm{\theta}})$ $\displaystyle=\sum_{k\neq
j}u_{k}((0,{\bf 1}_{-j}),\mathbf{n}^{\star}(\bm{\theta}))-\sum_{k\neq
j}u_{k}({\bf 1},\mathbf{n}^{\star}(\bm{\theta}))$
$\displaystyle=\underbracket{W((0,{\bf
1}_{-j}),\mathbf{n}^{\star}(\bm{\theta}))-W({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))}_{\mathbf{(I)}}-[\underbracket{u_{j}((0,{\bf
1}_{-j}),\mathbf{n}^{\star}(\bm{\theta}))-u_{j}({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))}_{\mathbf{(II)}}]\;.$ (66)

Consider $j\in\\{1,\ldots,L^{\star}\\}$. By the contribution scheme Corollary
1,

$u_{j}({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))=-a(\mathcal{R}^{\star}_{0}+\varepsilon({\bf
1},\mathbf{n}^{\star}(\bm{\theta})))-cn^{\star}_{j}(\bm{\theta})=\underline{u}_{j}=u_{j}((0,{\bf
1}_{-j}),\mathbf{n}^{\star}(\bm{\theta}))\;,$

where we used in the third inequality that
$n^{\star}_{j}(\bm{\theta})=\overline{n}_{j}(\mathsf{B},\mathbf{n}^{\star}(\bm{\theta}))$.
Thus, $\mathbf{(II)}=0$. Moreover by Theorem 1, $W((0,{\bf
1}_{-j}),\mathbf{n}^{\star}(\bm{\theta}))<W({\bf
1},\mathbf{n}^{\star}(\bm{\theta}))$ so $\mathbf{(I)}<0$. Thus, by (66) we
have $t_{j}(\widetilde{\bm{\theta}})<0$. ∎

See 3

###### Proof.

Let $\mathsf{B}^{\star}=(1,\ldots,1)^{\operatorname{T}}$, so the aggregator
has at her disposal $\widehat{\theta}_{1},\ldots,\widehat{\theta}_{J}$.

We first focus on the event under which $\widehat{\theta}_{j}$ correctly
approximates $\theta_{j}$ for any $j\leqslant J$. Define
$\mathsf{E}_{j}(\delta)=\\{\omega\in\Omega:\>|\widehat{\theta}_{j}(\omega)-\theta_{j}|\leqslant\eta_{\delta}\\}$
and $\mathsf{E}(\delta)=\bigcap_{j\leqslant J}\mathsf{E}_{j}(\delta)$. We have

$\mathbb{P}(\mathsf{E}(\delta/J))\geqslant 1-\delta\;,$ (67)

because $\mathbb{P}(\mathsf{E}(\delta))=\mathbb{P}(\cap_{j\leqslant
J}\mathsf{E}_{j}(\delta))=1-\mathbb{P}(\cup_{j\leqslant
J}\mathsf{E}_{j}(\delta))\geqslant 1-\sum_{j\leqslant
J}\mathbb{P}(\mathsf{E}_{j}(\delta))=1-J\delta$, and setting
$\delta^{\prime}=J\delta$ leads to Equation 67. In what follows, we assume
that $E(\delta/J)$ is true so
$|\widehat{\theta}_{j}-\theta_{j}|\leqslant\eta_{\delta/J}(\underline{q})$ for
any $j\in\mathopen{}\mathclose{{}\left[J}\right]$. We denote by
$\mathcal{C}=\\{j\in\mathopen{}\mathclose{{}\left[J}\right]:\>m_{j}(\widehat{\bm{\theta}})=n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})>0\\}$
the set of contributors, and to lighten notations we write

$\displaystyle\vartheta(\widehat{\bm{\theta}})$
$\displaystyle=\bar{N}^{-1}\mathbf{n}^{\star}(\widehat{\bm{\theta}}+\bm{\eta}_{j})^{\operatorname{T}}\widehat{\bm{\theta}}=\bm{\lambda}^{\star}(\widehat{\bm{\theta}}+\bm{\eta}_{j})^{\operatorname{T}}\widehat{\bm{\theta}}$
$\displaystyle\text{and}\quad\widehat{\vartheta}_{j}(\widehat{\bm{\theta}})$
$\displaystyle=\bar{N}^{-1}\mathbf{n}^{\star}(\widehat{\bm{\theta}}+\bm{\eta}_{j})^{\operatorname{T}}(\widehat{\bm{\theta}}+\bm{\eta}_{j})=\bm{\lambda}^{\star}(\widehat{\bm{\theta}}+\bm{\eta}_{j})^{\operatorname{T}}(\widehat{\bm{\theta}}+\bm{\eta}_{j})\;,$
$\displaystyle\text{where}\quad\bm{\eta}_{j}$
$\displaystyle=\eta_{\delta/J}(\underline{q}){\bf
1}-2\bm{\delta}_{j}\eta_{\delta/J}(\underline{q}),\quad\text{with}\quad\bm{\delta}_{j}=(0,\ldots,0,1,0,\ldots,0)\;,$

for any $j\in\mathopen{}\mathclose{{}\left[J}\right]$. Consider first a
contributor $j\in\mathcal{C}$ who is asked
$n^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})>0$ samples. Their payoff
under $\mathsf{B}^{\star}$ is

$\displaystyle\hat{v}_{j}(1,{\bf 1}_{-j})$
$\displaystyle=-a(\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\widehat{\bm{\theta}}),N))-cn^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j})$
$\displaystyle=-a(\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\widehat{\bm{\theta}}),N))-c\mathopen{}\mathclose{{}\left[\underline{n}-\frac{a}{c}\mathopen{}\mathclose{{}\left(\varepsilon(\widehat{\vartheta}_{j}(\widehat{\bm{\theta}}),N)-\varepsilon(\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q}),\underline{n})}\right)}\right]$
$\displaystyle=-a\mathopen{}\mathclose{{}\left(\mathcal{R}^{\star}_{0}+\varepsilon(\theta_{j},\underline{n})}\right)-c\underline{n}$
$\displaystyle+a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\varepsilon(\theta_{j},\underline{n})-\varepsilon(\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q}))}\right)-\mathopen{}\mathclose{{}\left(\varepsilon(\vartheta(\widehat{\bm{\theta}}),N)-\varepsilon(\widehat{\vartheta}_{j}(\widehat{\bm{\theta}}),N)}\right)}\right]$
$\displaystyle=\underline{u}_{j}+2a\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\theta_{j}-(\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q}))}\right)-\mathopen{}\mathclose{{}\left(\vartheta(\widehat{\bm{\theta}})-\widehat{\vartheta}_{j}(\bm{\theta})}\right)}\right]$
$\displaystyle=\hat{v}_{j}(0,{\bf
1}_{-j})+2a(1-\lambda^{\star}_{j}(\widehat{\bm{\theta}}+\bm{\eta}_{j}))(\theta_{j}-(\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q})))$
$\displaystyle-2a\sum_{\ell\in\mathcal{C}\setminus\\{j\\}}\lambda^{\star}_{\ell}(\widehat{\bm{\theta}}+\bm{\eta}_{j})(\theta_{\ell}-(\widehat{\theta}_{\ell}+\eta_{\delta/J}(\underline{q})))$
and since $E(\delta/J)$ is true,
$\theta_{j}\geqslant\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q})$ and
$\theta_{\ell}\leqslant\widehat{\theta}_{\ell}+\eta_{\delta/J}(\underline{q})$
for any $\ell\in\mathcal{C}\setminus\\{j\\}$, so
$\displaystyle\hat{v}_{j}(1,{\bf 1}_{-j})$
$\displaystyle\geqslant\hat{v}_{j}(0,{\bf 1}_{-j})\;.$ (68)

Second, consider $j\notin\mathcal{C}$ who is asked
$\underline{q}\leqslant\underline{n}-2(a/c)(\bar{\theta}-\underline{\theta})$
samples, and denote by $r\in\mathopen{}\mathclose{{}\left[J}\right]$ the agent
such that $\theta_{r}=\max_{k\in\mathcal{C}}\theta_{k}$. Observe that
$\underline{q}\leqslant n^{\star}_{r}(\widehat{\bm{\theta}}+\bm{\eta}_{r})$,
so

$\displaystyle\hat{v}_{j}(1,{\bf 1}_{-j})$
$\displaystyle=-a(\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\widehat{\bm{\theta}}),N))-c\underline{q}$
$\displaystyle\geqslant-a(\mathcal{R}^{\star}_{0}+\varepsilon(\vartheta(\widehat{\bm{\theta}}),N))-cn^{\star}_{r}(\widehat{\bm{\theta}}+\bm{\eta}_{r})$
$\displaystyle\geqslant\underline{u}_{r}\;,$ where the last inequality comes
from $r\in\mathcal{C}$ and (68). Since $j\notin\mathcal{C}$, we have
$\theta_{j}\geqslant\widehat{\theta}_{j}-\eta_{\delta/J}(\underline{q})\geqslant\widehat{\theta}_{r}+\eta_{\delta/J}(\underline{q})\geqslant\theta_{r}$
so $\underline{u}_{r}\geqslant\underline{u}_{j}$, and it follows that
$\displaystyle\hat{v}_{j}(1,{\bf 1}_{-j})$
$\displaystyle\geqslant\underline{u}_{j}=\hat{v}_{j}(0,{\bf 1}_{-j})\;.$

∎

See 2

###### Proof.

Let $j\in\mathopen{}\mathclose{{}\left[J}\right]$ and $g\in\mathscr{G}$, we
have

$\displaystyle\widehat{\theta}^{\textsc{erm}}_{j}$
$\displaystyle=\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{j}(g)-\widehat{\mathcal{R}}_{0}(g)}\right|$
$\displaystyle\leqslant\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{j}(g)-\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)}\right|+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{0}(g)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|$
$\displaystyle\leqslant\alpha_{\delta/4}\mathopen{}\mathclose{{}\left[(q+1)^{-\gamma}+(q^{\prime}+1)^{-\gamma}}\right]+2\beta+\theta_{j}\;,$
(69)

with probability $1-\delta/2$ by H 2, H 1, H 6, and a union bound. Similarly,

$\displaystyle\theta_{j}$
$\displaystyle=\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|$
$\displaystyle\leqslant\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\mathcal{R}_{j}\mathopen{}\mathclose{{}\left(g}\right)-\widehat{\mathcal{R}}_{j}(g)}\right|+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{j}(g)-\widehat{\mathcal{R}}_{0}(g)}\right|+\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{0}(g)-\mathcal{R}_{0}\mathopen{}\mathclose{{}\left(g}\right)}\right|$
$\displaystyle\leqslant\alpha_{\delta/4}\mathopen{}\mathclose{{}\left[(q+1)^{-\gamma}+(q^{\prime}+1)^{-\gamma}}\right]+2\beta+\widehat{\theta}^{\textsc{erm}}_{j}\;,\;$
(71)

with probability $1-\delta/2$. Combining (69) and (71) along with an union
bound yields

$|\widehat{\theta}_{j}^{\textsc{erm}}-\theta_{j}|\leqslant\alpha_{\delta/4}\mathopen{}\mathclose{{}\left[(q+1)^{-\gamma}+(q^{\prime}+1)^{-\gamma}}\right]+2\beta\;,$

with probability $1-\delta$. ∎

See 4

###### Proof.

  1. (i)

Let $j\in\mathcal{B}$. Observe that under H 7,we have

$\widehat{\mathcal{R}}_{j}(-g)=n_{j}^{-1}\sum_{i=1}^{n_{j}}\text{1}\\{-g(X^{j}_{i})Y^{j}_{i}<0\\}=n_{j}^{-1}\sum_{i=1}^{n_{j}}(1-\text{1}\\{g(X^{j}_{i})Y^{j}_{i}<0\\})=1-\widehat{\mathcal{R}}_{j}(g)\;.$

Since the hypothesis class $\mathscr{G}$ is symmetric, we have

$\displaystyle\widehat{\theta}^{\textsc{erm}}_{j}$
$\displaystyle=\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left|\widehat{\mathcal{R}}_{j}(g)-\widehat{\mathcal{R}}_{0}(g)}\right|=\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left(\widehat{\mathcal{R}}_{j}(g)-\widehat{\mathcal{R}}_{0}(g)}\right)$
$\displaystyle=\sup_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left(1-\mathopen{}\mathclose{{}\left(\widehat{\mathcal{R}}_{j}(-g)+\widehat{\mathcal{R}}_{0}(g)}\right)}\right)=1-\inf_{g\in\mathscr{G}}\mathopen{}\mathclose{{}\left(\widehat{\mathcal{R}}_{j^{-}}(g)+\widehat{\mathcal{R}}_{0}(g)}\right)\;.$

  2. (ii)

Let $j\in\mathopen{}\mathclose{{}\left[J}\right]$, we have

$\displaystyle\eta_{\delta/J}(q)$
$\displaystyle=\alpha_{\delta/4J}[(q+1)^{-\gamma}+(1+q^{\prime})^{-\gamma}]+2\beta$
$\displaystyle=\ln(4J/\delta)^{1/2}[(1+q)^{-\gamma}+(1+q^{\prime})^{-\gamma}]+2\mathrm{Rad}(\mathscr{G})\;.$

∎