Unravelling in Collaborative Learning
Authors: Aymeric Capitaine
Etienne Boursier
Antoine Scheid
Eric Moulines
Michael Jordan
El-Mahdi El-Mhamdi
Alain Oliviero Durmus
Venue: NeurIPS 2024 poster (2024)
Keywords: Collaborative learning
unravelling
adverse selection
Primary area: algorithmic_game_theory

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.

Unravelling in Collaborative Learning
Aymeric Capitaine
Etienne Boursier
Antoine Scheid!
Eric Moulines'
Michael I. Jordan'
El-Mahdi El-Mhamdi
Alain Durmus'
Centre de Mathématiques Appliquées - CNRS École polytechnique - Palaiseau, 91120, France INRIA Saclay, Université Paris Saclay, LMO Orsay. 91400, France 3 Inria, Ecole Normale Supérieure, PSL Research University Paris, 75, France
Abstract
Collaborative learning offers a promising avenue for leveraging decentralized data. However. collaboration in groups of strategic learners is not given. In this work, we consider strategic agents who wish to train a model together but have sampling distributions of different quality. The collaboration 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 solely comprised of the worst agent. We show how this issue can addressed without making use of external transfers, by proposing 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 Introduction
Collaborative learning is a framework in which multiple agents share their data and computational resources 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 tempted to withhold or misrepresent the quality of their data gain competitive advantage. These strategic behaviors and their consequences have been studied extensively the literature on information economies [Mas-Colell 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.
vivid illustration of adverse selection is found 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 -aand market, their inclination to pay decreases. As 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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- 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 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 low-quality data owner may harm the model, prompting high-quality owner to leave the collaboration and train 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. 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 do- main adaptation to capture a notion of data quality formally. On the other hand, we model collaboration 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 celffre-maximizaee
collaboration scheme when data quality is public information.
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. We present solutions to unravelling. When transfers suffices to re-establish optimality. When transfers are not possible, we leverage probabilistic verification techniques to design mechanism which breaks unravelling. More precisely, 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 mechanism practically in the setting of classification.
allowed, the VCG mechanism
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 [TTu 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 proper incentive scheme. Huang et al. [2022] show that under-provision of data points in federated learning arises from privacy concerns. Yan al. [2023] consider a federated classification game where agents 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 Ananthakrishman et al. [2023] study hidden actions when principal delegates predictive task to another agent, and show that thresholds linear contracts are able to approximate the optimal contracts.
Adverse selection is another type of information asymmetry, where preferences of agents are un- observed rather than actions. This issue also naturally arises in collaborative learning, because the data distributions from which agents sample about which they care may not be public. While
2

---

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 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 single agent and leave aside the question of participation. Finally, Werner et al. [2024] and Tsoy and Konstantinov [2024] 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 full information benchmark, which allows us derive the 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 game where the grand coalition is pure strategy Nash equilibrium with high probability.
contribution scheme. In Section 4, we
2 Model
Statistical framework. Let (X, X²) and (Y,3)) be two measurable spaces and denote by P a family of probability measures on (X x Y, X' @ y). We consider [J] {I,..... [I,....J} agents who aim to perform a prediction task associated with a hypothesis class C {g: x Y}. loss function é: Y x Y and probability measure Po E P. Each agent seeks to minimize 9 E 9 + Rr, (g) where for any probability distribution P E P, Rg(g) = [(g()), y)d y) is the risk associated to g z with respect to P.
We leverage tools and results from statistical learning theory. Denote by {(X,, Y,),2 the canonical process on X x Y and denote by Pp and Er the canonical probability and expectation under which {(X,, 121 are i.i.d. random variables with distribution P P. With this notation, we can introduce our assumptions on & and P.
H1. For 8 E (0. 1), there exist ass > 0, B 0 and > O such that for any distribution P E P, hypothesis g E and n > 1
1 n - n
Pp RP(g)
(g(()))
06 (1+n)) + +3
> 21
This assumption covers wide range of situations. For instance in the classification case where Y {-1,1} and é (v. + 1 (wv as = (1m(1/))2 3 2RAD(5) and y 1/2 where RAD(S) is the empirical Rademacher complexity of & [Bousquer et al., 2003]. Similarly, the Bayesian PAC approach in the linear regression context with bounded loss leads to as = [) Inn(//)) $ = |1elig/ 8 and y = 1 where and π are any distributions on & [Shalaeva et al., 2019, Corollary 4].
For ease of notation, we let Rg) serve as a shorthand for Rp, (g). It is moreover assumed that agent j E [J] cannot directly sample from Po. but has instead access to a distribution P3 E P which deviates from Po according to the 9 -ddieergence:
H2. For any j E [J), P3 E P has finite 3 --divergence: 03 suP (R - Ro(g) < +00
Intuitively, for any j E [J], 0, > 0 models the bias incurred by having access to samples from P. instead of the target distribution Po. More precisely, the risk excess associated with empirical risk minimization (ERM) based on samples from P, is in the worst case at least 8,. A poor sampling dis- tribution which corresponds to high 82 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 H2 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 natural
3

---

framework to analyze the behavior of models trained on diverse distributions, and is practically appealing since it can be easily estimated the context of classification [Ben-David et al., 2010].
We make the following assumptions on the quality indexes (01....,0) ......,)). hereafter referred to as types.
H3. There exists (0, 0) E I such that 01 < 02 <. ... < 0, < 0.
H3 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 convenience in simplifying the proofs.
Collaborative learning framework. We further suppose that agent j E [J] can fit a model g E y based on i..d. samples {(}] Yi',..... (X2, Y }} of size nj > 0 from P3 E P in of two ways: they can compute their own, or collaborate. This is captured by the two following options:
Option 1) Agent performs ERM on their own samples:
fj argmin gew Rg(9).
(((())) E
(I)
This non-collaborative procedure is referred to as the outside option.
Option 2) Agent j can take part in coalition orchestrated by central data aggregator, encoded as = (Bi.... B,) E {0, 1)" where B, means that agent j is member of the coalition. We also write B = {j E [J]= Bj = 1}. In exchange for their samples, agent gains access to the collaborative model trained over the concatenation of samples:
gB argmin Rg(g),
ny
where (g) = N Σ B, Σ ((o(x)), JE(J]
Y/) and = Σ B
jEM
Agent utilities. We assume that agents incur unitary cost for sampling from their distribution and dislike statistical risk. Therefore, a baseline model for measuring the preferences associated with model g E G and number of samples is based on linear map: (g, + -aRo(g) for a, c > 0. In practice, however, Ro(g) is typically unknown so agents instead can use a PAC bound of the form (())( < R2 + E) > 8 to assess model 9n E y trained over their samples, where E > 0, 5 E (0, 1) and Ri = inf Ru(g). Our next result shows that and H allow each agent pin down such
0, under either Option 1) Option 2). Assuming H1,
define the function e for any (0, n) E θ x RR+ by
E(0, n) = 2 as +
(3)
Lemma 1. Assume HI and H2.
(i) Any agent j E [J] picking the outside Option 1) obtains a model G3 achieving
Ro(o,) & RS + =(0))nn) with probability 1 1- 8
(ii) Any coalition B E (0,1)* 1)' drawing (f1....,71.) ...) RRY, samples obtains model Fe E 3
achieving
Ro(ğB) Rí + () with probability 1-8,
where N is the total of samples and 9 is the weighted average type within the coalition:
N(B, n)
Σ B JE(J]
((B,n) = N Σ
B,n00,
JE[M]
When the context is clear, we write <BB n) = c()(B, (B, n)) to lighten notation. Based on Lemma 1, we define the utility of agent j [J]
Uy : (B, + -a R (1 B,)=(0,,nn)) n,) + (B, n)) enz
(5)

---

Note that for any j E [J], we take n, > 0 to be a real number for ease of presentation. In (5), a/c > 0 captures the extent which individuals are willing to trade off model quality against sampling cost.
For any j E [ and B -- (BI.... Bj B,+1- 1....... B₁) E f0, (0,1)---1 we denote by slight abuse of notation [B, B = (BI..... _ B, Bj+1. B,......... B,) for any B E {0. 1). Similarly for n-j (M1,.... . m2 n., Rit1...... ..)) for any n > 0. We can then characterize the optimal behavior of any agent picking the outside option as follows.
(N1,.... ......... : 1g+1..... (n)) R write n-))
Proposition 1. Assume HI and H2. For any j [J]. B-, (0, (0, and n RR--1 the optimal number of samples to draw under Option 1) is argmax,20 (0, B B-j), (n, n-)); 0j) = n where
n -2ac Slacc--ook (os))/((+1)))
In what follows, we assume 20/c > (yau)) to exclude the pathological case where no agent is willing sample data points. From now on, denote by
M u (O, (n, n-)))
the best achievable utility under the outside option. Note that ni does not depend on 03 E ④ (but ", does) all agents outside of the coalition draw a same number of data points n This result, which may be surprising at first glance, comes from the fact that all agents have the same -ecuracy-to-samplig--oo ratio a/c in their utility.
Aggregator. We finally assume that the aggregator benevolently up Pareto-optimal collaboration, by maximizing the total welfare under individual rationality, In other words, they solve:
maximize : (B, e {0, 10 x R +
Σ JE(J]
uy,
(8)
subject min uj uy n) 3j 0 jE(J]
In the Social Choice literature, W is referred to as the utilitarian social welfare function. The participation constraint ensures that agent within the coalition finds it beneficial to switch to their outside option. Note that n E Ry required to have non-negative entries, which prevents the aggregator from giving away data points agents.
Full-Information Benchmark: First-Best Collaboration
In this section, we assume that the profile of types (f.....,d.) 0,) e e' is public, and study how the aggregator can implement optimal collaboration among agents under this fost-favorable scenario.
Exact solution. We looking for solution the aggregator's problem (8). For any B {0, 1) and n E R., denote by
(B n) max 0: uj (1 [ (n, ;); 0,) n,}
= = (a/c)(e(B,)) 20),
the maximum number of samples that agent can be asked to provide within the coalition under its participation constraint, where is defined as in (6), and my as in (7). With this notation, problem (8)
rewrites
maximize
W(B, n) subject to
min n. (B, n) - 2 0. JEB
(10)
Theorem Assume HI, H2, H3. Problem (8) admits unique solution (Bops, opt (0)) E (0, 1) x RL. Moreover,
(i) Bopt 1 (I,
5

---

(ii) Denoting n nt no)(() (0) = (ni" (0)""((),..))) ............ (()((())) (0)), there exists L E [J] such that for any j E [
71, opt
if < Lopt,
gpt (0)
E 00, 7, n oP (0)))
i = Lopt,
(11)
=
otherwise.
The couple (Bops, nopt) 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 Lopt > 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; (0) slightly differs from 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; on the other hand the agent gets worse model by collaborating (i.e., they are 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 (Bapt, " nt) is difficult because (1, (0)) has no explicit expression. To make the analysis tractable, we slightly simply the optimal contribution scheme in Theorem and consider the simplified optimal contribution scheme (B*,n*) n²) where B Bopt (I...., 1) and for any j [J),
(I. (1. (0) L (jgtt) FI
and L' ='=min e [J]:
Σ (1, > N). (12) k&j
with N= (n 1) -1
Note that (B", n²) only differs from (Bope not in two ways. First, (B*, nn) all contributors' participation constraint bind, while in (Bopt, nott the Lott-the one could be slack. Second, the total number data points required from the coalition fixed and equal to N @(JI+r). The quantity N comes from natural relaxation of the original problem Equation (10) where we leave aside an intricate term of the objective function. This relaxation, which is formally described in Appendix A, provides good approximation of the exact solution in reasonable settings. Indeed, the following result establishes that applying (B*, n²) instead of (Bopt, n ot comes at a negligible welfare cost when types sufficiently evenly spaced.
Lemma 2. Assume H1, H2 and 02 0--1 O(1JJ) for any j J2. Then,
W(B n nPT(() W(B", no".,n (0)) + O(J+t))
Moreover, following proposition shows that n (0) admits a workable expression.
Corollary 1. Assume HI, H2 and H3. Then L' = ((J+t)) and for any j E [J].
N
2a
() 1s
+
02
02
T
T
Since (B*, n") correctly approximates the optimal scheme while being more tractable, we work with in the remainder to lighten proofs.
H4. The aggregator applies the simplified contribution scheme (B*,n").
Hidden information
The welfare-maximizing contribution scheme described in (12) depends explicitly on 0 E O 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 collaboration when types private.

---

4.1 Naive aggregation and unravelling
naive solution to coping with the private nature of 0 O' is for the aggregator to ask agents to disclose their types, and apply the simplified optimal contribution scheme defined in (12). In this setting, however, agents may declare type 8, different from their true type 0g.
This approach corresponds direct-revelation mechanism r follows.
(B, 0) ~ n (0) which unfolds as
1. Any agent j E [J] declares tuple (,, E {0.1) e (t). Bf 1, then agent picks Option 2), and enters the coalition with type 0,. If B; = 0, then agent j picks Option
1), their declared type 03 is f by convention.
2. Setting B = (Bi.... B,) and 0 E (@u(t))' then the aggregator applies the contribution scheme defined in (12), so the vector of number of contributions within the coalition is n' (0)
I' induces direct revelation game ([J), 9P,, (1y))E(sn where the action space y 0(1,0) :0
θ U {(0, t)} and payoffs are for any j E [J] and s yrd
(0) By -a R3 + =(B. n' (())(()))))))))))) - cn) + + +1--B))u,
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 HI, H2, H3, and H4. Let & C CSP be the set of pure-strategy Nash equilibria of the game induced by r. We have
(i) & +
(ii) any s* E E (0, (0,....0) B (0, (0....,0.) 0,1).
Theorem 2 shows that under r, the coalition undergoes a full unravelling: is either empty or comprised solely of the worst agent in any Nash equilibrium. Thus, collaborative learning is not immune to adverse selection, and may suffer from unravelling as any market characterized by information asymmetry.
.,, (0, f)) corresponding to B = (0.... 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 s E & such that B * (0...., O).
Sketch of proof. The profile of actions ((0, f)....
Denote by C (j [J]: B, and nz nz(0) 0} the set of contributors under this equilibrium. It can be shown that (i) for any (j. C², 0, i 0g 0g, and (ii) For any j E C, (1, with 0, @ is strictly dominated by (1, so 0, 0 at the equilibrium. As a consequence, 0, = 0g for any kj C², which implies by H3 that [C] = 1. From the definition of the contribution
scheme (12), we can deduce that Σjen B₁ = [ = 1, because [B] > would entail [C] > 1. Finally, B5 1 because e,((1, (1,11)) > (0, t), s.)) and is a Nash equilibrium. This leads to B = 00, 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 because agents do not find beneficial to declare their true type and eventually opt for their outside option. This could be avoided by modifying I' to make it
individually rational, that is vy (,) (.))),s)))) (,((0.)) for any j [J..s s_, E J-1
ii and incentive compatible, that is ((, 0,), s-,) v,((1, s_,) for any 0, θ.
7

---

Under these conditions, the truthful, optimal profile of actions ((1, .1)..... (1, would emerge as 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 Ivce + (n (0), t(0)) where t t(Ø) = R is a set of transfers satisfying for any j E [J]:
E
&g 20)
Σ ((,, 1-)).,n())))
Σ 2x 2x,1n,n kØj
k
It re-establishes truthfulness as a dominant strategy by aligning individual payoff's ey (0) Ug 4g(1, n" (0)) (0) with total social welfare. Unfortunately, the VCG approach is unavailable in our framework, because of the following observation.
Lemma 3. There exists
[J] such that t, (0) >0
Lemma shows that some agent would need 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 al., 2022]-, which we exclude here.
A probabilistic verification-basee 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 9j with few samples from P3 for any E [J]:
HS. There exists decreasing function 116 IR + Ri, with (0,1) defined in HI, such that for any j E [J] and i.i.d samples (X1, YY),. (Xy, Y?) of size > 0 from Pj. there exists a (X), YP),..................... Yi ) estimator 82 satisfying
P(O0- 0,1 < n1)4)) 8
In Section 4.2, we show how the aggregator can design such estimators. H5 allows us to consider a new mechanism π: + m(B) as follows:
1. any agent j E [J] declares By E {0,1). If B, 1. the principal asks for g < n ((a/c) 8) i.i.d samples from P3 and estimates types as θ = (0,) following H5.
2. Based on the estimated types @ (0,) (0,), the aggregator asks for [n] (0 + n,) q ]+
additional samples from Pj. where n²(.) is defined as in (12) and
n Tay ( 26,ns/ with ò5 = (0, ................................ 0,
0)T
Thus, the number of draws required from agent j is max (g. nn( n;)]]
3. The aggregator keeps my ( = 1 + ny) > 0} max(g. n (0 + ny)] samples from agent j, and trains a collaborative model with these pooled samples.
induces game ([J), (0. 1) (ūg) where any agent j E [J] has a payoff function
و3 : (B,, B-,) + B3 -a R3 + eBB =BB,m(0)) m())) cmaallg, nō m + (1 B,)u,
The rationale behind this mechanism is fairly intuitive: since ① is correct estimate of 0, nz (0+m) +n;) Rd
n; (0) correctly approximates the optimal contribution n² (0) for any contributor E B. Note that type estimates are purposely biased by when asking for samples. This is safeguard against over-estimated types, which would lead to asking to many data points and could deter agents from participating in the coalition.
Critically, m0) does not depend on declared type, so agents are no longer able to strategically manipulate the mechanism. Moreover, I does not require agents to know their own types, which would an unrealistic assumption. Finally, observe that the number of data points asked to estimate types g is low enough to never deter agents from participating in the coalition.
8

---

Theorem 3. Assume HI, H2, H3, H4 and H5. == ="==1, (I....,1) 1)" is Nash equilibrium under I with probability 5.
Theorem shows that the optimal coalition sustainable equilibrium under f', which effectively breaks unravelling: the set of (approximate) Nash equilibria is 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 f in a collaborative learning setting. This requires defining a collection of estimators (0z); satisfying H5. To this end, we assume that few samples from the target distribution are available.
H6. There are o' i.dd samples {(XP, ..... (Xg. yg) from Po available the aggregator and agents.
= Under H6, define Ro(g)= E (()(X)), YP) for g E g. This allows to devise suitable estimators 0g as follows.
Proposition Assume HI, H2 and H6. For any j E [J] the estimator
R2(g) Ro(g)),
sup
gE
satisfies H5 with
no(9) = [ +1 11 23.
(13)
Proposition 2 shows that the empirical version of the 3 -ddivergence defined in H2 correctly estimate types. Note that the tighter the PAC bound in H1, the better the approximation term in (13). The type estimator ØERM defined in H5 can easily be computed in the classification case, shown with the following example.
H7 (Classification setting). y = (-1, symmetric (g E 3 if and only if g E I) class of classifiers.
f,,1 : (w.2)) E y x + [vv and 3 is
Example 4. Assume HI, H2, H6 and H7.
(i) Denoting R2 (g) =n En lo.1 (9(x)), -Y?), have
PaRm = - inf (Ro(s) + R
958
(ii) In HI, assume as = ln(1/0) 3 2RAD(9) and 7 [Bousquet et al., 2003). With 053 defined in Proposition 2, we have
(g) ln(41/6))/2
(1 91) (9)
Example 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 Po. and perform empirical risk minimization to compute Bj... The approximation error grows no more than logarithmically with the number of agents, while decreasing at rate 7 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 collaborative model. More precisely, under 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 transfer-fre free mechanism based estimation of types. This effectively counteracts unravelling by letting the grand coalition ranks among the approximate Nash equilibria with high probability.
Several possible extensions can be considered. First, it would be interesting to relax the assumption that all agents have the same ratio a/c / in their utility, and see how heterogeneity affects the results.

---

Second, the mechanism presented in Section 4 aims for individual rationality. A more desirable, yet difficult achieve, property would be core stability, 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 collahoration not only emerges as 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 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 held responsible for them.
References
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: rwpec. org/ a/ oup/qj maeeeeoo//vvyy/ eccon/884197013344B8
50m...tml.
Nivasini Ananthakrishnan, Stephen Bates, Michael Jordan, and Nika Haghtalab. Delegating data collection in decentralized machine learning, 2023.
lan Ball and Deniz Kattwinkel. Probabilistic verification mechanism design. September 2019.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan. theory of learning from different domains. Machine Learning, 79:151-175, 2010. doi:
Avrim Blum, Nika Haghtalab, Ariel Procaccia, and Mingda Qiao. Collaborative PAC learning. In Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems. Curran Associates, 2017.
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for Equilibria and optimality of collaboration in federated learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1005-1014. PMLR, 18 18-24 Jul 2021. URL fttts::/pproeediie
all for all:
mlr prwsspresssseee htt////1////lll/ html.
Olivier Bousquet, Stéphane Boucheron, Gábor Lugosi, Ulrike Luxburg, and Gunnar Rätsch, Intro- duction to statistical learning theory. Advanced Lectures on Machine Learning, 169-207 (2004), 01 2003. doi: 10. 01177797883-40-2667777
Joannis Caragiannis, Edith Elkind, Mario Szegedy, and Lan Yu. Mechanism design: From partial probabilistic verification. Proceedings of the ACM Conference on Electronic Commerce, 06 2012. doi: 10. 00.1145/222911.222955.
Edward Clarke. Multipart pricing of public goods. Public Choice 11(1):17-33, Septem- ber 1971. doi: 10. 10.00//FF0172210. URL https://idest wwwiiidassreeee...eeee repec.
711y1971i1p17 1--7-31333333 33. html.
Kate Donahue and Jon Kleinberg. Optimality and stability in federated learning: A game-theoretic approach, 06 2021a.
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 b.21b. doi: 10. 11609/aai.vv3555 16669.
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: //tpiiapaaaaa h swwanticschol.at... wrw. : 258887502.
10

---

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.11. URL
https: / //www//wwww///// aeaweb. orggartiicessiieeeee......... jep7/jep 25 1.115.
Diodato Ferraioli and Carmine Ventre. Probabilistic verification for obviously strategyproof mecha- nisms, 2018.
Lei Fu, Huanle Zhang, Ge Gao, Mi Zhang, and Xin Liu. Client selection federated learning: Principles, challenges, and opportunities, 2023.
Dashan Gao, Xin Yao, and Qiang Yang. A survey heterogeneous federated learning. arXiv preprint arXiv:2210.04505. 2022.
Jerry Green and Jean-Jacques Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 4502):27-33 1977. URL URL.httts://Ecoaaaprss
repec. org/ Drg/RePEc: ecm:
Theodore Groves. Incentives in teams. Econometrica, 41:617-631, 1973. URL https://api.
semanticscholar. .rg. wwrg/CorpusID-... 264740987.
Nathaniel Hendren. Private Information and Insurance Rejections. Econometrica, 81(5):1713- 1762, September 2013. doi: ECTA10931. URL https://ideas. repec org/a//cn/ eeetrp/
181y2011166p1713-1722. html.
Bengt Holmstrom. Groves' scheme on restricted domains. Econometrica, 1T 1377441144 19799 URL httts://EconPaperes repec. org/RePEc: ecm: emstrp::::47.y 1o
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/
pttp/pppee//////55 httppp..rr/////rpppprrr..ee 05w.0.559222. html.
Chao Huang, Shuqi Ke, Charles Kamhoua, Prasant Mohapatra, and Xin Liu. Incentivizing data contribution in cross-silo federated learning, 2022.
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 Konevený, 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 Tramer, 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.
Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I. Jordan. Mechanisms that incentivize data sharing in federated learning, 2022.
Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. pages 180-191, 04 2004.
Nikola Konstantinov and Christoph Lampert. Robust learning from untrusted sources, 2019.
Jean-Jacques Laffont and David Martimort, The Theory of Incentives: The Principal-Agem Model. Princeton University Press, Princeton, NJ, USA, 2001.
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, 1.542-56,, 2023. doi: 10.1 009/TSIPN.223333361100
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. Number 9780195102680 OUP Catalogue. Oxford University Press, 1995. ISBN ARRAY(0x)160000)) URL https: :ttes:///ddee /i//aad..... dadeas..epeee. repec. org/b/ oxp/ http://ooook///////ooo /38011//77000991000688 htmll.

---

Michael Rothschild and Joseph Stiglitz. Equilibrium in competitive insurance markets: An essay on the economics of imperfect information. The Quarterly Journal of Economies, 90(4):629- 649, 1976. URL atttps:/Ecconappess repec. org/RePEc oup 4:p:629-649.
Eden Saig, Inbal Talgam-Cohen, and Nir Rosenfeld. Delegated classification, 2023.
Vera Shalaeva, Alireza Fakhrizadeh Esfahani, Pascal Germain, and Mihály Petreczky. Improved pac-bayesian bounds for linear regression. In AAAI Conference Artificial Intelligence, 2019. htatpp///app..smmttiiccciiieeeee
URL aattps://app www.sseeaaaanooo........ watpriaarrrrr/opppuiieee mwgg/orrpusID:20885777 208857400.
Nikita Tsoy and Nikola Konstantinov. Strategic data sharing between competitors. Advances in Neural Information Processing Systems, 36, 2024.
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, 83)):1666-1593, 2022. doi: 10.1109/ T02.3.20.....7722...
William Vickrey, Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16 (1):8-37, 1961. URL http:: https://///coo repec. org/RePEc: bla: (tllaaiffiaann:::::y:::.. 1:1:p:8-37.
Zhepei Wei, Chuanhao Li, Tianze Ren, Haifeng Xu, and Hongning Wang. Incentivized truthful communication for federated bandits, 2024.
Mariel Werner, Sai Pranceth Karimireddy, and Michael I. Jordan. Defection-free collaboration between competitors a learning system, 2024. URL htttps://aarttti wwwgobgg////eeeooooo/oooooeeeeet hwtg/abs/240066 15898.
Yizhou Yan, Xinyu Tang. Chao Huang, and Ming Tang. Price of stability in quality- federated learning. In GLOBECOM 2023 2023 IEEE Global Communications Conference, pages 734-739, 2023. doi: 10.1099GGLOBBECM54440222222222 104477777
A Relaxation of the optimal aggregation problem.
Let B E 1), and the associated coalition B = [J]: B₁ 1} be fixed. We present in this appendix a natural relaxation of problem Equation (10) which motivates the choice ΣjeB (0)
Ñ = (n + 1) B) के. - in the simplified contribution scheme (B*, n²). The optimal aggregation problem with fixed
maxjes nj (B, n) < 0
maximize n NER'H
Σ (B.
subject to
max n2 0
JE[J]
Since agents outside of the coalition maximize their utility, the problem equivalently be stated as
(TB)
maximize
IR
Σ (B n) + CB subject to EB
where
maxjeB(n, n, B, (B. < } and SB = Σ Uj
EB =
(14)
maxjeB n, <
j
We start by rewriting (TB) in more convenient way. Instead of working with n E R8 directly, we make appear (i) the total number of samples and (ii) the sharing out of samples between agents. Formally, for any n E 18] consider N n B and A = N- E A where A is the simplex of dimension B3. Observe that the average type in the coalition reads ((B n) A Moreover,
12

---

the welfare evaluated in (B, rewrites
Σ jC(J]
Ug (B, n)
Σ
B + + (((.AN) -n,] + Σ (1 B2)u,
jE[J]
jE[
-a|BB(R + = (B)) - cN LB.
NN Ro] + N xT cN + <B
W)
We denote by Eg (AA,N) A x R+ XN Eg} and To the problem:
(TB): minimize (A, E 1 -
subject to (A,N) E Eg. (15)
By definition, if NA is solution to TB. then n AN is solution to TB. We can further decompose TB by observing that
-)(A = +(N)+ 9
with
S(N) a (R 20x + N 7 + 28) + cN + (B and g(A) 2a|B|A"O.
Finally, denote slice of Eg along N > 0 as EB(N) ( A (a, E and
N = [N > 0: (N) + 0}. TA comes down to
min {f(N) [(A)} (A.N)E
(f(N) + min .(\)) NEN
min
(16)
X
strategy solve Equation (16) is (i) address the innermost problem min (N)) g(A) with N N fixed, and denoting (NN [NV its solution, (ii) solve the outermost problem:
min (SN)) + g(\(N)) NEN
(17)
Point (i) is done in the proof of Theorem However, the resulting problem in (ii) is hard tackle because X has simple form. Therefore, leave aside the term ((((N)) (which can be easily controlled, as shown in Lemma 2) to determine and only consider the problem
min S(N). N30
(18)
Since f is differentiable and strictly convex, its minimizer's uniquely defined by J'(N) = 0, which gives
N (n + 1
(19)
where is defined in Proposition 1. As the solution of the relaxed problem (18), take Ejeps (0) = N the simplified contribution scheme (B*, n²). In many reasonable settings, this approximation is very satisfactory as shown by Lemma
B Proofs
Lemma 1. Assume Hl and H2.
(i) Any agent j E [J] picking the outside Option 1) obtains a model 93 E 9 achieving
Ro(ū,) < RS + =00),n)) with probubility 1 1-1 8
(ii) Any coalition B E {0, 13 drawing (n.....,, .n.) ) RR,, samples obtains a model Ge E 9 achieving
Ro(āa) < Rī + E) with probubility 8
where is the total of samples and 9 is the weighted average type within the coalition:
N(B,n) = Σ Byng.
O(B, = N-1 Σ
Byn00,
(4)
jE[
13

---

Proof. (i) Let vi)........ (Xhy, Y knz)) be ny > 0 i.id samples from Pj E P and ã = inf (g). First, observe that
Rolo,) & (gj) + sup Ro(g) - 'Eの
(20)
Let 0 and oj E 9 such that R, & e9 R,(g) + v. Then with probability at least 1 8,
R2 = R, - R, (0j) + R, (0))
< (0)) R, (7)) + R, (T,) RR + (0))
< 2 sup Rg( - (g) + inf Rg(g) +
gEt/
gE
a6
<
+
3
inf gE
Rg)
(21)
(n + 1)7
where the last inequality holds taking the limit + 0 and using H 1. Finally, observing that inf (g) Rg = inf Rg(9) - infgew Ro(g) < sup sup (g) Ro(g)] = 8,, and
combining (20) well as (21) yields
Ro(ā,) < RT + 20, +
+ 11++17 +3) - + + =0),,n)
as
(22)
with probability at least 1 - 8.
B. (ii) Let B {0, 13" and n (n (m.....,yy n2y R. For any j B, let ((X].Xi).. (XL,, Y2,) } be a collection of nj > 0 i.i.d samples from P3 E P. Denote by = E Byn, and consider A = (AI...., AJ) such that λ = Byn;/N, /N. Note that A belongs to the J-dimensional simplex. For any g 9. the empirical risk over contributions is
RB(g)
1 N
Σ B3 Σ
(o(X)),))) E B))
(23)
JC(J]
JE(M
and the population risk is
Re(g) = R = Σ BJA, (R = Σ By)
(24)
JEM
jEM
One the one hand, the collaborative model ØB E 3 satisfies:
(0B)) < RB (TB) + sup|Ro(0) RB(o)) < RB(TB) sup 9E
Σ Xy)R((9) Ro(o)l
g
jEIJ
< Rg( + Σ
X sup R - Ro(o)1 yE0
_E(J]
=B((BB) + ((B n).
(25)
with n) N-1 N-1EEEiJ B,n,0, = E)Ee ByAyBy. Now, let 0 and g" 3 such that Re(g") < inf ges RB(g) + v. We also have
Re(āB) Rg(ōB) RB(g") RB(g")
< (Re(O") RB(08)) RB RB(g") + RB(9")
< 2 sup Ra(g) - RB(l)
inf Ra(g) + gEt
get
2
068
+ 88)
+ inf Rs(g) get
with probability at least 1 - 8
(26)
(N 1)7
14

---

where the first inequality comes from Rg( inf RB(g) < Re(g"), and the
last is obtained by taking + and applying assumption H Now, observe that infgest Rg(
Rs = infger Rg(g) inf Ro(g) &
sue (R((g) Ro(g) $
Σ B5 suPe (R)()) Ro(g)l @(B, n). Combining this observation with Equation (25)
and Equation (26) gives with probability 1 5
Ro(TB) < R +2
(N 1)7 +3 + +0( - R3 + (()((B
as
(27)
Proposition 1. Assume HI and H2. For any j [J], B-y (0,1)/-1 and n-j R the
optimal number of samples to draw under Option 1) is argmax u,((0, B-5), (n, n-):: :))))))))))) where
02) = n
n (2ac 1 ((os))((+11)..
Proof. For any E [J] and 0, Lemma gives that
-uy ((,, (O,) (n, n,)), a [[ + 2(as(n
+n f(n)
Since f is strictly convex and differentiable, it admits unique maximizer nt 0 determined by
[n) = 0. Simple algebra leads to (2syc //+11=++--- 1
Theorem Assume HI, H2, H3. Problem (8) admits a unique solution (Bops, (0)) E (0,1)*
RC Moreover,
(i) Bopt 11 (1,...11))
(ii) Denoting nt (PPt()) = (n, (nip)(())
opt (P)(())))))) there exists T,opt E [J] such that for any j E [J).
,1, [1, (P)
ifj < Pt
n np (0)
E [0, (1 opt (0))
if = L otherwise.
(11)
Proof. Recall that the optimal aggregation problem reads
maximize WBB, n) E {0, x RR - Σ
(B,
(28)
j
subject
min (B n) U > 0. SE(j]
Define for any J [J], B-j E 1)-1 and n-j - the maximum number of samples agent j E [J] having By = may be asked given their participation constraint:
(B, n) = maxin 0: (,, B-j); (n, n-;)) > 2
Given Equation (5) and Proposition we obtain
TB, n) n ac (E(B, =(0,, n))
(29)
where N = Ejen Byng TB.. Problem (28) rewrites in canonical form
maxxes n (B, < max -ni < 0,
minimize WBB, n)
subject
(30)
where B = [J B, = 1}. We first show that it admits a unique minimum.
Fix a B E 10, and consider problem (30) with respect to n E R only. We call this subproblem TB. First, we show that is enough to focus on (ny),es rather than (nz))e(J) in Tg. With ng (nz)jeB and ng- (nz) note that W(B, n) is decomposable in ng and ng:::
W(B, n) W(B, ns) + W(B, ng=)
15

---

where, by slight abuse of notation W(B, ng) = (BB, and W(B, ng.)
EjEB (B, n). With
maxjeB - (B, <0 }
EB ng E R
maxjeB -Ij $ {
(31)
problem TB is equivalent to min (B) + min B
(B, ng.) = min W(B, ng) + --(1-B) (32) 1-18
ER 1181
nge
JE(J]
by Proposition Since ΣjE(J -(1 - By )r, is constant, by Equation (32) it is enough to focus on
the existence of minnnge - W (B, ng). On the one hand, Eg is bounded. Indeed for any j E B, by Equation (29) and Lemma 1
(B, ng) =
[=(BB ng - -E(0). n)]
Rg + 2
06
3 (B, - Rg 2 (1 n B - 03)
(1 + B)7
2a
0s ((1 + B) 7 (1 (1+ + (0(B, -00]
=
2a
<
ais (1 (1 + +) max 0j
jEB
= M
(33)
Thus, EB M]|M |8| Moreover, Eg is closed and convex. For any B, rewrite
2a
as (11 n 7 (1 21) ((n) "n50 -0;]
(B, ng) -
c
9j (s))
and define hg ag + ng 9j (ns). Observe that Eg {ng E R!al Vj B, nB,j > o and (ng) & 0}. that is Eg = A n B with A = 1 and B = h ((-oo, 0)) 0 n h ( (-000 0]). For any j B, h, ((- 0J) is convex, because is hy. Additionally, h, ((-o0, 0)) is closed as the inverse image of closed set by a continuous function. It follows that Eg is convex and closed as the intersection of convex and closed sets.
As consequence EB is compact and convex, and - WB, is strictly convex so Ta admits unique minimizer ng Eg.
Since there finitely many B E (0,1)' min ( nB, 2rT) + ExEB= By B E (0, exists and coincide with the minimum of problem (30). We show later the proof that the optimal Bopt {0, 17 is unique (see part 1), so the minimizer of Equation (30) unique. This establishes the point (i) of the result.
The remainder of the proof proceeds as follows: we first characterize the optimal Bopt E {0, 13 and then prove that the solution go R.|a of Tgoot has the form presented in point (ii) of the result.
Part 1: Optimal B E (0)
We show that Bopt (I,...,1)) 1)T By contradiction, assume there exists B' * (I,...,1) 1)T and n' E Ry such that for any (B, n) E {0, 13" x R
-W(B', n') -B,
(34)
Denote by j [J] agent such that By 0, and first assume 02 > 0B'', n'). Consider the alternative allocation (B". n²) ((1, B' ), (0, n' n)) Observe that B/ = B" 0, so
N' = BT 'n' B" nnn N and ((B', n') = 0("", nn")
(35)
16

---

This in particular implies
s(B', n') -
=2(as(1 + ++ 0B", N²)] = = nn".
(36)
Thus by (36)
- uy n') u [(, a(R + =(f).
> a + =BB' ( c n n")) = uB
(R
(37)
where the second inequality results from 8 > (BB' and N' > n. Finally by definition of (B", ,n",",, (35) and (36), for any * such that BE =
(B", n²) a [R (1 +3+ 0 nn))
+
en
= a [Ri + 2 (ass(1 - + D n')]] + cnly = -ux' (38)
Hence, (38) together with (37) give
(B(B", n²) Σ (x", n²) uy(B", n²
Σ u:(B', (0B',nn)uu("" uusB",
kzj
kØj
uB n') u, n') = WW n')
kØj
(39)
This contradicts (34). Now assume 0j < (('', n'), and let R E [J] be such that I = max e
BJ. Consider (B", nn) E 10, Rd where
B" [B|, ... B 1 B and n " = (n,,..., n/ "ig....,ngn-- n, ++1- ................................ nta max(0, n'a - , (.)))....,.,) ,'y)T
BJ)
which is feasible. Observe on the one hand that
ny No (0, 0R) < 0(B' n'),
N" N' and A("", n²) E
because 8, ((B n') E RR. particular
e(B", n²) R2 + (No" + + 0B" n")]
RØ + (N + (B', n')] = =(BB,
(40)
(40) in turn implies that for any + such that B²=
-4 (B", ) = RRR + eB", n )} + en < alR + e(B', n')] + cnky = ud' n').
(41)
because ni. = n² for A E B (i. R) and n² < n'z. On the other hand, we have
(B", n" 41 = (B, n')
(42)
by definition (29) of (B", n²). (41) and (42) together yield
WB",, n²) = (B". n²) uy ,B",n") = ua(B", n²) =B,BB,nn)) n')
(B I')',,')= uu;('' n') WWBB, n'),
which once again violates (34). Thus, we obtain Bopt (l,...,1)) 1)T that is Bopt = [J].
Part 2: Characterization of n.f opt E TR/
We now focus on the problem Tgert To lighten notations, we write ntt R instead of ngeet and B instead of Bopt (I,...,1) 1). We first reformulate TB in more convenient way. Recall that Ts reads
opt
(Te) minimize
(B, n) subject to n EB
(43)
17

---

where Eg is defined in (31). As explained in Appendix A, this problem can equivalently be stated as
(TB)
minimize
-W)(A,N)
subject to E
(44)
where
-WB(A, = f(N) g(2),
with
S(N) (R(j 21s + +N) + cN and g()) 2a.
and
EB ((A,N) A R++ AN EB}
Writing EB(N) = ( A (A E Es} for N > and N = {N > 0: SB(NN + 03. 7
comes down
min (A.
(1(N) +())
(s(N++ min ((\)} NEN
min
(N)
In this proof, we address the innermost problem, which is enough to show that n satisfies the point (ii) of the result. Let N > 0 such that Eg(N) / 0, which exists because Eg & 0 (for instance, ((1, (L..,...., 0), (n. O, 0)) E EB). By definition of Eg, reads
EjEB: X 0
(T()):
minimize A AEAs 2 subject to
VjE B: A (B,
Ejes A =1,
(45)
The following lemma provides necessary condition for any solution to problem (45).
Lemma 4. Let ((N) = (M( (M) ..... 1 E As be a solution to (45). If there exists E [J] such that N O, then X/ N ( (B.N N A (M) for any <.
(B, n)) T for any E R. The Lagrangian associated to problem (45), with μe, and v the associated dual variables, reads:
Proof. We denote by n(B, n) (Tr1 (B, n).
((A.H.P.V) 2a X T 0 μ T r(1 1 x²1) + -==I-AA-(BB,..
= -a.JA + cN 11 T + v(1 1
2a + n1 ass ((N 1) - (m+1) ((AT0)1-0)
Since the objective and the constraints convex, L admits saddle point (X(M), ,,, p, v)
E
x R x R x R which is solution to problem (45) and verifies the following KKT conditions:
Vk < J 2aJ0, 14 + PN(N N + 2ac 00x) =
(46)
Vk < J: pk px (N) = 0. μk 3 0
(47)
Vk < J: ph (xN) - 11--,,C7 (B, (B,ALN))) =0, Ph > 0
(48)
A =
(49)
KEB
Assume there exists E B such that X (N) > 0. By complementary slackness (47), 0, and (46) gives for any k < r:
2aJ0; - us + (N + 2ac 2aJJ,, + pr(N + 2ac (0,)
(50)
That is
2a. 0x) + Ms
N N 20c-18. 10
Ps
+ Pr
N 2ac 10p
N + 2ac 10p
By assumption 0, > Ou. and since for agent k that X N = n(BB (N))).
> as well as pr > 0, we have Pk: > 0. It follows from (48)
18

---

Now, define
M₁ = Σ (B, N) and L= min(j E B: Mj 2 N).
(51)
kāj
We show that
2 To prove the first point, assume by contradiction that there exists l < L such that x TB NN By the contrapositive of Lemma 4, A .... Aj 0. Thus
(N) Th (B, NA(M)) for any t < L and x = 0 for any k > L.
(52)
Ex
(B A A M&N <
KEJ
by definition of Equation (51) and l < L. This violates the third constraint of problem (45). For the second point, assume there exists > L such that X (N) (B, N) for any k < L <. 4, so
> 0. By Lemma 4, 2 (N)
(N)
(N)
1 (N)
= Σ (B, ( + (M)
A
A L
KEL
M,, X/
(N)
> 1 X > 1
(N)
which once again violates the constraints of the problem. Finally by (52),
(N)
1-1
(N) = Mr MI-IN
(53)
KLL
K>L
by (52). By (52) and (53) we obtain for any j E [J]:
x N (B, ( | (جزر) ()) + +1
M (j=t))
(54)
Now, consider the solution n (0) E Rd to the initial problem (45), and define
Nopt
Σ Eje n opt (0)
(0) = Nopt op (0)
T,
= min(j [J] Ens (B (P))))(())) > Nopt).
(P) satisfies (54), and multiplying by Nops yields for any j [J]:
opt (0) n
nī (B, opt (0)) + (Nopt Σ
nj o (0))
(55)
which establishes point (ii), and concludes the proof.
Corollary 1. Assume HI, H2 and H3. Then L = -(Jitt)) ) and for any E [J],
N
2a
L
nz(0) 1 (SLL*}
T +
0j
0r
T
Proof. By definition of the simplified scheme (12), n0 = 11
= 1
(2nn))(((1,nn(00)) =((0, n2)] for any j < L* Since ΣØE[J] (z) N, we get
N L' L'e((,n"(()))
Σ 2(0
JEL
2a [as (1 + Ny (1 + n) 7) + (U(1, - 81-11
I* n
19

---

By Lemma and denoting 82. L Σ JEL Bg. This yields
((),n((0) = 1,. ass((1 + (o(((+NN)- 7 11077-11+101 + (c/2oonn
Plugging back this value in (0)) (0(1,n"(0)) 0,)] gives for any j [J]:
n -20/c)oc(11 (1++))) -)
N 2a (02. - 01)
0) = (EE))
(56)
L'
We now determine the order of magnitude of L* E {I,...,d)
J}. Recall on the one hand that by
(33), there exists M > 0 such that 0 & (0) & M for any j E [J]. and on the other hand that
01- 8, < 0 - 0 diam( (9) Therefore by (56),
N &
N < M + diam( so
diam(
= 0(1)
(57)
L
L-
Since N (n + 1)]B*1 155 1 and B
[J], (57) results in L O 1t7).
any Lemma 2. Assume HI, H2 and 8, - -8 O(1JJ) for any j J.. Then,
W(B n (0)) W(B", nnn((n)) + 0(J
Proof. Recall that for any admissible E EB, we can define N = 1sn and A = N n so that the social cost rewrites
-W(B,n) n) -WW N) f(N) +(())
with
S(N) = (Ro + 20s(1 + ?) + cN and ( T
By definition,
Ejeny (0) = -N where N = (n + 1) -1 argmin Nzo f(N). Hence,
W(Bopt n opt (0) WBB", n²))) WB(APPE NoPe) WB(A",
f(V) + 9(X") f(NoPt) - g( Aot)
< 9(\") - -(( = 2aJ(A* - APPt) To.
Since 03 & Or, for any j E [J] such that X3 > 0, and 02 > 0, for any E [J] such that 1UPt >
W(Bopt n opt (0)) W(B* (0)) < 2a. (0,. 01)
By assumption, for any j E (2..... J} 0j 03-1 = O(1/J) so there exists kj > 0 and Ry 2 0 such that 62 - 0- & kyJ for J > Ry. Denoting R max Ry and & = maxje(J] by, for any J > R we have O2- 01 kL*,
kL* 2akL*
WBott o w(B',n'(0)) < 2a.J
J
so W (Bott n ppt (0)) (B (0) O(L)) = OJ by Corollary 1.
Theorem 2 (Unravelling). Assume HI, H2, H3, and H4. Let & C I be the set of pure-strategy Nash equilibria of the game induced by T. We have
ii) 6 + 9
(it) any s* 6, B (O....,0)) 0) B 0,
20

---

Proof. First, we show that the situation where the coalition is empty is Nash equilibrium. Consider
((0, (o..t)........... (0, ()) E gr. For any j [J] and deviation (1,0 B { so ØB 3 and
")((0,)),s-))== - m 2 ((((1,))), by Proposition Thus, 8* E 8.
Now, consider a pure-strategy Nash equilibrium s* E & such that = (j E [ B, 1 + 0. Denote by C = { E B: nz (0) > 0} the set of contributors. We start with two technical lemmas:
Lemma 5. There exists A E R such that for any (j. k) E C²
0j - 0, - 02 02 A.
Proof. To lighten notation, we write in this proof
(0) N Σ
In)(0) 03 and (0)) N Σ (0)
where
N = Σ (0)
JEC
jEC
REC
By Equation (12) and H4, for any j E C, nz my (B)) = = =(E(0()), NN E(0,, n2), so their payoff reads
(1,,0)) = - a(Ri + = - - a c (<(((()). .N) - ( e(f):.))]
-a(R + e(0g. - c2
=a[(s(0))2) 12) - =00 1)) - -(((0()), N) - c ((()), N7)]
44 + 2a (0 0.) (0(0) ((0)
(58)
Since s is a Nash equilibrium and 4 = Uز (00, f), {.j)), we have in particular that
2a (0; - 0,) ( (0))) ) 20
that is 03 0 0, Aj > A - (0) a() for any C. We now show that this holds with striet
equality for any j E C. By contradiction, assume there exists r E C such that A, A + x with X 0. Then
== 0(0) ((0)- = E E Xر(0) + X +x)
JEC
)EC(()
A + x00
because (² r E C. This is contradiction, and establishes the result.
Lemma 6. For any j E C, 03 =
Proof. Let E C. by (58):
1y ((1,0,), u + 2a
(0, -,,) - m(0)
(0(0)-5(0))
( 11-13(00 x3(0) (0, 0,) Σ
xt( 0x - -0a)
u + 2a
kECWL
\,(0) (0r. oi))
u + 2a
Σ \Z
(0, 08) Σ
kECIf)
= =; + +2ag (0,, 0-,),
where
2 (,00 = Σ
(0)) - -,) - (0, - 02,]
(59)
RECH(
21

---

We prove that 0y((1, ),,)))) is strictly decreasing in 82 for j E C, by showing that @0,((1, 02) s-i, 1,00, 0 For any E C. For 2/ to be differentiable, we need qj to be differ- entiable, that is (3 = =(Exee (k)( (0) to be differentiable for any j E C. We re-index C as ( hcy) so that 0i, <... < D Observe that for < h < 8 for > O sufficiently small, 0, < 0j + < 01g11 because 01 <0 < 0 1 by Lemma and H3. Hence, the bid ordering does not change for any infinitesimal variation dØ, 0, nor does the indicator 1 < $/c }. (0)
Consequently by Corollary 1, nz (0) is differentiable in 0g and so is X (0). We have for any j E C:
(v,((1,0) 0,), 8t) 20. 0uz (0,,0
302
30,
20 E
(1)
((0)-0,) -(% (0--0a) x1
08,
kECl))
011
2a
Σ
(A - A) - 2a Σ Xi(0)
(60)
a0j
kECW()
kECr(()
<0.
(61)
where we have used Lemma at the third line. This implies
0 0
for any j E C.
(62)
To see why, assume by contradiction that there exists j E such that 8; = (1, 0,) with 0, > 0. Then for any h E (0, f f.). by (61):
(o) 100 Jōp-
@u5((1,(),s)) dt > ((1,0)),,))
(1 03 h). = uj (1(,())))
Öt
which contradicts being a Nash equilibrium.
Combining Lemma 5 and Lemma 6 gives for any kj, E C²:
0 02
(63)
Recall that by H3, 6n. 6n if and only m n, so (63) implies |C| This in turn implies
[3] = 1. Indeed, assume by contradiction |C| = and [8] > 2. Denote E B the only contributing
agent. They are asked n; Tú, (0) n. Moreover by (19) N | 1/1+2 (n + 1)
n, so
by definition of the contribution scheme (12), there exists l E B {r} such that ( > 0. This contradicts |C| = 1.
We now show that B = (J}. By contradiction, assume {i} with j < J. In particular, S, = (0, t). Consider a deviation s's = (1,0g) with 0, E θ, so B = Ji under s-), By
Lemma 6, 8 Ø f. so (58) rewrites:
un (x((1, (,), = + +. 2a AB, n (0))
(64)
for any k E J.. Since 02 < (B, (nn(())) (0)) < 0, by H3, we have
(, (1,()))sss))) い, .. ((0, f).s-)),
which contradicts s begin a Nash equilibrium. Hence, = (J). This concludes the proof.
Lemma 3. There exists [J] such that (0) 0.
Proof. Let (B. Ø) E 10. N be an equilibrium of the game induced by VCG Since the VCG mechanism is strategyproof in dominant strategy, = O. For any j E [J], the VCG payment is
(θ) Σ ((0 n
up n1
j -W((0,1,))) (O)) W(1, n (0) (1, 1-5), n" (0)) -u,,,, (,,1,n(())) (65)
KSj
(1)
(II)
22

---

Consider j E L"). By the contribution scheme Corollary 1.
u, (,(,,n((0) (a =(1, n (0))) (0) = , u u 1-1), 1-1)),"(0)))
n n)(B,n(())) Thus (IT) = 0. Moreover by Theorem 1, ((O0, 11),)11),n_ (0)) < (1, n" (0)) so (I) < 0. Thus, by (65) we have (0) < 0. L
where we used in the third inequality that n0) =
Theorem 3. Assume H1, H2, H3, H4 and H5. B = (1,..., 1)T is Nash equilibrium under I' with probability 1 5.
Proof. Let B" = (l...., 1)", so the aggregator has at her disposal 0I.....o.. 0..
We first focus on the event under which 8 correctly approximates 8, for any j < J. Define (6) {w i (w)(w) 0,1 & no} and E(d) Лe (O)) We have
P(E(5/J)) > 1- because P(E(O)) P(NGE)E,(0))
(66)
1 P( > 1 - Σjeu P(E,(0)) = 1 - J8,
and setting 8' = JJ leads to Equation (66). In what follows, assume that E(6/J) is true so
10, 0,l & (6) for any j E [J]. We denote by c= -- [J]: my(0) = nz (0 + nn)) > 0) the set of contributors, and to lighten notations write
a()) = N (0 + n;) T = X- + +7;)
and
(0( N 'n 0,
-x-(0 + m7, T + n1) with 6, = 0.
where 77 = 1
0, 1, 0, 0)
for any E [J]. Note that (()) is the actual weighted type within the coalition, whereas 1() is the weighted type estimated by the aggregator. Consider first a contributor E C who is asked nz (0 + n,)) > 0 samples. Their payoff under B* is
(1,1,,,) = a(R3 + c (8 N)) - on + n;)
= - aRRi + (())), N)) - c (c(0, - c(0, (6/5(2)) m))
a
= - -a(Ré + (0) - en
+ a [[(((())))) n) - =(0, (b))(2)) - (S(0()), N) -00-ee00,100 =0,, N3)]
= ., + 2a (0, - (0, - (())(1)) (0(O) -000)-7,000 3,(
0, 1-,) + 2a(1 - x +,))(0, 100--00, (0) m6/ (g))
2a Σ 1²(0 n;) (0. + (b)r(
BEC(()
and since E(6/J) true, 02 > 0, 18/r(4) and 02 < o. - m5/ for any E C {i}, so (, > úz (0, 1-j)-
(67)
Second, consider j & C who is asked g < n ((acc)) 0 samples, and denote by E [J] the agent such that 0, maxkec Og. Observe that q < (0 + +,)), so
(1,1 -Rgg + =()(0), N)) -oq > (R + =() N)) - -cn; + n.)
Up
where the last inequality comes from r E C and (67). Since j $ C. we have 0, 35>60 20 mm,)s(g) > 0. )g) 0, so u, >> uj and it follows that
(1, > = e0 1-)).
23

---

Proposition 2. Assume HI. H2 and H6. For any j E [J] the estimator
0,3
Rg(g) Ro(g)), gEg
sup
satisfies H5 with
(a(g) as/4 (1 + (d' + + +
(13)
Proof. Let j [J] and g I, have
00 = sup
(g) Ro(d)
ge
Rg(g) R3( + sup RRp/R Rg( Ro(g)) + sup Ro(g) Ro(g)
sup
gE
gE'd
gE
< 05/4 (g + 1 + (q' + 1) + 2/3 + 0g
(68)
(69)
with probability 1 6/2 by H2, HI, H6, and union bound. Similarly,
0g sup Rg) Ro(g) gEg
< sup gEtl
R2 (g) - Rg( + sup
R3( -R(l)) + sup Ro(o) - Ro(o)
gE
ge
< 0/84 [(9 + 1) + (d' 1) + 2,3 + 0.1
(70)
with probability 6/2. Combining (68) and (70) along with an union bound yields
16 051 < 06/4 + 1 + (d' + +1) +) + 23,
with probability 8.
Example 4. Assume H1, H2, H6 and H7.
(i) Denoting Rg) (g) = =nj" En f (o)))) -Y?), we have
Daun = = inf (Rols) + R (1)}
9E0
(ii) In HI, assume oss = = 3 = (RA and 7 1 |Bousquet et al., 2003). With 0 defined in Proposition 2, we have
(6) = In(3]])))()
(1 -- 2R)
Proof. (i) Let E B. Observe that under H7, have
R₂(-9) = Σ 1( 1(-o(xx)) <) n Σ ( =1) -
R,(o). -
Since the hypothesis class & is symmetric, we have
@jRn sup R, (g) Ro(o) =sup (R((9) Ro(9) ,E3
1 - (R, (-9) + +Ro(o))) = 1 inf 3a
(R) + +Rolo))
sup
gEt
(ii) Let j E [J], we have
= -1(1//))(((1+00)+++0001001011111 2R)
24

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
the claimed contributions are supported by proven theorems.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: all the made assumptions are clearly highlighted and discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Assumptions are made clear and given for each theorem individually. Full proofs are given in the Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: no experimental result in the paper
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer:
[NA]
Justification: no experimental result in the paper
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
comnoollcyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
httaai//ggiddeeeeeeuuutiiiii / //nips.c.// wttpccccppppcccaceeeccccccccccct wwwbblicguuids..../ /Codeeeooiiisaeeeeeee ieeniissiinnooooo ceiinnilccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: no experimental result in the paper Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
no experimental result in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
experimental result in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurIPS Code of Ethics https: /ttp///eerpp//eeeee cc httppu/icc/cchcccccueeeeee....ee
didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: no data used for this work
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: societal impact of the work performed
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
28

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: no data
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: no existing assets
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
29

---

Answer:
[NA]
Justification: no new asset
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "aV6Zs7Eg83", "reviewer": "Reviewer_pCrN", "summary": "The paper studies adverse selection in federated learning, due to varying levels of data quality among the clients. In particular, a phenomenon of unravelling, in which the collaboration is essentially destroyed due to insufficient incentives for participation for the agents with high quality data, is identified and studied. Within a specific model for the incentives of the clients and the server objective, the authors first derive optimal protocols under full information. Then they prove the emergence of the unravelling effect under hidden information and suggest a mechanism that avoids this effect by estimating the clients' dataset qualities from data.", "questions": "- For H1, it will be nice if the authors can clarify what $alpha$, $beta$ and $gamma$ can depend on in their framework. Are they absolute constants, can they depend of $\\mathcal{H}$, the distribution $P$, etc?\n\n- In H3, does the lower bound on $\\theta_j$ need to be larger than $0$?\n\n- Could the authors clarify how Lemma 1 and Proposition 3 relate to classic results from domain adaptation about the generalization of classifiers learned on multi-source data and about estimating the discrepancy distance from finite samples?", "limitations": "It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper studies a very relevant topic, namely participation incentives in FL. It also provide a new model for such incentives in the presence of varying data qualities and demonstrates and studies the effect of unravelling, which is, to my awareness, also a novelty in the context of FL.\n\n- The paper is well-written and the model design choices are well-justified.\n\n- Related work is covered well.\n\n- The paper shows how to incentivize participation by estimating the clients' data qualities by an initial sampling phase. In this way, more data can be collected from the clients with high-quality distributions. I think this approach is valuable, since it does not require any payments/penalties, but instead incentivize collaboration purely by changing the learning algorithm.", "weaknesses": "- In the proposed frameworks, the utilities of the clients are evaluated based on upper bounds on the loss and therefore on the type of guarantees on the model that can be obtained. One might expect that clients would instead reason about the expected loss (and hence utility) that they will get from the FL protocol, under the decisions they take (and over the randomness of the sampled data). It will be nice to see a discussion about why clients may chose to reason via statistical guarantees as compared to expected rewards; as well as a discussion of whether the techniques in the paper can be extended to the case where expected reward is considered.\n\n- If I interpret equation (8) correctly, currently the problem that the server solves requires that agents who are not included in the collaboration also would benefit from joining. Intuitively, this feels unfair/undesirable, since these agents will be \"left out\" of the collaboration. Of course, that won't be a problem if the grand coalition is chosen, but how about the remaining cases?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback, and try to address the points they raised below. \n\n\n\n> \"In the proposed frameworks, the utilities of the clients are evaluated based on upper bounds on the loss...\"\n\nWe thank the reviewer for their comment. Indeed, it may seem natural to assume that agents maximize their expected utility. We thought during elaborating our work about this alternative, but we came up with the conclusion that this approach would hardly apply to our specific problem. Indeed, agents would need to know $P_0$ to be able to form an expectation about their reward. This would make the statistical inference problem meaningless, as they could simply consider the Bayes estimator rather than performing an empirical risk minimization based on samples from $P_j$.  Additionally, the risk does not generally admit an exact expression, making this approach mathematically hardly tractable. We would like to stress that our modeling choice of working with a high probability upper-bound is actually common in the literature, see for instance [1,2,3].  \n \n\n> \"If I interpret equation (8) correctly, currently the problem that the server solves...\"\n\nWe deeply thank the reviewer for this remark, which unveils a typo in the formulation of problem (8). The correct formulation should be\n\n$$\n\\begin{aligned}\n    &\\text{maximize}\\quad W:(\\mathsf{B},\\mathbf{n})\\in\\{0,1\\}^J \\times R_{+}^J \\mapsto \\sum_{j\\in [J] }u_{j} (\\mathsf{B}, \\mathbf{n})\\\\\n    &\\text{subject to}\\quad\n        \\min_{j\\in [J]}u_{j} ( \\mathsf{B}, \\mathbf{n})- \\underline{u}_j \\geq 0.\n\\end{aligned}\n$$\n\nWe will correct this typo in the revised text accordingly.\n\n\n> \"It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.\"\n\nWe agree that discussing the optimality of mechanisms incentivizing participation with information asymmetry would be very interesting. However, there is no easy answer to this question at first glance. One option we have thought of is to first compute an upper-bound on the welfare achievable by any incentive-compatible transfer-free mechanism. And second, see how close the welfare derived under our proposed mechanism is from this bound. However, we were not able to complete these ideas in the time being. Therefore, while this question is interesting by its own, we leave it for future work.\n\n\n> \"For H1, it will be nice if the authors can clarify what $\\alpha$, $\\beta$ and $\\gamma$ can depend on in their framework. Are they absolute constants, can they depend of $\\mathcal{H}$, the distribution $P$, etc?\"\n\nWe thought that the parameters $\\alpha, \\beta$ and $\\gamma$ were already motivated and exemplified. Indeed, a remark (line 115 to 120) is made in our submission, where explicit values for these parameters were provided in the classification case, as well as in the regression case using Rademarcher complexity and a recent PAC Bayes bound. To summarize this remark, typically, $\\gamma$ is an absolute constant, $\\alpha$ should be thought of as a parameter which depends on the desired level of confidence $\\delta$, and finally $\\beta$ is related to the complexity of the problem at hand (related to the Rademacher complexity of the considered function class in the classification case, and the sup-norm of the loss in the regression case). We would be happy to clarify this remark in the paper if the reviewers feel the need to.\n\n> \"In H3, does the lower bound on theta_j need to be larger than 0?\"\n\nFor any $j \\in [J]$,  $\\theta_j$ needs indeed to be non-negative, because by definition: \n$$ \\theta_j = \\sup_{g\\in\\mathcal{G}} \\mid\\mathcal{R}_{j}(g)-\\mathcal{R}_0(g)\\mid \\geq 0.$$\nNote that nothing prevents from $\\underline{\\theta} = 0$, so an agent can have access to the target distribution $P_0$ in our framework.\n\n> \"Could the authors clarify how Lemma 1 and Proposition 3 relate to classic results from domain adaptation about the generalization of classifiers learned on multi-source data and about estimating the discrepancy distance from finite samples?\"\n\nThe domain adaptation results we use are well-known in the literature, however we acknowledge that further details should have been included.  Lemma 1 is a straightforward application of a more general, well-known bound which can for instance be found  in [Theorem 5.2, 4] or [Theorem 1, 5]. Contrary to these works where the weights on source distributions can be any point in the simplex, we use weights that are proportional to the number of samples provided to the aggregator, hence the simpler expression. Likewise, Proposition 3 is known and has been used for estimation of the G-divergence from a finite sample. It has been applied to the classification case for instance in [6]; see in particular Lemma 2. We thank the reviewer for this comment and we will provide further details about how our work relates to domain adaptation literature. We would also like to stress that the aim of our work is not to bring novel results in domain adaptation, but rather to use the domain adaptation literature to motivate our (utility) model.\n\n[1] Huang, Karimireddy, & Jordan (2023). Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning. arXiv preprint arXiv:2306.05592.\n\n[2] Karimireddy, Guo, & Jordan (2022). Mechanisms that incentivize data sharing in federated learning. arXiv preprint.\n\n[3] Ananthakrishnan, Bates, Jordan, & Haghtalab (2024, April). Delegating data collection in decentralized machine learning. In International Conference on Artificial Intelligence and Statistics. PMLR.\n\n[4] Zhang, Zhang & Ye (2012). Generalization bounds for domain adaptation. Advances in neural information processing systems, 25.\n\n[5] Konstantinov, & Lampert, (2019). Robust learning from untrusted sources. In International conference on machine learning. PMLR.\n\n[6] Ben-David, Blitzer, Crammer, Kulesza, Pereira, & Vaughan, (2010). A theory of learning from different domains. Machine learning, 79.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bZIYl2sFSN", "reviewer": "Reviewer_K1qa", "summary": "Adverse selection is a phenomenon studied in economics in which  information asymmetry may have a negative  effect in the market equilibrium. The paper considers a federated learning setting when the agents are strategic, and the authors formalize the concept of ``adverse selection'', and analyze it in several directions.\nThe question they ask is the following: assume that different agents are able to collect samples with different quality and share it with other agents. In this case agents with high quality sample may benefit little from sharing their information. This may have a spiral effect so that none would be happy to share their samples. \nThe authors formalize this problem and analyze it trough a series of results:\n\n(1) they model the above mechanism in which each agent i can sample data points with quality \\theta_i\n\n(2) they show how a benevolent social planner can maximize the overall utility for all agents if she knows all \\theta_is\n\n(3) they formalize the strategic setting in two cases and ask whether unraveling may occur:\n\n- They  that indeed this may occur if the social planner is unaware of the quality of samples. Assuming that agents are able to statically share the value of \\theta_i they show that in this case the Nash equilibrium is when the lowest quality agent or no agent shares their samples. \n\n- Motivated by this negative result the authors consider a different scenario in which the agents do not share the value of the quality of their samples but they share a fixed number  samples if they want to participate in the aggregation process, using these samples the planner estimates the quality of their data and asked for more samples if needed. In this case, agents will all reveal the true value of the quality of their samples, and the social planner can  maximize the overall utility function so that unravelling will not occur. \n\nI find the results interesting and solid (although I didn't check the proofs). The presentation is a bit hard to follows but I don't see an easier way of presenting all of these theoretical results.", "questions": "I didn't understand the subsection about VCG mechanism. What is it and why it is not available in your framework?", "limitations": "The authors have discussed the future directions in the conclusion.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- solid mathematical modeling and analysis \n- interesting result: extending an interesting concept called unravelling to federated learning", "weaknesses": "- hard to follow all details", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback, and are glad that they find our result interesting. We answer to their questions and remarks below.\n\n> \"Weaknesses: hard to follow all details.\"\n\n We understand that our notations may appear somewhat intricate and our text dense. We tried to lighten it as much as possible, and strike a balance between legibility and exactness despite the inherent complexity of the topics under study. In case the reviewers have suggestions to improve notations, we would gladly take them into account.\n\n> \"I didn't understand the subsection about VCG mechanism. What is it and why it is not available in your framework?\"\n\nThe VCG mechanism [7, 8, 9] is a fundamental concept in mechanism design. It is a generic transfer-based mechanism which allows the principal to maximize social welfare in the presence of strategic agents. More precisely, it ensures that participating and bidding true types is a dominant strategy for all agents. Incentive-compatibility is achieved through monetary transfers, which align individual payoffs with total welfare by paying each agent the total value of the other agents. An introduction to the topics can for instance be found in [10, chapter 9].  Given the paramount importance of the VCG approach in the mechanism design literature, it seemed important that we mentioned it. We however claim that it is not available in our case because it relies on monetary transfers, which we do not allow in our study. Indeed, we only allow the principal to implement transfer-free mechanisms, since monetary payments to participants seem unlikely in many collaborative learning applications. We nonetheless agree that the subsection dedicated to VCG may be too allusive, and we will do the necessary to flesh it out in the final version of the text. In particular, we will (i) explicitly write down the VCG payment and provide an intuitive explanation, and (ii) prove in a lemma that at least one player must receive a non-zero monetary payment when using VCG. \n\n--------------------------------------------------------------------------------------------------------------------\n**References**  \n[7] Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1), 8-37.\n\n[8] Clarke, E. H. (1971). Multipart pricing of public goods. Public choice, 17-33.\n\n[9] Groves, T. (1973). Incentives in teams. Econometrica: Journal of the Econometric Society, 617-631.\n\n[10] Roughgarden, T. (2010). Algorithmic game theory. Communications of the ACM, 53(7), 78-86.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C9jAyqeyV0", "reviewer": "Reviewer_MuDH", "summary": "There can be strategic learners and collaborations for collaborative learning is not trivial. When data qualities are private, coalitions may undergo unravelling wherein only worst agents will be left in the coalition.  \n\nAuthors propose a probabilistic verification-based mechanism to make optimal collaboration as Nash Equilibrium with high probability.", "questions": "As the aggregator is estimating the types of contributor's types, they need to have access to the probability distribution from which they are sampling data. How practical is this scenario?", "limitations": "As authors proposed by the authors, it would have been better if agents learned their types themselves in an online fashion.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Authors consider the formation of coalitions and consider strategic agents with distribution of different quality. \n\nAuthors also propose that optimal coalition occurs at NE as per their mechanism with high probability and back it up with rigorous theoretical proofs.", "weaknesses": "The authors don’t show that if the agents report the type profile of the agents truthfully. They rather consider that the aggregator to approximate it based on their probability distribution. Also, experimental verification isn’t provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, although we are quite surprised by the provided summary which does not correspond to our paper. We believe that there was a mistake on their side. We however reply to their questions below.\n\n> \"Weaknesses: the authors don’t show that if the agents report the type profile of the agents truthfully. They rather consider that the aggregator to approximate it based on their probability distribution.\" \n\nWe appreciate the reviewer's feedback and would like to clarify the principles of our mechanisms, as there may have been a slight misunderstanding. To rephrase them, we consider two mechanisms. The first is a direct-revelation mechanism which asks agents to report their types. In this naive approach, incentive-compatibility is not enforced and this leads the coalition to be either empty or reduced to a singleton at any equilibrium, which precisely corresponds to unravelling. In a second time, we propose a new mechanism which recovers the grand coalition as a pure Nash equilibrium. Contrary to the standard direct revelation approach, it does not incentivize agents to truthfully report their profile of types, but only asks whether they wish to participate.\n\nAs opposed to what the reviewer suggests, we believe that this feature is one of its strengths. Indeed, the fact that the agents’ action space is reduced to either opting in or out prevents them from strategically manipulating the mechanism. This allows to circumvent the common difficulties of implementing incentive-compatibility. We would like to stress that our approach rests on a well established line of literature in mechanism design, at the intersection of verification-based [11] and evidence-based [12] methods. Additionally, our mechanism does not suppose agents know their type, as their participation constraint holds with high probability by design.\n\nAn alternative procedure, which may be closer to what the reviewer has in mind, would be to:\n1. ask agents to declare a type,\n2. estimate actual types based on the provided samples,\n3. design penalties for agents with declared types which are not aligned with the estimation made in step (2) (for instance, through accuracy shaping).\n\nEven though this lying cost-like [13] approach could recover the optimal grand coalition as a pure Nash equilibrium through enforcing incentive compatibility, we were not able to find additional beneficial features and clear improvement over our proposed mechanism. In addition, it seems to us that this alternative mechanism asking for types is more complicated to analyze than our proposed solution.  Finally, such a procedure would require the agents to know their own type, in opposition to our mechanism.\n\n> \"Also, experimental verification isn’t provided.\"\n\nIf the reviewers agree with this point, we will add experiments on toy examples in our revised version to empirically validate our results. In particular, we will:\n* provide a figure illustrating the socially optimal allocation,\n* compare the optimal allocation with the one induced by the mechanism $\\hat{\\Gamma}$,\n* empirically verify that the strategy profile $(1,\\ldots,1)$ is a Nash equilibrium under the mechanism $\\hat{\\Gamma}$.\n\n  \n> \"As the aggregator is estimating the types of contributor's types, they need to have access to the probability distribution from which they are sampling data. How practical is this scenario?\"\n\nEstimating types does not require access to the full sampling distribution of each agent (which would indeed be unrealistic), but only each contributor sending $q$ samples from $P_j$ to the aggregator. That being said, an issue the reviewer may have in mind is that agents might be tempted to twist their sampling process to fool the mechanism, that is providing samples from a distribution which is not $P_j$. This issue falls in the category of hidden action, and several methods have been devised in the literature to solve it [14, 15]. In our work, we are interested in hidden information rather than hidden action. Since concurrently addressing moral hazard and adverse selection is a notoriously hard problem in mechanism design, we leave aside the former by assuming that agents honestly sample from their distribution $P_j$. We would like to stress that this choice is customary in the strategic learning literature [16] and more generally in the mechanism design community [17].\n\n> \"As authors proposed by the authors, it would have been better if agents learned their types themselves in an online fashion.\"\n\nAs argued in our previous reply, our verification-based mechanism does not require agents to know their own types for them to benefit from joining the coalition with high probability. We will change the text in the conclusion of the revised version accordingly.\n\nWe hope we have addressed the reviewer's concerns. If they are not satisfied with our response, we would be happy to answer any further questions.\n\n------------------------------------------------------------------------\n**References**  \n[11] Green, & Laffont (1986). Partially verifiable information and mechanism design. The Review of Economic Studies, 53(3), 447-456.\n\n[12] Grossman (1981). The informational role of warranties and private disclosure about product quality. The Journal of law and Economics, 24(3), 461-483.\n\n[13] Lacker, & Weinberg (1989). Optimal contracts under costly state falsification. Journal of Political Economy, 97(6).\n\n[14] Karimireddy, Guo, & Jordan, (2022). Mechanisms that incentivize data sharing in federated learning. arXiv preprint.\n\n[15] Huang, Karimireddy, & Jordan (2023). Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning. arXiv preprint.\n\n[16] Ananthakrishnan, N., Bates, S., Jordan, M., & Haghtalab, N. (2024, April). Delegating data collection in decentralized machine learning. PMLR.\n\n[17] Laffont, J. J., & Martimort, D. (2009). The theory of incentives: the principal-agent model. In The theory of incentives. Princeton press.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ifIUJ06wBl", "reviewer": "Reviewer_DYwo", "summary": "The paper models the collaborative learning problem using a statistical model. In this model, since each agent has its own utility with respect to the risk and the cost of sampling, they may not converge to the Nash equilibrium of optimal general risk. More precisely, the process may undergo a phenomenon known as unraveling, wherein it contracts to the point that it becomes empty or consists solely of the worst agent. The paper designs a mechanism to avoid this phenomenon and provides a practical implementation for the transfer-free mechanism.", "questions": "- Hypothesis 4 appears to be a bound on the number of agents. Could you provide an example of the number of agents required in practice?\n- As mentioned in the weaknesses section, could you demonstrate the \"unraveling\" problem and the mechanism to address this issue in practice? How common is this problem?\n- Is the selection of $\\eta_{\\delta}$ in proposition 3 optimal?", "limitations": "I do not foresee any negative societal impact from this paper. For other limitations, please see the questions and weaknesses sections.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper models the collaborative learning problem in a manner that is both strict and easy to understand.\n- The paper identifies the \"unraveling\" problem during the process of collaborative learning and provides a solution. This seems like a very important issue for making collaborative learning work.\n- The paper clearly lists the hypotheses used in every theorem, making it easy to understand the conditions under which the theorems apply.", "weaknesses": "- The paper does not show empirically when the \"unraveling\" problem occurs or whether the mechanism in section 4.2 makes a difference.\n     It is not clear whether the problem is common in practice.\n-  The empirical implementation of the mechanism in section 4.2 requires hypothesis 7, which may not be feasible in practice if the aggregator does not know $P_0$ exactly or the number of samples is relatively small, i.e., less than $q'$.\n- The notation is confused, i.e., $\\underline{n}$  is used to denote an expression of $\\arg\\max_{n}\\cdots$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback, and answer their questions below.\n\n> \"The paper does not show empirically when the \"unraveling\" problem occurs or whether the mechanism in section 4.2 makes a difference. It is not clear whether the problem is common in practice.\"\n\nUnravelling is a common issue which arises in many real-world markets, as documented by several econometric studies. For instance, [18] or [19] study the phenomenon on the American insurance market. Our mechanism in section 4.2 is largely inspired by verification methods, which are actually implemented by insurance companies to limit adverse selection.  Regarding the specific case of collaborative learning, our study is still prospective since, to our knowledge, currently deployed federated learning systems do not explicitly give the possibility to agents to opt out (think of Google keyboard which is trained while the phone is charging and the user is away). However, we expect collaborative learning systems involving strategic agents to develop, in particular among competing firms (see for instance [20] for the power market). Given that such markets will likely feature asymmetry information, we believe that our work provides guidance to ensure the stability of such decentralized learning systems. In this sense, our main objective is to highlight the risk posed by adverse selection to policy makers for nascent data markets. We thank the reviewer for this remark, we will make clearer the practical importance of unravelling, and the solution brought by our mechanism $\\hat{\\Gamma}$ in the final version of the text.\n\n> \"The empirical implementation of the mechanism in section 4.2 requires hypothesis 7, which may not be feasible in practice...$.\n\nThe aggregator does not need to access the full distribution $P_0$, but indeed needs to have at their disposal $q’$ i.i.d samples from it. We agree that when $q’$ is very small, the quality of the type estimation would be low, with adverse effects on the stability of the coalition and the welfare under $\\hat{\\Gamma}$. This mechanism is typically suited for regimes where $q’$ is large enough to estimate the types, but not too large, so that we can still largely benefit from collaborative learning. However, we would like to recall that even when $q’$ is very small, it is still possible to re-establish the truthful, optimal collaboration by the means of VCG transfers as explained in our answer to reviewer K1qa. Indeed, the VCG mechanism ensures that participating in the coalition and reporting their true types is a dominant strategy for agents, by aligning their individual payoffs with social welfare. We thank the reviewer for this remark, which we will include in the final text. \n\n> \"The notation is confused...\"\n\nThe reason why we rooted for this notation is that $\\underline{u}$ (the utility under the outside option) is the minimum utility the aggregator must ensure within the coalition, hence the underscore. $\\underline{n}$ inherits from this underscore because it is the number of samples which achieves $\\underline{u}$. We would however be glad to take into account any alternative suggestion from the reviewer.\n\n> \"Hypothesis 4 appears to be a bound on the number of agents. Could you provide an example of the number of agents required in practice?\"\n\nSince the bound in H4 features many problem-dependent quantities (such as the amplitude of types, the utility parameters a and c…) it is hard to provide a one-size-fits-all answer to this question. The paper has been written with the rationale that $J$ is large, as we expect federated learning systems to involve many agents. However, even in the case where $J$ would be too small for H4 to hold, Theorem 1 would remain valid. We would only be unable to characterize $L^{opt}$ as accurately, that is with the optimal total number of samples $\\bar{N}$ (instead, we can only guarantee that the total number of samples is smaller than $\\bar{N}$). Hence, our results would remain true even with a small number of players, but would be slightly less precise. We thank the reviewer for pointing this out, and we will add this remark to our final text. \n\n> \"As mentioned in the weaknesses section, could you demonstrate the \"unraveling\" problem and the mechanism to address this issue in practice? How common is this problem?\"\n\nWe refer the reviewer to our reply to the mentioned weakness.\n\n> \"Is the selection of $\\eta_{\\delta}$ in proposition 3 optimal?\"\n\nWe acknowledge that this is an excellent question if we are interested in getting sharp bounds in Theorem 2 and thank the reviewer for pointing it to us. After having looked in the literature, we are not sure whether the proposed estimator achieves optimality, for instance in the minimax sense. We however suspect that the parametric rate $1/q$ is almost optimal from primary considerations. However, due to its complexity and since it would not change our conclusions, the question on the optimality of $\\eta_\\delta$ is out of the scope of the paper, in our opinion, and we leave it for future research.\n\nWe hope that we replied to the reviewer's concerns, and would be happy to answer any additional question.\n\n-------------------------------------------\n**References**  \n[18] Einav, L., Finkelstein, A., & Cullen, M. R. (2010). Estimating welfare in insurance markets using variation in prices. The quarterly journal of economics, 125(3), 877-921.\n\n[19] Hendren, N. (2013). Private information and insurance rejections. Econometrica, 81(5), 1713-1762.\n\n[20] Pinson (2023), \"What may future electricity markets look like?\", Journal of Modern Power Systems and Clean Energy 11", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We deeply thank the reviewers for their evaluation of our work and their insightful feedback. We will take into account their remarks for the final version of the text. They seem to agree on the importance of adverse selection in collaborative learning and the fact that our research question is meaningful. In what follows, we reply individually to each reviewer and try to address their concerns. We will gladly answer additional questions, if any, during the author-reviewer discussion period.

Meta-review: The paper studies unravelling, a celebrated economic phenomena, in the context of collaborative filtering. 

I agree with some of the reviewers about confusing notations, which the authors have addressed in their rebuttal.

After carefully reading the paper, the reviews, and the rebuttal, I believe this paper could interest the community and deserve acceptance.
Decision: Accept (poster)