Unravelling in Collaborative Learning

Authors: aymeric  capitaine
etienne  boursier
antoine  scheid
eric  moulines
michael i jordan
el-mahdi  el-mhamdi
alain  durmus
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:57:59

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.

Main paper: 
 introduction: 
 Collaborative learning is a framework in which multiple agents share their data and computational resources to address a common learning task [Blum et al., 2017 , Kairouz et al., 2021] . A significant challenge arises when the quality of these distributions is unknown centrally and agents are strategic. Indeed, participants may be tempted to withhold or misrepresent the quality of their data to gain a competitive advantage. These strategic behaviors and their consequences have been studied extensively in the literature on information economics [Mas-Colell et al., 1995, Laffont and Martimort, 2001] . In particular, information asymmetry is known to result in adverse selection, whereby lowquality goods end up dominating the market. In the current paper we study collaborative learning from the perspective of information economics.A vivid illustration of adverse selection is found in Akerlof's seminal work on the market for lemons [second-hand cars of low quality, Akerlof, 1970] . Because buyers cannot properly assess the quality of cars on the second-hand market, their inclination to pay decreases. As a consequence, sellers with high-quality cars withdraw from the market, since the proposed price falls below their reservation price. This in turn lowers the buyers' expectation regarding the average quality of cars on the market, so their willingness to pay decreases even more, which de facto crowds out additional cars. The market may therefore enter a death spiral, up to the point where only low-quality cars are exchanged in any competitive Nash equilibrium. This phenomenon is known as unravelling. The insurance market serves as another poignant example of this effect [Rothschild and Stiglitz, 1976 , Einav and Finkelstein, 2011 , Hendren, 2013] . In insurance, information asymmetry arises due to the fact that insurees possess private knowledge about their individual risk profiles, which insurers lack. Individuals with higher risk are more inclined to purchase policy, while those with lower risk opt out. Consequently, insurers are left with a pool of policyholders skewed towards higher risk, leading to increased premiums to cover potential losses. This, in turn, prompts low-risk individuals to exit the market, exacerbating adverse selection further-a cycle reminiscent of the unravelling described by Akerlof.We study the problem of whether collaborative learning could also fall victim to unravelling. We consider strategic agents who have access to sampling distributions of varying quality and wish to jointly train a model. They delegate the training process to a central authority who collects samples so as to maximize total welfare. We ask whether adverse selection can arise when data quality is private information. In particular, the presence of a low-quality data owner may harm the model, prompting high-quality owner to leave the collaboration and train a model entirely on their own. Their departure would decrease the average data quality even more, and create a vicious circle. In the worst case, the coalition of learners would reduce to the lowest data quality owner alone. This question is of prime importance from a practical point of view, because unravelling could jeopardize the long-run stability of collaborative models deployed at large scale.Our contribution is threefold:1. We provide a rigorous framework for analyzing collaborative learning with strategic agents having data distributions of varying quality. On the one hand, we leverage tools from domain adaptation to capture a notion of data quality formally. On the other hand, we model collaboration as a principal-agent problem, where the principal is an aggregator in charge of collecting samples so as to maximize social welfare. This setup allows us to derive the benchmark welfare-maximizing collaboration scheme when data quality is public information. 2. 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 are allowed, the VCG mechanism suffices to re-establish optimality. When transfers are not possible, we leverage probabilistic verification techniques to design a mechanism which breaks unravelling. More precisely, we ensure that the optimal, grand coalition ranks with high probability among the Nash equilibria of the game induced by our mechanism. We demonstrate how to implement our mechanism practically in the setting of classification.Related work. The issue of information asymmetry in machine learning has been an area of recent activity. Several learning settings have been considered, including bandits [Wei et al., 2024] , linear regression [Donahue and Kleinberg, 2021a,b] , classification [Blum et al., 2021] and empirical risk minimization [Dorner et al., 2023 , Liu et al., 2023] in a federated context [Tu et al., 2022] .Most of these studies focus on the sub-problem of moral hazard, where agents take actions that are unobserved by others. This situation usually results in under-provision of effort and inefficiency at the collective scale [Laffont and Martimort, 2001] . This issue appears naturally in federated learning, because model updates are performed locally. For instance, Karimireddy et al. [2022] show that heterogeneity in sampling costs results in total free-riding without a proper incentive scheme. Huang et al. [2022] show that under-provision of data points in federated learning arises from privacy concerns. Yan et al. [2023] consider a federated classification game where agents can reduce the noise in their data distribution but incur a costly effort to do so. In the same vein, Huang et al.[2023] study the case of agents who are interested in different models, and may skew their sampling measure accordingly. Saig et al. [2023] and Ananthakrishnan et al. [2023] study hidden actions when a principal delegates a predictive task to another agent, and show that thresholds or linear contracts are able to approximate the optimal contracts.Adverse selection is another type of information asymmetry, where preferences of agents are unobserved rather than actions. This issue also naturally arises in collaborative learning, because the data distributions from which agents sample or about which they care may not be public. While data heterogeneity is a widely explored topic in federated learning (see for instance Gao et al. 2022 for a general survey, and Fu et al. 2023 for the specific problem of client selection), the strategic aspect has been rarely considered. Most studies doing so focus on hidden sampling costs (see, e.g., Karimireddy et al. 2022 , or Wei et al. 2024 in a bandit context), but few address the fundamental problem of distribution shift. Ananthakrishnan et al. [2023] mentions the issue of adverse selection when a principal delegates a predictive task to an agent, and provide qualitative insights about the optimal contract. However, they consider a single agent and leave aside the question of participation. Finally, Werner et al. [2024] and Tsoy and Konstantinov [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 a full information benchmark, which allows us to derive the welfare-maximizing contribution scheme. In Section 4, we turn to the more realistic case where data quality is private information. We first show that in this case, a naive aggregation method leads to total unravelling. Second, we introduce a mechanism which breaks unravelling by inducing a game where the grand coalition is a pure strategy Nash equilibrium with high probability.2 Model Statistical framework. Let (X, X ) and (Y, Y) be two measurable spaces and denote by P a family of probability measures on (X × Y, X ⊗ Y). We consider [J] = {1, . . . , J} agents who aim to perform a prediction task associated with a hypothesis class G ⊂ {g : X → Y}, a loss function ℓ : Y × Y and a probability measure P 0 ∈ P. Each agent seeks to minimize g ∈ G → R P0 (g) where for any probability distribution P ∈ P, R P (g) = ℓ(g(x), y)dP (x, y) is the risk associated to g ∈ G with respect to P .We leverage tools and results from statistical learning theory. Denote by {(X i , Y i )} i⩾1 the canonical process on X × Y and denote by P P and E P the canonical probability and expectation under which {(X i , Y i )} i⩾1 are i.i.d. random variables with distribution P ∈ P. With this notation, we can introduce our assumptions on G and P. H1. For δ ∈ (0, 1), there exist α δ > 0, β > 0 and γ > 0 such that for any distribution P ∈ P, hypothesis g ∈ G and n ⩾ 1P P R P (g) - 1 n n i=1 ℓ(g(X i ), Y i ) ⩽ α δ (1 + n) γ + β ⩾ 1 -δ .This assumption covers a wide range of situations. For instance in the classification case whereY = {-1, 1} and ℓ : (y, ỹ) → 1 {y ỹ⩽0} , α δ = ln(1/δ)/2, β = 2RAD(G ) and γ = 1/2where RAD(G ) is the empirical Rademacher complexity of G [Bousquet et al., 2003] . Similarly, the Bayesian PAC approach in the linear regression context with bounded loss leads to α δ = KL(ρ∥π) + ln(1/δ), β = ∥ℓ∥ 2 ∞ /8 and γ = 1 where ρ and π are any distributions on G [Shalaeva et al., 2019, Corollary 4] .For ease of notation, we let R j (g) serve as a shorthand for R Pj (g). It is moreover assumed that agent j ∈ [J] cannot directly sample from P 0 , but has instead access to a distribution P j ∈ P which deviates from P 0 according to the G -divergence: H2. For any j ∈ [J], P j ∈ P has finite G -divergence:θ j = sup g∈G |R j (g) -R 0 (g)| < +∞ .Intuitively, for any j ∈ [J], θ j ⩾ 0 models the bias incurred by having access to samples from P j instead of the target distribution P 0 . More precisely, the risk excess associated with empirical risk minimization (ERM) based on samples from P j is in the worst case at least θ j . A poor sampling distribution P j -which corresponds to a high θ j in the previous expression-might be the consequence of low-quality sensors or degraded experimental conditions resulting in noisier data points.The class of discrepancies appearing in 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 a natural framework to analyze the behavior of models trained on diverse distributions, and is practically appealing since it can be easily estimated in the context of classification [Ben-David et al., 2010] .We make the following assumptions on the quality indexes (θ 1 , . . . , θ J ), hereafter referred to as types. H3. There exists (θ, θ) ∈ R 2 + such that θ ⩽ θ 1 < θ 2 < . . . < θ J ⩽ θ.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 is for convenience in simplifying the proofs.Collaborative learning framework. We further suppose that agent j ∈ [J] can fit a model g ∈ G based on i.i.d. samples {(X j 1 , Y j 1 ), . . . , (X j nj , Y j nj )} of size n j ⩾ 0 from P j ∈ P in one of two ways: they can compute on their own, or collaborate. This is captured by the two following options:Option 1) Agent j performs ERM on their own samples:EQUATIONThis non-collaborative procedure is referred to as the outside option.Option 2) Agent j can take part in a coalition orchestrated by a central data aggregator, encoded as B = (B 1 , . . . , B J ) ∈ {0, 1} J , where B j = 1 means that agent j is member of the coalition. We also write B = {j ∈ [J] : B j = 1}. In exchange for their samples, agent j gains access to the collaborative model trained over the concatenation of samples:EQUATIONwhereR B (g) = N -1 j∈[J] B j nj i=1 ℓ(g(X j i ), Y j i ) and N = j∈[J]B j n j .Agent utilities. We assume that agents incur a unitary cost for sampling from their distribution and dislike statistical risk. Therefore, a baseline model for measuring the preferences associated with a model g ∈ G and a number of samples n is based on a linear map: (g, n) → -aR 0 (g) -cn for a, c > 0. In practice, however, R 0 (g) is typically unknown so agents instead can use a PAC bound of the form P(R 0 (ĝ n ) ⩽ R ⋆ 0 + ε) ⩾ 1 -δ to a assess a model ĝn ∈ G trained over their samples, where ε > 0, δ ∈ (0, 1) and R ⋆ 0 = inf g∈G R 0 (g). Our next result shows that H 1 and H 2 allow each agent to pin down such an ε > 0, under either Option 1) or Option 2). Assuming H1, define the function ε for any(θ, n) ∈ Θ × R + by ε(θ, n) = 2 α δ (1 + n) -γ + β + θ .(3)Lemma 1. Assume H1 and H2.(i) Any agent j ∈ [J] picking the outside Option 1) obtains a modelg j ∈ G achieving R 0 ( g j ) ⩽ R ⋆ 0 + ε(θ j , n j ) with probability 1 -δ . (ii) Any coalition B ∈ {0, 1} J drawing n = (n 1 , . . . , n J ) ∈ R J + , samples obtains a model g B ∈ G achieving R 0 ( g B ) ⩽ R ⋆ 0 + ε(ϑ, N )with probability 1 -δ , where N is the total of samples and ϑ is the weighted average type within the coalition:EQUATIONWhen the context is clear, we write ε(B, n) = ε(ϑ(B, n), N (B, n)) to lighten notation. Based on Lemma 1, we define the utility of agent j ∈ [J] asEQUATIONNote that for any j ∈ [J], we take n j ⩾ 0 to be a real number for ease of presentation. In (5), a/c > 0 captures the extent to which individuals are willing to trade off model quality against sampling cost.For any j ∈ [J] and B -j = (B 1 , . . . , B j-1 , B j+1 , . . . , B J ) ∈ {0, 1} J-1 , we denote by a slight abuse of notation (B, B -j ) = (B 1 , . . . , B j-1 , B, B j+1 , . . . , B J ) for any B ∈ {0, 1}. Similarly for n -j = (n 1 , . . . , n j-1 , n j+1 , . . . , n j ) ∈ R J-1 + , we write (n, n -j ) = (n 1 , . . . , n j-1 , n, n j+1 , . . . , n j ) for any n ⩾ 0. We can then characterize the optimal behavior of any agent picking the outside option as follows.Proposition 1. Assume H1 and H2. For any j ∈ [J], B -j ∈ {0, 1}J-1 and n -j ∈ R J-1 + , the optimal number of samples to draw under Option 1) is argmax n≥0 u j ((0, B -j ), (n, n -j ) ; θ j ) = n where n = (2ac -1 γα δ ) 1/(γ+1) -1 .In what follows, we assume 2a/c > (γα δ ) -1 to exclude the pathological case where no agent is willing to sample data points. From now on, we denote byEQUATIONthe best achievable utility under the outside option. Note that n does not depend on θ j ∈ Θ (but u j does) so all agents outside of the coalition draw a same number of data points n > 0. This result, which may be surprising at first glance, comes from the fact that all agents have the same accuracy-to-sampling-cost ratio a/c in their utility.Aggregator. We finally assume that the aggregator acts benevolently to set up a Pareto-optimal collaboration, by maximizing the total welfare under individual rationality. In other words, they solve:EQUATIONsubject to minj∈[J] u j (B, n) -u j ⩾ 0 .In the Social Choice literature, W is referred to as the utilitarian social welfare function. The participation constraint ensures that no agent within the coalition finds it beneficial to switch to their outside option. Note that n ∈ R J + is required to have non-negative entries, which prevents the aggregator from giving away data points to agents.3 Full-Information Benchmark: First-Best CollaborationIn this section, we assume that the profile of types (θ 1 , . . . , θ J ) ∈ Θ J is public, and study how the aggregator can implement an optimal collaboration among agents under this most-favorable scenario.Exact solution. We are looking for a solution to the aggregator's problem (8). For any B ∈ {0, 1} J and n ∈ R J + , denote byEQUATIONthe maximum number of samples that agent j can be asked to provide within the coalition under its participation constraint, where n is defined as in ( 6), and u j as in (7) . With this notation, problem (8EQUATION)Theorem 1. Assume H1, H2, H3. Problem (8) admits a unique solutionEQUATIONThe couple (B opt , n opt ) is referred to as the optimal contribution scheme. Although implicit, the condition ( 11) provides insights about the optimal scheme. The aggregator makes everyone enter the coalition, but only asks the L opt > 0 first-best agents to contribute. This allows to obtain the best possible collaborative model while sparing any sampling cost to other agents. Moreover, the number of required samples n opt j (θ) 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; if on the other hand the agent gets a worse model by collaborating (i.e., they are a contributor with very high quality data), the aggregator can only ask less data because of the participation constraint.Relaxed solution. Working with the optimal scheme (B opt , n opt ) is difficult because n j (1, n opt (θ)) has no explicit expression. To make the analysis tractable, we slightly simply the optimal contribution scheme in Theorem 1 and consider the simplified optimal contribution scheme (B ⋆ , n ⋆ ) where B ⋆ = B opt = (1, . . . , 1) and for any j ∈ [J],EQUATIONwithN = (n + 1)J 1 1+γ -1 . Note that (B ⋆ , n ⋆ ) only differs from (B opt , n opt ) in two ways. First, in (B ⋆ , n ⋆ ) all contributors'participation constraint bind, while in (B opt , n opt ) the L opt -the one could be slack. Second, the total number of data points required from the coalition is fixed and equal to N = Θ(J1 1+γ). The quantity N comes from a 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 a good approximation of the exact solution in reasonable settings. Indeed, the following result establishes that applying (B ⋆ , n ⋆ ) instead of (B opt , n opt ) comes at a negligible welfare cost when types are sufficiently evenly spaced.Lemma 2. Assume H1, H2 and θ j -θ j-1 = O(1/J) for any j ∈ {2, . . . , J}. Then,W (B opt , n opt (θ)) = W (B ⋆ , n ⋆ (θ)) + O(J 1 1+γ ) .Moreover, the following proposition shows that n ⋆ (θ) admits a workable expression.Corollary 1. Assume H1, H2 and H3. Then L ⋆ = Θ(J 1 1+γ ) and for any j ∈[J], n ⋆ j (θ) = 1 {j≤L ⋆ } N L ⋆ + 2a c θ j - 1 L ⋆ L ⋆ ℓ=1 θ ℓ .Since (B ⋆ , n ⋆ ) correctly approximates the optimal scheme while being more tractable, we work with it in the remainder to lighten proofs.H4. The aggregator applies the simplified contribution scheme (B ⋆ , n ⋆ ). 
the aggregator keeps m: 
 j ( θ) = 1{n ⋆ j ( θ + η j ) > 0} max[q , n ⋆ j ( θ + η j )] samples from agent j, and trains a collaborative model with these pooled samples.Γ induces a game ([J], {0, 1} J , (v j ) j∈[J] ) where any agent j ∈ [J] has a payoff function vj : (B j , B -j ) → B j -a R ⋆ 0 + ε(B, m( θ)) -c max[q , n ⋆ j ( θ + η j )] + (1 -B j )u j .The rationale behind this mechanism is fairly intuitive: since θ is a correct estimate of θ, n ⋆ j ( θ+η j ) ≈ n ⋆ j ( θ) correctly approximates the optimal contribution n ⋆ j (θ) for any contributor j ∈ B. Note that type estimates are purposely biased by η j when asking for samples. This is a safeguard against over-estimated types, which would lead to asking to many data points and could deter agents from participating in the coalition.Critically, m( θ) does not depend on declared type, so agents are no longer able to strategically manipulate the mechanism. Moreover, Γ does not require agents to know their own types, which would be an unrealistic assumption. Finally, observe that the number of data points asked to estimate types q is low enough to never deter agents from participating in the coalition.Theorem 3. Assume H1, H2, H3, H4 and H5. B ⋆ = (1, . . . , 1) T is a Nash equilibrium under Γ with probability 1 -δ.Theorem 3 shows that the optimal coalition is a sustainable equilibrium under Γ, which effectively breaks unravelling: the set of (approximate) Nash equilibria is no more reduced to profiles of actions where the coalition is empty, or reduced to the worst agent.Practical implementation. We now explain how to practically implement Γ in a collaborative learning setting. This requires defining a collection of estimators ( θ j ) j satisfying H5. To this end, we assume that few samples from the target distribution are available. H6. There are q ′ > 0 i.i.d samples (X 0 1 , Y 0 1 ), . . . , (X 0 q ′ , Y 0 q ′ ) from P 0 available to the aggregator and agents.Under H6, define R 0 (g) = q ′-1 q ′ i=1 ℓ(g(X 0 i ), Y 0 i ) for g ∈ G .This allows us to devise suitable estimators θ j as follows. Proposition 2. Assume H1, H2 and H6. For any j ∈ [J] the estimatorθ ERM 0,j = sup g∈G | R j (g) -R 0 (g)| ,satisfies H5 with η δ (q) = α δ/4 (q + 1)EQUATION)Proposition 2 shows that the empirical version of the G -divergence 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 0,j defined in H5 can easily be computed in the classification case, as shown with the following example.H7 (Classification setting). Y = {-1, 1}, ℓ = ℓ 0,1 : (y, y ′ ) ∈ Y × Y → 1 {yy ′ <0} , and G is a symmetric (g ∈ G if and only if -g ∈ G ) class of classifiers.Example 4. Assume H1, H2, H6 and H7.(i) Denoting R j -(g) = n -1 j nj i=1 ℓ 0,1 (g(X j i ), -Y j i ), we have θ ERM 0,j = 1 -inf g∈G R 0 (g) + R j -(g) .(ii) In H1, assume α δ = ln(1/δ) 1/2 , β = 2RAD(G ) and γ = 1 [Bousquet et al., 2003] . With θ ERM 0,j defined in Proposition 2, we haveη δ/J (q) = ln(4J/δ) 1/2 [(1 + q) -γ + (1 + q ′ ) -γ ] + 2Rad(G ) .Example 4 shows that in the classification case, it is sufficient to flip the labels of the data received from each contributor, merge these samples with those from P 0 , and perform an empirical risk minimization to compute θ ERM 0,j . The approximation error grows no more than logarithmically with the number of agents, while decreasing at rate γ with the number of samples used in the estimation. 
hidden information: 
 The welfare-maximizing contribution scheme described in (12) depends explicitly on θ ∈ Θ J , so it is implementable only if types are public. This often unrealistic, either for legal or competitive reasons. We therefore turn to the problem of setting up a collaboration when types are private.A naive solution to coping with the private nature of θ ∈ Θ J 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 a type θj different from their true type θ j .This approach corresponds to a direct-revelation mechanism Γ : (B, θ) → n ⋆ ( θ) which unfolds as follows.1. Any agent j ∈ [J] declares a tuple (B j , θ j ) ∈ {0, 1} × Θ ∪ { †}. If B j = 1, then agent j picks Option 2), and enters the coalition with type θ j . If B j = 0, then agent j picks Option 1), their declared type θ j is † by convention.2. Setting B = (B 1 , . . . , B J ) and θ ∈ (Θ ∪ { †}) J , then the aggregator applies the contribution scheme defined in (12), so the vector of number of contributions within the coalition is n ⋆ ( θ).Γ induces a direct revelation game([J], S J , (v j ) j∈[J]) where the action space is S = {(1, θ) : θ ∈ Θ} ∪ {(0, †)} and payoffs are for any j ∈ [J] and s ∈ S J ,v j (s j , s -j ) = u j (B, n ⋆ ( θ)) = B j -a R ⋆ 0 + ε(B, n ⋆ ( θ)) -cn ⋆ j ( θ) + (1 -B j )u j .This mechanism is obviously vulnerable to strategic manipulation, since it disregards incentive compatibility. This has severe consequences for the coalition, as shown by the following proposition.Theorem 2 (Unravelling). Assume H1, H2, H3, and H4. Let E ⊂ S J be the set of pure-strategy Nash equilibria of the game induced by Γ. We have(i) E ̸ = ∅ (ii) at any s ⋆ ∈ E , B = (0, . . . , 0) or B = (0, . . . , 0, 1) .Theorem 2 shows that under Γ, the coalition undergoes a full unravelling: it 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.Sketch of proof. The profile of actions ((0, †), . . . , (0, †)) 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, . . . , 0). Denote by C = {j ∈ [J] : B j = 1 and n ⋆ j ( θ) > 0} the set of contributors under this equilibrium. It can be shown that (i) for any (j, k) ∈ C 2 , θ j -θ j = θ k -θ k , and (ii) For any j ∈ C, (1, θ j ) with θ j > θ is strictly dominated by (1, θ) so θ j = θ at the equilibrium. As a consequence, θ j = θ k for any (j, k) ∈ C 2 , which implies by H3 that |C| = 1. From the definition of the contribution scheme (12), we can deduce that j∈[J] B j = |B| = 1, because |B| > 1 would entail |C| > 1. Finally, B J = 1 because v J ((1, θ), s -J ) > v J ((0, †), s -J) and s is a Nash equilibrium. This leads to B = (0, . . . , 0, 1).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 it beneficial to declare their true type and eventually opt for their outside option. This could be avoided by modifying Γ to make it(i) individually rational, that is v j ((1, θ j ), s -j ) ⩾ v j ((0, †), s -j ) for any j ∈ [J], s -j ∈ S J-1 , (ii) and incentive compatible, that is v j ((1, θ j ), s -j ) ⩾ v j ((1, θ j ), s -j ) for any θ j ∈ Θ.Under these conditions, the truthful, optimal profile of actions ((1, θ 1 ), . . . , (1, θ J )) would emerge as a Nash equilibrium. Since the aggregator seeks to minimize the utilitarian function W , one option would be to rely on the VCG mechanism [Vickrey, 1961 , Clarke, 1971 , Groves, 1973] , which is the direct-revelation mechanisms fulfilling these desiderata [Green and Laffont, 1977, Holmstrom, 1979] . Formally, the VCG mechanism writes Γ VCG : θ → (n ⋆ ( θ), t( θ)) where t( θ) = (t 1 (θ), . . . , t J (θ)) ∈ R J is a set of transfers satisfying for any j ∈ [J]:t j ( θ) = k̸ =j u k ((0, 1 -j ), n ⋆ ( θ)) - k̸ =j u k (1, n ⋆ ( θ)) .It re-establishes truthfulness as a dominant strategy by aligning individual payoffs v VCG j ( θ) = u j (1, n ⋆ ( θ)) -t j ( θ) with total social welfare. Unfortunately, the VCG approach is unavailable in our framework, because of the following observation.Lemma 3. There exists j ∈ [J] such that -t j ( θ) > 0.Lemma 3 shows that some agent would need to receive a strictly positive transfer. This is impossible without a monetary payment-utility can only be decreased by the aggregator, for instance through accuracy shaping [Karimireddy et al., 2022] -, which we exclude here.A probabilistic verification-based mechanism. We now show how to design a mechanism that recovers the optimal collaboration as a Nash equilibrium in high probability without the need for transfers. Inspired by the probabilistic verification approach [Caragiannis et al., 2012 , Ferraioli and Ventre, 2018 , Ball and Kattwinkel, 2019] , we assume that the aggregator can approximately estimate θ j with few samples from P j for any j ∈ [J]: H5. There exists a decreasing function η δ : R ⋆ + → R ⋆ + , with δ ∈ (0, 1) defined in H1, such that for any j ∈ [J] and i.i.d samples (X j 1 , Y j 1 ), . . . , (X j q , Y j q ) of size q > 0 from P j , there exists a (X j 1 , Y j 1 ), . . . , (X j q , Y j q )-measurable estimator θ j satisfyingP(| θ j -θ j | ⩽ η δ (q)) ⩾ 1 -δ .In Section 4.2, we show how the aggregator can design such estimators. H5 allows us to consider a new mechanism Γ : B → m(B) as follows:1. any agent j ∈ [J] declares B j ∈ {0, 1}. If B j = 1, the principal asks for q ⩽ n -2(a/c)( θ -θ) i.i.d samples from P j and estimates types as θ = ( θ j ) j∈B following H5.2. Based on the estimated types θ = ( θ j ) j∈B , the aggregator asks for [ n ⋆ j ( θ + η j ) -q ] + additional samples from P j , where n ⋆ ( • ) is defined as in (12) and η j = η δ/J (q)1 -2δ j η δ/J (q), with δ j = (0, . . . , 0, 1, 0, . . . , 0) T .Thus, the number of draws required from agent j is max[q , n ⋆ j ( θ + η j )]. 
conclusion: 
 In this work, we show that information asymmetry has deleterious consequences when strategic agents try to learn a collaborative model. More precisely, under a naive aggregation procedure, the ignorance of others' data quality leads the coalition of learners to be either empty or reduced to the lowest-quality agent. We introduce a transfer-free mechanism based on estimation of types. This effectively counteracts unravelling by letting the grand coalition ranks among the approximate Nash equilibria with high probability.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 to achieve, property would be core stability, to ensure that no group of agents would benefit from a coordinated deviation, i.e., forming an alternative coalition. Finally, it would be interesting to check whether there exist mechanisms where the optimal collaboration not only emerges as a Nash equilibrium, but as a dominant equilibrium under imperfect information.A Relaxation of the optimal aggregation problem.Let B ∈ {0, 1} J and the associated coalition B = {j ∈ [J] : B j = 1} be fixed. We present in this appendix a natural relaxation of problem Equation (10) which motivates the choice j∈B n ⋆ j (θ) = N = (n + 1)|B| 1 1+γ -1 in the simplified contribution scheme (B ⋆ , n ⋆ ). The optimal aggregation problem with B fixed ismaximize n ∈ R J → j∈[J] u j (B, n) subject to max j∈B n j -n(B, n) ⩽ 0 max j∈[J] -n j ⩽ 0 ,Since agents outside of the coalition maximize their utility, the problem can equivalently be stated as(T B ) : maximize n ∈ R |B| → j∈B u j (B, n) + ζ B subject to n ∈ Ξ B ,whereEQUATION)We start by rewriting (T B ) in a more convenient way. Instead of working with n ∈ R |B| + directly, we make appear (i) the total number of samples and (ii) the sharing out of samples between agents. Formally, for any n ∈ R u j (B, n) = j∈[J] B j [-a(R ⋆ 0 + ε(B, λN )) -cn j ] + j∈[J] (1 -B j )u j = -a|B|(R ⋆ 0 + ε(B, λN )) -cN + ζ B , = -a|B| R ⋆ 0 + 2 α δ (1 + N ) -γ + β + λ T θ -cN + ζ B = W B (λ, N ) .We denote by Ξ B = (λ, N ) ∈ ∆ |B| × R + : λN ∈ Ξ B and T B the problem:( T B ) : minimize (λ, N ) ∈ ∆ |B| × R + → -W B (λ, N ) subject to (λ, N ) ∈ Ξ B . (15)By definition, if (λ, N ) is a solution to T B , then n = λN is a solution to T B . We can further decompose T B by observing thatEQUATIONA strategy to solve Equation ( 16) is to (i) address the innermost problem min λ∈ Ξ B (N ) g(λ) with N ∈ N fixed, and denoting λ (N ) ∈ Ξ B (N ) its solution, (ii) solve the outermost problem:EQUATIONPoint (i) is done in the proof of Theorem 1. However, the resulting problem in (ii) is hard to tackle because λ (N ) has no simple form. Therefore, we leave aside the term g(λ (N ) ) (which can be easily controlled, as shown in Lemma 2) to determine N and only consider the problemEQUATION)Since f is differentiable and strictly convex, its minimizer is uniquely defined by f ′ ( N ) = 0, which gives N = (n + 1)|B|EQUATION)where n is defined in Proposition 1. As the solution of the relaxed problem (18), we take j∈[J] n ⋆ j (θ) = N is the simplified contribution scheme (B ⋆ , n ⋆ ). In many reasonable settings, this approximation is very satisfactory as shown by Lemma 2. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• 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 a 96% CI, if the hypothesis of Normality of errors 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 of range (e.g. negative error rates). • 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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: no 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 
 
 Appendix: Lemma 1. Assume H1 and H2.(i) Any agent j ∈ [J] picking the outside Option 1) obtains a modelg j ∈ G achieving R 0 ( g j ) ⩽ R ⋆ 0 + ε(θ j , n j ) with probability 1 -δ . (ii) Any coalition B ∈ {0, 1} J drawing n = (n 1 , . . . , n J ) ∈ R J + , samples obtains a model g B ∈ G achieving R 0 ( g B ) ⩽ R ⋆ 0 + ε(ϑ, N) with probability 1 -δ , where N is the total of samples and ϑ is the weighted average type within the coalition:EQUATIONProof. (i) Let {(X j 1 , Y i 1 ), . . . , (X j nj , Y j nj )} be n j > 0 i.i.d samples from P j ∈ P and g j = inf g∈G R j (g). First, observe thatEQUATIONLet υ > 0 and g υ j ∈ G such that R j g υ j ⩽ inf g∈G R j (g) + υ. Then with probability at least 1 -δ,EQUATIONwhere the last inequality holds taking the limit υ → 0 and using H 1. Finally, observing that and combining (20) as well as (21) yieldsinf g∈G R j (g) -R ⋆ 0 = inf g∈G R j (g) -inf g∈G R 0 (g) ⩽ sup g∈G |R j (g) -R 0 (g)| = θ j ,EQUATIONwith probability at least 1 -δ.(ii) Let B ∈ {0, 1} J and n = (n 1 , . . . , n j ) ∈ R J + . For any j ∈ B, let {(X j 1 , Y i 1 ), . . . , (X j nj , Y j nj )} be a collection of n j > 0 i.i.d samples from P j ∈ P. Denote by N = j∈[J] B j n j and consider λ = (λ 1 , . . . , λ J ) such that λ j = B j n j /N . Note that λ belongs to the J-dimensional simplex. For any g ∈ G , the empirical risk over contributions isEQUATIONand the population risk isEQUATION)One the one hand, the collaborative model g B ∈ G satisfies:EQUATIONEQUATIONwhere the first inequality comes from R B ( g B ) = inf g∈G R B (g) ⩽ R B (g υ ), and the last is obtained by taking υ → 0 and applying assumption H 1. Now, observe thatinf g∈G R B (g) -R ⋆ 0 = inf g∈G R B (g) -inf g∈G R 0 (g) ⩽ sup g∈G |R B (g) -R 0 (g)| ⩽ j B j λ j sup g∈G |R j (g) -R 0 (g)| = ϑ(B, n).Combining this observation with Equation (25) and Equation ( 26) gives with probability 1 -δEQUATION)Proposition 1. Assume H1 and H2. For any j ∈ [J], B -j ∈ {0, 1} J-1 and n -j ∈ R J-1 + , the optimal number of samples to draw under Option 1) is argmax n≥0 u j ((0, B -j ), (n, n -j ) ; θ j ) = n where n = (2ac -1 γα δ ) 1/(γ+1) -1 .Proof. For any j ∈ [J] and n ≥ 0, Lemma 1 gives that-u j ((0, B -j ), (n, n -j ), θ j ) = a[R ⋆ 0 + 2(α δ (n + 1) -γ + β + θ j )] + cn = f (n) .Since f is strictly convex and differentiable, it admits a unique maximizer n ⩾ 0 determined by f ′ (n) = 0. Simple algebra leads to n = (2aγc -1 α δ ) 1/γ+1 -1.Theorem 1. Assume H1, H2, H3. Problem (8) admits a unique solutionEQUATION)Proof. Recall that the optimal aggregation problem readsmaximize W (B, n) ∈ {0, 1} J × R J + → j∈[J] u j (B, n) (28) subject to min j∈[J] u j (B, n) -u j ⩾ 0 .Define for any j ∈ [J], B -j ∈ {0, 1} J-1 , and n -j ∈ R J-1 + , the maximum number of samples agent j ∈ [J] having B j = 1 may be asked given their participation constraint:n j (B, n) = max{n ⩾ 0 : u j ((1, B -j ), (n, n -j )) ⩾ u j } .Given Equation ( 5) and Proposition 1, we obtainEQUATIONwhereEQUATIONwhere B = {j ∈ [J] : B j = 1}. We first show that it admits a unique minimum.Fix a B ∈ {0, 1} J and consider problem (30) with respect to n ∈ R J + only. We call this subproblem T B . First, we show that it is enough to focus on (n j ) j∈B rather than(n j ) j∈[J] in T B . With n B = (n j ) j∈B and n B c = (n j ) j / ∈B , note that W (B, n) is decomposable in n B and n B c : W (B, n) = W (B, n B ) + W (B, n B c ) ,where, by a slight abuse of notationEQUATIONproblem T B is equivalent toEQUATIONby Proposition 1. Since j∈[J] -(1 -B j )u j is constant, by Equation ( 32) it is enough to focus on the existence of min n B ∈Ξ B -W (B, n B ). On the one hand, Ξ B is bounded. Indeed for any j ∈ B, by Equation ( 29) and Lemma 1n j (B, n B ) = n - a c [ε(B, n B ) -ε(θ j , n)] = n - a c R ⋆ 0 + 2 α δ (1 + n T B B) γ + β + ϑ(B, n) -R ⋆ 0 -2 α δ (1 + n) γ -β -θ j = n - 2a c α δ (1 + n T B B) -γ -(1 + n) -γ + (ϑ(B, n) -θ j ) ⩽ n - 2a c α δ 1 -(1 + n) -γ + max j∈B θ j = M (33) Thus, Ξ B ⊂ [0, M ] |B| .Moreover, Ξ B is closed and convex. For any j ∈ B, rewriten j (B, n B ) = n - 2a c α δ (1 + n T B B) -γ -(1 + n) -γ + n T B B -1 n T B θ -θ j = g j (n B ) ,and define h j : n B → n B,j -g j (n B ). Observe that Ξ B = {n B ∈ R |B| + : ∀j ∈ B, n B,j ⩾ 0 and h j (n B ) ⩽ 0}, that is Ξ B = A ∩ B with A = R |B| + and B = h -1 1 ((-∞, 0]) ∩ . . . ∩ h -1 |B| ((-∞, 0]). For any j ∈ B, h -1 j ((-∞, 0]) is convex, because so is h j . Additionally, h -1 j ((-∞, 0]) is closed as the inverse image of a closed set by a continuous function. It follows that Ξ B is convex and closed as the intersection of convex and closed sets.As a consequence Ξ B is compact and convex, and -W (B, • ) is strictly convex so T B admits a unique minimizer n opt B ∈ Ξ B . Since there are finitely many B ∈ {0, 1}J , min{-W (B, n opt B ) + j∈B c u j , B ∈ {0, 1} J } > 0 exists and coincide with the minimum of problem (30). We show later in the proof that the optimal B opt ∈ {0, 1} J is unique (see part 1), so the minimizer of Equation ( 30) is unique. This establishes the point (i) of the result.The remainder of the proof proceeds as follows: we first characterize the optimal B opt ∈ {0, 1}J , and then prove that the solution n optB opt ∈ R |B| + of T B opt has the form presented in point (ii) of the result. Part 1: Optimal B ∈ {0, 1} [J]We show that B opt = (1, . . . , 1) T . By contradiction, assume there existsEQUATION)Denote by j ∈ [J] an agent such that B ′ j = 0, and first assume θ j ⩾ ϑ(B ′ , n ′ ). Consider the alternative allocationEQUATION)where Ξ B is defined in (31). As explained in Appendix A, this problem can equivalently be stated asEQUATIONwhere-W B (λ, N ) = f (N ) + g(λ) , with f (N ) = aJ(R ⋆ 0 + 2α δ (1 + N ) -γ ) + cN and g(λ) = 2aJλ T θ , and Ξ B = (λ, N ) ∈ ∆ |B| × R + : λN ∈ Ξ B . Writing Ξ B (N ) = {λ ∈ ∆ J : (λ, N ) ∈ Ξ B } for N ⩾ 0 and N = {N ⩾ 0 : Ξ B (N ) ̸ = ∅}, T B comes down to min (λ,N )∈ Ξ B {f (N ) + g(λ)} = min N ∈N {f (N ) + min λ∈ Ξ B (N ) g(λ)} .In this proof, we address the innermost problem, which is enough to show that n opt satisfies the point (ii) of the result. Let N ⩾ 0 such that Ξ B (N ) ̸ = ∅, which exists because Ξ B ̸ = ∅ (for instance, ((1, 0, . . . , 0), (n, 0, . . . , 0)) ∈ Ξ B ). By definition of Ξ B , it readsEQUATIONThe following lemma provides a necessary condition for any solution to problem (45).Lemma 4. Let λ (N ) = (λ (N ) 1 , . . . , λ (N ) J ) ∈ ∆ J be a solution to (45). If there exists r ∈ [J] such that λ (N ) r > 0, then λ (N ) k = N -1 n k (B, N λ (N ) ) for any k < r. Proof. We denote by n(B, n) = (n 1 (B, n), . . . , n J (B, n)) T for any n ∈ R J + .The Lagrangian associated to problem (45), with µ, ρ and ν the associated dual variables, reads:L(λ, µ, ρ, ν) = 2aJλ T θ -µ T λ + ν 1 -λ T 1 + ρ T [N λ -n(B, N λ)] = 2aJλ T θ + cN -µ T λ + ν 1 -λ T 1 + ρ T (N λ -n1 + 2a c α δ (N + 1) -γ -(n + 1) -γ 1 + (λ T θ)1 -θ ) .Since the objective and the constraints are convex, L admits a saddle point (λ (N ) , µ, ρ, ν) ∈ ∆ × R J × R J × R which is solution to problem (45) and verifies the following KKT conditions:EQUATIONAssume there exists r ∈ B such that λ (N ) r > 0. By complementary slackness (47), µ r = 0, and (46) gives for any k < r:EQUATIONThat isρ k = 2aJ(θ r -θ k ) + µ k N + 2ac -1 θ k + ρ r N + 2ac -1 θ r N + 2ac -1 θ k .By assumption θ r > θ k , and since µ k ⩾ 0 as well as ρ r ⩾ 0, we have ρ k > 0. It follows from ( 48) for agent k that λ opt k N = n(B, N λ (N ) ).EQUATIONWe show thatEQUATIONTo prove the first point, assume by contradiction that there exists ℓ < L such that λ(N ) ℓ < n ℓ (B, λ (N ) N )N -1 . By the contrapositive of Lemma 4, λ opt ℓ+1 = . . . = λ opt J = 0. Thus k⩽J λ (N ) k = k⩽ℓ λ (N ) k ⩽ k⩽ℓ n k (B, λ (N ) N )N -1 = M ℓ N -1 < 1 ,by definition of L Equation ( 51) and ℓ < L. This violates the third constraint of problem (45).For the second point, assume there exists ℓ > L such that λ(N ) ℓ > 0. By Lemma 4, λ (N ) k = n k (B, λ (N ) N )N -1 for any k ⩽ L < ℓ, so k⩽J λ (N ) k ⩾ k⩽L λ (N ) k + λ (N ) ℓ = k⩽L n k (B, λ (N ) N )N -1 + λ (N ) ℓ = M L N -1 + λ (N ) ℓ ⩾ 1 + λ (N ) ℓ > 1 ,which once again violates the constraints of the problem. Finally by (52),EQUATION. By ( 52) and ( 53) we obtain for any j ∈ [J]:EQUATIONNow, consider the solution n opt (θ) ∈ R J to the initial problem (45), and define     N opt = j∈[J] n opt j (θ) λ opt (θ) = 1 N opt n opt (θ) L opt = min{j ∈ [J] : k⩽j n k (B, n opt (θ)) ⩾ N opt } .λ opt (θ) satisfies (54), and multiplying by N opt yields for any j ∈ [J]:EQUATIONwhich establishes point (ii), and concludes the proof.Corollary 1. Assume H1, H2 and H3. ThenL ⋆ = Θ(J 1 1+γ) and for any j ∈ [J],n ⋆ j (θ) = 1 {j≤L ⋆ } N L ⋆ + 2a c θ j - 1 L ⋆ L ⋆ ℓ=1 θ ℓ .Proof. By definition of the simplified scheme (12), n ⋆ j (θ) = 1 {j⩽L ⋆ } n j (1, n ⋆ (θ)) = 1 {j⩽L ⋆ } [n - (2a/c)(ε(1, n ⋆ (θ)) -ε(θ j , n))] for any j ⩽ L ⋆ . Since j∈[J] n ⋆ j (θ) = N , we get N = L ⋆ n - a c   L ⋆ ε(1, n ⋆ (θ)) - j⩽L ⋆ ε(θ j , n)   = L ⋆ n - 2a c α δ (1 + N ) -γ -(1 + n) -γ + (ϑ(1, n ⋆ (θ)) -θL ⋆ ) ,By Lemma 1 and denoting θL ⋆ = L ⋆-1 j⩽L ⋆ θ j . This yieldsϑ(1, n ⋆ (θ)) = θL ⋆ -α δ ((1 + N ) -γ -(1 + n) -γ ) + (c/2a)(n -N /L ⋆ ) .Plugging back this value in nEQUATIONWe now determine the order of magnitude of L ⋆ ∈ {1, . . . , J}. Recall on the one hand that by (33), there exists M > 0 such that 0 ⩽ n ⋆ j (θ) ⩽ M for any j ∈ [J], and on the other hand that θLEQUATION) Since N = (n + 1)|B ⋆ | 1 1+γ -1 and B ⋆ = [J], results in L = Θ(J 1 1+γ ).Lemma 2. Assume H1, H2 and θ j -θ j-1 = O(1/J) for any j ∈ {2, . . . , J}. Then,W (B opt , n opt (θ)) = W (B ⋆ , n ⋆ (θ)) + O(J 1 1+γ ) .Proof. Recall that for any admissible n ∈ Ξ B , we can define N = 1 T n and λ = N -1 n so that the social cost rewrites-W (B, n) = -W B (λ, N ) = f (N ) + g(λ) , with f (N ) = aJ(R ⋆ 0 + 2α δ (1 + N ) -γ ) + cN and g(λ) = 2aJλ T θ .By definition, j∈[J] n ⋆ j (θ) = N where N = (n + 1)J1 1+γ -1 = argmin N ⩾0 f (N ). Hence, W (B opt , n opt (θ)) -W (B ⋆ , n ⋆ (θ)) = W B (λ opt , N opt ) -W B (λ ⋆ , N ) = f ( N ) + g(λ ⋆ ) -f (N opt ) -g(λ opt ) ⩽ g(λ ⋆ ) -g(λ opt ) = 2aJ(λ ⋆ -λ opt ) T θ .Since θ j ⩽ θ L ⋆ for any j ∈ [J] such that λ ⋆ j > 0, and θ j ⩾ θ 1 for any j ∈ [J] such that λ opt j > 0:W (B opt , n opt (θ)) -W (B ⋆ , n ⋆ (θ)) ⩽ 2aJ(θ L ⋆ -θ 1 ) ,By assumption, for any j ∈ {2, . . . , J} θ j -θ j-1 = O(1/J) so there exists k j > 0 and R j ⩾ 0 such that θ j -θ j-1 ⩽ k j J -1 for J ⩾ R j . Denoting R = max j∈[J] R j and k = max j∈[J] k j , for any J ⩾ R we have θ L ⋆ -θ 1 ⩽ kL ⋆ , so:W (B opt , n opt (θ)) -W (B ⋆ , n ⋆ (θ)) ⩽ 2aJ kL ⋆ J = 2akL ⋆ , so W (B opt , n opt (θ)) -W (B ⋆ , n ⋆ (θ)) = O(L ⋆ ) = O(J 1 1+γ) by Corollary 1.Theorem 2 (Unravelling). Assume H1, H2, H3, and H4. Let E ⊂ S J be the set of pure-strategy Nash equilibria of the game induced by Γ. We have(i) E ̸ = ∅(ii) at any s ⋆ ∈ E , B = (0, . . . , 0) or B = (0, . . . , 0, 1) .Proof. First, we show that the situation where the coalition is empty is a Nash equilibrium. Consider s = ((0, †), . . . , (0, †)) ∈ S N . For any j ∈ [J] and deviation (1, θ j ), B = {j} so g B = g j and v j ((0, †), s ⋆ -j ) = u j ⩾ v j ((1, θ j ), s -j ) by Proposition 1. Thus, s ⋆ ∈ E . Now, consider a pure-strategy Nash equilibrium s ⋆ ∈ E such that B = {j ∈ [J] : B j = 1} ̸ = ∅. Denote by C = {j ∈ B : n ⋆ j ( θ) > 0} the set of contributors. We start with two technical lemmas: Lemma 5. There exists ∆ ∈ R such that for any(j, k) ∈ C 2 θ j -θ j = θ k -θ k = ∆ .Proof. To lighten notation, we write in this proofϑ( θ) = N -1 j∈C n ⋆ j ( θ) θ j and ϑ( θ) = N -1 j∈C n ⋆ j ( θ) θ j , where N = k∈C n ⋆ k ( θ) .By Equation ( 12) and H4, for anyEQUATION)Since s is a Nash equilibrium and u j = v j ((0, †), s -j ), we have in particular that2a θ j -θ j -ϑ( θ) -ϑ( θ) ⩾ 0 ,that is θ j -θ j = ∆ j ⩾ ∆ = ϑ( θ) -ϑ( θ) for any j ∈ C. We now show that this holds with strict equality for any j ∈ C. By contradiction, assume there exists r ∈ C such that ∆ r = ∆ + χ with χ > 0. Then∆ = ϑ( θ) -ϑ( θ) = j∈C λ ⋆ j ( θ)∆ j = j∈C\{r} λ ⋆ j ( θ)∆ j + λ ⋆ r ( θ)(∆ + χ) ⩾ ∆ + λ ⋆ r ( θ)χ > ∆ , because λ ⋆ r ( θ) > 0 as r ∈ C. This is a contradiction, and establishes the result.Lemma 6. For any j ∈ C, θ j = θ .Proof. Let j ∈ C, by (58):EQUATIONWe prove that v j ((1, • ), s -j ) is strictly decreasing in θ j for j ∈ C, by showing that ∂v j ((1, θ j ), s -ij )/∂ θ j < 0 For any j ∈ C. For v j to be differentiable, we need q j to be differentiable, that is λ ⋆ j ( θ) = ( k∈C n ⋆ k ( θ)) -1 n ⋆ j ( θ) to be differentiable for any j ∈ C. We re-index C as {i 1 , . . . , i |C| } so that θ i1 < . . . < θ i |C| . Observe that for 0 < h < δ for δ > 0 sufficiently small, θ ij-1 < θ j + h < θ ij+1 because θ ij-1 < θ j < θ ij+1 by Lemma 5 and H3. Hence, the bid ordering does not change for any infinitesimal variation d θ j > 0, nor does the indicator 1{i j ⩽ i |C| }. Consequently by Corollary 1, n ⋆ j ( θ) is differentiable in θ j and so is λ ⋆ ( θ). We have for any j ∈ C:EQUATION< 0 .(61) where we have used Lemma 5 at the third line. This impliesEQUATION)To see why, assume by contradiction that there exists j ∈ C such that s j = (1, θ j ) with θ j > θ. Then for any h ∈ (0, θ j -θ], by (61):v j ((1, θ j -h), s -j ) = v j ((1, θ j ), s -j ) - θj θj -h ∂v j ((1, t), s k ) ∂t dt > v j ((1, θ j ), s k ) ,which contradicts s being a Nash equilibrium.Combining Lemma 5 and Lemma 6 gives for any (j, k) ∈ C 2 : We now show that B = {J}. By contradiction, assume B = {j} with j < J. In particular, s J = (0, †). Consider a deviation s ′ J = (1, θ J ) with θ J ∈ Θ, so B = {j, J} under (s ′ J , s -J ). By Lemma 6, θ j = θ J = θ, so (58) rewrites:EQUATIONEQUATIONfor any k ∈ {j, J}. Since θ j < ϑ(B, n ⋆ ( θ)) < θ J by H3, we havev J ((1, θ J ), s -J ) > u J = v J ((0, †), s -J) , which contradicts s begin a Nash equilibrium. Hence, B = {J}. This concludes the proof.Lemma 3. There exists j ∈ [J] such that -t j ( θ) > 0.Proof. Let (B, θ) ∈ {0, 1}J × Θ N be an equilibrium of the game induced by Γ VCG . Since the VCG mechanism is strategyproof in dominant strategy, θ = θ. For any j ∈ [J], the VCG payment ist j ( θ) = k̸ =j u k ((0, 1 -j ), n ⋆ (θ)) - k̸ =j u k (1, n ⋆ (θ)) = W ((0, 1 -j ), n ⋆ (θ)) -W (1, n ⋆ (θ)) (I) -[u j ((0, 1 -j ), n ⋆ (θ)) -u j (1, n ⋆ (θ)) (II)] .Consider j ∈ {1, . . . , L ⋆ }. By the contribution scheme Corollary 1,u j (1, n ⋆ (θ)) = -a(R ⋆ 0 + ε(1, n ⋆ (θ))) -cn ⋆ j (θ) = u j = u j ((0, 1 -j ), n ⋆ (θ)), where we used in the third inequality that n ⋆ j (θ) = n j (B, n ⋆ (θ)). Thus, (II) = 0. Moreover by Theorem 1, W ((0, 1 -j ), n ⋆ (θ)) < W (1, n ⋆ (θ)) so (I) < 0. Thus, by (65) we have t j ( θ) < 0.Theorem 3. Assume H1, H2, H3, H4 and H5. B ⋆ = (1, . . . , 1) T is a Nash equilibrium under Γ with probability 1 -δ.Proof. Let B ⋆ = (1, . . . , 1) T , so the aggregator has at her disposal θ 1 , . . . , θ J .We first focus on the event under which θ j correctly approximates θ j for any j ⩽ J. DefineEQUATION) because P(E(δ)) = P(∩ j⩽J E j (δ)) = 1 -P(∪ j⩽J E j (δ)) ⩾ 1 -j⩽J P(E j (δ)) = 1 -Jδ,and setting δ ′ = Jδ leads to Equation ( 66). In what follows, we assume that E(δ/J) is true so | θ j -θ j | ⩽ η δ/J (q) for any j ∈ [J]. We denote by C = {j ∈ [J] : m j ( θ) = n ⋆ j ( θ + η j ) > 0} the set of contributors, and to lighten notations we writeϑ( θ) = N -1 n ⋆ ( θ + η j ) T θ = λ ⋆ ( θ + η j ) T θ and ϑ j ( θ) = N -1 n ⋆ ( θ + η j ) T ( θ + η j ) = λ ⋆ ( θ + η j ) T ( θ + η j ), where η j = η δ/J (q)1 -2δ j η δ/J (q), with δ j = (0, . . . , 0, 1, 0, . . . , 0) , for any j ∈ [J]. Note that ϑ( θ) is the actual weighted type within the coalition, whereas θ( θ) is the weighted type estimated by the aggregator. Consider first a contributor j ∈ C who is asked n⋆ j ( θ + η j ) > 0 samples. Their payoff under B ⋆ is vj (1, 1 -j ) = -a(R ⋆ 0 + ε(ϑ( θ), N )) -cn ⋆ j ( θ + η j ) = -a(R ⋆ 0 + ε(ϑ( θ), N )) -c n - a c ε( ϑ j ( θ), N ) -ε( θ j -η δ/J (q), n) = -a(R ⋆ 0 + ε(θ j , n)) -cn + a ε(θ j , n) -ε( θ j -η δ/J (q)) -ε(ϑ( θ), N ) -ε( ϑ j ( θ), N ) = u j + 2a θ j -( θ j -η δ/J (q)) -ϑ( θ) -ϑ j (θ) = vj (0, 1 -j ) + 2a(1 -λ ⋆ j ( θ + η j ))(θ j -( θ j -η δ/J (q))) -2a ℓ∈C\{j} λ ⋆ ℓ ( θ + η j )(θ ℓ -( θ ℓ + η δ/J (q))) ,and since E(δ/J) is true, θ j ⩾ θ j -η δ/J (q) and θ ℓ ⩽ θ ℓ + η δ/J (q) for any ℓ ∈ C \ {j}, soEQUATIONSecond, consider j / ∈ C who is asked q ⩽ n -2(a/c)( θ -θ) samples, and denote by r ∈[J] the agent such that θ r = max k∈C θ k . Observe that q ⩽ n ⋆ r ( θ + η r ), so vj (1, 1 -j ) = -a(R ⋆ 0 + ε(ϑ( θ), N )) -cq ⩾ -a(R ⋆ 0 + ε(ϑ( θ), N )) -cn ⋆ r ( θ + η r ) ⩾ u r ,where the last inequality comes from r ∈ C and (67). Since j / ∈ C, we have θ j ⩾ θ j -η δ/J (q) ⩾ θ r + η δ/J (q) ⩾ θ r so u r ⩾ u j , and it follows that vj (1, 1 -j ) ⩾ u j = vj (0, 1 -j ) .Proposition 2. Assume H1, H2 and H6. For any j ∈ [J] the estimatorθ ERM 0,j = sup g∈G | R j (g) -R 0 (g)| ,satisfies H5 with η δ (q) = α δ/4 (q + 1) -γ + (q ′ + 1) -γ + 2β .Proof. Let j ∈ [J] and g ∈ G , we haveEQUATIONwith probability 1 -δ/2 by H2, H1, H6, and a union bound. Similarly,EQUATIONwith probability 1 -δ/2. Combining ( 68) and ( 70) along with an union bound yields| θ ERM 0,j -θ j | ⩽ α δ/4 (q + 1) -γ + (q ′ + 1) -γ + 2β , with probability 1 -δ.Example 4. Assume H1, H2, H6 and H7.(i) Denoting R j -(g) = n -1 j nj i=1 ℓ 0,1 (g(X j i ), -Y j i ), we have θ ERM 0,j = 1 -inf g∈G R 0 (g) + R j -(g) .(ii) In H1, assume α δ = ln(1/δ) 1/2 , β = 2RAD(G ) and γ = 1 [Bousquet et al., 2003] . With θ ERM 0,j defined in Proposition 2, we haveη δ/J (q) = ln(4J/δ) 1/2 [(1 + q) -γ + (1 + q ′ ) -γ ] + 2Rad(G ) .Proof. (i) Let j ∈ B. Observe that under H7,we haveR j (-g) = n -1 j nj i=1 1{-g(X j i )Y j i < 0} = n -1 j nj i=1 (1 -1{g(X j i )Y j i < 0}) = 1 -R j (g) .Since the hypothesis class G is symmetric, we have • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.θ ERM j = sup g∈G R j (g) -R 0 (g) = sup g∈G R j (g) -R 0 (g) = sup g∈G 1 -R j (-g) + R 0 (g) = 1 -inf g∈G R j -(g) + R 0 (g) . (ii) Let j ∈ [J], we have η δ/J (q) = α δ/4J [(q + 1) -γ + (1 + q ′ ) -γ ] + 2β = ln(4J/δ) 1/2 [(1 + q) -γ + (1 + q ′ ) -γ ] + 2Rad(G38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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?
questions: 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?

- In H3, does the lower bound on $\theta_j$ need to be larger than $0$?

- 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: limitations: It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.
paper_summary: paper_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.
The 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. 
The authors formalize this problem and analyze it trough a series of results:

(1) they model the above mechanism in which each agent i can sample data points with quality \theta_i

(2) they show how a benevolent social planner can maximize the overall utility for all agents if she knows all \theta_is

(3) they formalize the strategic setting in two cases and ask whether unraveling may occur:

- 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. 

- 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. 

I 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.
strength_weakness: strength_weakness: - hard to follow all details
questions: questions: I didn't understand the subsection about VCG mechanism. What is it and why it is not available in your framework?
limitations: limitations: The authors have discussed the future directions in the conclusion.
paper_summary: paper_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.  

Authors propose a probabilistic verification-based mechanism to make optimal collaboration as Nash Equilibrium with high probability.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: As authors proposed by the authors, it would have been better if agents learned their types themselves in an online fashion.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
-  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'$.
- The notation is confused, i.e., $\underline{n}$  is used to denote an expression of $\arg\max_{n}\cdots$.
questions: 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?
- 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?
- Is the selection of $\eta_{\delta}$ in proposition 3 optimal?
limitations: limitations: I do not foresee any negative societal impact from this paper. For other limitations, please see the questions and weaknesses sections.

Comments: comment: Thanks for the clarifications.
I have updated the review and rating.
Thank you for your response and I will keep my rating.
We deeply thank the reviewer for having updated their evaluation, and we will make the necessary changes in the VCG session as per explained in our response.
I agree that the complicated notation is somewhat necessary for presenting all the technical results. I think that VCG section should be either removed or something should be added there. At the current form it is not adding anything to the paper. Given that the authors make this change, I am updating my score to an accept.