FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding?

Thank you, Reviewer k1Mz, for your insightful review of our paper. Below, we address all questions you raised.

Addressing Weaknesses

Weakness 1: Eq 10, 26, and 27 lack punctuation.

Response to Weakness 1: We begin by thanking you for catching the punctuation issues, and have fixed them within our paper.

Weakness 2: Line 447, 452, 459, 475, 485, 496, and 514 are extra blank lines.

Response to Weakness 2: Each of these lines include an "end of proof" symbol on the far right of the line.

Weakness 3: It may be better to add one figure in the Introduction to show the proposed issues.

Response to Weakness 3: We have added such a schematic into the Introduction of our paper.

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.

Response to Weakness 4:

• FACT does not incur extra communication costs during FL training.
• FACT simply details a mechanism to distribute agent rewards after FL training is complete.

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

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.

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.

• We have included the accuracy plots within our PDF rebuttal for the reviewer to view.

Question Responses

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?

Response to Question 1:

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

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

In summary, since we develop the first mechanism to eliminate free riding when agents can be untruthful, there are no comparable mechanisms to test against.

Question 2: Is it a limitation that the parties cannot collude? If the parties collude, can FACT also effectively protect FL?

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.

Question 3: What is the additional computational overhead of FACT compared to traditional FL and local training?

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.

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.

Response to Question 4:

• 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.
• The degradation is a result of the penalties that are incurred in order to ensure agent truthfulness.
• 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.

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.

Response to Question 5: As mentioned above, no comparable mechanism exists which can deal with agent untruthfulness.

• Neither provided paper proposes a mechanism to defend against FL free riding through incentives, and neither deal with agent untruthfulness.

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

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

Response to Question 6: As mentioned above, we will include accuracy plots and ablation studies in our final version.

We thank the reviewer for their great suggestions. We have included the accuracy plots in the global rebuttal as well.

Thank you, Reviewer dpi3, for your insightful review of our paper. Below, we address all the questions you raised.

Question Responses

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?

Response to Question 1:

• The type of game we consider is a One-Shot, Simultaneous Game.
• The solution concept within FACT is a Pure Nash Equilibrium.

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

• Alternative abstractions in FL Free-Riding mechanism have equivalent game types and solution concepts.

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

We have added this discussion to our paper.

Question 2: How do you address recent critiques on the practicality of truthful mechanisms...?

Response to Question 2:

• The theory underpinning truthful mechanisms, like our own, is rigorous and will hold as long as the underlying assumptions are satisfied.

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

• Theory provides important insight into the current limitations of truthfulness within the field and provides avenues for future progress into eliminating such limitations.
• 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.

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

Question 3: What are the incentives for the server to implement the sandwich mechanism...? How do you ensure clients trust the server...?

Response to Question 3:

• Eliminating free riding allows the central server to train higher-performing models.

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

• The server receives leftover agent contract fees.

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

• Implementation costs in FACT are much smaller than related mechanisms.

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

We have added this discussion to our paper.

Question 4: Can you provide more extensive experimental validation... to demonstrate the robustness and applicability of the proposed mechanism?

Response to Question 4:

• Our validation showcases that FACT performs well within multiple practical scenarios.

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

• Our validation is more extensive than those in related FL mechanism works.

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

• We have added additional validation in practical scenarios within our global rebuttal that demonstrate the effectiveness and robustness of FACT.

Thank you again for your insightful review! We wanted to follow-up to ensure that our rebuttal has indeed addressed all concerns listed within your original review. If not, we would be happy to continue discussion before the end of the discussion period tomorrow.

Thank you, Reviewer hdyq, for your insightful review of our paper. Below, we address all questions you raised.

Addressing Weaknesses

Weakness 1: Are there any real-world examples that illustrate the necessity of addressing free-riding and dishonesty issues in federated learning?

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.

• 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]).
• Realistic examples of FL free riding include training models for healthcare applications, an example we provide additional experiments for in our global rebuttal.

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?

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.

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?

Response to Weakness 3:

• Equation (2) defines the local agent loss.

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

Weakness 4: Please elaborate more clearly on the logical relationship between Equation 2 and Equation 3.

Response to Weakness 4:

• Equation (2) defines the local agent loss (training alone), while Equation (3) defines an agent's loss when it participates in distributed training.

Weakness 5: It would be better if the intuitive principles behind the formula design could be provided, such as for Equation 4.

Response to Weakness 5:

• 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}$).

We thank the reviewer for this comment and agree that this should be provided within the paper. We have added this explanation within the paper.

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?

Response to Weakness 5: Yes, the "No Collusion" assumption is standard within truthful mechanism theory (for example Vickrey auctions).

• 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.
• Up until our work, it was an open question within FL whether a mechanism can provably guarantee agent truthfulness when querying their participation workload.
• 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?

[R1] Lin, Jierui, et al. "Free-riders in federated learning: Attacks and defenses." arXiv preprint arXiv:1911.12560 (2019).

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

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

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