Incentivizing Honesty among Competitors in Collaborative Learning and Optimization
Authors: Florian E. Dorner
Nikola Konstantinov
Georgi Stoyanov Pashaliev
Martin Vechev
Venue: NeurIPS 2023 poster (2023)
Keywords: Game Theory
Federated Learning
Optimization
Strategic Behavior
Economics
Mechanisms

Abstract: Collaborative learning techniques have the potential to enable training machine learning models that are superior to models trained on a single entity’s data. However, in many cases, potential participants in such collaborative schemes are competitors on a downstream task, such as firms that each aim to attract customers by providing the best recommendations. This can incentivize dishonest updates that damage other participants' models, potentially undermining the benefits of collaboration. In this work, we formulate a game that models such interactions and study two learning tasks within this framework: single-round mean estimation and multi-round SGD on strongly-convex objectives. For a natural class of player actions, we show that rational clients are incentivized to strongly manipulate their updates, preventing learning. We then propose mechanisms that incentivize honest communication and ensure learning quality comparable to full cooperation. Lastly, we empirically demonstrate the effectiveness of our incentive scheme on a standard non-convex federated learning benchmark. Our work shows that explicitly modeling the incentives and actions of dishonest clients, rather than assuming them malicious, can enable strong robustness guarantees for collaborative learning.

Incentivizing Honesty among Competitors in Collaborative Learning and Optimization
Florian E. Dorner
Nikola Konstantinov INSAIT, Sofia University
MPI for Intelligent Systems, Tübingen ETH Zurich
nikola, konttaatiiinnoniisattt......
florian dow.erruueiinnnnnnn.mmmmmmm mpg. de
Georgi Pashaliev Sofia High School of Mathematics
Martin Vechev ETH Zurich
martin. ethz.. ch
Abstract
Collaborative learning techniques have the potential to enable training machine learning models that are superior to models trained on a single entity's data. How- ever, in many cases, potential participants in such collaborative schemes petitors on a downstream task, such as firms that each aim to attract customers by providing the best recommendations. This can incentivize dishonest updates that damage other participants' models, potentially undermining the benefits of collaboration. In this work, we formulate game that models such interactions and study two learning tasks within this framework: single-round mean estimation and multi-round SGD on strongly-conver objectives. For a natural class of player actions, we show that rational clients are incentivized to strongly manipulate their updates, preventing learning. We then propose mechanisms that incentivize honest communication and ensure learning quality comparable to full cooperation. Lastly, we empirically demonstrate the effectiveness of our incentive scheme on standard non-convex federated learning benchmark. Our work shows that explicitly mod- eling the incentives and actions of dishonest clients, rather than assuming them malicious, can enable strong robustness guarantees for collaborative learning.
com-
Introduction
Recent years have seen an increased interest in designing methods for collaborative learning, where multiple participants contribute data and train a model jointly. The premise that the participants will then be able to obtain better model than if they were learning in isolation. Most prominently, federated learning (FL) (Kairouz et al. 202T) provides method for training models distributed manner, allowing data to stay with institutions, while still harvesting the benefits of collaboration.
An underlying premise for the success of collaborative learning schemes is that the participants contribute data (or gradient updates) relevant to the learning task at hand. However, when participants in competition on some downstream task, they may have an incentive sabotage other participants' models. For instance, firms that are competing on the same market can often improve their machine learning models by having access their competitors's data, but the same time will likely benefit from a gap between the quality of their models and those of other firms.
These conflicting incentives raise concern that collaborative learning may be vulnerable to strategic updates from participants. Previous work has empirically demonstrated that irrelevant or malicious updates can negatively impact collaborative learning (Tolpegin et al. 2020 Kairouz et al. 2021 In
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

particular, if subset of participants is modeled as cully-malicious (Byzantine) agents, that collude in a worst-case manner, it is known that optimal convergence rates contain leading-order term that is based on the fraction of Byzantine agents and is irreducible as the number of players increases Yiin et al. 2018 Alistarh et al., 2018). This suggests that collaborative learning the presence of strategic behavior may often not provide asymptotic benefits over learning with one's own data.
Contributions In this work, we study collaborative learning in the presence of strategic behavior by explicitly modeling players' competitive incentives. We consider a game between multiple players that exchange updates via a central server, where players' rewards increase both when they obtain a good model for themselves, and when other players' models perform poorly.
We study two important instantiations of this collaborative learning game: mean estimation with a very general action space and strongly-conse stochastic optimization with attacks that add gradient noise. We show that players are often incentivized to strongly manipulate their estimates, rendering collaborative learning useless. To remedy this, we suggest mechanisms inspired by peer prediction (Miller et al. 2005). that penalize cheating players using side payments. Our results on stochastic optimization rely
novel recursive bound for the squared norm of differences in SGD-iterates between a clean trajectory and a strategically corrupted trajectory. Meanwhile, we show that side payments can be avoided in the mean estimation case, using a novel communication protocol in which the server sends noisy estimates back to players that are suspected of cheating. Our mechanisms are solely based on observable player behaviour, and recover near-optimal convergence rates at equilbrium. Furthermore, expected payments cancel out when all players are honest, so that players are incentivized to participate in the training. rather than use their own data only, despite the penalties.
Finally, we conduct experiments on the FeMNIST and Twitter datasets from LEAF (Caldas et al., 2018) and demonstrate that our mechanisms incentivize honesty for realistic non-convex problems
Related work
Game theory and collaborative learning Many works that study connections between FL and game theory focus on clients' incentives to participate in the training process at all (see Tu et al. (202T) for a recent survey, Graddoohl & Tennenholtz to competition). Similarly,Karimiredde et al. (2022) study incentives for free-riding, i.e. joining collaborative learning without spending resources to contribute data. In contrast, our setting covers clients that strategically manipulate their updates in order to damage other participants' models.
(2022) for an analysis of how this relates
Another line of work studies FL as coalitional game theory problem, in which the players need to deal with potential issues of between-client heterogeneity by deciding with whom to collaborate
Donahue & Kleinberg (2021a b). Optimal behavior under data heterogeneity is also studied by Chayti et al. (2021). ). while Gupta et al. (2022) studies invariant risk minimization games in which FL participants learn predictors invariant across client distributions. In contrast, we study FL as non-cooperative game and seek to address strategic manipulation, rather than data heterogeneity.
Robustness in federated learning The robustness of FL. to noisy or corrupted updates from clients has received substantial recent interest, see (Shejwalkar et al. (2022) for recent overview. One line of work studies federated learning in the context of various data corruption models, e.g. noise or bias towards protected groups (Fang & Ye, [022] /Abay et al. 2020). In contrast, we study strategic manipulation by clients as the source of data corruption.
Clients attacking the training are typically modeled as Byzantine (Blanchard et al. 2017; Yin et al., 2018 Alistarh et al.) 2018), adversarially seeking to sabotage training by deviating from the FL protocol in worst-case manner. The goal of Byzantine-robut learning is to achieve guarantees in that setting. Similar models have been studied in a statistical context, where data is stored at a single location and communication is not concern (Qiao & Valiant 2018 Konstantinov et al.) 2020). In contrast to these works, we model manipulation as a consequence of competitive incentives rather than maliciousness and analyze client behaviour using game theory (Osborne & Rubinstein 1994). Rather than focussing on robustness to manipulations, we aim to prevent manipulation alltogether.
Peer prediction mechanisms Our mechanisms for inducing honesty are closely related to peer prediction that aims to incentivize honest ratings on online platforms. In their seminal paper,

---

Miller et al. (2005) suggest paying raters based on how much their rating helps to predict other raters' ratings. While they require a common prior shared by all raters and the mechanism designer. Witkowski & Parkes 2012) extend their results relaxing that assumption. Closely related to our work, Cai et al. (2015) suggest to incentivize crowdworkers to produce accurate labels by paying them more, the better their label gets predicted by model estimate from other workers' data. Meanwhile, Waggoner & Chen (2014) prove that peer prediction elicits common knowledge, rather than truth from participants. Lastly, while Karger et al. (202I) find that peer prediction can elicit subjective forecasts of similar accuracy as scoring based on the ground truth, Gao et al. (2014) demonstrate that human raters can end up with dishonest strategies despite the existence of honest equilibria.
3 Competitive federated learning
In this section, we present our framework on high level and explain how it models competitive behaviour in FL. In this generality. however, it is impossible to analyze the problem quantitatively. We therefore define specific instantiations of the framework, which we study for the rest of the paper.
3.1 General framework
Overview
Throughout the paper, we assume that there are N 2 2 players, who each have a private dataset. The players participate in an FL-like procedure, which takes place over multiple rounds and requires them to send messages with information relevant to update a centrally trained model at every step. In our setup, players act strategically and competitive pressures might incentivize them to try to corrupt other players' models. This is done by manipulating updates sent to the central model, while simultaneously keeping track of an unmanipulated private (presumably more accurate) model.
To model the participants' strategic interactions, we need to define a game by specifying their action spaces and rewards. To this end, one needs to specify: their attack strutegies, that describe whether and how they will corrupt their messages to the server; their defense strategies, which describes how they postprocess the server's 's updates defend themselves against others' manipulations; and their rewards, in a way that reflects the quality of learning and the competition between them. Given these components, are interested in the Nash equilibria of the corresponding game, in order to understand strategic behavior in FL and how affects the quality of the players' models.
Formal setup We denote the samples of each player i by z' = (xi.... z where z E X. and assume that {aj distribution D P(2)). For simplicity, we assume that all players have an equal number of samples n. Players communicate via an FL-like protocol, through which central server model 0= Rd is updated. The intended goal of this procedure is to find a value for 0 that minimizes a loss function (0). Note that because D is unknown to the players, they can benefit from honest collaboration.
[N]. E [n]} are not necessarily independent samples from an unknown
The protocol consists of T rounds and the central model is initialized at some 0f E Rd. At time t = 1,,,.... T the server sends the model Bj to all participants. Each agent i is then meant to send an update gr (0;, x²) the server, for some function ge Rd x X - Rd For example, in the standard FedSGD setting, (0) Ezeplf.. (f, for functions fx: R + R and g = 1, Σ3 Vf (0:) serves as an estimate of the gradient of f evaluated at the data of player i. Each player then sends a message mi Rd to the server (which may or may not be equal to gr (0,,x') Finally, the server computes new model 1 = Agg (i, m. ..... . via an aggregating function Agg Fd x R Nxd + Rd
(for example, in FedSGD this will be gradient update computed as m. = 1 Σ mQ).
Players' strategies At every step, the players take two decisions: how to attack by sending a manipulated estimate the server, and how to defend themselves from unreliable estimates when updating their locally tracked model based on information received from the server. Formally, we assume that each player i E [N] chooses (potentially randomized) functions aj ag. .... dy and di...., di that describe their behavior for the attack and defense stages at every time step. These functions are chosen from two respective sets of possible actions s and D. The tuple of chosen actions Dd (af...., .., ot,, di ... dl)) E of -" represents the player's global strategy.
In the most general case, the attacks and defenses of each player i may take into account all information available to the player, throughout the history of the optimization process. At time this
3

---

include the models oj.... or received by the server, the local models ..... of the player kept at ......,, previous iterations; the attack strategies af .i.....e. a; used up time (e.g. to correct for one's own ., faulty estimate at time 1); as well as additional randomness .i.....5 sampled at each round.
Players' rewards Each player aims to obtain a final model 0++ that approximately minimizes Jo (0)+)) Crucially, their reward also depends on other players' models. Specifically, we assume that each player has a reward function Ri IR Nxd xd x p(()) - IR and receives the reward
= R2 (0++1: O7 O ,0 D)
Note that the messages m² sent by players and thus 07-1 and each player's reward depend not only on players' strategies, but also on the particular realization of their samples x². We thus focus on expected rewards, averaging out the effects of particular realizations of players' samples and randomness in their strategies. We study the vector of expected rewards E(r ((......,,." ,.N) and its dependence on the strategy profile, that is on the distribution of strategies = (p' p ,.. chosen by each player.
Assumptions on players' behaviour To analyze players' behaviour, we make two assumptions, giving rise to classic game-theoretic setup. The first is that players seek to maximize their expected reward, as defined above, i.e. players are rational. In addition, since the reward of each player depends on the actions of the other players, players account for the actions of the others, which means that their behavior is strategic. A natural solution concept in this context is the Nash equilibrium (Nash] 1951). This describes a strategy profile in which no player can improve their reward by unilaterally changing their strategy. In our case, this classic notion translates to the following definition.
=p-" Definition 1. Let p = (p',p², .r....,.,... ,.. E (P(al x xTT) N be a strategy profile. Then is a (mixed) Nash equilibrium if:
Vp" E P( x "²) and Vi [M] E (r'(p),.....)
)²) E (p''p",.. ......
where the expectation is taken with respect to the randomness of the data and the players' strategies.
3.2 Specific instantiations: mean estimation and stochastic gradient descent
We study two specific cases of the game, each modeling a fundamental learning problem. The first single-round mean estimation (Sections 4 and 5). which correspond to the general setup with T= 1, (0) ||0 n1|2,, where μ = E x ()) ). and the updates g being the sample means of the players. The second multi-round stochastic optimization of strongly-convex functions (0) via SGD (Section 6.. in which case the updates g stochastic gradient estimates based players' data. In the corresponding sections, we define natural rewards that model the competing incentives.
Strategy spaces To describe the attack strategies, in both cases we model attacks that send a noisy update gr (0;, x²) + fj, for normalized zero-mean noise E and an attack parameter of E IR, to the server. Up to certain magnitude of a², these attacks have natural interpretation as the act of hiding a random subset of a player's 's data. addition, the at parameters have a natural interpretation as the of aggressiveness of the player. In the case of mean estimation, more general attack strategies that can adjust a; based on the players' samples x² and additionally allow for adding directed bias to the communicated messages.
also able to analyze much
For the defense strategies in the mean estimation case, we consider a defense strategy that corrects the mean estimate received from the server for the player's own manipulation. The player then computes a weighted average of the result and the their local mean. The weighting parameter 3 used then has natural interpretation as the cantiousness of the player. In the SGD case we directly provide mechanisms that incentivize honesty at the attack stage, making potential defenses redundant.
single-round version of the game: competitive mean estimation
In this section analyze single-round version of the game, in which players aim to estimate the mean of a random variable X E P(R)). Specifically, we consider the game defined in Section 3 in the case of = 1 rounds. Players sample from distribution D P(Rd) by first independently sampling random mean μ4 Dj and "variance" of == E|| pill Do (this models potential

---

heterogeneity between clients), and then receiving (conditionally) independent samples from random variable X" with mean μi; and "variance" of. We call μ EE,, o² Eo? and o = Bll p. 11. We assume that players do not know the distributions D2 and Da.
Each player wants estimate the global mean l as well possible. During the single communication round, the players are meant to communicate the mean of their samples: (0f, = - zy.. Instead, they send messages mi. The server aggregates the received messages by averaging them, so that 0 = \
N Σ mi. The players then receive the value of 8g from the server and use their defense strategy to arrive at a final estimate 0- = d(0š; .r") of the mean. For simplicity of notation, we ignore the dependence of all values on the time 1 in the rest of this and the next section.
Reward functions To model competitive incentives, the reward of each player needs to increase as their own estimate of the mean becomes better, and as the estimates of other players become worse. Therefore, a natural reward function is:
10 1 ml1
..... 0% n)) R'.0'....,,0"
111 -ul?,
for some X; 2 O. The value of X; quantifies to what extent player prioritizes the quality of their own estimate over damaging the estimates of the other players.
Attack strategies We assume that players choose what estimates to communicate by deciding how to perturb the empirical mean of their data. Specifically, each player selects parameters a (xx') N 0, 1' (xx)) IRd based on their sample, in potentially randomized manner, and communicates:
m² = x' + (x'x=)) + bxx'),
(3)
where F'' = Eド Eig"| = 0 and 1| 1. Here ø' is the standard empirical mean of x', while a' represents the magnitude of the noise player adds to the estimate and 6 (x*) is an additional bias term. Note that the case of 6 (z²) 0 recovers the data-hiding attack discussed in Section 3.2
In order to prevent "non-general" strategies, such simply setting m² μ., that cannot be analyzed properly as their success depends on the true parameter μe, we assume that players do not base their strategies on guesses about j beyond the information they obtained from x². Formally, we assume
E < L - μ. ((') >= O.
(4)
This prevents b² from linearly encoding additional knowledge about and for example holds whenever 69 (x²) is independent of the residuals z² fs. We also assume that the noise variables g are independent of each other and all æ² and & (a="), but make further distributional assumptions about go. Indeed, all of our theorems will hold regardless of any additional assumptions about g².
We denote this set of attack strategies as a Each element in af can be uniquely identified via the distribution of the noise Ç and the functions a (x") and 6' b'(x²). As covering the fully collaborative case, while a, + co covers the fully malicious case, the (adaptive) parameters a, have natural interpretation as measures of the aggressiveness of player.
0 can be interpreted as
We also note that these attacks are very general: m m'(x') ) - H² can always be written as the sum of a determinstic component b(x²) and zero mean noise {(x'), such that (4) and the fixed distribution of ç are the only assumptions separating us from the most general possible set of attacks strategies.
Defense strategies In the defense stage each player uses the received estimate 0= = 17t N. treme approaches for player i are being fully cautious and using their local mean z only, or fully trusting other players and computing the average of all sent updates, corrected for their own manipula- tion, that is m N (NO* mn + )²). We consider defense strategies that take a weighted average of these two extremes: Each player i chooses parameter 3 E [0, 1] and constructs a final estimate
1 E m² and their local data x' to compute a final estimate of the unknown mean. Two ex-
(5) Denote the described set of defenses, as 2. Each element in 2 is uniquely identified via the corresponding parameter 3 with B = 0 and 3 covering the extreme cases from above. Since can be used to interpolate between these two extremes, it can be seen measure of cautiousness.
0¹ = (1 - 3 m'm + .
5

---

We do not cover more complicated defense strategies for two reasons: First, our proposed mechanisms will incentivize players to be honest even without any defenses such that more advanced defense mechanisms are not necessary. Second, as defenses can be seen as method for mean estimation, analyzing the optimality for general classes of defenses would be fundamentally challenging for d 2 3 due to Stein's ' Paradox (Stein 1956), even for a single player version of our game.
4.1 Expected rewards and Nash equilibria
We now analyze the game with strategy set (e/ x 2). As the specific distribution of & does not affect the players' rewards, the attack and defense strategies are for all relevant purposes uniquely determined by the functions a, b, and respectively. We abuse notation and consider (a* b² ,3*) as the strategy of player i. First we derive a formula for the MSE of a player, for a fixed strategy profile.
Theorem 4.1. Let D be described above. Then the expected mean squared error (MSE) of player i [Nr any strategy profile ((a) ,,,,",.. (..)....,(0)) (oN, ,,N, ,Ba)) (ed x B)x is:
o²
o
E (110' -mll²) (1 (1-
Σ
B(a2
El
[
Nn
N
N²
N
jti
jti
(B)) ( + o.) + 2
3d
3
This is proven in Appendix similar to the varianari decomposition. This result allows to analyze the expected rewards defined by equation 22) of the players for any strategy profile.
One can immediately see that there is no incentive for players to cooperate as long as , < 1: other players can always increase their reward by increasing E[aa (I )²) (unless it is already infinite). But for finite E(a' (x') )²) and El| Eز 6 (x') the optimal ( can be shown to never equal one, such that equilibria are only possible at infinity":
Corollary 4.2. The game defined by the reward in equation 2 and the set of strategies st x 2 does not have any (pure or mixed) Nash equilibrium for which (( (x))²) and El (x*) )l} are finite for all players.
For details, see Appendix C This shows that our defenses are unable prevent maximal dishonesty by at least some players and formalizes simple intuitive observation: as long as a player considers other players' updates at all, others are incentivized reduce the information their updates convey about their samples. As at equilibrium at least one other player will infinitely distort the server estimate m, no player can benefit from collaborative learning without modifications to the protocol.
5 Mechanisms for incentivizing honesty
Given the impossibility of successful learning with rational competing agents in the simple mean estimation setting, shift focus to modifications of the protocol that allow for honest Nash equilibria (that is, equilibria where a (xxz) = 6 (x²) 0, Vj). To this end, we design two mecha- nisms that seek to penalize dishonest players proportionally to the magnitude of their manipulations (and, thus, the damage caused to other players). Note that this is complimentary to robust estimation methods (Diakonikolas al. 2019 that can reduce but not eliminate the impact of manipulations.
The first relies on explicit side payments and requires transferable utility (that is, the existence of an outside resource R such as money, that is valued equally and on the same scale as the reward R by all players). The second is a modification of the FL. protocol, in which the server adds noise to the estimates it sends players that have sent suspicious updates. Importantly, for both mechanisms, the penalties can be computed by the server without the need for knowing a', D' or other additional information beyond the players' updates, and without prior knowledge of the true distribution D.
5.1 Efficient solution for fully transferable utility
We first consider the case of transferable utility. In this case, we introduce a more general penalized reward for player i, which is given by
R2 R$ (0) ..... ON .1) p'mm ...., m

---

Here p'mm'.... .m.m )) denotes penalty paid by player to the server, measured in terms of the resource R and depending on the messages that the clients sent. As players value the reward and resource equally, they optimize for R instead of R'.
Inspired by peer prediction (Miller al. 2005)) we consider a penalty for player proportional the squared difference between that player's update and the average update sent by all players:
p² (m=....,,m) mx) = C'Ilm' - ml]
(6)
for some constant C 2 O. This is a natural measure of the "suspiciousness" of the client's 's update. In order prevent excessive payments for honest players, redistribute the penalties as
C'lmm mll? -
p'(m' ,...,, m = ClIm² mll?
This redistribution also makes it possible to implement our mechanism in a decentrally with messages sent publically, if players are able to credibly commit to the implied payments to other players.
Theorem 5.1 establishes that this penalty can incentivize full honesty for the right choice of C:: Theorem 5.1. the setting of Theorem 4. for the penalized game with rewards
Rig E 100
pl
x1100' - mul2-p''(m
N
the strategy profile ae = b 30 = O for all j is a Nash equilibrium, whenever C (N-1Y-1 and maximizes the sum of all players' rewards among equilibria whenever X 2 for all players.
At this equilbrium, the expected penalty p'mm².... ...,, mm player is incentivized to participate in the penalized game rather than relying on their own estimate, whenever N 2, the other N players participate at the honest equilibrium, and X (N (1-
paid by each player is equal to O. Each
Intuitively, our incentive mechanism is effective because at and be only affect the first term of the original reward of player (equation 2). as well as the penalty, to which they contribute at most as and (1- C respectively. At the honest equilibrium every player's MSE is in O( / such that for large N a player can strongly improve their own error by joining the collaboration, while barely affecting others' errors. For complete proof consider Appendix D.I
Theorem 5. shows that our mechanism fulfills two desirable properties: (budget) balance and (ex-ante) individual rutionalit//olluntay participation (Jackson 2014). The first property means that the server neither makes a profit nor a loss. The second holds as long as A > (N-1)z and the other players take part in the optimization, and means that a player will receive better reward at the game's ' equilibrium, than when learning with their own data, despite the penalties assigned by the server. While non-honest equilbria exist, these are difficult to coordinate on (as they lack the natural symmetric Schelling point of honesty), while also yielding less total reward summed across players than honesty, such that there is no strong incentive for such coordination.
5.2 Non-transferable utility
We now discuss a way to achieve similar results in the case of non-transferable utility, where players' rewards are not translatable to monetary terms. Instead of modifying players' reward function, we modify the FL protocol, altering the server's messages to players. This effectively results in a robust learning algorithm that the server can implement. We do so by letting the server send noisier versions of its mean estimate to players whose messages suspiciously deviate from the average of all players' updates. The penalization scheme is designed in a way such that players receive expected rewards E(R') similar the expected penalized rewards E(R;, in the previous section. This conceptually similar to methods against free-riding (e.g. Karimireddy et al. (202)), which often tie the accuracy of the model client receives in an FL. setting to the client's overall contribution model training.
Theorem 5.2. Consider the modified game with reward R = Ei 1101 100--p0 >x - ==ll; where N-1
player receives an estimate mn + /Ce I|mm - mll for independent noise e with mean Red and "variance" 2| 1. instead of the empirical mean m. from the server. Then honesty
7

---

0,'' c++) is Nash equilibrium, as long as C' X-N-I1=-1 and A > (N-1)2- Furthermore, honesty maximizes the sum of all players' rewards among equilibria whenever X 2 1 for all players.
For fixed X k, 1 and C -XN-IP=-1 IE =11)=
and players are incentivized to participate in the penalized game rather than relying on their own estimate, whenever N 2, the other N players participate at the honest equilibrium and 2 1.
Essentially, the noise added by the server increases the expected MSE for player i by C mll. producing similar incentives as in Theorem 5.1 Theorem 5.2 is proven in Appendix D.2 We obtain voluntary participation at least two other players participate at the honest equilibrium and À >
The benefits of modeling clients' rationality Note that at the equilibrium, players' MSEs are of the same order as if all clients honestly communicated their sample means. In particular, when (i.e. homogeneous clients), this is in contrast to known negative results for worst-case poisoning attacks Qiao Valiant (2018) and single-round Byzantine robustness AAlistarh et al. (2018) this sense, our modified protocol acts as robust and efficient collaborative learning algorithm. This is possible because our data corruption model is derived by explicitly modeling clients' incentives.
Beyond mean estimation: stochastic gradient descent
We now extend the ideas from the last section to multi-round collaborative Stochastic Gradient Descent (SGD) in the Fl. setting. We show that under stronger assumptions, mechanisms similar to those described in Section 5. can still provide arbitrary bounds manipulations by rational players. Again, this is complimentary to methods for robust federated learning such as median-based gradient aggregation that can reduce but not eliminate the impact of existing manipulations.
6.1 The game and rewards
We consider a T-round version of the game described in Section The FL protocol is designed to minimize a loss function fD over a closed and convex set of model parameters E W C Rdd that contains the global minimizer of (0) At every time step I, each player is meant to communicate an update Gr (0 x²) with expectation V (Ø[)). We denote by (0,) = 9i (0), xx) V ((,,) the difference between the gradient and the estimate, which a deterministic function of for fixed data x', but is assumed to fulfill e (0) = 0 for all 0, and to be independent across time and players. Intuitively, (f) can be thought of as an expected loss EgwD f()()) for which player computes approximate stochastic gradients as ff (8)_1) using their t-th sample xt. The message sent by player i is termed mf- The server averages the received messages to compute gradient estimate my N Σ, mi and updates the parameter via 0/+1 = 1l 7.))), using a fixed learning rate schedule Tt and the projection 1l onto W. Finally, the server sends the updated 0j41 to all players.
Strategies and rewards We consider attacks of the form m 9o (0f x²) + aiSt that is, the true gradient estimate plus random noise of the form atg,, where TE; = 0, 1|| and & is sampled independent from the other E and the algorithm's 's trajectory. The set of attack strategies A is then described by the sequence of aggressiveness parameters ag >> O. which we assume to be selected in advance, independent of the optimization trajectory. Since defenses were already ineffective for mean estimation, we directly focus on mechanisms and only consider adjustments to the server's
final estimate for the noise player added themselyes in the final step T: 0 = Or % et- The assumption of non-adaptive strategics is needed to avoid complicated dependencies between successive SGD rounds and more sophisticated attack strategies are beyond the scope of our analysis.
We do not consider a bias term for these attacks. Our unbiased attacks have natural interpretations. both in terms of hiding randomly selected data points and differential privacy defenses, and unlike in the mean estimation case, the effects of a fixed-direction attack on the loss fD(0) can strongly depend on the current estimate 0g and the attack's 's precise direction, making it substantially harder to analyze such attacks. That said, it is easy to see that if the server aims to optimize (0(0++1) and is allowed to shift its estimate 0g to defend against fixed-direction attacks at every step I, the fixed direction attacks would be neutralized by the server at any equilbrium, unless they inadvertently improved fD(0r+1).
8

---

Given these strategies and a Lipschitz function U/ : BRV - R, player aims to maximize the reward
Ri = U (1 5(0
is easy to see that this game does not always have an equilibrium and players are often incentivized
to lie aggressively. In particular, we recover the mean estimation setting with 3 = 0 when setting
(x) ب |0 - 05 2 A 10 0' || T 1, 01 = 0 and 71 = 0.5, as 20 11 - .r! 1| = 2(0 - (000))))..
Our next result establishes that players can be incentivized to be arbitrarily honest, using penalty scheme similar to the one in Section [.1] Again, penalties are redistributed such that players' penalties have zero expectation whenever of = og for all i L. We set my
NV E3 my and
T
T
Ri, = U U'((((+(+)) f(O.+)))))))
Σ t=1
Cillm - mill? + N
Σ Kefii
Σ Cillm mell
for constants C.. With this penalized reward we prove:
Theorem 6.1. Assume f is B-smooth and L-Lipschitz on W and m-strongly convex on E (See Appendix for definitions of these properties). Also assume that for all i and the gradient noise of is B' Lipschitz with probability one and that there exist scalars M 2 0 and My 2 0. such that for all t:
E., (I((e)) S M + My V (0)))
1 Set the learning ?/1 qu tun for an integer constant v) > 1, such that mm++m I B(My/N+1y
Then U² is (i-Lisschitz with constant LU for all players i, all player's best response strategy fulfill 8LL.,N
of S (LNN-2mn/THH independent of other players' strategies. If od, Vi, j, L, each player's
expected penalty is O. For e >> 0, C³ 2 c(N-2)m /T4 yields af S raforiaaaaall rational players. In that case, if in addition W is bounded and we have that P(31 < T Ilw (0ī -mmma) + 02- -xm))) E ((TT))
8LLg
we get E (f - f(0)) E 1(00(11)) + NT + (z))).
Intuitively, small perturbations of gradient estimates sent to the server should only have small effect on the final learnt model. Formally, our assumptions allow us to inductively prove bounds on the difference between the values of (f in a clean (a)- = 0) scenario and a scenario with other values of af. By setting Ct large enough, we can then ensure that the penalties paid by dishonest player always outweigh their effect on the final model. The condition on Iw ensures that SGD is not slowed down by projections and holds for "sufficiently large" distances between the boundary of W and f). See Appendix E.2 for more details on this and the theorem proof. Theorem 6. immpleleessp implies that for sufficiently large C", despite all players acting strategically, the model converges at speed comparable to when all clients share clean updates (where the convergence rate is 0 NT + )), thereby ensuring full learning benefits from the collaboration. Moreover, as long as all players are equally honest, this is achieved with zero expected penalties for players and thus with budget balance.
7 Experimental results
To verify that our mechanisms can work for SGD in the non-convex case we simulate FedSGD McMahan et al. (2017) with clients corrupting their messages to different degrees, and record how players' rewards and penalties are affected by their aggressiveness a for different penalty constants C. The of that empirically maximizes a player's 's reward is an approximate best response for a given C' and fixed of for j + i, and should thus be small for a successful mechanism.
First, we simulate FedSGD, treating each writer as a client, to train CNN-classifier using the architecture provided by Caldas et al. (2018) for the FeMNIST dataset that consists of characters and numbers written by different writers. Second, we train two-layer linear classifier with 384 hidden neurons on top of frozen beertbass--ncasee estimate gi for the cross entropy loss ff using a single batch containing 90% of the data provided by the corresponding writer at time step < T 10650 We test the remaining 10% of the data.
embeddings on the Twitter Sentiment Analysis dataset from Caldas et al. (2018). In both cases, we randomly select = 3 clients and compute gradient
't' was selected 3 times the number of writers in the FeMNIST dataset, as reported by Caldas et al. 2018

---

0.7
()))) [x) gruup A
0.40
0.5
0.5-
RCC)
Avenge Rewznl R.
04
0.25
0.3
C=0
C-
02-
0.20
C-0.0001
C-0001
C=0,0002
0.1-
C-01002
0.15
Added Noise
Figure 1: FeMNIST Dataset
Figure Twitter Dataset
Figure Average reward (C) received by players in group for ag and varying a.A- Different colors represent different penalty weights C. Results are averaged over 10 runs and error bars show the standard error.
For both experiments, we randomly split writers into two groups A and B containing one and two thirds of the writers respectively, and corrupt the gradient estimates (m/), (ge)) + (a(Et)) sent by players in group A for each weight tensor and bias vector / separately, by adding isotropic normal noise (Ei), with "variance" 1l 1. We do the same with a' for group B. At each step, the three corrupted gradients are then averaged (weighted by the corresponding writers' datasets' sizes) m4, which is used update our neural network's parameters with learning rate 0.06, iee. 0.+1 = 02 0.06m7,- Unlike in our theorems, writers reuse the same data points whenever they calculate gradients. In the clean case (a.a ag = 0), our final models achieve test accuracy of 86% on FeMNIST and 63% on Twitter. We record both the cross cross-entropy loss f achieved by the final model Or on the test set, well as the sum of the squared deviations ||m mell incurred by each individual client i across all steps. This allows us to calculate the estimated reward (C) f(Or)
Ei (i)Cllmm m + Engi E. ( (k) m, 2 received by every player for penalty weights C held constant to whenever player provided an update at time t.
time, where (f) is binary indicator equal
Figure 3 shows the average reward R (C) received by players in group A for varying on the x-axis for different penalty weights C. clearly shows that penalization decreases players' gains from adding noise even in the non-convex case, and that near-zero noise is optimal for players given sufficiently large penalty weights C. At the same time, despite client heterogeneity. the penalties paid by honest players small: In the FeMNIST experiments, if all players overwhelming majority (98%) of players end up paying less than 0.0031 on average (over 10 rounds), C 0.0002. This is order of magnitude under the increase in loss from moving from a = 0 to a = 9, which already disincentivized for the substantially smaller penalty constant C 5c 5. On the Twitter dataset, noise has larger effect the loss (the loss is degraded by 0.084 already at noise level a = 5 compared to 0.034 at noise level a 9 for FeMNIST). This means that larger penalty weights
and a
honest,
necessary to incentivize honesty. Correspondingly, the 98th percentile of penalties paid at the largest considered penalty level C = 0.002 is also larger (0.0243) than on FeMNIST. Additional experimental results can be found Appendix B.2
8 Conclusion
In this paper, we studied framework for FL with strategic agents, where players compete and aim not only improve their model but also damage others' models. We analyzed both the single- and multi-round version of the problem for natural class of strategies and goals and showed how to design mechanisms that incentivize rational players to behave honestly. In addition, we empirically demonstrated that our approach works on realistic data outside the bounds of our theoretical results.
For comparison, Caldas et al. 2018 aim for accuracy threshold of 75% using 5% of the training data.
10

---

Acknowledgments
This research was partially funded by the Ministry of Education and Science of Bulgaria (support for INSAIT, part of the Bulgarian National Roadmap for Research Infrastructure). Florian Dorner is grateful for financial support from the Max Planck ETH Center for Learning Systems (CLS). The authors would like to thank Mark Vero and Nikita Tsoy for their helpful feedback on earlier versions of this manuscript.
References
Abay, A., Zhou, Y., Baracaldo, N., Rajamoni, S., Chuba, E., and Ludwig, H. Mitigating bias in federated learning. arXiv preprint arXiv:2012.022447 2020.
Alistarh, D., Allen-Zhu, Z., and Li, J. Byzantine stochastic gradient descent. Conference on Neural Information Processing Systems (NeurIPS), 2018.
Balashov, M. V. and Golubev, M. O. About the lipschitz property of the metric projection in the hilbert space. Journal of Mathematical Analysis and Applications, 394(2):545-551, 2012.
Blanchard, P., El Mhamdi, E. M., Guerraoui, R., and Stainer, J. Machine learning with adversaries: Byzantine tolerant gradient descent, Conference on Neural Information Processing Systems (NIPS), 2017.
Bottou, L., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM review, 2018.
Cai, Y., Daskalakis, C., and Papadimitriou, C. Optimum statistical estimation with strategic data sources. In Conference Learning Theory, pp. 280-296. PMLR, 2015.
Caldas, S., Duddu, S. M. K., Wu, P., Li, T., Konečný, J., McMahan, H. B., Smith, V., and Talwalkar, A. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1812.01097, 2018.
Chayti, E. M., Karimireddy, S. P., Stich, S. U., Flammarion, N., and Jaggi. M. Linear speedup in personalized collaborative learning, arXiv preprint arXiv:2111.0596 2021.
Chung, K. L. On a stochastic approximation method. The Annals of Mathematical Statistics, 1954.
Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A., and Stewart, A. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2): 742-864, 2019.
Donahue, K. and Kleinberg, J. Model-sharing games: Analyzing federated learning under voluntary participation. AAAI Conference on Artificial Intelligence, 2021a.
Donahue, K. and Kleinberg, J. Optimality and stability in federated learning: A game-theoretic approach. Conference on Neural Information Processing Systems (NeurIPS), 2021b.
Fang, X. and Ye, M. Robust federated learning with noisy and heterogeneous clients. In Conference Computer Vision and Pattern Recognition (CVPR), 2022.
Gao, X. A., Mao, A., Chen, Y., and Adams, R. P. Trick treat: putting peer prediction to the test. In Proceedings of the fifteenth ACM conference on Economics and computation, pp. 507-524, 2014.
Gradwohl, R. and Tennenholtz, M. Coopetition against an amazon. In International Symposium on Algorithmic Game Theory, pp. 347-365. Springer, 2022.
Grimberg, F., Hartley M.-A., Karimireddy, S. P., and Jaggi, M. Optimal model averaging: Towards personalized collaborative learning. International Workshop on Federated Learning for User Privacy and Data Confidentiality Conjunction with ICML 2021. 2021.
Gupta, S., Ahuja, K., Havaei, M., Chatterjee, N., and Bengio, Y. games: federated learning framework for distribution shifts. arXiv preprint trXiv:2205.11100 2022.
Jackson, M. O. Mechanism theory. Available at SSRN 2542983,2014

---

Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et Advances and open problems in federated learning. Foundations and Trends in Machine Learning. 2021.
Karger, E., Monrad, J., Mellers, B., and Tetlock, P. Reciprocal scoring: A method for forecasting unanswerable questions. Available at SSRN, 2021.
Karimireddy, S. P., Guo, W., and Jordan, M. Mechanisms that incentivize data sharing in feder- ated learning. In Workshop Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurlPS 2022), 2022.
Konstantinov, N., Frantar, E., Alistarh, D., and Lampert, C. On the sample complexity of adversarial multi-source pac learning. In International Conference on Machine Learing (ICML), 2020.
McMahan, B., Moore, E.,, Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effioii learning of deep networks from decentralized data. In Conference on Uncertainty in Artificial Intelligence (AISTATS), 2017.
Miller, N., Resnick, P., and Zeckhauser, R. Eliciting informative feedback: The peer-prediction method. Management Science, 51(9):1359-1373, 2005.
Nash, Non-cooperative games. The Annals of Mathematics, 54(2):286-295, 1951.
Osborne, M. and Rubinstein, A. course in game theory. MIT press, 1994.
Paszke, A., Gross, S.. Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L.,, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Qiao, M. and Valiant, G. Learning discrete distributions from untrusted batches. Innovations of Theoretical Computer Science (ITCS), 2018
Rakhlin, A., Shamir, O., and Sridharan, K. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1571 2012.
Shejwalkar, V., Houmansadr, A., Kairouz, and Ramage, D. Back the drawing board: critical evaluation of poisoning attacks on production federated learning. In IEEE Symposium on Security and Privacy, 2022.
Stein, C. Inadmissibility of the usual estimator for the mean of a multivariate normal distribution. In Proceedings of the Third Berkeley Symposiun Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics, volume 3, pp. 197-207. University California Press, 1956.
Tolpegin, V., Truex, S., Gursoy, M. E., and Liu, L. Data poisoning attacks against federated learning systems. In European Symposium on Research in Computer Security, 2020.
Tu, X., Zhu, K., Luong, N. C., Niyato, D., Zhang, Y., and Li, J. Incentive mechanisms for federated learning: From economic and game theoretic perspective. arXiv preprint arXiv:2111.11850 2021.
Waggoner, B. and Chen, Y. Output agreement mechanisms and common knowledge. Second AAAI Conference on Human Computation and Crowdsourcing, 2014.
Witkowski, J. and Parkes, D. C. Peer prediction without common prior: In Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 964-981, 2012.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Byrantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, 2018.
12

---

A Ethical considerations
Our theoretical results establish that penalties average out to zero in expectation, but substantial client heterogeneity can still cause large payments for individual honest participants. Despite our experimental results indicating that variance problematic for two reasons: The first is about fairness: Paying some honest participants large amounts, while demanding large amounts from others, based on what essentially amounts to luck is problematic, especially when the participants are individuals rather than firms, and when the nature of the problem might make it difficult for participants gauge the order of magnitude of payments in advance. The second is about diversity: Clients that expect their data to deviate strongly from the mean of the overall data distribution might opt to not participate FL with our mechanisms, even though underrepresented types of clients can provide data that is crucial to a model's broad performance and generalization. our formalism, this problem is obscured by the assumption that all participants sample their data independently from the same distribution, and are unable to predict whether or not their data represents outliers.
be manageable even for real-world data, this is
Correspondingly, it is important to keep penalty weights C' as low as possible to reduce the likelihood of overwhelmingly large penalties, only apply our framework in the context of firms rather than individuals (for whom competitive incentives might often play less of a direct role either way), as well as ensure that the our assumptions about a common data distributions are plausible for the problem at hand. The former can be particularly challenging for non-convex problems, or convex problems with unknown problem parameters, for which no strong candidate for C' can be established theoretically.
Furthermore, our results do not establish collusion- psssoonnrroonesss of our mechanism. While we expect mechanism to be collusion-prodd against small coalitions, there is problem once the colluding coalition is large enough to significantly affect the mean estimate, as the shifted mean would reduce the penalty paid by each member of the coalition.
B Additional results
B.1
Nash equilibria in the mean estimation game under bounded attacks
The conclusion that no Nash equilibria exist in the mean estimation game described in 4 is rather intuitive, since all participants have an incentive to send as modified an update as possible, therefore damaging the other players' estimates. In practice, however, attacking in an unbounded manner, that is, sending updates very far from the true mean, may not be plausible. Indeed, if most players send their true mean, one expects the variance of the estimates that the server receives to be of order O
+o2) Therefore, players might in practice be reluctant to send estimates that are further
than A 0² + o? away from there true local mean, for some constant A.
We therefore consider the same game as before, in the case when an upper bound A on the parameters a' is given. Denote the resulting set of attack strategies by SA Since AA C ofm Theorem 4.1 holds for the joint set of strategies (effT x 2). Then have the following
Corollary B.1. In the setup of Theorem 4.1 if the set of available strategies is s x 9 for some constant A O, the only Nash equilibria of the game with bi ((x)) 0 fixed for all players i the strategy profiles for which:
A
ladl
A and 8
Vi E [N].
(9)
+ ++o
Furthermore, at each of these equilibria the value of mean squared error of the estimate of each player i is
(1
+o? A2)
E (100 - -u1l3) = + + (N
+ A2)
As a result, whenever A = O1), each player's estimate at any Nash equilibrium achieves a mean squared error of O 6² o² N)) which of the same order as the MSE of the estimates that would have been obtained in a fully collaborative setting.
[n +
13

---

B.2 Additional details on experiments
The network we train is based on the network used in the LEAF repository 2 but implemented in pytorch Paszke et al. (2019). It consists of two convolutional layers with relu activations, kernel size 5. (2,2) 2) padding and 32 and 64 filters, respectively, each followed by max pooling with kernel size and stride 2. After the convolutional layers, there is single hidden dense layer with 2048 neurons and a relu activation, and a dense output layer. All experiments were conducted using a single GPU each per run.
Eusreio
1.0
Countc
0.30
13
Figure 4: QB = 1, 0.A vary- ing.
Figure 5: 0A- = 0, O vary- ing.
Figure 6: a 1, 0 vary- ing.
Figure 7: Average reward R (C) received by players in group for different values of a and a. Different colors represent different penalty weights C. Results are averaged over 10 runs and error bars show the standard error.
We downloaded the FEMNIST and Twitter datasets using the code provided at https://github.com hat.wa/lar.ab///a/trr//aaaaa
opting not to filter writers that only have produced small amount of samples. Correspondingly, our FeMNIST dataset contains 817851 examples of handwritten digits and characters written by a total of 3597 writers rather than the 805263 samples from 3550 writers reported in Caldas al. (2018).
Figures 6 show results similar to 2 for a fixed to 1 instead of (Figure or & varying while 1 (Figure 6), respectively. As payments are redistributed, the average payments for players in group B increase slower with ag, as each individual's 's increase in payment is partially balanced out by an increase in received payments from encountering other members of group B (Figures 5 6). Meanwhile, figures 4 and 6 hint at honest players receiving money when others are adding noise: In both cases, players of one group receive slightly higher reward for larger penalties when they are honest (a = 0) while the other group slightly cheats (a 1).
a is fixed to 0 (Figure
It is worth noting, that we do not perform projection step in our experiments, such that numerical instabilities become an issue for large values of a. In particular, for a > or ag > 6 we regularly observed NaN gradients on FeMNIST for one more of our 10 runs.
Figure 10 show histograms over the total penalty for C 0.0002 (FeMNIST) and C 0.002 (Twitter) paid by each individual client over the whole 10650 steps for the honest case of a a = 0, averaged over 10 runs. Clearly, most penalties are on the order of 0.01 (FeMNIST) or 0.1 (Twitter) which is substantially smaller (FeMNIST) comparable (Twitter) to the negative effects of larger noise values on the order of 0.1, which are strongly disincentivized by the considered penalty values.
Figure 13 shows additional results using SGD with Median-based rather than Mean-based aggregation as a baseline that is more robust to noisy gradients. We can see that while using Median-based aggregation helps, players can affect the loss as much as before by adding even more noise (see Figure [T]. such that adding noise is still incentivized. At the same time, our mechanism still works: As can be seen in Figure 12, rewards still decrease with increased noise for sufficiently large C. Correspondingly, players remain disincentivized add noise. This empirically suggests that our mechanism can also be applied to more advanced federated learning protocols that go beyond simple aggregation.
SGD with
Phups://github.c httpsshhhuhcoom/co hommTa/wllarrl T wwt/aa//ubbbaaacc////////miiiiia
We used assigned GPUs from cluster that employs mostly, but not exclusively Nvidia V100 GPUs
14

---

1000
300
200-
100
-0.005
0.000
0.005
0.010
0.015
0.020
0.025
-0.3
-0.2
-0.1
0.2
03
Figure FeMNIST with penalty C' 0.0002
Figure 9: Twitter with penalty C 0.002
Figure 10: Histogram of average (over 10 runs) total penalties paid by players for a ag
0.45
Mean
C-0
Aoargg Rewand #916) Ie gooqt
-
Medias
0.42
Cole-06
+ Caled8
0.41
Rewan R.(C) R,
0.40
0.39
0.36
0.34
10
Added Noise de
Addedd Nose as.
Figure 11: Mean vs Median- baseed aggrega- tion in the unpenalized setting (C = =).
Figure 12:
Median-based aggregation with different penalty weights C.
Figure 13: Results FeMNIST with median-basse based aggregation: Average reward (C) (with penalties calculated in terms of the distance to the median rather than the mean for Median-based aggregation) received by players in group A for ag 0 and varying a' Results are averaged over 10 runs and error bars show the standard eтror.
C Proofs on mean estimation
First we prove Theorem 4.1
Theorem C.1. Let D be as described in Then, for any strategy profile ((o), 6,, ,.,..., (o.", ,,,,BB,, BNN) (al x 2)x and for any player i E [N], the expected
mean squared error of player is:
E (110' - -11
x² o² Nn
= -1-88)
+
Σ
(x))))
+
Ell Σ (()))1
N
N2
N2
j7i
jti
+ ( 2 n +0?) +
d2
a²
3²) 3
Nn
N
Proof. Recall that 0¹ (1 3mm +B (1
8¹ (NO' m² + +x+) + +3x Therefore,
0¹ - p= )3 ( (No' m² + xー) - 1) + f
(zt - 11)
15

---

Denote
1 N (NO* mm' + x²) - 14
z= x¹ - 1
Then we have:
E (110* 1=l3)) E (11 (1 3) Y 3z
(10)
(1- B| + ( | + + (1- --) (Y
The second term the mean squared error of the (clean) estimate based on the local data of player i and So:
B 2( = (1 - 1113)
1
Σ m3 1ll
=
12 3
1
Σ (a) - 11)1
|| Σ (as 11)1
n²
E
11 I (arh n²)1 Σ (ut -1)1
n
Σ E (1(x)) 1²) + E (1ln(e² - 13)113)
n
E
(II(X* -,)) + El(( - n)l?
n
+ o
0²
0
(11)
Where we can split E. (1E, - m)){3) because of the tower law of expectation and using that B(x)) = μº conditional on the value of μ²; and the squared norm of the last sum factors, as all 2 μ² terms are independent and have zero mean such that
El
(af 2
Σ (nf - m1) ))
=B|
11) 12 + 11
1ul2 + 2
(+) 11)
J>1
1>1
E|
( (4) 12 + E | 1lll + 2E
I(of (af M)a
Σ (z) H)d
5>1
E1|
(4)) (1) 1 + 11 10l2 + + > E (xi - 4)a
Σ (xt 1
1>1
E
>
(1)) - 12)
+ E1 - 2112 + >
E(of - p)LE
Σ (ar) - 1a)a
j>1
1>1
16

---

E|
(ar) 1= + E E| 1ul1
+
Σ OE
(vr) 1d)
j>1
1>1
E|
(1))
1 + E | nll
and so on, allowing us to inductively factor the sum.
Now, to compute the terms that depend on Y. note that by definition 0 1/2 E m² and therefore:
== N
(N0*
m² + x¹) 1
1
Σ
m²
m2 + x² 1
N
1=1
N
1
Σ
m²
N
1
x¹
11
Define random variables:
1 Yi
1
mr
Y/2
N x¹
so that Y = Y1 + Y2. This implies that:
=E = (YI Y2)) = (1) + E())
Since the value of Y1 only depends on the data of all players j E 11, N H/{i} and the value of Z depends only on the data of player i, it follows that Z and Yı are independent and therefore E(Z'Yi) = ((Y)).
Therefore,
B(Z'Y)= =B Ez' (Yi + Y2))
= =((Z) + 1B(2")2)
= E (=' - w)'BE E
Σ me
+ (0²')1)²² 11)² (x
N
1 ((=+)11))
1
N L' (5*) - - (x') + ||11|12
N
1
E
(1=+11))
12 1t ||
N
1
E
(117113)
N |lull2
N
1
E
1
Σ
12/12
* 11u12
1
N
n
E
|1(
Σ 2 14) + 1112?)
1
|110|12
N
N
1
N
E
|1( Σ d 11)1 + |11012
N llal
E
|1(
Σ 25 1I11?
N
17

---

(12)
Nn
Where the squared norm of the sum factors as all x f terms have zero mean, while μ is constant and the last equality follows from the computations in TTT.
Now, by definition m² = . + (x²))) + 1/' (xx2 for every j E [V], where the ş are random variables with zero mean and unit "variance" B(Ils (12). Note that because Y1 and Y2 depend only
on the data of all players j E 21, .... NN....NN//.//. //(} and on the data of player i respectively, they are independent and we get:
E 11) = T. (IlY Y)
= EE [[x + E (1x2)l)) + 2E (Xi) E (Y2)
(13)
In order to calculate the value of E (Y²) we have to compute E(Y)), E(Y2), E (IIG1??) and E (1 (2))). We have:
B(Yi)
E
1
+0(
N
jti
E
Ela (x')
Σ (()())))
N
N 3
N
(p) +
B (x²),
N
N
jti
since B((2) = 0 and ę is independent from all other variables. In addition,
(1 N)
B(V2) = E
N x² -1 11)
= N
H( 1
N
1
Next,
1 Σ (I' (2 + +0((2)) 12
E
11) =
|
E
N
1
Σ
b
+
Σ
A
E
Σ
3هج + Σ
((22)11
Σ (x))3
N2
N2
j$1
E
Σ
c n
-++0((0))
+ (N - 1)a1(3 )
+ N²
Σ
Ela (x))²)
N
j&
j
E
Σ
111 +1 11
Σ
8 (0+2) + - (N-1)a11
+
1
Σ
(x22))
N2
N2
j&1
371
E
ΣΣ>
1
2 10
+ N2 EII(N- - 1)μ4 + Σ
8
+
Σ
N2
n
N2
jyt
k
j
E
-1-1
Σ
2/ 22
+ No ElI - 1) + Σ
Ela' [(a2(x))3) (x1)3)
N2
N2
} k
E
Σ
Σ o 1
+ No El - 1) + Σ
(((0))122 +
E(a (x)))2
N2
N2
18

---

(N -
1) +o.
o²
+ N2 BI - + + Σv(2D)1
1
Σ
+
N2
N2
J#1
Where the first squared norms factors because
Σ x' 3=++6(z)), =K a (x²) 1 Σ i+1
BIK N
( +
as the E are independent of all other variables and have zero mean, the E(Il Ejtt a (x2) 1113)) term factors because all a² (x²) and E are independent (and the Ej have zero mean), the b (x²) terms factor because EE < x) μ. 6 (xx) >= 0 by assumption and because the / - -u have zero mean and are independent of b' (xx) for j + i. The last squared norm factors because all Σn 2 1 terms are independent and have zero mean.
Finally,
E (11
= E
1 || N
E¹ - -m12))
Nn Σ 2tj Hul?
E
E
Nn Σ (aj - 10) + N 11/2
Σ (a}} - 111 + 11 1 N
E
|| Nn
N nll
j
E
|| 1 |1 n2
Σ (n) - 1)12
+ (1 N)²
||m|12
N2
N2
1
+ o?) + (1 N2²
N2 ||al1
N2 n
1 2 + o + (1 - N)²
||
N
N2
N2
with the sums factoring for the same reasons as above. Substituting in 13
E (1)x21) EE (IIY) (2) E (112219) + 2 (Y1) (Y2)
(N
1)
02 + o
+
1
E| 1)1+ +
10(22)1 +
Σ
Fla
N² n
N2
N²
1
0²
+
1
(1 (1- N
|| + 2(
N --1 1
1
Σ
Eb (2)))) (1 - -N)
N2n
N2
N2
N
N
N
0²
0²
E(a' (x²)))
Nn
N
N2
iti
(N 1)2
||u||2
+
No E||
Σ
ba
( 2
2(N 1)
Σ EE (10)())))))
N2
N2
jzfi
(N - 1)2
||x||2
2
(N
1)(1 N)
||1|
+
2(1 -
N)
Σ
(b')'s
N2
N2
N2
jti
Nn
0²
02
N
N
E(a (x+)²)
+
No
1
BIl Σ (12))))
(14)
3+1
19

---

Substituting
111
12 and
14
into 10
we have:
(110' - -+1l²) = (1 - 3*) 2 E (1|Y12) + ( + 2 (1 - 8*) 3 (z'r)
= 31)
0²
+ -
1 Σ
B(a²(x))))+
B1 Σ b (x)1)))
Nn
N
N
N
j
J
0² + (8))2
( + + +
21 (1- - (1 3r
+
Nn
N
Next we prove lemma that gives the optimal value of the defense parameter 3 of player, assuming that the attack parameters a of all players are fixed.
Lemma C.1. For fixed set of values 01,...;ay, aN [0, 00) and b' ...... bv IRd, the value of 3 that minimizes the mean squared error of the estimate of player is given by:
N Σ
B(a (1>
NZ E
E 12 (1r))12
(B')
j$z
(15)
E job
((o)( + N Ell b
Nn
N2
Proof. Re-writing the statement of Theorem C.T
E (106 - n0l²)= = (Bi)2
0²
+
0
a²
0. +
Σ
B(a2(1))))+
+
El Σ
((
n1
Nn
N
N2
N2
g²
2
Σ
(x)))
+ EEll
Σ (
N
jæi
j71
0²
+
Σ El ( #
El
Σ
(2)))
Nn
N2
This is a quadratic function of 3 with a positive coefficient in front of the square term. Therefore, the function is minimized over (-o0, oo) the point:
No Extt B(a (2)) + A E 8 (x))1²
(35)*
G2 Nn
2 +
x²
+ N2 E ((a)))
N E (1
72
This result is closely related to the work of Grimberg et al. (20TT) which studies the optimal way of averaging two sample sets from two different distributions, with the goal of minimizing the mean squared error of the estimate on one these distributions. However, in our case the estimate from the server is an average of manipulated samples coming from multiple distributions, rather than i..dd samples from a single one. Now. C.I allows us to prove Corollary 4.2
Corollary C.2. The game defined by the expected reward
E ( ,NO ,1) EjØr E (1101 mll
XE (10' nnl²))
and the set of strategies of x D does not have (pure or mixed) Nash equilibrium at which B((a)) )?) and Elbbb [22 are finite for all players.
Proof. Assume that a strategy profile ((a 87, .....,,,. (a bN ,3N)) E P x 2) is (po- tentially mixed) Nash equilibrium for which E((a)) (2) and BBbb (r)) are finite for player j #
20

---

(with the expectations taken both over the randomness of the strategy profile and x). Note that in the definition of the (expected) reward function, the value of the defense parameters of the i-th plaver ( only affects the MSE of the estimate 0; of that player. Therefore, it follows from Lemma C.1 that each 1 must be non-random and defined by equation (15).
particular, is easy to see that each 3 E [0, 1). In that case, it follows from Theorem C.1 that the expected reward of each player j is strictly monotonically increasing in EE (x')²)) ) so that player j can increase their
reward by increasing (((a)))). This contradicts the assumption that the strategy profile is a Nash equilibrium.
Finally, we prove corollary B.1 For this, consider the same game as before, in the case when an upper bound A on the parameters a' is given. Recall that we denote the resulting set of attack strategies by d'x- Since dA C _d Theorem 4.1 holds for the joint set of strategies (of x Φ). Then we have the following
Corollary C.3. In the setup of Theorem 4.1 if the set of available strategies is A D for some constant A > O, the only Nash equilibria of the game with b' (x*) = 0 fixed for all players i are the strategy profiles for which:
A
[a'(z')= = and 8
E [N].
(16)
+ + A
Farthermore, at each of these equilibria the value of mean squared error of the estimate of each player i is
(1
A2)
E E110' - -ull?)
+ of)
+
n
(N + 2² +o²
A2)
Proof. Assume that strategy profile ((a b², ,1 )....... ...... (a b. BBB)) is a Nash equilibrium. As in
Corollary C.2 it follows that each 3¹ is given by equation 15 and is therefore in the interval [0, 1).
Therefore, the reward of each player is increasing with B(a" )2) It follows that o (x²) A for all i E [N]. Substituting for the value of (8")* we get that for every i E [N]:
N-1A2 A2
A
g (8')*
N2
+
Ø2 of
+
No
A2
( + N + A²"
Substituting into Theorem C.I
and setting 0² 0² + no? we get:
G²
+ (B1 62
+2(1 - 8¹) gr G²
E (110* - -1]l)) = (1 - (1=)
Σ
(ad))
+
Nn
N2
n
Nn
2²
G2
N
A4
8²
A 2
82
n
Nn + N2
A²)
+
+2
n
N
A2)2
Noa
A2)2
N
A2 Nn
1
n
Ng
+ 22 (N- - 1)A43 + At82
+2 n²
n
(No² + A2)2
2
N
+ L 35
(N - 1)A²² + A + 20 A2
R
N6o + 2
02 N + 0 N + A + 82 A
N + A2)2
82 N + 57 2 + n² A + 2
n
(N + RL A2)2
8² (1+ 8 AA + 3 A2)
n
(N 82 2
8 (1+ (1+ A²)
n (N + A2)
21

---

(1+ A2)
0² -(- + o.)
a² +o? n (N + A2)
D Proofs on mechanisms for mean estimation
Next, we proof a version of Theorem 5.1
without redistribution.
Proposition D.1. In the setting of 4.1 the penalized game with rewards
j 100 ull
R2
Xel10' - rull - C'Ilm² - 0-1|
N
has Nash equilbrium consisting of the strategies a = b 30 for all whenever C > IN-1
At this equilbrium, the expected penalty
... paid by each player i is equal to C CNN-12 0², thus a player is incentivized to participate in the penalized game rather than relying on their own estimate, whenever N 2. the other N- - 1 players participate at the honest equilibrium and X; >
C (N-1)2 or N = 2 and A > ++
N
Proof. We
begin
by
inserting
the
equality
E (110) - -213))
(1 - 3²)² Na
N + No
Eztt
( + A Ee
(2())) + (8 + +o?))
2 (1 - 5*) 8' + N from 4.1 in the first two terms to obtain
ERI
E 1|0 - 1ul2
>xe10' - 1lll C'Im"*
1
Σ m² 8#1
1
N
Egjs (1 (1-))
0² +
N + No Enyz Bia (2 + A1 El Exeps 6tt (22))
Nn
E
N
Ejti
a + +0 (18))((22
2 (1 Bd)
8 No
+ x
+
E
N-1
02 0²
A (1 - (1-)
+
B((2((2)))
+
Bl Σ (
Nn
N
N2
N2
Ar (1858) σ² + +2 (1 - 8*) 3
+ 0²
n -E (Cllm² 1²)
Nn
N
Correspondingly, we get
d d'a' (x
91-
ER p
C
dai (wi))
Bllm' 8º112
(17)
(N - 1)N22
j71
To analyze the second term, we calculate:
E El|m= 8-112 = |lm 8-122
1 N Σ m² 112
Ellmm*
(El) + 66 +b(x*t)
1
Σ
ok
N (a
1
Σ 1
n
n
(x')( +
1
Σ
x -4)
n
k
22

---

Σ
- D (otk 12)
+ u df
"
a a'('')²* + - Σ क - 11)
E1
N
k
(x') Σ (ook - 12) + djil2
N
N
N - 1 )
Σ
2 ml|
N
72
Bl (r))
+
E
Σ
2
MI + E1d11
N
N2
n2
j
N
(N
1)²
0²
PE((
+ 02)
N²
n1
(N --11 1)
0²
(aa)()))))
+ + + Bl|dbl1
N2
N2
N
Σ
E(a (x))9
N
N
jti
(N - 1)
N - 0. + B|
0²
(18)
Nn
N
setting di. = x b' (x²)
Ejtt ((r')
The squared norm again factors because of the independence
and zero means of both g¹ and o l and because < n pr, b² (x*) >= 0, while bi (x*) is
independent of Ø' μ for i + j. Now, inserting 18 in
17
we obtain
(1 3192
dEa' ( ,0 .4)
C( - )²
(N 1)N2
N
1
C (N - -1)2
<
N2
N2
1
((1 C(N 1)3))
(19)
N2
As 3 [0, 1]. Thus E an Ri is negative whenever C(N -1) > 1 C কー- Correspondingly, for such C. player is incentivized to set a² = 0, independent of other players' strategies. Now, assuming 6 (x²) 0 for all other players j af i, we also get
(1 3--2
N 1
ERi (0)
,N ,K)
Σ
C(
dE b (xx)))
J NN - 1)N22
c (N-11) - 1)2
N2
N2
N2 ((1 (11-((N- - 1)3))-
C(N
(20)
Correspondingly, 6' for all players is a Nash Equilbrium. As the penalty p (m² ..... m N does
not dependend on the defense strategies 8², the optimal 8 at the equilbrium a' = 0 and b' 0 can still be calculated using 15 and is equal to zero as well.
The average penalty honest players pay at the Nash equilbrium is then given by C C + +o?),
go n
according to 18
To understand participation incentives, we compare the equilbrium reward RO 0N (J) player i receives if they do not participate while all other players do, to the penalized reward R, player i
23

---

would obtain when participating. We first calculate R' A%, μ.) assuming player i only uses their own estimate and does not send an update the server, while the other N players participate in the penalized game equilbrium:
1101(N - 1) - 14l1
1).....0'(11) ER' (N ......... (1), 1N (N 1),1)) E
1110((1) - -ll?
N -
0²
o²
0² Ax
+ +
(21)
(N 1)m
(N-1)
(N - 1)
n
using 4.1 ER p-
with a² = 65- = B 0 and substituting N and for N respectively. We then calculate
Eitts 110 - -lll
ER = E
A1110' 11112 ClImm - 8¹112
-
0²
) - c( - -C
Nn 1) - + (N - 1) 0.)
= (1 A
(22)
Nn
N
using 4.1 with a = 35 = 30 = 0 and D.1
The difference between these can the be calculated as
ER, p ER' (0 (N 1).....0 (I....((1.........
A (N 1),
(1 ( o²
o
- -C(N 1)
+ N
+ + + Ax +
Nn
N
N - 1
(1 A.) C --11
+ A
11
N
N
N-1
n
N
1
N
(4: -0)
n
N
N
0²
N
+
() C)
N
N
02
1
N
+
N (): -
C
(N 1)2
and is positive whenever \ > C + (N- -)-1) such that in these cases player i is better off participating in data sharing, despite the penalties. If N = 2, we instead obtain
0² ( 1
- -0)) (2:
ER (O' (.....,,((11.................. (1)...... 8N ONN(NNNNNNNN 1),
7
2
which is positive whenever A > C.
We now prove 5.1 Theorem D.1. In the setting of 4.1 the penalized game with rewards
R Ej 1100
>1110' - -all -Clmm' - 8¹112 +
N Cllm - mml
N-1
has a Nash equilbrium consisting of the strategies a .y 3i for all whenever C > (N-I)=-- Furthermore, this equilibrium maximizes the sum of all players' rewards among equilibria whenever >; for all players.
At this equilbrium, the expected penalty p' (ml .an......'' m) paid by each player is equal to O. such that player is incentivized to participate in the penalized game rather than relying on their own estimate, whenever N > 2, the other N players participate at the honest equilibrium, and N Xa -N-1Y=
24

---

Proof. Analogous to the proof of D.1 We have that
d
ER = dBaa(x') ER +
N - Σ I#C (Ita2 Bllm' - 8-1
d
dBaa(xt))
((L - C(N 1)))) +0 +O-
N
N ((1 C C(N - -
by inserting 18 and
Similarly, assuming b' (x*) = for all players j + i we get
d
ER
ER + N E SzCC dE [z+)|
[=)|b((>')] Bl|m - 1-1
dIE <
((1 (I-C(N 1)2) 1 N2
N2
1
N2 ((1 ((N 1)2 1)))
by inserting 18 and 20
Thus (2 R2 is negative whenever C((N - 1) - 1) 1 or C > (N-IY-I and (ar))" ER under the same conditions as long as 6 (x²) = 0 for all other players j.
The expected penalty paid by each player zero by symmetry, as every players' paid penalty gets redistributed equally among all other players, such that the payments cancel out in expectation.
Similarly, the calculations for participation incentives are exactly in D.I but ERI, is now equal to
Nn 0² (1-A) o² + o? rather than (1 - Ax) N' + x) - (N-1) No. penalty paid by players is equal to zero equilbrium.
(N-1)
of) because the expected N
Lastly, easy to see that (x+)((=>*)12 has to nonzero for at least two players any other equilibrium. Compared to the honest equilibrium, that increases every players' MSE. But the
(unpenalized) expected reward for player equals - -1| A1100 wll such that the sum N-1
of all players' (unpenalized) rewards equals Σ, - 21) mll which strictly monotonically decreasing in all players' MSEs when X, 2 for players. As all players' penalties add up to zero in expectation, the sum of penalized rewards is equally strictly monotonically decreasing in all players' MSEs.
Next, we prove 5.2
Theorem D.2. Consider the modified game with reward
Ri. Ejjs 100 -0l2 N
dell0² pul2,
where player i receives an estimate mn + VCé'llmm - mill for independent noise é' with mean Ee 0 and "variance" 112 = instead the empirical mean m, fromrom the server. Then honesty (a* 0, 0, 0, (t)) is Nash equälibrium, as long C A.(N-11²-1 and X > IN 172 Furthermore, honesty maximizes the sum of all players' rewards among equilibria whenever X 2 for all players.
Furthermore, for fixed constant X; = (I -11)) E E E + whenever C= X(-11)=1
for any constant & > 1, such that players incentivized participate in the penalized game rather than relying on their own estimate, whenever N 2, the other players participate at the honest equilibrium, and X 1.
Proof. In order to calculate the reward Ri ..... AN 11) E ||00 Aa n1| for player N-1
we have closer look at the mean squared error incurred by players in the modified game. For
25

---

convenience, we set 0² = d² o
B110' - -u1l2 = [i|(1 - 8¹) mm + -Cllm' + +3' - -ull
- 0-1(e) [1 y'm + Ba - m11 + [1 -B')//mmm' 0-116'112
+E < (11 1C ((1- ymm + 5''²" - 1))
= -11 =11-
σ² 1
Σ
B(a2(12)))
N2
1 E Σ b) (x0))1
N
N2
izi
3e o²
+ +88)202 +2 - 36)
N
( ) (((a (x)))) + N2
(N 1) 0²
+ +1 31-
Σ
M(a
+ E|bbb| (
2E
(1- - 0' ((1 3 ym
- m)
using the calculations from the proof C. for the first term and D.I for the second. The last term is equal to zero because:
E
< (1 (1- (t)C - 8' ((1- + +3' - 1) >)
= =B(<,, (I 001 ((1 - 3" ym + 8 - 11) >)
= E(<d,E E (11 Bi- - 0'l| ((1 - 3¹ )m² + +g' - (1) >)
= 0
as ef is independent of all the other terms and has mean zero Simplifying, we obtain
El 1ll
= -11-30) 3
2
Ela" (x))))
1
El
Σ
((())) + (80))00+22 +2(1 3*) 3i 02
N
N2
N2
N
jzz
+ (11 8-8C
N
}² (z + El1db12
+
1
Σ (xa) +
(N (N-1) 11
N
N2
N
= =(81) 0² ++
C(N - 1)-1 0² +
1+C
Σ
E (()))
N
N2
N2
N - 1 +
+ +C(
N
C+C Σ B(a2(<))))+
-28
E
Σ (()))
N2
N2
iti
N
(B(aa( ( + C (N (N - 1) })
+ +C(
N
N
1+C
1- C+ CN CCC+CN 62
((a2(x))3)
+ No
Bl bb(l)))
N2
j+1
N
+ +C(
N
26

---

As in C.1 this yields an optimal value for 3¹ of
H)(a,)) + C 02)
(8-)- (2 C(N-1)-- 02 H(
for H; b) = No Eز (x)))x))) )) + TZ E i# (()2))1 + (() Now, calculating the derivative of (ER ...., 0N ,1, with respect to ((a)(x')) yields:
d ER'(O', ,...,0 ON, 11) dIE(a'
Ejss ||0 - 1111
d
>, Ae110 ul1
(x1)))))))
N
[F((o((x))
Σ (1 31)2
(N 1)N2 (1- (N - 1))
N²
Similarly, assuming 6 (xx)) 0 for all other players j # i, get
d
Ejjs ||0: - 1111
d
ER (0) ,..., ON 1)) dE|b(>>))1>
b' (x )| A 11102 uul2
dlElbb (x+))
N
(1 - 3
(N - 1))²
N 1jN2 -1-
N2
j
Both negative, whenever 33 = B² and A,C - 1)2 1 1+C or C(A(N - 1)2 1) >
which is true whenever C' 111--11-- and A; (N-1)=
But for at = b² = for all players j. the formula for (B")* simplifies to
C'N-"10>
C
CLN-D
C
N 02 1+ CIN-I-I (8')* 62 + OIN
N-1 N + CIN-I
1 1+0
N
N
for all players. In particular, we have (z < for C> O, such that B² = = +
and the derivatives
with respect to both and b are negative for all players, turning a = bb = (3*) Nash equilibrium.
C into
1+C
We can upper bound E||0* 2ll2 at the honest equilbrium by considering it at the suboptimal 3 0:
σ² N
N N-1 02
E 0'
pll S
+
N
which is is ((5)) as long C in 2, which is the case for constant X; X, A(N-1)a-1
&
and any 1: >
In terms of participation incentives, we again look at the difference in rewards obtained by player in both cases:
ER' (0) ON 11) - ER' (0'(N (N - -.,,.., (') (N
(N--NN) - 1),
(23)
Σ i | (NN H112 - Ao)lo'(N) mnl2 -ull?
E
(24)
N 1
Σ Ejtt 110i(N 1) mll
E
x1100(1) -u112)
N-1
Exet 1000(N - -1) - 1all2 N
= (1 - (N) - -11l22 - E
A (1((1)) - -w1l2
is obvious that ElI0 (N) - 11|22 < because of symmetry and players could otherwise improve their reward by setting 3 1, which
(B) 1r13 at the honest equilibrium
27

---

was shown to be suboptimal in the proof of 5f This has two implications: First. 23 is positive for A; 1. Second, the derivative of of with respect to X, is always positive. Combmed, this implies that 23 is positive for all X; 2 1.
Lastly, it is easy to that (ar has be nonzero for at least two players any other cquilibrium. Compared to the honest equilibrium, that increases every players' MSE. But the N-I
expected reward for player i equals -0 >= 21 such that the sum of all players'
rewards equals E,(1 >y)110s nll2, which is strictly monotonically decreasing in all players' MSEs when X; 2 1 for all players.
E Proofs on stochastic gradient descent
To this end, we first present the formal definitions of the assumptions on f' that we make. Next, we prove two results which bound the difference between the performance of model resulting from a corrupted optimization scheme (in which players send corrupted estimates) and the performance of model resulting from honest participation (i.e. from vanilla SGD). In particular, Theorem E.I provides such a result for a simple penalization scheme, which then easily extends to the penalties presented in Section 6 (Theorem E.2 Next, combine these results with classic bounds on the distance of the plain SGD trajectory to the minimum value upper bound the difference between the performance of the corrupted trajectory and the minimum value of f in Theorem E. Finally, we show how this last result can be extended to general Lipschitz utilities in Theorem the main text.
Outlook In this section we prove Theorem 6.1
of f (Lemmaa E.T. D. to provide
thereby proving the result from
Definitions First we formally state our assumptions on the function f.
Definition 2. A function f C R" - Rd is called L-Lipschitz with respect to given norms || llx and || lla if for all x. y E W
[f(x) f()ll - L||z yll..
Definition 3. continously differentiable function f W R + R is called B-smooth if its gradient Vf: W + =²" is Lipsschit with respect to the euclidean norm.
Definition 4. A differentiable function f W C R
E is called m-strongly convex if for all
x,y E W
f(x) 2 ~ y) + m || yll
2
where || denotes the euclidean norm.
We start with proving weaker version of 6.1 with constant learning rates in which player's paid penalties do not get redistributed:
Proposition E.1. Assume f B-smooth and L-Lipschitz with respect to the euclidean norm on W and m-strongly convex on Rd. Also assume that for all i, t the gradient noise et is B' -iiischhi with respect to the euclidean norm with probabilliy one and that the constant learning rate "y fulfills 0 < B Then for the penalized game with reward
NN (1 ...... 01.1.
E jf1
1(
Σ Cellmt
1 N
Σ mlll?
N
INo T-t C.(N-1)² S
any player's best response strategy fulfilis of S 2ym), independent of other players' strategies.
INy C(N-Iy' for c 2B+
Given e > 0, the expected absolute change in function values f(0)) due to noise added by players
playing best responses compared to full honesty can be bounded by - by choosing Ct Z
LNN -1-- The total penalties paid by player can then be bounded by I- (N-1)
LN-
In G²
ON 11-
<) for global bound on the "variance" of the gradient estimates [ee)(0)] < G².
28

---

Proof. We compare two trajectories 0r and 8 starting at the same do and sharing the same realizations for the noise variables of and Ç in which player employs different agressiveness schedules aj and (aj) with squared difference 67 = (af - (a)) We define E # 2, e, Then:
E| 0c+1 - 0/+1112 (0000000000000))0+))0)))))> +
Σ
af + )
N
jpl
- IIlw (0: -. (0)
Σ
+ N (a))
1
N
1
+ 1
S El|0 - (V (0)) +
Σ
0f
N
N
0f 72 (Vf(()) ((9) + 1
Σ at (a))
iti
El10, 6,11 + / (0,) - ( 1/2++,, 1 (0,) (0))2
2 Bl - /012
+ By 0, 8. ( - vf(0.) >
N2
Ey é, (0.) é. (0.), 0, 0g (V. v)(())
Where the first inequality follows from the well-known 1 L-Lipschitzness of projections onto convex closed sets with respect to the euclidean norm (Balashov & Golubev (2012) ) and the 5 terms factor because of their zero mean and independence of the other variables. Similarly, the last term turns out to equal zero because:
< (O,) (,)))) O2 - - (VV((0)) - VV(())
E|[[< (0.) - (6),,, 0, - 8 (V.((())) - Vf((()) > 10,,, 61] EKK (0.) - (6) 0r, 81), 0, - 8/ (VV -V)())) >]
[K| 0, 02 0/- - (6 (0,, vf((') >]=0
as (0) = 0 for any fixed 0. Correspondingly.
E E11011 0/+211 =3100 - 0,11 (3 V/(0111 + (0.) (0)12
+ N2 Blaa; (a)))) + 2 < 0, - 06 V/(0) - VS(0)) >
22
El10, 0/112 + + (.)) - V/(0)12 + (0.) - (0011 +
N2" 82
+ 27,1 < 0, 0% V/(0) +2 < 00 0. Vf(0)) >
7
< BB10 0/]1 1 (0)) V 2100
+ 7 (0)))
+ 2,, - f(())
m 10: 21le + f(0) f(0)) 2 110 0,11))
m
2
Ell0, - 0/111 72 f/(0)11 + =B)) 21)))12
72
6
N2
- 2n.mEl66 - -
22 N2"
< BB100, - -0,11 + 7, B2 02112 + (B' 0211 +
8
2nmmBl100 - -0,11
72 N2
(1 (B² + B 27 0,112
of
(25)
Where the first inequality follows from strong convexity.
29

---

Now for a constant learning rate = >/ and c = (1 71+ + B²) - 2mm))
(B. 1 (000+)))))) 15(00-100)))))0) (10++)))2 s 5B|00 - 07+111 11
(R] 0 11)2
T
T 72
< B(001 0f +
Σ
N2 o3
T
T 12
N2
1=
so that
T
- s L
cf'
01
<
L
T-t
8
T-t
la (a
N2
N
N
t=1
Where the last incquality follows from the general inequality inductively follows from
V 2i S Ei V bz for xs 2 0. which
Vx -リナリー - V=+ク= ViT + VD)
V /V= + /D) Vx Vリ-
In particular if we set 0g to the trajectory in which player i is honest ((af)' = 0), we obtain
T
(1 - 1(0++111
L
Σ
c
T-t
oz-
(26)
N
The same inequalities holds for players' final estimates 6/41 and (0) Y, as the noise correction
step 0741 0r+1 a' is the same in both cases, that
Ell
1' Ell0++1 (0r+1)'13.
is worth noting, that the contribution of noise at early time steps to the sum diminishes exponentially as long which is true for 2132 B²2 2ymm < O, i... y
2m
Next, we consider the expected difference in penalties received by player i time if they use (at) rather than of and thus send message (mt)' rather than mf:
Em/(m (mi) :........,,
mi - (m
m
m
N)
- N 1
(mi)) Σ
my
N 1
1
m ml ||
m
N jti
E
N
((at)&t + +
Σ
m 2
E
N
1
(afst
+ gi)
1
Σ
mf 1?
N
N
j
N 1
N-
E
(at)
E|
(
N
N
+ EI
(ot)
1
Σ
m
||
- E
N (gt)
Σ
m
N
N
N
N
N
(at))22
0
N
N
for of = gr (0
In particular, we can bound the difference between expected penalized rewards for two trajectories with all of fixed but two different values of and (af)' varying for k = t as follows:
30

---

E
R' (00++)) - Σ Cmpy bioi............. mp..... .m²")
-R(((0++)')+ +
N - Σ (1(0)/+)) - 5((()(1)))))))))0))))) Ci((
N -
N (a;))² - -
- a²)²)
N
T= Ja -aaaa) Iajj' +ill N - (at))² - N - a;)²)
In particular, for (at) = 0, we obtain
E ('rr Σ Cupi m . - R'(()))) + Σ Cupklmby.... (mp),.... ..... m
- af C.(( - a3)
N
By the quadratic formula, this is zero at zero and at
-2L No LNc T-t -2,, 12 CNNN-1 -
of
(27)
and because of the negative quadratic term negative whenever of > LNC 3
C((N-1) Correspondingly, in
terms of penalized reward players are always better off by not adding any noise all a compared LN
to adding large noise, such that rational players will never choose of > C.(N-1J2 Therefore, the noise af added by any player
given time step can be limited any fixed constant e by
choosing C2 such that LNc LN C. S i.e. C. 2
LNC 1(N-1)
Applying this observation to each player, substituting into Equation (26) and using the triangle inequality, the overall damage caused by all N players compared full honesty can then be bounded by
T
- f(6 s In
T-t c
where 02 represents the fully honest strategy and 0g represents a strategy in which all players act rationally given the penalty magnitude Ct Using a geometric series bound, obtain (0r++) f(0++1)l --yaL
Lastly, for a global bound on the "variance" of the gradients [|e((0)]12 < G2 we get,
Ep
[m]
mi.
my))
E
N
1
m
1
Σ
ml
N
N
N
E
(g)
+
aftt)
Σ
(g) + o
N
N
E
Dt
ge
2
(2)))2
+ Nº
Σ (at)²
N
N
N
< E
N
1
(0:(0)
v
(()))
1
Σ
(0)
v(())) + N -1
N -
N
N
N
31

---

N
)e
N
= [|
N
(0)
E
(00)11100]
( )c²
N
N
N
N
N |EEE
ΣEE[G
N - ( )c² N
N
N jنز
>
(G +
as the şj are independent with zero mean, and the gradient noise (0) are independent with zero mean, given O. Correspondingly, for C2 be bounded
LNc "I6 c11-11= the total expected penalties paid by player can
E
Σ Copt m......,m.................. - m,,)
T
Le Le=
(K2 + 2)
cNN - 1)
La K²
$ 1 Vc (N -)
+c)
Next, prove the budget-balanced version of E. Proposition E.2. Under the assumptions of E.
in the balanced penalized game with reward
(0 ON 01+
1
f(0) (1)
Cillm
1 N
Σ mfll 1|
N
Crllm
N Σ mz m/ll?
N
any player's 's best response strategy fulfills of I 2ymm,, independent of other players' strategies.
- C((N-2]
Ly 2(( for for ? + B
Given é > 0, the expected absolute change in function values f(0)) due to noise added by players playing best responses compared to full honesty can be bounded by T-vo Lye by choosing C. Z
Le 2 < Lx QN-22) As long as all players choose the same strategy (a} og, Vi,j, (), the expected c(N-2)
total penalty paid by each player equals zero.
Proof. We begin by considering the expected difference in penalties received by player at time t if player i uses (aty rather than of and thus send message (m?) rather than mi;
Ep,(m,
(mi) ..... mi pl m
m,²)
= El|mm
m
(m - El|mb
Σ m
mi|1
N f
N
N
N
= =Ellmb
Σ
m
1
((af)( + 9 - ml
Σ m
(afst + gf)l
N
N
N
N
=llmm
Σ
m
1
+
1
(att\
NV
N
32

---

E lm
N
1
Σ
m
N
oill
E
1 N² |att!||
j
(a))' N
ai 2
N
Again, we can bound the difference between expected penalized rewards for two trajectories with all 0j fixed but two different values aj and (atY varying for k = t as follows:
(OR+())))) E Capi ....e......... m... ,......, m
1 Capk .... mp. ,.....,,.. m
N
-R((((+)))++ I Copi ...., (mm))..... mm
Capk (mb)....,,
,...,, m ))
JF1
1
E(ro+++ f((0+-1)))
N
SFi
N- 1 (at)))² - - (aa)))² - N - ai)²) +
1
1
1 [a))3)
+cll
N
N
[(s()++)) -(((0=1))
1 C.ll( (at))² (a)))=1(( (at)) - -N a;)3) + (xaa3))
N -
N
N
- |0 - (a))' Cal -2 N ((ab)))
N -
S L N
N (ai)²)
Again, for (aty = 0 we obtain
(OT+)) - E Chrilmb ..., m ..,...,,111. mū
1 Carl ........"?))
&
Ri + 1)) Σ Cuphimb....... (mi),..... mm
1 Cap (mh).. ))
N 17
(N- - 2) (at)2)
< L N
aj Ci(
N
which is zero at zero and at
- 21
3 T-t
Le Loztyy 7
0f
(28)
-20,
N-2
CN(N - 2)
N
and negative for of > that do not fulfill that inequality.
Le - [x as long as N > 2. Players are thus again incentivized to select of
As in the overall damage caused by all players compared to full honesty can then be bounded
by E f(0++1) - f(0r-1)l S - Lye by choosing C₁ > Le
where 6, represents the fully
33

---

honest strategy and 0n represents a strategy in which all players act rationally given the penalty magnitude Ct, and the same is true for player's estimates 4/ and (0/+1)' By symmetry, as long as all players choose the same strategy (af = of Vi, 1); the expected penalties paid by each player equal O.
To prove 6.1 we adapt a classic result from convex optimization give convergence rates for SGD with bounded perturbations from the clients and with a linearly decaying learning rate.
Lemma E.1. In the settings of E.2 assume that all players use bounded attacks, so that (at)² I e² for all i,l. Also, assume that there exist scalars M 2 and Mv 2 O, such that for all L:
Ex, (1ee((00)))) - (1la (0,,=)0) x²)]?²) - 9e (0; xt 11 S M + Mv ((0))
(29)
Assume that for some integer constant 1) O, such that qu S B(N//N+T) the learning rate is set as "h- 1m++tm In that case, if P(Et S ' 1l (0, 7mt))) # 02 Teme)) E 0 NT we get
E (J(O)) f(0)) E 10 + +0(21 ((22), ), we have:
E (J((O)) -(0))) S 8B(M +
1
1
O
+
O
(30)
NT
NT
72
for any T 2 17.
Proof. We first condition on the case in which there is S T with 1w (0; -0 + 0 7, so that we do not have to worry about projections. Then, for a random vector g. denote V(g) = E (1]gl(²) [[( Note that, by the independence of the stochastic gradients and players' noise,
it follows that:
N |B<
m
EI
V.(0.) (00) +(00)
+ +((0)+++)(())
1=1
E
(V)(()) ++(00)+
N2 V 2(0))12
N2
E
Σ (0))))
E Σ + + [[
N2 ((
N
N
(0
Σ ()))))))1
N
N
N
M + My VV +
(a:)²)
N
M+
My
+
VFF()
N
N
Additionally, since f is strongly convex, it has a unique minimizer 0* E RRd. Now since the learning rate is of the form 7/-
4/m
8 S B[M+/N+1J' the conditions of 7+7 with 4 > -/2 17 0 and m 74I
Theorem 4.7 in Bottou et al. (018)) hold with μ = 1, My = My NN M = (M + 2)/N Mv /N + 1. Using equation 4.23 in their proof gives:
E (f((r+1)- < (1
4
E(f(B)) f(0))) 8B(M 2)
(31)
7 ++
Nm + t)2
for any t 12 1. We now use classic result by Chung:
34

---

Lemma E.2 Chhng 1954 ). Let fon h221 be a sequence of real numbers, such for some no E N.
holds that for all no.
(1-
d.
bn+1 S
bn
71
n2a
where c 1, > 0. Then
c
bn S
+
+0
+
d
1
n
112
n
We set 2444 == (J(O,) f(0*))
for t 2 and m
E (f - f(0*)) for k S 17. Using 31 and
k t ++1 we get
4 jkkt +
8B(M +c²)
2x+1 S (1
Nm²
Now using d = 4 and c
8B(M++3) Nm
we have Tk41 S (1
f)xx +
şेt such that E.2 yields
8B(M + +22)
1
1
2t
+0
+
3Nm2t
f2
td
and thus
8BMM 22
1
8B(M 62)
(
1 12
( S (t +1) + +0
+
S
3Nm + 0
8
td
Now, if there is 1. with [0p ) # 02 7, we can still bound EE (f(()) - )())) by some constant because W is bounded and f is Lipschitz. Correspondingly, as P( s T
Tw (0r - m * of 7em)) E 0 (TT)) the total expectation for both cases combined is bounded
by 8B(M+22 NM"NT + NT O (7²).
To prove theorem we use a an-mmttpttiicc version of Chung's Lemma Chung 1954) similar to the one used in the proof of Lemma 1 in Rakhlin et al. (2012): Lemma E.3. For constants e
0 and d >> 1, whenever t + 1 2 d and the recursive inequality
d
F++1 S (1
)x +
t+1
(t 1)2
holds we get that if
2dcc
It S 1(33 - d2)
for t- l the same is true for t = l: + 1.
Proof. Using the condition on I2, we obtain
T++1 (1
1.a +
++1
(t 1)²
2dcc
2
101 + () d2) +
1(d3
d2)
(1 + 1)2
as by assumption
< 1. As dl > 1,
[1+1](d' dJj is positive and we can divide the equation above
2d c
by it to obtain
xz-1 (t + () d²)
t+1 d (d 3 (d- d2)
2dc
(t+ 1)2d?
35

---

for which we want to show that it is bounded above by 1. Multiplying the equation
t ++1
d
d2 (1 1)2d
dd
3 1
b 1
by t(t + 1) for t we get
(d
dD)
e2 + 2 dt d
ff +1
2d²
which is equivalent to
1+1 1 - dl - d + 2 (d 1) S
2
i.e.
1 (1 - d)t +1 1 d0
2
and
(1 d)t S 2(d 1),
which is whenever
t -2
Theorem E.1. In the settings of E.2 assume that there exist scalars M 2 0 and Mv 0, such that for all t:
B. (I(C)(0))))) S M My (
(32)
Assume that for some integer constant y 1, such that 1p1---m22 B(My/N+1y the learning rate is set as qmm+tmm
Then any player's 's best response strategy fulfills at S 2m independent of other players' strategies, such that for any given e O, C2 2 c(N-2)m /Ti yields of S e.for rational players. In that case, as long as W is bounded and we have that P( < T II (0" -()) + 0 7 E 0 ) we get IE (f().) f(0*)) E 0 0(1+M42) + (
Proof. We make use of inequality 25 from the proof of E. to analyse the difference between two trajectories that are identical except for the actions of player i.
E 0 1122l
72
< (1 + (B² + B²2) - -2ym Bllm
0,12+
N2 ot
16
8
16
=(1+ m² (1 + t)2
(B² B²²)
E|| 0
+
(n + 2) m
16
8
16
< (1 + m² 1)2
(B2
- B
EE| 0,1
(1) 1)2 N2 2
11
Fort 2 0 and 7) > max 32( +
1} get
13m
B2 + B2
1.5
16
(33)
m + 7)
(+
1
by calculating
32(B² + +B²)
17 2
13m²
16( + B22)
6.5m + 6.5t
m²
16( + Br2)
8n 8t
> 1.5n 1.5t
m
36

---

16( + B²)
(t
+ n))
81) + 81
1.5
m²
1 ++1
8
16( B
1.5
+
(1 + m)
++
16(B² + 3
1.5
5
(1) + 1)
1) 1
1+
We now set Fett = 01 0, 2| for 1. 2 and 3g = for k S These definitions are consistent for = 0 because 0 0f || 0.
Using 33 and k -- + get
1.5
16
1k++ S (1
Jun +
(I: + 1)2 N2 5f
+
At the same time, = = - 111 0 < T-
4a for any > 0. Correspondingly.
E.3 with d = 1.5
and N max, {5.} implies that for le 2 1j and ls + 2 1.5 we get
4c
3t S k
and thus
4c
E - 0/11 - 1 1-111 + 11
fort 2 1. This yields
64 max, {8,} (T N2
E B|0r41 - 6//41112
Consequentially, obtain
64 max: m {
(1((++))-(((r))))) S V
(T + N2
Again, we can bound the difference between expected penalized rewards for two trajectories with all og fixed but two different values af and (a?) varying for k = by considering 8₁ 0 for all & + t. This yields
648
64|a (at) (T + N)
B]f(0r+1) - f((r+1) S LV
(T + N2 = LV
As in E.2 this allows us to upper bound the gains in penalized reward from changing ot to (at)' by
Nm T + oo (at) Ca( N - 2
8T.
N ((at)))²
N-2
(a))²)
N
In particular, for (aty = 0 this bound becomes
8L
N 9-2 2 N (at)²)
Ci(
Nm T +1
which is zero at of = 0 and at
af -20, N 2
NmyTTa
8L
(34)
CN(N
2m
and negative for af larger than that as long as N 2.
Again the noise of added by any rational player at given time step can therefore be limited to any fixed constant c > 0 by choosing C2 such that CNN S C, i.e. Ct 2 <(N (NN2)mmyTT)
8L
8L
We conclude by using E.I to obtain the convergence rate.
37

---

As final step, we show that version of E. also holds for more general reward functions, thus pr
Theorem E.2. Up to constants, theorems E.2 and
E.1 also hold for the reward Ei= Ct Imm
Ri; (07+1....,
1) 00+1:...,0.11:1
('(f(0++1).....
+()++)))
dे mi]l E
N-T Exeps El= Cf Imm - m2 I12 for arbitrary 1 Lipischhit UA with common Lipschitz con-
stant Lu. Any bound on af can be achieved by setting Cf = L the C₁ achieving the same bound Er. respeccvvlcy.llllll.
Proof. We first note that for any pointwise bound -f((0)--))((((++))))))))))))))))
s ELU -
Lu Σ DBISOH+)) -((00+))))
Ly
This means that the gains (U nalized reward player i can achieve by using a given ag at time instead of of 0 is multiplied by N compared to [8d
f(Oo), in unpe-
Thus, for given C²², the bound on aj for rational players multiplied
by NL as well, as the quadratic formula solution for of is linear in the linear term. Correspondingly, we need to set CP LyNNCG Ce to achieve the same bounds on aj as in E.2 or E.1
Now, for of I c, the bound on the expected absolute change in (f (f +i,,.... 1)) is N times higher than for f(0)+1) using the bounds above. Because these bounds are linear in for E.2 we can achieve bound of 8 for U (f ............. f(07+1)) by ensuring af S NLe for achieving a bound of 8 for ((0)). In total, we thus need to multiply the corresponding C2 by LL twice to achieve given bound on the gains in unpenalized reward from cheating: Once because we need
smaller bound on af to achieve the same bound on the unpenalized reward, and once to ensure that
rational players are incentivized use that smaller bound.
Discussion the projection assumptions We note that the assumption P(3r < T Bw (0)
Tem))) * 0j- m)) E O( NT in particular holds if W is chosen such that ||w - 051 E ((() for all w in the boundary of W while mell E O(110 - 0jll) with probability one for all & < T. In that case, the linearly decaying learning rate ensures that (10) - Ojll) stays in O(T) and thus in W (for
appropriately chosen constants) with probability one.
Similarly, Lemma in Rakhlin et al. (012) states that for probability one bound on the gradient norm m² < G, Vt, we have that 0 Hs 2G with probability one, such that the iterates stay in
W without the need for any projections, as long as G grows slower in T than inf wes(w) |w 8* [] In particular, if f grows quadratically in 0 O* and noise is proportional
the gradient norm, G grows linearly in the distance between 6* and the boundary of W, such that the condition holds for the right proportionality constants.
38


Reviews:
[{"review_id": "CBk1LOsJOw", "reviewer": "Reviewer_seCF", "summary": "The authors investigate the issue of  manipulation (in the form of falsifying data or model updates) among agents who mutually contribute to a shared model. Incentives for such behaviors arise when agents possess differing objectives with respect to the shared model. The authors first demonstrate that without external intervention, these incentives are essentially unavoidable. However, the authors propose two methods for inducing incentive compatibility in such settings; namely payments when utility is transferable, and noisy server messages  when utility is non-transferable. The authors derive these mechanisms and provide additional theoretical results for two settings of collaborative online learning, single shot mean estimation and multi shot shared gradient updates. Lastly the authors provide experimental results on the FeMNIST data set demonstrating that their mechanisms dissuade strategic behavior.\n", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Distributed learning is a rapidly growing area and there is a real danger that strategic agents could disrupt the efficacy of these systems if their incentives are not properly accounted for. As such, the authors’ work is well motivated and helps to fill an important piece which is currently missing from the literature.\n\n2. Manipulations in these types of settings are often framed as being adversarial. The authors model agents as being strategic rather than purely adversarial. As we have seen in areas like supervised learning the differences between adversarial and strategic agents can be highly consequential in terms of designing robust systems; considering both types of behavior is imperative (the former is already covered in prior work).\n\n3. The need for such mechanisms is well motivated both from a narrative perspective and from a theoretical perspective (Corollary 4.2).\n\n- Considering the case of non-transferable utility increases the applicability of the authors results, and the case of transferable utility provides the system more options to incentivize collaboration when payments are feasible.\n\n4. The authors’ results are constructive, rather than simply existential. For example, rather than saying that there exists a $C$ and $\\lambda$ such that players participate honestly, the authors provide specific ranges of these variables for which honest behavior is an equilibrium. This makes it easier for others to implement their methods in real-world scenarios. \n\n5. While some strong assumptions are made for the theoretical results, such as convexity, the inclusion of the experimental results helps demonstrate that the authors’ approach is effective even when such assumptions do not hold.\n\n6. The paper is well written and the authors take the time to outline the intuition and implications of their results.\n", "weaknesses": "1.  The mechanisms proposed only induce truthfulness as a Nash Eq, implying that other non-truthful equilibria exist. I understand that these types of results are standard throughout the literature, but when deploying these mechanisms in practice it is important to note that we have no guarantee which equilibrium agents will end up in. This is a far weaker result than truthfulness being a dominant strategy.\n\n2. Similar to the last point, the mechanisms do not appear to be collusion proof. In particular one player could pretend to represent multiple clients (i.e., sending multiple updates each round). For example, in the case of single-shot mean estimation, if such an agent monopolizes a sufficiently large position of the data being submitted, they could force the other agents into submitting any desired value for large enough $C$ (since the deviation penalty will outweigh the other parts of their utility). If agents are willing to misreport data, they are probably also willing to collude. Not accounting for this possibility limits the scope of the work. With that said, the authors appear to be the first work to study robustness to strategic behavior in distributed systems, so perhaps asking for additional results on collusion is too much. However, this should be more clearly stated as a limitation of the work.\n\n3. The experiments are somewhat limited. The primary contribution of the paper is theoretical and the point of these experiments is to show that the payment scheme works even when convexity does not hold, but this observation on a single dataset, for a single model, is a bit unconvincing. In particular, I would expect that the average reward received when increasing $\\alpha_A$ would decrease more rapidly for larger $C$, however, it is not clear to me that the small amount of fines paid by honest players would hold across different scenarios.\n\n\n\n\n### Comments and minor issues: no impact on score and need not be addressed in the author response. \n\n1. Line 259: should this say “... at the honest equilibrium [when] ….”? In the supplement this is stated as an [and] rather than a [when].\n\n2. Corollary 4.2 should probably be a Theorem. This is actually quite an interesting result and somewhat non-trivial based on the proofs. Although Theorem 4.1 is doing most of the heavy lifting here the corollary is actually the main results, while the Theorem feels more like a helping lemma. \n\n3. Links to theorems and references are broken in the main body. Looks like this is the result of compiling the document with the supplement and then using a PDF editor to trim the supplement pages.\n\n4. Figure 6 in the supplement takes up its own page.\n\n5. The naming convention of Theorems is not consistent with the main body and makes it difficult to find a specific theorem within the supplement, unless using the reference provided in the main body.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive and thoughtful review. We are glad you liked our paper and plan to incorporate your feedback in the next revision. In the following, we aim to address your concerns: \n\n**The mechanisms proposed only induce truthfulness as a Nash Eq, implying that other non-truthful equilibria exist.**\n\nThank you for pointing out this important issue. We agree that honesty as a dominant strategy would be a more desirable result. As we discuss in more detail in the general response, we do not think that the other existent Nash equilibria would pose a large problem in practice. In particular, they are simultaneously more difficult to coordinate on and make all players’ receive larger MSEs than at the honest equilibrium, such that it is unlikely that players will choose to coordinate on these equilibria when they care more about their own models than others’ ($\\lambda_i>1$). \n\nWe will update our manuscript to better reflect this important point. \n\n**The mechanisms do not appear to be collusion proof**\n\nThank you for bringing this up. Collusion in our framework is an important topic that would be interesting to analyze in future work, and we will highlight this limitation in an updated version of the paper. \n\nWe do expect our mechanisms to be collusion-proof against small coalitions because an actor that pretends to be multiple actors will also have their penalty multiplied accordingly. However, we do agree that there is a problem once the colluding coalition significantly affects the mean estimate, as the shifted mean would reduce the penalty paid by each member of the coalition. \n\n**There are only experiments for a single dataset and model.**\n\nWe reran our experiment on a subset of the LEAF Twitter sentiment analysis benchmark, training a 2-layer classifier on top of frozen BERT embeddings. These results are plotted in the response PDF in Figures 1 and 2. We observe similar trends as in the experiment in the main paper, in particular if $C$ (the scaling on the monetary penalties) is sufficiently large, players are strongly disincentivized from adding large noise. \n\nWe found our model in the Twitter benchmark to be more sensitive to gradient noise than the CNN in our FeMNIST experiments, with a noise level of $\\alpha_A=5$ degrading the loss by more than twice as much ($0.084$ vs $0.034$) as noise level $\\alpha_A=9$ did for the CNN. Correspondingly, the penalties needed to achieve honesty were roughly 10 times larger than on the FeMNIST dataset, which leads to a similar increase of the 98th percentile of payments at the honest equilibrium (from $0.0031$ to $0.0243$) for the largest considered penalty $C = 0.002$. We would like to note that this outlier payment is still only a third of the damage caused to the loss at $\\alpha_A=5$, and that a 4 times smaller penalty of $C = 0.0005$ still appears to be sufficient to incentivize honesty.  \n\nLastly, we would like to thank you for the additional feedback. We will incorporate it in the updated version of the paper.\n"}, {"review_id": "DrCrQB8NtQ", "reviewer": "Reviewer_Mvyk", "summary": "The paper studies a centralized collaborative learning problem. Authors provide theoretical guarantees for an attack method and a defense method. Further, the paper proposes two mechanisms to incentivize honesty: a method that uses an explicit side payment method and requires transferable utility, a centralized punishment mechanism where a central server adds noise to the estimates it sends to players that have sent suspicious updates. Simulation results are provided supporting the claims.", "questions": "-- I encourage authors provide a comparison with existing methods.\n\n-- Is it possible to add a proof sketch in the main paper highlighting the technical challenges addressed in the analysis?\n\n-- Can these results be extended to the decentralized setting?", "limitations": "Authors do not provide a discussion on limitations of their method. Authors include a discussion on societal impacts in the Appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-- The paper is well written and easy to follow.\n\n-- Authors provide a description of related work and background. The problem formulation considered in the paper is well positioned in the relevant literature. \n\n-- Authors provide several theoretical results making novel technical contributions. Authors provide discussions around the implications of the theoretical results.\n\n-- The paper provides simulation results supporting the theoretical claims.\n\n\n\n", "weaknesses": "-- Problem formulation is well positioned in the relevant literature. However, authors do not provide a discussion on how their results and methods compare to existing literature.\n\n-- Authors provide numerical simulation results supporting their analysis. However, authors fail to compare their method with existing methods in the simulations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thoughtful review. We are glad you found our paper easy to follow and our contributions novel. We aim to answer your questions and address your concerns in the following: \n\n**Can these results be extended to the decentralized setting?**\n\nIn a decentralized setting where players publicly communicate their estimates to all other players, our payment-based mechanism could be implemented without a server, as the payment is a simple function of all players’ communicated estimates, so everyone’s payment can be computed publicly. However, this does not work for our noise-based mechanism, as players can just personally aggregate the public clean estimates when there is no payment-based penalty. \n\n**There is no discussion on how the methods/results compare to the existing literature. Is it possible to add a proof sketch in the main paper highlighting the technical challenges addressed in the analysis?**\n\nWe appreciate this suggestion and plan to add further details on the key technical challenges in future versions of the paper with an extended page limit. \n\nAs a brief summary, the first key technical insight is that ideas from peer prediction can be applied to our novel setting of competition in collaborative learning. With this insight, Theorem 5.1 can be derived with versions of techniques used in previous work on peer prediction, generalized to treat the d-dimensional case without strong distributional assumptions.\n\nNext, as far as we know, our noise-based mechanism is entirely novel and the analysis required a nontrivial reduction of that mechanism to the payment-based case. A key challenge in the analysis is that the magnitude of the added noise is correlated with a players’ sampling error, such that standard independence-based decompositions of the squared loss do not work. \n\nLastly, our treatment of peer prediction for SGD is also entirely novel to the best of our knowledge. In this setting, it is not possible to base the mechanism on the final output as is usually done in peer prediction. Instead, our analysis bounds the effect a player can have on the final loss by manipulating an update at time t, which can be highly complicated due to ripple effects, using a novel recursive bound for the squared norm of differences in SGD-iterates between a clean trajectory and a trajectory with time-varying gradient noise. This allows us to connect the expected deviations between a player’s gradient and other gradients to the overall “damage” they cause, and bound that damage by penalizing gradient deviations. \n\n**There is no comparison to existing methods in the experiments.**\n\nThank you for the suggestion. We would like to include comparisons to baseline methods from existing work, but since the formal setting we consider is entirely novel, there are no established methods to fairly compare to. While there are existing methods that aim to make collaborative learning robust to updates from dishonest players, our methods are orthogonal as they instead aim to prevent dishonesty in the first place. \n\nIn order to demonstrate how our work complements existing robust collaborative learning methods, we provide an additional experiment using one such method: robust stochastic gradient descent using the median rather than the mean of players’ updates (Yin et al., ICML 2018). Please refer to the PDF response for the results. We present two plots, to demonstrate how the median compares to the standard mean-based aggregation in the presence of noise (Figure 4); and how our mechanism performs in combination with the median-based aggregation (Figure 3).  As can be seen from the first plot, while this median method increases robustness to noise, it still performs worse the more noise is added, such that incentivizing honesty remains important. From the second plot we see that, similarly to the experiment in the main text, the players are incentivized to not send noise as long as the constant C, that controls the strength of our penalties, is sufficiently large. Therefore, our mechanisms are effective in preventing attacks that would otherwise hurt the performance of the players models, even in cases when a robust FL defense is used.\n\nYin, Dong, et al. \"Byzantine-robust distributed learning: Towards optimal statistical rates\". In: International Conference on Machine Learning (ICML), 2018.\n"}, {"review_id": "1TasaWbnJz", "reviewer": "Reviewer_hQqh", "summary": "The paper considers a federated learning setting with strategic data resources. The authors assume that the entities taking part in the learning process are selfish players incentivized to get the best model but benefit if their competitors receive inaccurate models. This selfish behavior pushes players to lie to the central learning mechanism in their reports.\n\nThe authors consider two cases: Mean estimation and a multi-round SGD on strongly convex objectives. They model the players' strategies as multiplicative/additive factors that could be added to the players' actual local computations. The authors show that even in the straightforward case of mean estimation, a PNE does not exist. They offer two remedies: Monetary payments (via peer-prediction techniques) and punishments (noisy model updates by the central mechanism). Then, they show that a PNE exists and characterize the form of payments/punishments required.\n\nFinally, they conduct an experimental analysis demonstrating that their remedies positively affect the learning procedure.\n", "questions": "1.\tStrategy spaces: The assumption that players report their updates along with $\\alpha^i \\xi^i$, where $\\alpha^i$ is player $ i$'s strategy and $\\xi^i$ is a random variable seems completely arbitrary and unjustified. Typically, one makes assumptions about what players aim to do (e.g., maximize their payoff) and what they can do (e.g., bounded computation or memory, acting myopically, etc.). Explicit assumptions about players' strategies without proper grounding and reasoning are cumbersome and inconvenient. Could the authors justify what real-world scenarios the strategy spaces in Eq. (3) models? Could the authors present assumptions about player rationality\\behavior that would recover their modeling? \n2.\tThe assumption about $b^i$ in Eq. (4): What is the justification for this? Indeed, it facilitates the analysis but seems entirely out of context.\n3.\tMulti-round: The authors assume that in the multi-round case, players pick their strategies only once initially. What is the rationale for this modeling? Allowing players to change their strategies throughout the execution will be harder to analyze, but this compromise does not make much sense. \n4.\tCorollary 2: The authors show that a pure Nash equilibrium does not exist, concluding that \"without modifications to the protocol, no player can benefit from collaborative learning.\" While this might be true, I do not see how the inexistence of Nash equilibrium implies collaboration is useless. To reach this conclusion, the authors must show that players are better off (i.e., their estimates are more accurate) without the protocol. Where is this analysis located in the paper? Further, I suspect that a mixed Nash equilibrium does exist, so arguing about whether players can benefit from collaboration should at least consider their payoff under some form of a solution concept (be it mixed equilibrium, sink equilibrium, or otherwise). My question: Could the authors describe why the inexistence of PNE suggests that collaboration is useless?\n5.\tThe methods the authors adopt, e.g., scoring rules, seem to treat the most general case where players can report whatever they want, beyond limiting the structure of their message (Eq. (3) for the mean estimation case). This is at least true in the mean estimation case. The same thing applies to the payment case. What does this paper benefit from making the limiting (and, as I argued before, the highly unjustified) assumption of the structured strategy spaces? \n6.\tWhat is the technical modification of peer-prediction\\noise communication required for this paper? How novel is the derivation needed for this paper, and how does it differ from previous papers? Answers to this question could facilitate the assessment of this paper's contribution.\n\n\nMinor:\n\n•\tWhy are the super scripts m and w needed in lines 198 and 211 (they also appear later in the paper)? \n\n•\t173: clients->players\n\n", "limitations": "None", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe paper deals with a practical issue that is somewhat under-explored.\n2.\tDespite the abundance of notations, the authors have done an excellent job in making the paper read smoothly. \n", "weaknesses": "1.\tThe paper adopts a game theoretic approach, but many modeling assumptions seem cumbersome and unjustified (see questions below).\n2.\tIt is hard to assess this paper's technical contribution. Particularly, the novelty of the peer prediction-based mechanisms are well-studied ideas. The authors did not explain whether this paper adopts these ideas in a plug-and-play manner or presents new non-trivial derivations. The \"our contribution\" part addresses the paper's content but not its marginal contribution to the line of research, making the technical contribution hard to assess.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive and thoughtful review. We are glad you found our paper smooth to read. We aim to answer your questions in the following:\n\n**I suspect that a mixed Nash equilibrium does exist. Also, what does the existence Nash equilibria have to do with benefits from collaboration?**\n\nThank you for pointing this out. Our result holds for mixed Nash equilibria with one important caveat: As explained in line 223, the players’ expected reward is monotonous in $\\mathbb{E}(\\alpha^j(x^j)^2)$ (with the expectation taken over both the sample $x^j$ and a player’s random strategy choice for mixed strategies) as long as any other player uses a fixed $\\beta^i<1$. As $\\beta^i$ and $\\alpha^j$ are independent, this extends to random choices of $\\beta^i$ with  $P(\\beta^i<1)>0$. But the optimal $\\beta^i$ never equals one for finite attacks, so no strategy profile with finite rewards can be stable. However, your comment made us carefully revisit the corollary, and we noticed that we do not explicitly rule out infinite values for $\\mathbb{E}(\\alpha^j(x^j)^2)$ or $\\mathbb{E}(||b^j(x^j)||^2)$. For these infinite strategies, our monotonicity-based argument fails.\n\nThe fact that the only equilibria are “at infinity” also explains why collaboration does not help: If one player uses an “infinite” strategy, all other players’ optimal $\\beta^i$ equals one, such that they completely ignore others’ data, like in the non-collaborative case.\n\nWe apologize for the confusion and will update our paper to better highlight our previously tacit assumption on the finiteness of strategies.\n\n**What do the strategy spaces in Eq. (3) model? What is the justification for assumption (4)?**\n\nAs we discuss in more detail in line 200 of the paper and the general response, Equation 3 without the restrictions posed by Equation 4 essentially expresses the most general attack strategy possible. This is because any possible modification to the mean can be decomposed into a deterministic shift and adding zero-mean noise.\n\nEquation 4 prevents “non-general” strategies whose success depends on the precise value of the parameter $\\mu$ to be estimated. In particular, without it strategies that cannot realistically be implemented without knowing the true parameter $\\mu$, like always sending the true mean $\\mu$, would be admissible. Behaviourally, the assumption can be interpreted as “players do not base their strategies on guesses about the real parameter $\\mu$ that go beyond information obtained from their sample $x^i$.\"\n\nWhile we do agree that Equation 4 also prevents some strategies without this issue, we currently do not know of a weaker assumption that excludes unrealistic strategies while retaining the same mathematical simplicity.\n\nWe will update our manuscript to make this point more clear.\n\n**Why is the strategy space in the multi-round setting restricted to predetermined strategies?**\n\nOur attack structure for SGD is inspired by data-hiding (which increases the variance of the gradient estimates) and Differential Privacy defenses (which add zero-mean noise to the gradient in order to increase the privacy of  local data). We opted for non-adaptive strategies, as adaptive strategies will lead to complex dependencies between consecutive SGD steps. In particular, this would make our already quite involved analysis of the SGD case even more difficult from a purely optimization perspective, since arbitrary dependencies between rounds are highly non-standard in usual gradient-based optimization proofs.\n\n**Why are assumptions made on the strategy spaces?**\n\nWe believe that rigorous analysis of a (relatively broad class of) special cases is essential for progress whenever analyzing the most general case is not tractable. In particular, if we considered more general defenses in the mean estimation setting, even solving a single player version of our game would essentially amount to the classic statistical problem of finding an admissible estimator. Unfortunately, we are unaware of such results for $d \\geq 3$ dimensions in the literature, due to Stein’s paradox. Please also refer to our general response for further discussion on these matters.\n\n**What is the technical modification of peer-prediction required for this paper? How novel is the derivation and how does it differ from previous papers?**\n\nTo the best of our knowledge, our use of noise rather than explicit payments to implement a peer prediction mechanism (5.2) is completely novel. We achieve this using a new reduction of the noise-based case to our payment-based result.\n\nSimilarly, we believe to be the first to use a peer prediction mechanism in a multi-round optimization scheme like SGD. Unlike in prior work, it is not possible to base the mechanism on the final output $\\theta$, as this is a function of all players’ strategies over multiple time steps. This makes it impossible to apply standard arguments that relate the quality of a player’s estimate and how well their estimate predicts other players’ estimates.\n\nInstead, we employ a novel recursive bound for the squared norm of differences in SGD-iterates between a clean trajectory and a trajectory with time-varying gradient noise, that has to take into account ripple effects of noise added during early time steps. This allows us to bound the effect a player that uses a particular strategy can have on the final SGD iterate and thus the loss.\n\nOur first result (5.1) is closest to the existing literature, but there are still important differences: a) In peer prediction, the goal is to incentivize effort to produce good estimates, while our setting focuses on penalizing malicious manipulations. b) As far as we know, our redistribution scheme used to achieve zero expected payment for honest players has not previously been analyzed c) we consider estimates for n-dimensional vectors and arbitrary distributions.\n\n**What do superscripts m and w mean?**\n\nThank you for pointing this out. We have removed these superscripts."}, {"review_id": "piq8BsEal5", "reviewer": "Reviewer_hRji", "summary": "The paper presents an incentive mechanism to encourage honest data reporting in the presence of spiteful behavior aiming to harm other participants. ", "questions": "\nHow can you scale the penalties without knowing the utilities of the model to the participants?", "limitations": "I think the fact that utilities have to be known needs to be stated more clearly.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nThe paper considers an interesting an novel setting.\n\nIt shows that incentive schemes can in principle induce cooperative behavior.\n\nThe incentive schemes show both budget-balance and individual rationality (ex ante).", "weaknesses": "While the reward scheme in the paper has truthful reporting as an equilibrium, it is well-known that peer-prediction schemes also admit uninformative equilibria; for example in this case all participants could report the same data without any penalty.\n*** This was my most important worry and the authors have addressed this weakness in their rebuttal ****\n\nThe schemes requires that the participants observe IID data, which is usually not the case in federated/distributed learning.\n*** This still remains to be improved ****\n\nOnly particular attack and defense strategies are considered.\n*** The authors have convinced me that they have gone far enough at least for this paper. ***\n\nThere is no consideration of data privacy.\n*** This remains future work. ***", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We are glad you find our setting novel and interesting. We aim to address your concerns in the following: \n\n**While the reward scheme in the paper has truthful reporting as an equilibrium, it is well-known that peer-prediction schemes also admit uninformative equilibria; for example in this case all participants could report the same data without any penalty.**\n\nThank you for bringing this up. We agree that equilibria beyond the honest one are usually an issue in peer prediction. However, as discussed in the general response as well, we believe that these are not as problematic in our case. First, as in the general peer prediction setting, honesty offers a natural Schelling point and other equilibria are substantially harder to coordinate on. Second, as laid out in our general response, any non-honest equilibrium will have at least two players with $b^i \\neq 0$, such that all players receive a larger MSE than at the honest equilibrium. Unlike in peer prediction, it is therefore unclear why players would coordinate on a non-honest equilibrium in our setting for the most natural parametrization, $\\lambda_i>1$, where players prioritize more the quality of their own model than damaging others’ models. \n\nWe will update our manuscript to better reflect this important point. \n\n**The schemes require that the participants observe IID data, which is usually not the case in federated/distributed learning.**\n\nWe disagree that we cover IID data only.  The general formulation in Section 3 allows for dependence between the samples (line 107) and we explicitly model heterogeneity in the mean estimation case (line 169). \n\nWhile our SGD theorems currently assume IID data, we believe that they could be extended to the non-IID case in future work. In particular, the FeMNIST dataset contains heterogeneous data, and our experiments demonstrate the efficacy of our mechanism for SGD on that dataset. \n\n**Only particular attack and defense strategies are considered.**\n\nWe would like to highlight that the attack strategies we consider in the mean estimation setting are very general: As discussed in line 200 of the paper and our general response, equation 3 essentially parameterizes arbitrary attacks. Correspondingly equation 4, which prevents unrealistic strategies like always sending the true mean $\\mu$ despite only having access to samples, is the only restriction placed on the strategy space for mean estimation. \n\nWhile the strategy spaces are clearly more restricted in our SGD setting, we would like to point out that intertemporal dependencies make the analysis of that case highly nontrivial, even with our restrictions. \n\nWe did not consider arbitrary defense strategies for two reasons: First, our mechanisms already fully incentivize honesty, such that there is no need for further defenses. Second, as defense strategies can be viewed as statistical inference procedures, analyzing arbitrary defense strategies would require a fundamental breakthrough in statistics: In particular, due to Stein’s paradox, the optimal defense strategy is currently not known for $d\\geq 3$ dimensions, even in a single player setting with data distributions restricted to isotropic gaussians. \n\n**There is no consideration of data privacy.**\n\nWe first note that the considered mechanisms all use gradient information only, so in this sense our approach is equally private/non-private as classic Federated Learning. \n\nAdditionally, privacy concerns are reflected in the considered attack model: Indeed adding noise is a standard way of increasing the Differential Privacy of an algorithm and is often used in practice in Federated Learning, to increase users’ privacy. In that sense, our mechanism could be interpreted as a way to balance players’ privacy concerns with the degradation of the learnt model that is caused by actions taken to ensure privacy. \n\nBeyond that we indeed do not explicitly model privacy into the objectives, as it is an orthogonal aspect compared to competing incentives, which is the focus of this work.\n\n**How can you scale the penalties without knowing the utilities of the model to the participants?**\n\nIt is generally impossible to use any penalty-based incentive scheme without some knowledge about the functional form of players’ utility functions, as rescaling the utility functions by a factor of $K$ would also increase the smallest penalty factor that achieves honesty by $K$. \n\nThat said, a key advantage of our mechanism is that we only require limited information about players’ utilities ($\\lambda_i$ in the Mean Estimation case and the smoothness, Lipschitz and convexity parameters in the SGD case) to correctly scale the penalty. In particular, we do not require any information about the true values of the unknown parameters $\\mu$ or $\\theta^*$. \n"}]

Author rebuttal:
We thank the reviewers for their valuable and constructive feedback. We are glad that the reviewers find our setting novel and interesting ($\color{blue}hRji$), well motivated ($\color{lime}seCF$), our technical contributions novel ($\color{red}Mvyk$) and our text smooth to read ($\color{cyan}hQqh$). We now address the most common questions brought up by the reviewers, and look forward to the reviewers’ replies.

**The mechanisms induce honesty as a Nash equilibrium, but there are other equilibria ($\color{lime}seCF$, $\color{blue}hRji$)** 

While this is true, we would like to put it in context. 

In the peer prediction setting, dishonest equilibria are usually preferable to all players (but the server), but this is not true for most natural instantiations of our setting. In the mean estimation setting, by the proof of theorem 5.1, $\mathbb{E}[b^i(x^i)]$ has to be nonzero for at least two players at non-honest equilibria such that all players receive at least one manipulated update and a worse model than at the fully honest equilibrium. Correspondingly, the sum of all players’ MSEs increases, such that at least some players would prefer the honest equilibrium as long as $\lambda_i>1$. This makes it unlikely for players to take on the difficult coordination task of playing a non-honest equilibrium. In the SGD setting, Theorem 6.1 guarantees that at any equilibrium the losses of the players are close to optimal.

We thank the reviewers for pointing this out. We will add a more detailed discussion of this in the final version.

**The considered strategy spaces are restricted ($\color{cyan}hQqh$, $\color{blue}hRji$)**

As noted in line 200, the attack strategies we consider for mean estimation are quite general: Equation (3) essentially parameterizes the most general attack space in a more interpretable way: Any random variable $m(x)$ that represents a message can be written as $\bar{x} + b(x)+\alpha(x)\xi$ where $b(x) =\mathbb{E}[m(x)|x]-\bar{x}$ and $\mathbb{E}[\xi|x]=0$. 

Equation (4) effectively prevents $b^i$ from encoding knowledge about $\mu$. This restriction is needed to exclude “non-general” strategies, whose success depends on the true value of the parameter mu that is to be estimated, such as always sending a constant value $m^i$, so that $b(x)=m^i-\bar{x}^i$.

Our strategy spaces are more restricted in the complex SGD setting, where, however, the attack space has several natural interpretations, such as adding a noise-based differential privacy defense or hiding samples from the empirical estimates. That said, we would like to point out that the use of restricted strategy spaces/classes of estimators is common in both game theory and statistics. In particular, the optimal solution to even a single player version of our Mean Estimation game for an isotropic gaussian distribution is unknown for fully general strategy spaces in $d\geq 3$ dimensions, due to Stein’s paradox.

**Do meaningful mixed Nash equilibrium exist without our mechanisms ($\color{cyan}hQqh$)?**

Indeed, our result already includes mixed equilibria. The confusion might in part have been caused by an imprecision in the corollary statement: As our monotonicity-based argument for the nonexistence of equilibria only works as long as rewards are finite, the corollary should state: “... does not have any (mixed) Nash equilibrium for which $\mathbb{E}(\alpha^j(x^j)^2)$ and $\mathbb{E}(||b^j(x^j)||^2)$  are finite for all players.”

We apologize for the confusion and will update the paper to clarify this point by updating the corollary statement to the version presented above.

For more details, please consider the individual response to reviewer $\color{cyan}hQqh$. 

**It is not clear from the manuscript whether our results are a straightforward application of existing peer prediction results or require novel technical methods ($\color{red}Mvyk$,$\color{cyan}hQqh$)**

We thank the reviewers for pointing this out and will aim to highlight the key technical challenges better in future versions of our manuscript. We respond to each reviewer individually and provide a summary below. 

To our awareness, our work is the first to explicitly model competitive incentives between clients in collaborative learning. Our first key technical insight is that ideas from peer prediction, which instead focuses on conflicting interests between the server and clients, can be applied to this setting.  

To the best of our knowledge, both the noise-based mechanism (Theorem 5.2) and our application of peer prediction to SGD (Theorem 6.1) are entirely novel. The analysis of the former required a nontrivial reduction to the payment-based case, while the analysis of the latter is based on a novel recursion for the squared norm of differences in SGD-iterates between a clean trajectory and a trajectory with time-varying gradient noise. 

**Additional experiments ($\color{lime} seCF$,$\color{red} Mvyk$)**
 
We added further experiments, one using a different dataset and model; and one that compares our schemes to an existing method for robust FL. Please refer to the response PDF and the individual responses to reviewers $\color{lime} seCF$ and $\color{red} Mvyk$ for further details.

**The schemes require that the participants observe IID data ($\color{blue}hRji$)**

We disagree that we only cover IID data – Sections 3,4,5 and 7 explicitly analyze various non-IID settings. We will highlight this better in the next version of the manuscript. We refer to the individual response to Reviewer $\color{blue}hRji$ for more details. 


Meta-review: Three of the four reviewers are positive, the fourth reviewer feels that the assumptions and the technical novelty are not sufficiently unjustified. My own opinion (after reading the paper, the reviews and the rebuttals) is that it is not a clear accept, but the positives overweigh the negatives. I strongly encourage the authors to revise the paper and address the reviewers' concerns to the extent possible.
Decision: Accept (poster)