FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding?
Authors: Marco Bornstein
Amrit Bedi
Abdirisak Mohamed
Furong Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: Federated Learning
Truthfulness
Free-Riding
Primary area: infrastructure
TL;DR: We propose a FL mechanism that ensures agents do not free ride even when they are untruthful.

Abstract: Standard federated learning (FL) approaches are vulnerable to the free-rider dilemma: participating agents can contribute little to nothing yet receive a well-trained aggregated model. While prior mechanisms attempt to solve the free-rider dilemma, none have addressed the issue of truthfulness. In practice, adversarial agents can provide false information to the server in order to cheat its way out of contributing to federated training. In an effort to make free-riding-averse federated mechanisms truthful, and consequently less prone to breaking down in practice, we propose FACT. FACT is the first federated mechanism that: (1) eliminates federated free riding by using a penalty system, (2) ensures agents provide truthful information by creating a competitive environment, and (3) encourages agent participation by offering better performance than training alone. Empirically, FACT avoids free-riding when agents are untruthful, and reduces agent loss by over 4x.

FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding?
Marco Bornstein University of Maryland marcobeund. edu
Amrit Singh Bedi University of Central Florida amritbedi @ucf edu
Abdirisak Mohamed University of Maryland SAP Labs, LLC edu amoham7
Furong Huang University of Maryland furongh@umd edu
O@umd. amoham70@umd.
Abstract
Standard federated learning (FL) approaches are vulnerable the free-rider dilemma: participating agents can contribute little to nothing yet receive a well- trained aggregated model. While prior mechanisms attempt solve the free-rider dilemma, none have addressed the issue of truthfulness. In practice, adversarial agents can provide false information the server in order to cheat way out contributing to federated training. In an effort to make free-riding-aver avverse federated mechanisms truthful, and consequently less prone to breaking down in practice, we propose FACT. FACT is the first federated mechanism that: (1) eliminates federated free riding by using a penalty system, (2) ensures agents provide truthful information by creating a competitive environment, and (3) encourages agent par- ticipation by offering better performance than training alone. Empirically, FACT avoids free-riding when agents untruthful, and reduces agent loss by over 4x.
1 Introduction
Truth is essential the functioning of fair systems. In its absence, fraud and corruption lead to negative effects on those left participating. This too true within machine learning (ML). Adversaries can attack ML algorithms for insidious purposes [3, 7]. and algorithms trained data that is not well-representattiv or poisoned can lead to dangerous and unfair results [28, 29, 37].
Issues of truthfulness have begun to bleed into multi-agent collaborative learning systems. Federated Learning (FL), the preeminent collaborative learning framework. susceptible the free-rider dilemma: agents can contribute little to nothing during training while still obtaining a well-trained final aggregated model [8. 12, 17J. Furthermore, Karimireddy al. [12] proves that standard FL algorithms naturally yield catastrophic free-riding equilibria, where most rational agents contribute nothing. It is important note that we do not consider the possibility of malicious gradient updates from adversarial agents, covered by recent works [6, 23, 25, 27J. We assume that agents share common goal of reducing loss, and act selfishly rather than maliciously.
Recent work has aimed to remedy the free-rider dilemma in through contract theory [4, 11, 16, 19), collaborative fairness [21, 26, 36), and mechanisms that incentivize contributions [2, 12]. The mechanisms presented in Karimireddy et al. [12] and Bornstein et al. [2] are notable because they do not require (i) carefully optimized contracts (agents will always participate because the mechanism is individually rational) or (ii) alterations to standard FL training (simple FedAvg [22] can be run with
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

no computation of agent reputations), However, these mechanisms assume that agents are honest and truthful with an orchestrating central server. If agents can lie, the proposed mechanisms no longer guarantee elimination of free riding.
In our paper, we propose mechanism, Federated Agent Cost Truthfulness (FACT), that provably climinates free riding even when agents are untruthful. Unlike standard FL approaches, where agents are incentivized to use little to none of their own data, agents participating in FACT are incentivized to use as much data for federated training as they would on their own. Furthermore, when agents use their locally-optimal amount of data, FACT is individually rational (IR): agents always receive greater benefit participating in FACT than by training alone. These results hold even if agents try to cheat the mechanism by misreporting individual training costs to the central server. FACT ensures that each agent's 's best strategy is to be truthful with the central server.
Summary of Contributions. In summary, the main contributions of our paper are, (No Free Riding):
Creating novel penalization scheme that shifts the catastrophic free-riding optimum back to each agent's s local optimum (thereby eliminating free riding).
(Truthfulness): Constructing a truthfulness mechanism (competition) that dissuades agents from lying about their individual costs with the central server.
(Realistic): Showcasing the efficacy of FACT empirically in eliminating agent free riding under untruthfulness, consequently improving federated training performance.
2
Related Works
Distributed Learning Mechanisms for Agent Contribution. An important line of mechanism research in distributed learning regards mechanisms that incentivize agent contributions for federated training [2, 12, 18, 38, 39J. Some of the first papers in this area were application-based, namely in mobile crowdsensing and smart sensors in vehicles. We detail these works in Appendix A. Zhan et al. [39] is one of the first works to define agent and server utility when data is shared between agents and the server train a global model (including agent training costs). The server announces a total reward, and agents determine how much data to contribute in order to maximize their reward. A deep reinforcement learning method is used by the server to learn the optimal announced reward.
An accuracy-shaping mechanism is proposed in Karimireddy et al. [12), which also follows a similar data sharing and iid setting. This mechanism does not require the use of contracts or learning of a reward, and guarantees that an agent will receive improved reward when participating in the mechanism than by not participating. In the accuracy-shaping mechanism, the server degrades model performance for an agent if it does not contribute as much data as locally optimal. Bornstein et al. [2] proposes similar securacy-shaping mechanism. However, unlike Zhan al. [39] and Karimireddy et al. [12]. agent utility is modeled in a non-lincar and more realistic manner. Additionally, the accuracy-shaping mechanism is generalized to the federated setting (no data sharing) where data can be non-iid. Unlike the majority of the works above, our mechanism seeks not just to incentivize agent contribution, but to eliminate free riders. Moreover, unlike [2, 12], we do not assume that agents truthful. Our mechanism ensures that agents contribute what is locally optimal, thereby eliminating free-riding, and punishes agents for lying the server about their costs.
Truthful Distributed Learning Mechanisms. Similar to the agent contribution mechanisms above, many existing truthful distributed learning mechanisms exist within the crowdsensing setting [9, 33, 35, 42]. We detail these works in Appendix A. The more recent works [14, 20, 34] examine truthful mechanisms within traditional FL. Lu et al. [20] explores truthful mechanisms in Vertical FL, where features are split up amongst agents. Specifically, truthful mechanism designed (via a novel transfer-payment when agents can lie about their costs. Within Horizontal FL (the standard approach), Le et al. [14] designs randomized auction for resource-conan constrained wireless agents, which achieves approximate- truthfulness in expectation. The server receives bids from agents to perform training, and selects a winning bid (agent) for each uplink sub-channel. The server pays reward designed to minimize agent social cost, and does not take into account the server's utility. Wu et al. [34] builds on the auction idea in Le et al. [14], instead using a federated auction bandit which learns to select bidding agents
rule) to maximize social utility, without use of an auction, even

---

that maximize the server's utility. The mechanism ensures truthfulness and individual rationality. Like the works above, our mechanism ensures truthfulness and individual rationality of participating agents. In contrast, our mechanism setting is within horizontal FI. and does not require an auction or bandit method to ensure truthfulness. As such, any willing agent can participate in training (no bids are rejected), an optimal server reward does not need to be learned, and agents do not need to have a private valuation. Finally, our mechanism requires no direct payment from the server (all reward payments come from other agents) and provably eliminates the free-riding dilemma. Due to space constraints, we detail works regarding fairness and agent selection mechanisms Appendix A.
3 The Challenge of Free Riding in Federated Learning
Federated Setting. Our work explores the setting of Centralized Federated Learning (CFL), where n agents collectively train model w under orchestration of central server. Within each iteration of CFL, the server sends down the current aggregated model w. to each agent. Agents then perform local gradient updates (with their own local data) to generate an updated model w Vi E [n]. Models are aggregated by the server and this process is repeated until convergence. Each agent is assumed to have access to the same data distribution DD and thus we assume data is independent and identically distributed (iid). We leave construction of truthful mechanisms in the non-iid setting for future research. Our work aims to bring truthful mechanisms to CFL, as none have existed in either the iid or non-iid settings prior this work. We now begin by detailing the objective that agents participating in FL seek to minimize.
Federated Objective. The goal of FL is to train a global model, leveraging the data and compute power of thousands of agents, that achieves low loss. To start, we utilize the convergence of distributed stochastic gradient descent (D-SGD) [15] to first-order stationary points in non-convex settings,
2A, 7
707
+ Σ EIVS(w))
2
2=j=1 mj
The parameter A, is the difference between the optimal objective value f and starting value f(w"). The global objective function f is the uniform sum over all device objective functions ft. There are I' total iterations. The step-size is y and L is the Lipschitz constant, where 7L 2. The effective gradient variance is o²/ j my. This stems from bounded variance assumptions, formally defined
as E|| EM i=1 Vf(u: (t) V f(w)] < o² M (for M batches of data E
Local Agent Loss. All rational agents seek to minimize their loss. As shown in Equation (1), this can be accomplished by using more data, and thus a larger batch size m, as well as more rounds of gradient updates T. However, all agents incur a cost c; for collection, sampling, and compute costs for each data sample m used. The linear cost e,m stems from our cross-agent setting. Within this setting, ToT devices are prevalent and data is not difficult to collect (e.g., IoT sensors). Thus, it makes the most sense that, on average, there are constant costs over time to collect and sample data (e.g., the cost to power sensor is usually constant on average) [30, 20, 34].
Overall, agents must balance the benefit of using more data to achieve better model performance with the costs of data collection, sampling, and computations. We formulate this tradeoff for each agent by defining local loss function (,,,m, that depends the data collected m, by each agent i. Each agent minimizes its loss function, which is a combination of data costs and convergence error terms. When training locally, alone, an agent loses the benefit of an increased batch size across all agents Σj=1 my. Thus, after removing constants, Equation (1) transforms into our local agent loss
(m)) = 700L + c;m4
(2)
2m;
The optimal amount of data each agent uses for local training can be determined with calculus.
3

---

Theorem (Optimal Local Data Usage). For an agent with marginal cost C₁. the optimal amount of data m used for local training is m ==
2
2c,
Remark 1. Agents' optimal amount of local data is inversely proportional to its cost Ct. Larger costs lead to less data used and vice versa. If costs were zero, agents would use infinite data.
The Free-Ridee Dilemma: Shifted Optima in Federated Settings. When agents engage in federated training, the effective batch size returns to the sum over all agent data Σ}=1 my- By participating in federated training, agents gain the benefit of an increased batch size. As such, each agent i's loss function in the federated setting becomes.
707L
(,,r(m;) == 2(m; mm
+ c.
While slight, this transformation changes the optimal amount of data used by each agent.
Theorem 2 (Free-Riding Optimal Federated Data Usage). For an agent i with marginal cost the optimal amount of data m used for federated training is m.,FF = =V1g2 7
Em---
2cr
By participating in federated training, each agent is incentivized use fewer data samples. This explicitly demonstrates the free-rider dilemma mathematically: it may optimal
Remark 2.
for an agent to use no data m = 0 (if Σ m_ 2 v
[ and still possibly achieve lower cost 20;
overall Cif m- 2 m.
Due to space constraints, we leave the proofs of Theorems and 2 in Appendix C.
4 Eliminating Free Riding via Penalization
The natural equilibrium of traditional FL is free riding: agents use less data than is locally optimal in proportion to how much data other agents use (Theorem 2). This necessitates the construction of mechanism to restore the equilibrium of FL back to what is locally optimal for each agent. In this section, we detail how penalization can perform this restoration.
Penalized Federated Learning (PFL). To disincentivize agents from straying from their locally optimal data usage m the central server can use contract theory to ensure each agent uses its locally optimal amount for reported cost q, Namely, when agrecing to participate in FL, each agent
i agrees to pay the following free-riding penalty Pfr if they do not use m
J0 data samples, 20;
(ma(m)) = >rl Ci 2A, 47, + Σ m_ + +m m2)
(4)
The hyperparameter A chosen by the central server, denotes the harshness of the free-riding penalty. The value of A; is known by each agent while deciding whether or not to participate in the mechanism. Since the penalty is levied on each agent by the server, incorporated into their federated loss function. This results in new amended federated loss function 4, (m:) defined as,
2
(mFF((m)) 2(m; + Σ m- + com, + (pr))..).
f. (m.)
Theorem (PFL Eliminates Free Riding). For an agent with marginal cost G. the optimal amount of data PFLFFL used for federated training under Equation (5) is M = / 1
2c,

---

Algorithm PFL: Penalized Federated Learning
1: Input: data [mi,...., Ma]. marginal costs [e1, y..., Cn), , h local steps, T iterations, E epochs, initial parameters w², loss f, step-size 7, and constants (I,, o² ,a,a,, a))
2: Output: model w".
3: Server determines expected optimal data use for each agent my +- V
200L 2c,
4: Server computes each agent's ' penalty scalar X; f-
(2-a)no²L
m; (
(c:
2 20
=+m3)²)
5: Server receives free-rider penalty payment Pyr from each agent via Equation (4) using X
6: 9, <- m./ 2///5510 m
7: (or1=1,.... do
8: Server distributes w' all agents
9:
for h local steps, each agent in parallel do
10: w f- AAgent Update(w" , m,
[AgentUpdate detailed Algorithm 3)
11: end for
12: w t- E,00
13:
end for
Remark 3. By utilizing the PFL loss in Equation (4), agents participating in FL will use locally optimal data amount (m, PFL. = m) This eliminates the free-rider dilemma seen in Theorem 2.
Agents participating in PFL (Algorithm 1) follow the amended loss shown in Equation (5). Careful selection of X; is required to ensure that PFL is IR.
Ensuring Individual Rationality (IR) in PFL. As shown above in Theorem 3, optimal for agents participating in the penalized federated scheme (with loss function shown in Equation (5)) to contribute what is locally optimal i.e., mi
m,, ensure individual rationality, must be true that participating in federated training will produce least as much reward for an agent than by not participating. The selection of X₂ is crucial in accomplishing this task.
Lemma 1 (PFL. Assurance of IR at Optimum). Let be the marginal cost for an agent i, m = 700L m mi,FLL be the agent's 's locally optimal data usage, and E (0, be 2c,
server- specif-e hyper-paraneen In order to ensure that the optimal penalized federated loss least lower than the optimal local loss, (.PFL((;) L.,(m?),
), one must select Xs such that,
m (E (Em)
(a - 2(E m_i
702L
A = (2 a2 L _m m_
(6)
2(Em, + )²)
Selection of such d; results in a loss gap between (i,pri(m") and (i,((m²) of.
se, = - a 70² L 1-Em-
(7)
4 m (mm()mm m_ + m
Agents provably receive improved loss A when they use their locally optimal data amount m participating in PFL (Algorrim 1) versus local training, thereby ensuring IR.
Remark 4.
Remark 5. The parameters Xs and a control the amount of benefit received by an agent i. larger value of a, and consequently > results in larger gap between F. (m²) and (,,(m²)). Inversely, a smaller value of a and 0 results in a smaller gap between local and PFL loss.
Due to space constraints, we leave the proofs of Theorem 3 and Lemma 1 in Appendix C. Now, we formally prove that PFL both (i) eliminates agent free riding and (ii) is individually rational.
Theorem (Elimination of Federated Free- Free-Riding With Truthful Agents). PFL (Algorithm 1) using X from Lemma is IR and eliminates the free-rider dilemma when agents are truthful.
Proof. The result of Theorem 3 is that each agent i's optimal strategy within the penalized federated 20LL Furthermore, Lemma states scheme is to use their locally optimal amount data m = / 2G,
that using my within the penalized federated scheme results in reward, or improvement over local
5

---

Algorithm 2 FACT: Federated Agent Cost Truthfulness
1: Input: data [mm,...., ma), marginal costs = [et,..., Cn), h local steps, T iterations, E epochs, initial parameters w', loss J. step-size 7, and constants (I., o² ,a,a), ())
2: Output: model w" and monetary reward rg.
3: Server receives contract payment from each agent: Al; +- a ( m
4 m: m)
4: Run Penalized Federated Learning: w" PFL(m, c, h, T, E, w J, 7, L, 0² a)
5: Compute each agent reward r; via the cost truthfulness game in Equation (10)
m Thus, by combining Theorem 3 and Lemma 1, truthful agents which choose to participate in PFL attain a reshaped and lower loss the same optimum. Individually rational agents would therefore prefer to participate in PFL (Algorithm 1) over local training due the reshaped optimum's s lower loss. This optimum achieves the same data usage as local training, thereby eliminating the free-rider dilemma.
training, of A4, = ya
Remark 6 (Truthfulness Concerns). Participating in PFL, rational agents contribute as much as they would locally (Theorem 3) and altain more benefit (Lemma 1). The only issue that remains is truthfulness: agents may lie about their costs in order to contribute less to federated training under the guise of what looks like an "optimal amount" the server (thereby avoiding large Pfr))
While PFI. eliminates free riding when agents are truthful, this assumption is not realistic in practice. Untruthful agents can report inflated costs to the server in order to trick it into expecting smaller data usage. In effect, agents can lie about their costs to free ride. In the next section, we propose mechanism which incentivizes agents to be truthful (i.e., their best strategy not to lie).
5 FACT: Eliminating Free-Riding With Untruthful Agents
When agents are truthful, PFL (Algorithm 1) provably eliminates the free-rider dilemma (Theorem 4). However, adversarial agent i can still free ride by misreporting, lying, about their true marginal cost C. As previously mentioned, we do not consider the situation of malicious gradient updates coming from adversarial agents, covered by recent works [6. 23, 25, 27]. We assume that agents share a common goal of reducing loss, and act selfishly rather than maliciously.
As seen in Theorem 2, an adversarial agent can lie their way to a smaller data optimum by inflating their cost: mn! = V 2 < m In this case, an adversarial agent will (i) avoid server penalty [[c+te)
(since it will be contributing what looks like an optimum from the server's view), (ii) incur smaller true costs c.m. lie < c,m,, and (iii) still reap the benefits of a larger batch size Σ m + m
Definition 1 (Truthful Mechanism). A truskful mechanism is one in which no agent can reduce its loss by reporting a cost different from its true cost, regardless of other agents' actions. Overall, each agent's dominant strategy is to report its true cost.
To counteract the possibility of an agent being untruthful with the server about its true cost, we propose truthful mechanism FACT: Federated Agent Cost Truthfulness (Algorithm 2). FACT ensures that each agent i's dominant strategy to report its true cost e; (thereby satisfying Definition 1).
Assumption (No Collusion). Agents have no knowledge of other agents' costs or the distribution of agent costs fc. In the absence of information, each agent believes that its cost e; is equally likely to be larger or smaller than any other agent's 's cost.
Our lone assumption about agent knowledge is that agents are unknowledgeable about the distribution of agent costs fc or any other agent's cost: agent costs are private. Assumption I ensures that there no collusion amongst agents. In the absence of knowledge about other agents' costs, it is reasonable for an agent to believe that their private cost is equally likely to greater or lesser than any other agent's 's cost (i.c., the median cost). Now that agents can report costs c which differ from their true cost

---

Expected Improvement in Loss
Expected Improvement in Loss
N-II (D-0.6)
N-IID (D-0.6)
(D-0.3)
(D-0.3)
0.8
0.6
Percent (%) Added/Subtracted from True Cost c)
Percent (%) Added/Subtracted from True Cost
Figure I: Enforcement of Agent Truthfulness. Average net improvement in loss over local training plotted for iid (dotted line) and two non-iid agent distributions (D-0.6: dashed, D-0.3: solid). For both CIFARIO (left) and MNIST (right), agents maximize their net improvement in loss when they truthful (0% added) about their true cost. This matches our theory in Theorem 5.
C₁ each agent's PFL penalty (Equation 4) and loss (Equation 5) becomes a multivariable function,
L
Pfr(m,,)
=d(
m,)²
(8)
21
41:(V
2021 2a
+ Σ m
2c
(.PFr.(m;,c) 2(m; + mm
c.m4 + (fr(m;;
Regardless of the reported cost c, each agent i will incur true cost c,m, locally in Equation (9).
Using Sandwich to Incentivize Truthfulness. Our mechanism is the first ensure truthfulness while solving the free-rider dilemma in FL. FACT ensures agent truthfulness by fostering a competition amongst agents. The competition begins the end of federated training (PFL) by randomly grouping reported agent costs into threes. The rules of this competition, or truthfulness mechanism, are simple: each agent "wins" the competition, and receives a reward, if its cost с is sandwiched between the two other agent costs in its group. If there is tie, the server randomly selects one of the tied agents as the winner. This mechanism is detailed mathematically below,
3
Σ Al, jAAE(()
if C. < Cb.
Par(c)== =
Cas Co fc randomly sampled costs (10)
AC
else.
Lemma 2. The probability of an agent "winning" in the truthfulness mechanism in Equation (10), given reported cost c, is v(c) == 2Fc(c) -F((c)), where Fc is the CDF of fc-
The crux of the truthfulness competition is that each agent never receives its own reward A Instead, shown Equation (10), each agent pays Ać; the server before training regardless the mechanism outcome. After training, if the agent "wins" the competition, by having a cost sandwiched between Cg and C.. then it receives triple the average of all other agent rewards 3 The average reward is tripled, since two other agents will lose the competition and receive no reward. By making the reward decoupled from agent's 's own reward AC, each agent can no longer increase or decrease reward by altering how much data m, they use for federated training. Now, they can only affect the likelihood of winning the competition by choosing what cost to report to the server.
n Ejzie(n) Aly-
Incorporating the truthfulness mechanism into the PFL function results in the FACT loss function,
702L
(s, c) 2(m; + Σ m..) cam, + (fr(m; c) +Pa(c).
(11)
(.PFI(mEe))

---

Expacted Lozs
Expected Loss
Expected Loss
10a
18a
Expectea LOSS
Expecten LOGS
Expected Loss
20
23"
Tranning Trainin
Feadioona
Training FACT Training Traditinal
Local Training
Training
Traditional
Reduction in Agent Loss. The average agent loss for baselines on CIFAR1O (top row) and MNIST (bottom row) under iid (left), and two non-iid data distributions (center: D-0.6, right: D-0.3). Traditional FL an upper bound on agent loss (if agents did not free ride). FACT improves agent loss over local training by up to factor of 3x for CIFARIO and 4x for MNIST.
Figure
Theorem 5 (Main Theorem). Each agent i's best strategy, when participating in FACT (Equation
11), to report its true cost and use its locally optimal amount of data (ma, c)ī (V
7
c.).
2c,
Remark 7 (Truthfulnesss. FACT is a truthful mechanism: each agent's 's best strategy is to report its true cost Cç. Agents cannot reduce their loss by reporting a different cost (satisfying Definition 1).
Remark (Elimination of Free Riding). FACT eliminates agent free riding: each agent's 's best strategy is to use as much data as locally optimal m = - T00L
(Theorem 1). Thus, the 2c,
improved optimum for PFL PFL (Theorem 3) is maintained even under agent untruthfulness.
Remark 9 (Individually Rational). When using their best strategy, agents participating in FACT either (i) receive loss equivalent to local training if they lose the competition or (ii reduced loss if they win (shown in Equation 10). Thus, FACT IR as agents using their best strategy never receive worse loss than if they did not participate. In fact, agents receive lower loss in expectation.
Experimental Results
Below, we analyze the effectiveness FACT at (1) enforcing agent truthfulness, (2) eliminating free riding, and (3) reducing agent loss compared local training. We perform true federated experiments (no simulations) using CIFARIO [13) and MNIST (5) datasets to train an image classification model.
Experimental Setup. Within our experiments, 16 agents train model individually (locally) as well as federated manner. Each agent uses 3,125 and 3,750 data samples each for CIFARIO and MNIST respectively. We analyze FACT under homogeneous and heterogeneous agent data distributions. For heterogeneous agent data distributions, we use Dirichlet distributions with parameters 0.3, 0.6 to determine the label ratio for each agent [10]. We simulate the sandwich truthfulness competition defined in Equation (10) by randomly sampling 2,000 synthetic agent costs from Gaussian distribution with mean centered at each agent's 's true cost (standard deviation of one-tenth of the true cost). We perform 100,000 simulation trials and compute mean performance for each agent over all trials. Further experiment details and hyperparameters found in Appendix B.

---

Free-Riding Penalty + Data Costs
Free-Riding Penalty Data Costs
Optimal Contribution
Thee Optimal Contribution
2.0
1.5
1.0
0.5
3250
3750
Data Contributed m)
Data Contributed
Figure 3: Elimination of Free Riding via Penalty. The penalty term (m,( plus data collection costs c,m, is plotted for CIFARIO (left) and MNIST (right) for varying data contributions my. These combined costs are minimized at the local optimum m. as predicted by Theorem 3.
Lack of Baselines. FACT is the first truthful Horizontal method that eliminates free riding while simultaneously enforcing truthfulness without the use of an auction or bandit (thereby allowing all willing agents to participate). As such, we compare the results of FACT with the only available option: local training. We showcase below that FACT reduces agent loss compared to local training while simultaneously avoiding free-riding and truthfulness issues.
FACT Enforces Truthfulness. The results of Figure back the theoretical result of Theorem which states that agents maximize their expected reward (i.e.. net reduction in loss versus local training) when truthfully reporting their cost. Across both homogeneous (iid) and heterogencous (n-iid) agent data distributions, agents' net improvement in loss peaks when reporting their true cost (0% added) and monotonically decreases as agents report an inflated or deflated true cost. Thus, the sandwich-styy truthfulness competition FACT employs disincentivizes agents from inflating deflating their true costs. This is important, as agents are no longer incentivized to lie to the server about their true cost in order free-ride without the free-rider penalty in Equation (4) being imposed. Net improvement in loss grows as data distributions become increasingly non-iid. FL is robust enough deal with the increasingly non-iid datasets while local training suffers (Figures 5 & 6). Therefore, the gap between FL and local training grows, and thus so too does the reward in FACT.
FACT Reduces Agent Loss. Agents participating in FACT on average achieve a reduction in total loss compared to training on their own when using the same amount of data. Consequently, participating in FACT is individually rational: agents at worst receive loss equivalent to local training and on average receive improved loss (Figure 2). Traditional FL achieves lower average agent loss than FACT when all agents use as much data they would locally. However, as shown in Theorem 2, this is unrealistic. Traditional FL emits catastrophic free-riding optimum. The results of traditional FL in Figure 2 is the upper bound achievable loss by agents, only attainable if agents refused to free ride. The gap in loss between FACT and the upper bound of traditional FL is the cost of agent untruthfulness and their inclination to free ride. The gap is the direct result of the penalty terms on free riding Pyr and truthfulness Pa found Equation (11). Average local loss increases as data distributions become increasingly non-iid, while traditional FL remains robust to the distribution shift (Figures & 6). Since the agents in FACT who lose the truthfulness competition receive a loss equivalent to local training, the loss of FACT also rises in proportion the local training loss.
FACT Eliminates Free Riding. Within experiments for CIFAR10 10 and MNIST, marginal cost was carefully selected such that it is locally optimal for each agent to use 3,125 and 3,750 data samples for training respectively. As shown in Figure the free-rider penalty Pfr harshly penalizes agents for deviating from this locally-optimal amount. This result accounts for the reduction (gain) in data collection costs for using less (more) data during training. Thus, proven theoretically in Theorem 3, we confirm that it is suboptimal for an agent to use either more or less data than is what locally optimal (for a given reported cost c,) when participating in FACT.

---

Frei Ridd-Ridinggg Penalty Duta Costs
123
Tux Outine Coesbekk
Expected Lozs
3.2
6.3
Local Trairing
Trilting
TradBtona
1951
Percent (%G Addet//ub True Cost
Contributed
Figure 4: FACT Eliminates Free Riding in Realistic Settings. When training an image classifier for diagnosing skin cancer, agents participating in FACT achieve much lower loss (66% less) than they did not participate (left). Agents maximize their improvement in loss local training when they are truthful; reporting inflated or deflated costs diminishes improvement in loss (middle). Agents minimize penalties when using their locally optimal amount of data (m" 801) for training (right).
6.1 Real-Worlee Case Study: Inter-Hospital Skin Cancer Diagnosis
We consider a realistic situation where a consortium of hospitals seek collaboration to train a model, privately FL manner, that can diagnose skin cancer. One of the hospitals smaller and resource- constrained. It is difficult, but not impossible, for this hospital to collect more data for training. Thus, in the absence of truthful FL mechanism, the smaller hospital could over-report its collection costs to the server in order to contribute little to no data towards training while still reaping the rewards of well-trained global model.
To test how FACT deals with this scenario, we train an image classification model on the HAM10000 [31] dataset. HAM10000 consists of a collection of dermatoscopic images of pigmented lesions. The goal is to train model which can perform automated diagnosis of pigmented skin lesions, including melanoma (skin cancer). Our setup is similar to the experimental setup detailed in the previous section. One difference that we fine-tune ResNet50 model on HAM1000K that is pre-trained on ImageNet (a realistic approach for hospital). HAM10000 is an imbalanced dataset, and evenly partitioning 80% the data amongst 10 devices, as their local training sets, further exacerbates the non-iidness of the data. This too is realistic, as data is often non-iid amongst FL agents. We the Adam optimizer with a learning rate of 1e-3 and batch size of 128.
As expected, FACT provably dissuades any hospital from lying about its cost in order to reduce their data contribution level. Agents incentivized to be truthful; reduction in loss is maximized when agents truthfully report their costs (see the middle plot in Figure 4). As a result, a smaller, snourced-constrained hospital would still contribute its locally optimal amount of data, face harsh penalties (see the right plot in Figure 4). Finally, all participating hospitals are still better off participating in FACT than training alone. Participating agent loss is reduced by nearly 66% compared to local training (see the left plot in Figure 4). The effectiveness of FACT to dissuade free-riding in the real-world setting of training a skin cancer classifier across hospitals indicates that it will be successful in other real-world settings.
7 Conclusion
Traditional FL frameworks are susceptible to free riding: it is often an agent's best strategy to contribute little to nothing during training while still obtaining well-trained final global model. Furthermore, many FL frameworks do not account for untruthful agents which report inaccurate information to server in order to skip penalties and collect greater rewards. Our proposed mechanism, FACT, simultaneously individually rational, truthful, and eliminates free riding. FACT leverages a novel penalization and sandwich mechanism to shift each agent's 's best strategy to report its true cost with the server (truthfulness) and use as much data as it would on its own (no free riding). Furthermore, agents which participate in FACT will never receive worse loss than by not participating. and receive lower loss on average if they participate (individually rational). Empirically, we find that FACT enforces agent truthfulness while reducing agent loss by upwards of factor of four.
10

---

Acknowledgments
Bornstein and Huang are supported by National Science Foundation NSF-IIS-2147277 FAI, DOD- ONR-Office of Naval Research under award number N00014-22-1-23355, DOD-AFOSR-Air Force Office of Scientific Research under award number FA9550-23-1-0048 DOD-DARPA-Defema Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD) HR001 12020007, Adobe, Capital One and JP Morgan faculty fellowships.
References
[1] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference Machine Learning, pages 1005-1014. PMLR, 2021.
[2] Marco Bornstein, Amrit Singh Bedi, Anit Kumar Sahu, Furqan Khan, and Furong Huang. Realfm: A realistic mechanism to incentivize data contribution and device participation. arXiv preprint arXiv:2310. 13681, 2023.
[3] Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-bars adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.0422 2017.
[4] Mingshu Cong, Han Yu, Xi Weng, and Siu Ming Yiu, A game-theoretic framework for incentive mechanism design in federated learning. Federated Learning: Privacy and Incentive, pages 205-222, 2020.
[5] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-142, 2012.
[6] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to (Byzantine- -orzantine-Robust federated learning. In 29th USENIX security symposium (USENIX Security 20), pages 1605-1622, 2020.
[7] Samuel G Finlayson, John Bowers, Joichi Ito, Jonathan L Zittrain, Andrew L Beam, and Isaac S Kohane. Adversarial attacks on medical machine learning, Science, (63 1289, 2019.
[8] Yann Fraboni, Richard Vidal, and Marco Lorenzi. Free-rider attacks model aggregation in federated learning. International Conference on Artificial Intelligence and Statistics, pages 1846-1854. PMLR, 2021.
[9] Guoju Gao, Mingjun Xiao, Jie Wu, Liusheng Huang, and Chang Hu. Truthful incentive mechanism for nondeterministic crowdsensing with vehicles. IEEE Transactions Mobile Computing, 17(12):2922-2997, 2018
[10] Liang Gao, Huazhu Fu, Li, Yingwen Chen, Ming Xu, and Cheng-Zhong Xu. Fedde: Federated learning with non-iid data via local drift decoupling and correction. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10112-10121, 2022.
[11] Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet of Things Journal, 6100:1070-11714 2019.
[12] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04555 044577, 2022.
[13] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.

---

[14] Tra Huong Thi Le, Nguyen H Tran, Yan Kyaw Tun, Zhu Han, and Choong Scon Hong. Auction based incentive design for efficient federated learning in cellular wireless networks. In 2020 IEFE wireless communications and networking conference (WCNC), pages 1-6. IEFE, 2020.
[15] Xiangru Lian, Ce Zhang. Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
[16] Wei Yang Bryan Lim, Zehui Xiong, Chunyan Miao, Dusit Niyato, Qiang Yang. Cyril Leung, and H Vincent Poor. Hierarchical incentive mechanism design for federated machine learning in mobile networks. IEEE Internet of Things Journal, 7(10):9575-9588 2020.
[17] Jierui Lin, Min Du, and Jian Liu. Free-riders in federated learning: Attacks and defenses. arXiv preprint arXiv: 19w.119011.1260,,, 2019.
[18] Jiaqi Liu, Wei Wang. Deng Li, Shaohua Wan, and Hui Liu. Role of gifts in decision making: An endowment effect incentive mechanism for offloading in the iov. IEEE Internet of Things Journal, 6(4):6933-6951, 2019.
[19] Yuan Liu, Mengmeng Tian, Yuxin Chen, Zehui Xiong, Cyril Leung, and Chunyan Miao. A contract theory based incentive mechanism for federated learning. Federated and Transfer Learning, pages 1 117-137. Springer, 2022.
[20] Jianfeng Lu, Bangqi Pan, Abegaz Mohammed Seid, Bing Li, Gangqiang Hu, and Shaohua Wan. Truthful incentive mechanism design via internalizing externalities and lp relaxation for vertical federated learning. IEEE Transactions on Computational Social Systems, 2022.
[21] Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative fairness in federated learning. Federated Learning: Privacy and Incentive, pages 189-204, 2020.
[22] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coamuuicaation-effcccen learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[23] Hamid Mozaffari, Sunav Choudhary, and Amir Houmansadr. Fake or compromised? making sense of malicious clients in federated learning. arXiv preprint wxXiv:2403.06319 2024.
[24] Aniket Murhekar, Zhuowen Yuan, Bhaskar Ray Chaudhury, Bo Li, and Ruta Mchta. Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maximization. Advances in Neural Information Processing Systems, 36, 2024.
[25] Virat Shejwalkar and Amir Houmansadr. Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning. In NDSS, 2021.
[26] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Col- laborative machine learning with incentive-awarc model rewards. In International conference on machine learning, pages 8927-8936. PMLR, 2020.
[27] Jinhyun So, Başak Güler, and A Salman Avestimehr:
Byzintine-resillent secure federated learning. IEEE Journal on Selected Areas in Communications, 39(7):2168-218) 2020.
[28] David Solans, Battista Biggio, and Carlos Castillo. Poisoning attacks on algorithmic fairness. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pages 162-177. Springer, 2020.
[29] Gan Sun, Yang Cong, Jiahua Dong, Qiang Wang, Lingjuan Lyu, and Ji Liu. Data poisoning attacks on federated machine learning. IEEE Internet of Things Journal, 1(13):1 2021.
[30] Nguyen H Tran, Wei Bao, Albert Zomaya, Minh NH Nguyen, and Choong Seon Hong. Fed- erated learning over wireless networks: Optimization model design and analysis. In IEEE INFOCOM 2019-IEEE conference on computer communications, pages 1387-1395. IEEE, 2019.
12

---

[31] Philipp Tschandl, Cliff Rosendahl, and Harald Kittler. The ham of multi-souree dermatoscopic images of common pigmented skin lesions. Scientific data, 5(1):
hammm0000 10000 dataset, large collection
1 1-9, 2018.
[32] Xuezhen Tu, Kun Zhu, Nguyen Cong Luong, Dusit Niyato, Yang Zhang, and Juan Li. Incentive mechanisms for federated learning: From economic and game theoretic perspective. IEEE transactions cognitive communications and networking. 8(3):1566-1533) 1593, 2022.
[33] Xiumin Wang, Wayes Tushar, Chau Yuen, and Xinglin Zhang. Promoting users' participation in mobile crowdsoureing: A distributed truthful incentive mechanism (dtim) approach. IEEE Transactions Vehicular Technology, 69(5):5500-5582 2020.
[34] Chenrui Wu, Yifei Zhu, Rongyu Zhang, Yun Chen, Fangxin Wang, and Shuguang Cui. Fedab: Truthful federated learning with auction-based combinatorial multi-armed bandit. IEEE Internet of Things Journal, 2023.
[35] Jia Xu, Jinxin Xiang, and Dejun Yang. Incentive mechanisms for time window dependent tasks in mobile crowdsensing, IEEE Transactions Wireless Communications, 14(11):6353-634, 2015.
[36] Xinyi Xu and Lingjuan Lyu. A reputation mechanism is all you need: Collaborative fairness and adversarial robustness in federated learning. arXiv preprint arXiv:2011 1. 10464, 2020.
[37] Yuancheng Xu, Jiarui Yao, Manli Shu, Yanchao Sun, Zichu Wu, Ning Yu, Tom Goldstein, and Furong Huang. Shadowcast: Stealthy data poisoning attacks against vision-language models. arXiv preprint arXiv:2402.06659, 2024.
[38] Yufeng Zhan, Yuanqing Xia, and Jinhui Zhang. Incentive mechanism in platform-centre mobile crowdsensing: A one-to-many bargaining approach. Computer Networks, 132:40-52, 2018 8.
[39] Yufeng Zhan, Peng Li, Zhihao Qu, Deze Zeng, and Song Guo. A learning-based incentive mechanism for federated learning. IEEE Internet of Things Journal, 7(7):6360-6368, 2020.
[40] Yufeng Zhan, Peng Li, Song Guo, and Zhihao Qu. Incentive mechanism design for federated learning: Challenges and opportunities. IEEE network, 35(4):310-3) 2021.
[41] Yufeng Zhan, Jie Zhang, Zicong Hong, Leijie Wu, Peng Li, and Song Guo. A survey of incentive mechanism design for federated learning, IEEE Transactions on Emerging Topics in Computing, 1035):00351104 2021.
[42] Honggang Zhang. Benyuan Liu, Hengky Susanto, Guoliang Xue, and Tong Sun. Incentive mechanism for proximity- -haei mobile crowd service systems. In IEFE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, pages 1-9. IEEE, 2016.
[43] Ruiting Zhou, Jinlong Pang, Zhibo Wang, John CS Lui, and Zongpeng Li. A truthful procure- ment auction for incentivizing heterogencous clients in federated learning. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages I83-193, IEEE, 2021.
13

---

Appendix
A Additional Related Works
While small, the research area of incentives and mechanism design in FL is growing. There are few surveys [32, 40, 41] which overview FL mechanisms, current research directions & challenges, and future opportunities. We hone in on a few of these research directions. namely agent contribution and truthful FL mechanisms, as well as fairness and agent selection mechanisms. Due to space constraints, we continue our related works (Section 2) here below.
Distributed Learning Mechanisms for Agent Contribution (Continued). Within Zhan et al. [38], an iterative Nash bargaining solution is proposed where mobile devices bargain with server over the amount of data to contribute and the payments it should receive. The server dynamically alters the payment price to adjust its gap between desired supply of data and the given demand. Liu et al. [18] designs reverse-auction approach, with subsidized or "endowment" compensation, that incentivizes non-participating vehicles to reduce roadside server congestion by offloading its data. Both of these works deal with data exchange and do not consider the FL setting, where models are collaboratively trained together. Furthermore, it is not guaranteed in either that agents and the server will both always achieve higher payoff for participating than not (in Liu et al. [18] the server attains smaller payoff by participating).
Truthful Distributed Learning Mechanisms (Continued). Xu al. [35] deals with agents submitted untruthful bids to a server, specifically where an agent can lie about sensing time windows and costs. The proposed mechanism leverages in bid price. Time-window truthfulness is ensured via trusted time stamping. Similarly, the remaining crowdsensing works leverage auctions to ensure agent bid truthfulness. Zhang et al. [42] introduces double auction mechanism, MobiAuc, for proximity- based mobile crowdsensing. MobiAuc addresses issues of dynamic mobility patterns (device matching) while maintaining agent truthfulness surrounding their bid (e.g., service valuation or arrival time). In Wang et al. [33], a distributed truthful mechanism proposed, where agents send bids for their services (usually data) buyers. Gao et al. [9] designs reverse auction mechanism that ensures vehicles report their true costs when crowdsensed. The works above do not consider the FL setting, where models are trained through the help of many agents. Thus, these works do not solve the free-rider dilemma, which only exists in FL settings. Furthermore, our mechanism able to ensure agent truthfulness without the use of an auction.
Serrey-Clarke-rrone
auction, thereby ensuring truthfulness
Fairness FL Mechanisms. Recent work within FL has focused agent faimness [1, 21, 24]. These works seek to fairly allocate model performance to agents depending upon how much they contribute during federated training. Lyu et al. [21] computes a "reputation" metric for cach agent (measures the amount of agent contribution). A better reputation leads to improved model performance. Both Blum et al. [1] and Murhekar et al. [24] seek to find agent contribution equilibria that improve the welfare of all agents. Within [1], the existence and stability of equilibria which avoid free riding and agent envy. In [24), mechanism is proposed to alter agent strategies in order to maximize the net utility of all participating agents. Unlike the works above, FACT is a truthful mechanism.
Mechanisms for FI. Agent Selection. There exists recent literature which aims to incentivize high-quality agents to participate in federated training [11, 19, 43]. Agents can be deemed as high quality if, for example, they have valuable data or are very willing to participate in training. In Liu al. [19], a two-dimensionall contract model is created to consider agent willingness and data quality when designing contract fees. Kang et al. [11] introduces a scheme where agent reputations are calculated (from previous interactions or other server interactions) and leveraged to select reliable agents for federated training. Zhou et al. [43] designs an auction method that incentivizes a diverse set of agents to participate in training. Truthfulness and individual rationality are ensured by properties of the auction that is constructed. FACT does not select agents based on a given quality or willingness criteria. All agents are able to participate if they choose. Instead, FACT solves agent free riding when agents are truthful as well as untruthful.
14

---

Algorithm 3 AgentUpdate
1: Input: model parameters w, agent index i, data used for training mi loss f, h local steps.
2: Oufput: updated model parameters w.
3: B + batch m, data points
4: for each epoch
1...., E do
5: for batch E B do
6: u f- - 7 ((w;b))
7: every h batches pause training and return w (resume at next call)
8: end for
9:
end for
B Additional Experimental Results
Experimental Setup. We use 16 agents to train a ResNet18 and small convolutional neural network (for CIFAR-I0 and MNIST respectively). The optimizer we use Stochastic Gradient Descent for CIFAR-10 and Adam for MNIST. We the standard FedAvg algorithm to perform federated training. We ran all experiments on a cluster of 2-4 GPUs, with the 16 CPUs (agents) pinned to a GPU. We use GeForce GTX 1080 Ti GPUs (1 1GB of memory) and the CPUs used are Xeon 4216. We provide table of the hyperparameters not listed in Section 6 below.
Table 1: Hyper-parameters for CIFAR-10 Experiments.
Model
Batch Size
Learning Rate Training Cost
Epochs
Local FedAvg Steps h
ResNet18
128
0.05
1.024e-07
100
6
Table Hlpee-parameters for MNIST Experiments.
Model
Batch Size
Learning Rate Training Cost
Epochs
Local FedAvg Steps h
CNN
128
le-3
7.11le-08
100
6
Test Loss and Accuracy Plots. We include the test loss and accuracy plots, including error bars, below for federated and local training for CIFAR-10, MNIST, and HAM10000. We run each experiment three times. As expected, FL outperforms local training in the iid (left), mild non-iid (middle) and strong non-iid (right) settings. Federated training, via FedAvg, is more robust to non-iid distributions than local training. As detailed Section 6, our non-iid distributions are Dirichlet with 0.3, 0.6.
10a
10.
107
Pederated
Pockrated Thakirg
Test Loos
4p2
Test Love
10a
0
20
300
100
107
10'
Teat Lous
Test Lous
locil tokring
20
2014
20
30
10-
150
Epochs
Figure 5: Test Loss for CIFAR10 (top) and MNIST (bottom) in Heterogeneous Settings. FL outperforms local training on iid (left) and mild (middle) & strong (right) non-iid Dirichlet settings.
15

---

lcael kuan
0.7
0.7
Test Recuraly 1iccuraa
Test Loss
0.4
0.4
0.2
Jnd TilVigg
0.7
20
0.1
80
100
Epochs
Epochs
Epochs
0.93
0.95
Teke: Accuracy
6.00
0.00
0.50
Locdl Thiniing
2nd Teaning
Local Thiriigg
80
0.75
40
100
0.79
20
Epochs
Epochs
Epocha
Figure 6: Test Accuracy for CIFARIO (top) and MNIST (hottom) in Heterogeneous Settings. FL
outperforms local training on iid (left) and mild (middle) & strong (right) non-iid Dirichlet settings.
Training
0.90
Federated Traiiin
0.85
5
Test Accuracy
Test Loss
0.80
0.75
2
0.70
Training
0.65
Rederated training
30
40
Epachs
Epochs
Figure 7: HAM10000 Test Loss (Left) and Accuracy (Right) for Federated and Local Training.
C Proofs
Theorem (Optimal Local Data Usage). For an agent i with marginal cost c, the optimal amount of data m used for local training is m.. =
1.21.
2c,
Proof. Each agent has local loss function as shown in Equation (2). Taking the derivative l (m) with respect to the data contribution amount yields,
dea;
- 2m²
702L
+ c; =
m == = 2c
(12)
dm
Theorem 2 (Free-Riding: Optimal Federated Data Usage). For an agent with marginal cost e₁ the optimal amount of data m used for federated training is m
Σ m_i.
Proof. Each agent a federated loss function as shown in Equation (3). Taking the derivative of (i.((m) with respect to the data contribution amount yields,
16

---

dla
70²
c =0
(13)
dm
2(m + 3 Em_;)²
Σ m=-)²== 70²1 I
10221.
(m +
m =V 2c,
Σ m-i
(14)
2c;
Theorem 3 (PFL Eliminates Free Riding). For an agent i with marginal cost Cj the optimal amount of data m pFr. used for federated training under Equation (4) is m. IFF. =
2c,
Proof. Each agent has a penalized federated loss function as shown in Equation (5). Taking the derivative of (m) with respect to the data contribution amount yields,
dei,PFL. dm
7
+ +
-
2201
+ 2A = 0,
2(m + Σ m=
2(
702L
+
+Em_.)
2c
2ca
702L
70²L
70² L
= 222;
0.
(15)
2c;
2(m + Σ m-
2(
T00L
+
m
2c;
Due to the convexity of Equation (5), as each piece of the utility function is convex, there single minimum which carefully constructed be at m
102T. 20,
dl,, (FL.)))(m") 20c(1
202L
2
70²L L
7 2 L
dm
20;
V
203
2(
L
+
Em
2(v
2 2e,
m_
T02T.
mpPPL
(16)
20
Lemma 1 (Assurance of IR at Optimum). Let G₁ be the marginal cost for agent m" Visit m mi.PFL be the agent's locally optimal data usage, and E [0, 2) be a server- specified soper-parameter In order to ensure that the optimal penalized federated loss is at least lower than the optimal local loss, (,.FL((m)) S (,,(m))) ), one must select Xr such that,
2 a Σ m_i (
m (
702T,
A
(17)
2 m_ + m²)²
Selection of such X results in a loss gap between (...L((m) and ((,(mm) of.
a 702 Lo2L_m m_i A4, = (a,(m") - (..FFL(m") 4 m m m_
(18)
mm + m²)
Proof. We can determine the range of X; values which ensure IR by plugging in m = m m., = m" into Equations (2) and (5) and finding the difference,
(m,(m") - (m.PPL(m)) = I
Ael Gi
I
}2.
2 m m Σ m_
2):
4di(
L0 2cr
+ -m
702L
Σ Em_
1
702L
(19)
2 m" (m" Σ m_))
41
2(m" + m m,
17

---

To ensure the Equation (19) is greater than or equal to O, we must select X as the following,
7021,
Σ m
7021
S 0,
m" (m* + Σ m.
41; 2(m* + Σ Em_))²
A m" (m' + +Σ m-i)
70²
C4 2(m* + + m_
(20)
2y0 L Σ m_i
Equation (20) shows that X must be non-negative (all values are positive and the squared term can be zero at minimum). One can think of A as the parameter controlling the benefit received by an agent i. A larger value of A; will result in a larger gap between (m,) and fi,rr (m") (Equation (19)). Inversely, a smaller value of X will result in a smaller gap between local and federated training utility. Therefore, we fully define A; with a user or server specified hyperparameter a E (0,
m m)
70²
A
(21)
1. m
2(Σ m)
Plugging this term into Equation (19) yields the following utility gap between la((m)) and (.pFI((m).
-., = a L m_
AC. = (,,FFr(m")
(22)
4 m E m m²)
Theorem 4 (Elimination of Federated Free-Riding With Truthful Agents). PFL (Algorithm using Xs from Lemma 1 is IR and eliminates the free-rider dilemma when agents are Iruthful.
Proof Reproduced from Section 4. The result of Theorem 3 is that each agent i's optimal strategy within the penalized federated scheme is to use their locally optimal amount of data m. Furthermore, Lemma states that using m, within the penalized federated scheme results in a reward, or improvement over local training, of A4; = m² 3 and Lemma 1, truthful agents which choose to participate in PFL attain reshaped and lower loss the same optimum. Individually rational agents would therefore prefer to participate in PFL (Algorithm 1) over local training due to the reshaped optimum's 's lower loss. This optimum achieves the same data usage as local training, thereby eliminating the free-rider dilemma.
/g021.
2cg
v0 [m m m. :)) Thus, by combining Theorem
Lemma 2.
The probability of an agent "winning" in the truthfulness mechanism in Equation (10), given a reported cost is vlc) (c) -F((c), where Fc is the CDF of fc.
Proof. The probability that an agent's cost c sandwiched in between two other randomly sampled agents' costs Cu. Cu is equal to,
P(sandwiched c) v(c) P(c, S S c.) ) P(c. ses G.).
(23)
Let Fc be the cumulative distribution function (CDF) of the agent cost distribution fc. The probability that random cost, let's say Cu, is smaller than is equal to Fc(c). The probability that random cost, let's ss say Gu, is larger than e is 1 - Fc(c). Since the costs are random, and the above situation could be flipped (i.e., Go is smaller than with probability Fo(c) and Ca is larger than with probability Fe(c)), the two probabilities in Equation (23) are equivalent. Thus, due to symmetry, P(c, < c c.) P(c, c ca). Therefore, we can rewrite the equation above as,
((c) = (1c(c) (F((c)))
(24)
Theorem 5 (Main Theorem). Each agent i's best strategy, when participating in FACT (Equation (1), is to report its true cost and use its locally optimal amount of data (m;, c)] = (V 2022
..).
2e;
18

---

Proof. Agents participating in FACT follow the loss function shown in Equation (11),
7o
Fact c) =
2(m; + Σ m-)) + 4,m, + (yr(ms; c) + Par(c).
(25)
Taking the expectation of the equation above over the distribution of agent costs fc, and using the results of Lemma 2, yields,
70²L
Efe la, (m4
(m;, c)]
2(m; + Σ mm + c.m4 + Pfr(m;, c) + (escPPt()))
2(m + mm_i) + c: + (fr(m; c) + Ad; 30(() Σ
Alj
(26)
jFiE(n)
Taking the partial derivative with respect to m, and setting equal to zero results in,
①
70²L
So Fact (m,, c)] 3m; 2(m + + m-
+ c,m, + Ppr(ms, c) =
(27)
3m,
From Theorem 3, we know that this results in m = V -2- Now, when taking the partial derivative with respect to can plug in m. (to ensure the critical point is evaluated as zero),
107L 2c
30(c)
dc 2(m mm_)) cam, + Psr(m, + Al,
Σ
Dej 0.
(28)
(,,((m))
By Lemma and specifically Equation (7), we find that the first four terms above are equivalent to the local agent loss at local optimum. Therefore, we can rewrite the equation above as,
0
10
L
c.m
3v(c)
Σ
DC,
Aly
i
v(c) 0,
ac
2m
n
T2
Dc
jttE(n)
jtie(n)
(m((mf)
A 2Fc(c)(1 Po(c)) =
(29)
de
The final line follows from Lemma Since Fe(c) is CDF, its range 10, 1]. The function
v(c) = (1 Fe(e)) achieves is global maximum when Fo(c) 1/2 (its critical point). Therefore, the value of which satisfies Equation (29) one such that Fe(e) = 1/2. By Assumption 1, we know that the median value is assumed by each agent as c, since each agent believes its cost is equally likely to be larger or smaller than any other agent's s cost. Thus, Fc = 1/2 and c* c₁. Plugging this optimal value of e back into the optimal value for m, leads to the following optimum:
(m,,c)* = (v L
..).
2c
D Impact Statement & Limitations
Current federated systems are inhibited by agent free riding. The result an unfair system. Some agents perform the bulk of training. while others sit idle. In the end, all the agents receive the same model performance. While there are current methods which eliminate agent free riding, they do not take into account agent truthfulness. Many agents can still provide false information the server in order to free ride. The impact of FACT is that it provides an easily implementable mechanism which can make federated training more robust free riding. Using FACT, agents are incentivized to no longer free ride even if they can lie about their training costs.
Our work faces limitations when agents and the central server act maliciously. On the agent side, we assume that agents are rational and do not collude with one another. Our future research direction is to prove that equilibria for FACT exist when agents are boundedly rational or colluding, On the server side, we assume that the central server acts honestly. In settings where the server cannot be trusted, new incentives or avenues must be built in order to ensure server honesty.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Theory is provided in Section 5 and experimental results are provided in Section 6 to back up the claims in the introduction and abstract.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We address our work's limitations in Appendix Furthermore, we provide the assumptions used for our work, as well as explain them, in Sections and 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are provided within the main body and all proofs found in Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
20

---

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

---

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

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
This is found in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: https://neurs /ttp::///eeup.p.eeeeee httppp..cpppuuueee sc/ppblic/Ethie Btw.hhhiiiiieeeeeeee
Question:
Answer: [Yes]
Justification: Paper conforms to Code of Ethics. No participants were used, and data is open-source and commonly used in the community. No risks arise from the results of paper. On the contrary, we seek to mitigate current risks distributed learning.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This can be found in Appendix D.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
23

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Paper poses no such risks (no generative models used).
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Paper does not use existing assets
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code provided is documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No study participants were used.
24


Reviews:
[{"review_id": "eUdE3GINhj", "reviewer": "Reviewer_dpi3", "summary": "The paper \"FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding?\" proposes a mechanism called FACT (Federated Agent Cost Truthfulness) to address the issue of free-riding in Federated Learning (FL). The key contributions include introducing a penalization scheme that incentivizes agents to provide truthful information, thereby eliminating free-riding and improving the performance of federated training. The proposed mechanism ensures that agents contribute as much data as they would in local training, thus aligning individual incentives with collective goals.", "questions": "Can you explicitly define the type of game and solution concept used in the proposed mechanism? How does it compare with alternative abstractions in the literature?\n\nHow do you address recent critiques on the practicality of truthful mechanisms, that is abundant literature havs found that agents are not telling the true in truthful mechanisms, not even in the one with the strongest solution concept dominant strategies, especially in complex and distributed environments like federated learning?\n\nWhat are the incentives for the server to implement the sandwich mechanism, given the potential increase in implementation costs? How do you ensure clients trust the server to follow through with the mechanism?\n\nCan you provide more extensive experimental validation, possibly with different datasets and practical scenarios, to demonstrate the robustness and applicability of the proposed mechanism?", "limitations": "The paper acknowledges some limitations but does not sufficiently address the practical challenges and potential negative impacts of the proposed mechanism. Specifically:\n\nServer-Side Incentives: The cost and incentive structure for the server to implement the mechanism is not thoroughly explored. This is crucial for practical adoption.\n\nBroader Applicability: The experiments are limited in scope, and further validation with diverse datasets and scenarios is needed.\n\nTrust and Adoption: The paper does not discuss how to build trust among clients that the server will implement the mechanism fairly, which is essential for the success of the proposed approach.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "Originality: The paper introduces a novel combination of penalization and competition mechanisms to address free-riding and truthfulness in federated learning.\n\nQuality: The empirical results demonstrate the effectiveness of the proposed mechanism in reducing agent loss and enforcing truthful behavior.\n\nSignificance: The problem of free-riding in federated learning is significant, and a robust solution would have considerable impact on the field.\n\nClarity: The explanation of the proposed mechanism is clear and detailed, making it easy to understand the core ideas.", "weaknesses": "Theoretical Reasoning: The paper does not explicitly define the game type and solution concept used, and lacks comparison with alternative abstractions. Recent critiques on the practicality of truthful mechanisms in complex environments are not addressed.\n\nPractical Application: The focus on client-side truthfulness overlooks server-side challenges. Implementing the sandwich mechanism on the server side could increase costs and disincentivize its adoption. Clients might not trust the server to implement the mechanism, leading to untruthful behavior.\n\nExperimental Validation: The experiments are limited to CIFAR-10 and MNIST datasets, and do not provide a broad validation of the mechanism's applicability and robustness across different scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, Reviewer dpi3, for your insightful review of our paper. Below, we address all the questions you raised.\n\n## Question Responses\n\n---\n\n> **Question 1:** Can you explicitly define the type of game and solution concept used in the proposed mechanism? How does it compare with alternative abstractions in the literature?\n\n**Response to Question 1:**\n\n- The type of game we consider is a One-Shot, Simultaneous Game.\n- The solution concept within FACT is a Pure Nash Equilibrium. \n\nTheorem 5 (Main Theorem) details FACT's Nash Equilibrium. Within the Proof of Theorem 5, we show that the best action for an agent, given the fixed actions of all other agents, is to contribute what is locally optimal and not to lie about its cost. \n- Alternative abstractions in FL Free-Riding mechanism have equivalent game types and solution concepts.\n\nThe closest alternative abstractions within FL Free Riding, Blum et. al. (2021), Kamireddy et. al. (2022), Murhekar et. al. (2023), and Bornstein et. al. (2023), are also Simultaneous Move Games which all find Pure Nash Equilibriums. Therefore, our paper follows closely along with these related works. However, unlike these works, ***we are the first to deal with truthfulness in FL Free Riding***. Within each of the previous works, costs from each agent are publicly known and cannot be untruthful. We take a big step forward within the current literature by proposing the first truthful approach to eliminating FL Free Riding.\n\nWe have added this discussion to our paper.\n\n> **Question 2:** How do you address recent critiques on the practicality of truthful mechanisms...?\n\n**Response to Question 2:**\n\n- The theory underpinning truthful mechanisms, like our own, is rigorous and will hold as long as the underlying assumptions are satisfied. \n\nAgents act untruthfully within provably truthful mechanisms only when the underlying assumptions of the mechanism are violated. Within FACT, we minimize the number of assumptions compared to related works and stick to only three assumptions standard within literature: agents (i) are rational and (ii) cannot collude with one another, and (iii) the server is honest in its mechanism implementation.\n- Theory provides important insight into the current limitations of truthfulness within the field and provides avenues for future progress into eliminating such limitations.\n- We are the first in the field to prove that a mechanism exists to eliminate FL free riding even when agents can be untruthful with the server. \n\nAlthough agents may act irrationally or collude in real-world scenarios, the insights that our theory provides is invaluable. Our theory allows researchers to better understand the nature of truthfulness within FL systems. Up until our work, it was an open question whether a mechanism can provably guarantee agent truthfulness when querying their participation workload. We hope to drive further progress that can address the new open questions that our work spurred: Can we find a solution when agents are boundedly rational or colluding? Can solutions be found when the server is dishonest?\n\n> **Question 3:** What are the incentives for the server to implement the sandwich mechanism...? How do you ensure clients trust the server...?\n\n**Response to Question 3:**\n\n- Eliminating free riding allows the central server to train higher-performing models. \n\nWithout implementing the sandwich mechanism, devices will be untruthful and not use as much data during training (free-ride). Thus, the server is incentivized to implement the sandwich mechanism in order to eliminate the free-rider dilemma, increase the total amount of data used during training, and subsequently train a higher-performing model (as more data is used for training).\n\n- The server receives leftover agent contract fees. \n\nWhile the bulk of agent contract fees are returned to the winning agents after the sandwich mechanism, there are leftover fees that the server pockets. This is shown in Equation (10), where winning devices receive $\\frac{3}{n}\\sum_{j \\neq i \\in [n]} \\Delta \\ell_j$. The summation term is over just $n-1$ agents, while the outside factor divides by $n$. Thus, the server pockets the remaining winner contract fees (since no winning agent wins back its own fee) $\\frac{3}{n}\\sum_{k \\in winners}\\Delta \\ell_k$.\n\n- Implementation costs in FACT are much smaller than related mechanisms. \n\nIn the most comparable FL free-riding literature, Kamireddy and Bornstein, the server is required to send each agent a custom model with a prescribed accuracy. This means that the server has to perform additional training at the end of the normal FL training process. In FACT, the server only needs to match agents together, determine the mechanism winners, and disperse rewards to those winners.\n\nWe have added this discussion to our paper.\n\n> **Question 4:** Can you provide more extensive experimental validation... to demonstrate the robustness and applicability of the proposed mechanism?\n\n**Response to Question 4:**\n\n- Our validation showcases that FACT performs well within multiple practical scenarios. \n\nWithin our work we test the performance of FACT on two standard datasets, MNIST and CIFAR-10. We perform testing within IID and non-IID scenarios, both practical scenarios. In each of our experiments we find that an agent's best strategy is be truthful (Figure 1) and that agents indeed receive greater benefit by participating in FACT than by not participating (Figure 2). \n- Our validation is more extensive than those in related FL mechanism works. \n\nComparable FL mechanism works either lack any validation on datasets (Kamireddy) or are limited to MNIST or EMNIST (Murhekar and Blum). We test on both MNIST and the larger and more difficult CIFAR-10 dataset.\n- **We have added additional validation in practical scenarios [within our global rebuttal](https://openreview.net/forum?id=JiRGxrqHh0&noteId=w65DtMxzEP) that demonstrate the effectiveness and robustness of FACT.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5tJTGuPnNn", "reviewer": "Reviewer_hdyq", "summary": "This paper introduces Federated Agent Cost Truthfulness (FACT) to tackle the issues of free riding and dishonesty in federated learning.  A penalty system is proposed to eliminate federated free riding. Meanwhile, a competitive environment is proposed to incentive agents provide truthful information.", "questions": "What if the individuals are boundedly rational?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.\tFACT addresses both the free riding and dishonesty issues in federated learning, making a highly significant contribution to the field.\n2.\tSufficient theoretical evidence has been provided to demonstrate the effectiveness of FACT.\n3.\tThis paper is well organized, ensuring it is easy to follow and offering a smooth reading experience.", "weaknesses": "1.\tAre there any real-world examples that illustrate the necessity of addressing free-riding and dishonesty issues in federated learning?\n2.\tThe paper states that \"All rational agents seek to minimize their loss,\" but a more intuitive understanding is that rational agents seek to maximize their gains. There is a slight discrepancy between these two statements. How can this discrepancy be understood?\n3.\tGenerally speaking, the payoff of a game is determined by the actions of all participants. Why, in Equation 2, can the payoff of agent i be calculated based solely on its own action mi ?\n4.\tPlease elaborate more clearly on the logical relationship between Equation 2 and Equation 3.\n5.\tIt would be better if the intuitive principles behind the formula design could be provided, such as for Equation 4.\n6.\tIn Assumption 1, the assumption of \"No Collusion\" is made. Is this a simplified assumption, or is it also quite consistent with real-world federated learning scenarios?\n7.\tWhat are the limitations of the mechanism proposed in this paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, Reviewer hdyq, for your insightful review of our paper. Below, we address all questions you raised.\n\n## Addressing Weaknesses\n\n---\n\n> **Weakness 1:** Are there any real-world examples that illustrate the necessity of addressing free-riding and dishonesty issues in federated learning?\n\n**Response to Weakness 1:** This is a good point. There are indeed lots of real world examples which illustrate the need of addressing free riding. We take this opportunity to expand upon this discussion as follows.\n\n- As detailed in [R1], free-riding has already been extensively studied and found in many peer-to-peer systems ([R2, R3]), such as BitTorrent ([R4]).\n- Realistic examples of FL free riding include training models for healthcare applications, [an example we provide additional experiments for in our global rebuttal](https://openreview.net/forum?id=JiRGxrqHh0&noteId=w65DtMxzEP).\n\n> **Weakness 2:** The paper states that \"All rational agents seek to minimize their loss,\" but a more intuitive understanding is that rational agents seek to maximize their gains. There is a slight discrepancy between these two statements. How can this discrepancy be understood?\n\n**Response to Weakness 2:** Within literature, equilibriums can be found when either maximizing concave functions (gain) or minimizing convex functions (loss); there is an equivalence as they are the negative of one another.\n\n> **Weakness 3**: Generally speaking, the payoff of a game is determined by the actions of all participants. Why, in Equation 2, can the payoff of agent i be calculated based solely on its own action mi?\n\n**Response to Weakness 3:**\n\n- Equation (2) defines the *local* agent loss. \n\nThe local agent loss describes the relationship between data quantity and loss for an agent training locally (by itself). Thus, other agent actions will not affect the agent's local loss.\n\n> **Weakness 4:** Please elaborate more clearly on the logical relationship between Equation 2 and Equation 3.\n\n**Response to Weakness 4:** \n\n- Equation (2) defines the local agent loss (training alone), while Equation (3) defines an agent's loss when it participates in distributed training.\n\n>  **Weakness 5:** It would be better if the intuitive principles behind the formula design could be provided, such as for Equation 4.\n\n**Response to Weakness 5:** \n\n- Equation (4) is designed such that first-order optimality conditions (zero gradient) of Equation (5) exists when an agent contributes its locally optimal amount data amount ($m_i^* = \\frac{\\gamma\\sigma^2L}{2c_i}$).\n\nWe thank the reviewer for this comment and agree that this should be provided within the paper. We have added this explanation within the paper.\n\n>  **Weakness 6:** In Assumption 1, the assumption of \"No Collusion\" is made. Is this a simplified assumption, or is it also quite consistent with real-world federated learning scenarios?\n\n**Response to Weakness 5:** Yes, the \"No Collusion\" assumption is standard within truthful mechanism theory (for example Vickrey auctions). \n \n- To the best of our knowledge, there hasn't been extensive evidence of collusion in FL. However, collusion is possible and this is a limitation of our work.\n - Up until our work, it was an open question within FL whether a mechanism can provably guarantee agent truthfulness when querying their participation workload. \n - We hope that our results drive further progress that can address new open questions that our work spurred such as: Can we find a solution when agents are boundedly rational or colluding?\n\n[R1] Lin, Jierui, et al. \"Free-riders in federated learning: Attacks and defenses.\" arXiv preprint arXiv:1911.12560 (2019).\n\n[R2]  M. Feldman and J. Chuang, “Overcoming free-riding behavior in peer-to-peer systems,” SIGecom Exch., vol. 5, no. 4, pp. 41–50, Jul. 2005.\n\n[R3] M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica, “Free-riding and whitewashing in peer-to-peer systems,” IEEE Journal on Selected Areas in Communications, 2006.\n\n[R4] T. Locher, P. Moore, S. Schmid, and R. Wattenhofer, “Free riding in bittorrent is cheap,” in 5th Workshop on Hot Topics in Networks (HotNets), 2006.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kRo0uT4mS3", "reviewer": "Reviewer_k1Mz", "summary": "This paper introduces Federated Agent Cost Truthfulness (FACT), a novel mechanism that addresses the free-rider dilemma in federated learning. FACT ensures truthful reporting by agents and eliminates free-riding through a penalty system, competitive environment, and by encouraging agent participation with better performance than training alone. Empirically, FACT effectively avoids free-riding even when agents are untruthful and significantly reduces agent loss.", "questions": "1. The core contribution of the paper is to prevent free-rider attacks by participants in federated learning when they are able to cheat. And the author claimed FACT is the first truthful Horizontal FL method that eliminates free riding while simultaneously enforcing truthfulness. However, other federated learning algorithms also can prevent free-rider attacks, even though the authors claim that they cannot prevent participants from actively cheating. Wouldn't it be helpful to prove the effectiveness of the FACT if the paper add comparative experimental results of several related algorithms? \n\n2. Is it a limitation that the parties cannot collude? If the parties collude, can FACT also effectively protect FL?\n\n3. What is the additional computational overhead of FACT compared to traditional FL and local training?\n\n4. According to Figure 2, why does using FACT to protect the FL process cause performance degradation? I noticed that the loss of FACT is higher than the loss of traditional FL.\n\n5. I think the loss is not enough to reflect the performance of the model. When the model is overfitted, the loss increases but the accuracy still decreases. At the very least, the paper should show the accuracy of the final prediction effect (necessary) and add some ablation and hyperparameter experiments (after accept). I suggest you refer to these papers to show your experimental results if you still have the intermediate records of the experimental results.\n\n[1] Fraboni, Yann, et al. Free-rider attacks on model aggregation in federated learning. International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[2] Lin, Jierui, et al. \"Free-riders in federated learning: Attacks and defenses.\" arXiv preprint arXiv:1911.12560 (2019).", "limitations": "Based on the checklist, the author said \"We provide the assumptions used for our work, as well as explain them, in Sections 3 and 5.\" However, I find it difficult to understand what the author wants to express in terms of specific limitations. I suggest writing it clearly at the end of the paper or in a separate section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The method part of the paper has clear logic, and the contract theory is used to effectively prevent free-rider attacks in federated learning.\n2. Almost all the proposed theories or definitions have been proven\n3. The problem solved is very critical, and it is the first study of free-rider attacks in federated learning under active deception conditions (according to the author)", "weaknesses": "1. Eq 10, 26, and 27 lack punctuation.\n\n2. Line 447, 452, 459, 475, 485, 496, and 514 are extra blank lines.\n\n3. It may be better to add one figure in the Introduction to show the proposed issues.\n\n4. The experimental part is not sufficient to thoroughly prove the effectiveness of the FACT mechanism. For example, it is obvious that the introduction of the FACT mechanism will bring additional communication overhead, but this part is completely missing in the experimental part.\n\n5. The experimental part lacks organization. For example, I think the overall accuracy of the model prediction after using the FACT mechanism should be shown first, and then the various parts of FACT should be ablated, such as removing the Sandwich module, Penalized module, etc. Finally, some hyperparameters or other visualization experiments should be shown. At present, I am very confused about the results of the experimental part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, Reviewer k1Mz, for your insightful review of our paper. Below, we address all questions you raised.\n\n## Addressing Weaknesses\n\n---\n\n> **Weakness 1:** Eq 10, 26, and 27 lack punctuation.\n\n**Response to Weakness 1:** We begin by thanking you for catching the punctuation issues, and have fixed them within our paper.\n\n> **Weakness 2:** Line 447, 452, 459, 475, 485, 496, and 514 are extra blank lines.\n\n**Response to Weakness 2:** Each of these lines include an \"end of proof\" symbol on the far right of the line.\n\n> **Weakness 3:** It may be better to add one figure in the Introduction to show the proposed issues.\n\n**Response to Weakness 3:** We have added such a schematic into the Introduction of our paper.\n\n> **Weakness 4:** The experimental part is not sufficient to thoroughly prove the effectiveness of the FACT mechanism. For example, it is obvious that the introduction of the FACT mechanism will bring additional communication overhead, but this part is completely missing in the experimental part.\n\n**Response to Weakness 4:** \n- FACT does not incur extra communication costs during FL training.\n- FACT simply details a mechanism to distribute agent rewards after FL training is complete.\n\nFACT can be added to the end of any existing FL training method. The mechanism does not begin until after training finishes. As such, there is no added communication overhead during training.\n\n> **Weakness 5:** The experimental part lacks organization. For example, I think the overall accuracy of the model prediction after using the FACT mechanism should be shown first, and then the various parts of FACT should be ablated, such as removing the Sandwich module, Penalized module, etc. Finally, some hyperparameters or other visualization experiments should be shown. At present, I am very confused about the results of the experimental part.\n\n**Response to Weakness 5:** We thank the reviewer for their suggestions, and have included accuracy plots within our paper and will include ablations over our mechanism modules (Sandwich & Penalized) in our final version.\n\n- We have included the accuracy plots within our PDF rebuttal for the reviewer to view.\n\n## Question Responses\n\n---\n\n> **Question 1:** Wouldn't it be helpful to prove the effectiveness of the FACT if the paper add comparative experimental results of several related algorithms?\n\n**Response to Question 1:** \n\n- All related mechanisms would break down and allow free riding if agents could report untrue and inflated costs (detailed at the end of Section 4). \n\nWe agree with the reviewer that in general, it would strengthen the work, but true to best of our knowledge ***our work is the first in the field*** to prove that a mechanism exists to eliminate FL free riding even when agents can be untruthful with the server.\n\nIn summary, since we develop the first mechanism to eliminate free riding when agents can be untruthful, there are no comparable mechanisms to test against.\n\n> **Question 2:** Is it a limitation that the parties cannot collude? If the parties collude, can FACT also effectively protect FL?\n\n**Response to Question 2:** Collusion is indeed a limitation, one that is common to many truthful mechanisms (such as Vickrey auctions). We address our effort to more clearly detail and discuss our limitations [within our global rebuttal](https://openreview.net/forum?id=JiRGxrqHh0&noteId=w65DtMxzEP).\n\n> **Question 3:** What is the additional computational overhead of FACT compared to traditional FL and local training?\n\n**Response to Question 3:**  As detailed within our response above, FACT does not incur any additional computational overhead compared to traditional FL and local training during the actual training process.\n\n> **Question 4:** According to Figure 2, why does using FACT to protect the FL process cause performance degradation? I noticed that the loss of FACT is higher than the loss of traditional FL.\n\n**Response to Question 4:** \n\n- The loss of traditional FL is an upper bound: it's the loss that would occur if all agents did not free ride. Unfortunately, in practice, agents free ride and this loss will not be attained.\n- The degradation is a result of the penalties that are incurred in order to ensure agent truthfulness.\n- Even though FACT does not reach the upper bound, it is individually rational as it provides improved benefit to agents that choose to participate versus not.\n\n> **Question 5:** I suggest you refer to these papers to show your experimental results if you still have the intermediate records of the experimental results.\n\n**Response to Question 5:** As mentioned above, no comparable mechanism exists which can deal with agent untruthfulness. \n\n- Neither provided paper proposes a mechanism to defend against FL free riding through incentives, and neither deal with agent untruthfulness.\n\nThe first paper deals with free-rider attacks (our paper is a defense) and the second focuses on defenses that utilize anomaly detection (we have cited both already within our paper). \n\n> **Question 6:** I think the loss is not enough to reflect the performance of the model. When the model is overfitted, the loss increases but the accuracy still decreases. At the very least, the paper should show the accuracy of the final prediction effect (necessary) and add some ablation and hyperparameter experiments (after accept).\n\n**Response to Question 6:** As mentioned above, we will include accuracy plots and ablation studies in our final version.\n\nWe thank the reviewer for their great suggestions.  [We have included the accuracy plots in the global rebuttal as well](https://openreview.net/forum?id=JiRGxrqHh0&noteId=w65DtMxzEP).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their constructive feedback. We address individual reviewer questions within their respective rebuttals. Below, we detail new experiments as well as a more thorough description of our paper's limitations.

## Real World Validation of FACT via Additional Experiments

---

We consider a realistic situation where a consortium of hospitals seek collaboration to train a model, privately in a FL manner, that can diagnose skin cancer. Now, let's say one of the hospitals is smaller and resource-constrained. It is difficult, but not impossible, for this hospital to collect more data for training. Thus, in the absence of a truthful FL mechanism, the smaller hospital could over-report its collection costs to the server in order to contribute little to no data towards training while still reaping the rewards of a well-trained global model. **We provide experiments that show FACT rebuffs this scenario, with figures detailing our results within the pdf rebuttal**.

To test this scenario, we train an image classification model on the HAM10000 [C1] dataset. HAM10000 consists of a collection of dermatoscopic images of pigmented lesions. The goal is to train a model which can perform automated diagnosis of pigmented skin lesions, including melanoma (skin cancer).

Our setup is similar to that within our original experiment section. One difference is that we fine-tune a ResNet50 model on HAM10000 that is pre-trained on ImageNet (a realistic approach for a hospital). HAM10000 is an imbalanced dataset, and evenly partitioning 80% of the data amongst 10 devices as local training sets further exacerbates the non-iidness of the data. This too is realistic, as data is often non-iid amongst FL agents. We use the Adam optimizer with a learning rate of 1e-3, batch size of 128.

- **FACT reduces agent loss by nearly 66% compared to local training.**
- **Agents maximize their reduction in loss compared to local training when they truthfully report their costs.**
- **Agents reduce their free-riding penalties when they use their locally optimal amount of data ($m^\star = 801$) for training.**

## Addressing the Limitations

---

We agree with the reviewers that a more detailed description and discussion of our limitations and impact is needed within our paper. Below, we expand upon FACT's limitations.

**(1) Agents are assumed to be rational and not collude with one another.**

Our future research direction is to prove that equilibriums for FACT exist when agents are boundedly rational or colluding.

**(2) The server is assumed to be honest.**

In settings where the server cannot be trusted, new incentives or avenues must be built in order to ensure server honesty.

[C1] Tschandl, Philipp, Cliff Rosendahl, and Harald Kittler. "The HAM10000 dataset, a large collection of multi-source dermatoscopic images of common pigmented skin lesions." Scientific data 5.1 (2018): 1-9.

Meta-review: This paper introduces Federated Agent Cost Truthfulness (FACT) to address the issue of free-riding in federated learning. The key contributions include introducing a penalization scheme that incentivizes agents to provide truthful information, thereby eliminating free-riding and improving the performance of federated training. The proposed mechanism ensures that agents contribute as much data as they would in local training, thus aligning individual incentives with collective goals. Empirically, FACT effectively avoids free-riding even when agents are untruthful and significantly reduces agent loss. Some strengths of the paper include that: the method part of the paper has clear logic, and the contract theory is used to effectively prevent free-rider attacks in federated learning;
almost all the proposed theories or definitions have been proven, so sufficient theoretical evidence has been provided to demonstrate the effectiveness of FACT.; the problem solved is very critical, and it is the first study of free-rider attacks in federated learning under active deception conditions. In the rebuttal discussion, the authors had provided relatively concrete content to resolve many of reviewers’ concerns. There are still few concerns related to experiment parts in the discussion. After reading the reviews and the rebuttal, and going through the paper, my own reading is that the effectiveness of FACT mechanism has been demonstrated generally by the way of proving theories. Therefore, I suggest to accept this paper.
Decision: Accept (poster)