Unravelling in Collaborative Learning

We thank the reviewer for their feedback, and answer their questions below.

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

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

"The empirical implementation of the mechanism in section 4.2 requires hypothesis 7, which may not be feasible in practice...$.

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

"The notation is confused..."

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

"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?"

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

"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?"

We refer the reviewer to our reply to the mentioned weakness.

"Is the selection of $\eta_{\delta}$ in proposition 3 optimal?"

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

We hope that we replied to the reviewer's concerns, and would be happy to answer any additional question.

---

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

[19] Hendren, N. (2013). Private information and insurance rejections. Econometrica, 81(5), 1713-1762.

[20] Pinson (2023), "What may future electricity markets look like?", Journal of Modern Power Systems and Clean Energy 11

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.

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

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

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

An alternative procedure, which may be closer to what the reviewer has in mind, would be to:

1. ask agents to declare a type,
2. estimate actual types based on the provided samples,
3. design penalties for agents with declared types which are not aligned with the estimation made in step (2) (for instance, through accuracy shaping).

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

"Also, experimental verification isn’t provided."

If 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:

• provide a figure illustrating the socially optimal allocation,
• compare the optimal allocation with the one induced by the mechanism $\hat{\Gamma}$,
• empirically verify that the strategy profile $(1,\ldots,1)$ is a Nash equilibrium under the mechanism $\hat{\Gamma}$.

"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?"

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

"As authors proposed by the authors, it would have been better if agents learned their types themselves in an online fashion."

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

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

---

References
[11] Green, & Laffont (1986). Partially verifiable information and mechanism design. The Review of Economic Studies, 53(3), 447-456.

[12] Grossman (1981). The informational role of warranties and private disclosure about product quality. The Journal of law and Economics, 24(3), 461-483.

[13] Lacker, & Weinberg (1989). Optimal contracts under costly state falsification. Journal of Political Economy, 97(6).

[14] Karimireddy, Guo, & Jordan, (2022). Mechanisms that incentivize data sharing in federated learning. arXiv preprint.

[15] Huang, Karimireddy, & Jordan (2023). Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning. arXiv preprint.

[16] Ananthakrishnan, N., Bates, S., Jordan, M., & Haghtalab, N. (2024, April). Delegating data collection in decentralized machine learning. PMLR.

[17] Laffont, J. J., & Martimort, D. (2009). The theory of incentives: the principal-agent model. In The theory of incentives. Princeton press.

We thank the reviewer for their feedback, and are glad that they find our result interesting. We answer to their questions and remarks below.

"Weaknesses: hard to follow all details."

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.

"I didn't understand the subsection about VCG mechanism. What is it and why it is not available in your framework?"

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

---

References
[7] Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1), 8-37.

[8] Clarke, E. H. (1971). Multipart pricing of public goods. Public choice, 17-33.

[9] Groves, T. (1973). Incentives in teams. Econometrica: Journal of the Econometric Society, 617-631.

[10] Roughgarden, T. (2010). Algorithmic game theory. Communications of the ACM, 53(7), 78-86.

We thank the reviewer for their positive feedback, and try to address the points they raised below.

"In the proposed frameworks, the utilities of the clients are evaluated based on upper bounds on the loss..."

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

"If I interpret equation (8) correctly, currently the problem that the server solves..."

We deeply thank the reviewer for this remark, which unveils a typo in the formulation of problem (8). The correct formulation should be

$$\begin{aligned} &\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})\\ &\text{subject to}\quad \min_{j\in [J]}u_{j} ( \mathsf{B}, \mathbf{n})- \underline{u}_j \geq 0. \end{aligned}$$

We will correct this typo in the revised text accordingly.

"It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context."

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

"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?"

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

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

For any $j \in [J]$, $\theta_j$ needs indeed to be non-negative, because by definition: $\theta_j = \sup_{g\in\mathcal{G}} \mid\mathcal{R}_{j}(g)-\mathcal{R}_0(g)\mid \geq 0.$ Note that nothing prevents from $\underline{\theta} = 0$, so an agent can have access to the target distribution $P_0$ in our framework.

"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?"

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

[1] Huang, Karimireddy, & Jordan (2023). Evaluating and Incentivizing Diverse Data Contributions in Collaborative Learning. arXiv preprint arXiv:2306.05592.

[2] Karimireddy, Guo, & Jordan (2022). Mechanisms that incentivize data sharing in federated learning. arXiv preprint.

[3] Ananthakrishnan, Bates, Jordan, & Haghtalab (2024, April). Delegating data collection in decentralized machine learning. In International Conference on Artificial Intelligence and Statistics. PMLR.

[4] Zhang, Zhang & Ye (2012). Generalization bounds for domain adaptation. Advances in neural information processing systems, 25.

[5] Konstantinov, & Lampert, (2019). Robust learning from untrusted sources. In International conference on machine learning. PMLR.

[6] Ben-David, Blitzer, Crammer, Kulesza, Pereira, & Vaughan, (2010). A theory of learning from different domains. Machine learning, 79.