RealFM: A Realistic Mechanism to Incentivize Data Contribution and Device Participation

We continue our rebuttal here and address the "Questions" section within the review.

Karimireddy et al. (2022) “requires data sharing between devices and the central server”. Is the amount of data sharing the same as centralised FL? How does the amount of sharing in this work differ?

No data is shared within centralized FL. Instead, gradient updates are communicated between the devices and a central server. In Karimireddy et al. (2022), devices share their actual data with a server which violates the fundamental underpinning of FL.

Shapley value and collaborative fairness based approaches in existing work may not assume that devices are willing to contribute data... rational devices should contribute more data as in this work. Can you clarify and make the differences/advantages of your work more specific?

We detail the novelty of our work in the first part of our rebuttal. Wang et al. (2020) proposes a method to estimate the federated Shapley Value (which holds similar properties as the regular Shapley Value) in order to determine data quality from the devices participating in FL training. Thus, Wang et al. (2020) and other Shapley Value works seek to evaluate each data source in the FL setting. Our work seeks to incentivize and increase device participation, through mechanism design, within FL. This is fundamentally different.

Collaborative fairness works such as Lyu et al. (2020) are closer to our own in that they seek to fairly allocate models with varying performance depending upon how much devices contribute to training in FL settings. There are a few key differences between this line of work and our own, namely:

1. Our mechanism incentivizes devices to both participate in training and increase their amount of contributions. There are no such incentives in collaborative fairness.
2. We model device and server utility. Unlike collaborative fairness, we do not assume that devices will always participate in FL training.
3. Our mechanism design provably eliminates the free-rider phenomena unlike collaborative fairness, since devices who try to free-ride receive the same model performance as they would on their own (Equations 12 & 13).
4. No monetary rewards are received by devices in current collaborative fairness methods.

What is the implication/significance of Theorem 2?

Theorem 2 provides the theoretical underpinnings for a mechanism with certain assumptions to reach a Nash Equilibrium. Our mechanism satisfy these assumptions and thus reach an equilibrium at which devices will not deviate from their strategies (contributions). We prove in Theorem 3 that accuracy shaping used within our mechanism provably increases device utility and contributions. By Theorem 4, our mechanism reaches an equilibrium (Theorem 2) at which devices contribute more, receive higher utility, and no free-riding exists (Theorem 3).

Does the mechanism need monetary rewards to incentivise devices (can the profit margin be set to 1)?

No. Monetary rewards are not required. In fact, for ease of empirical analysis, we set the profit margin equal to 1 in all of our experimental results. Thus, device contributions and utility would increase further if we had set the profit margin to a lower value. This showcases how strong our mechanism works empirically.

In Eq 10, must $\phi_C(a(\sum m))$ be less than $\sum m$ to ensure a profit margin?

There may be some confusion regarding the profit margin. The profit margin $p_m$ dictates what percentage of the overall utility gained by the server is kept by the server. The remaining $1-p_m$ percentage of the utility is uniformly returned (as a marginal monetary reward) to each participating device as defined in Equation 10. Overall, $\phi_C(a(\sum m))$ can be larger, equal to, or smaller than $\sum m$. This does not affect the profit margin, it only affects the amount of monetary rewards returned to each participating device.

What does $\epsilon$ in Theorem 3 represent or control?

The parameter $\epsilon$ simply ensures that Equation 11 will be a strict inequality. This is crucial to ensure that devices are receiving more utility participating in our mechanism, via accuracy shaping, than on their own. If the inequality is not strict then devices are not incentivized to increase their contributions.

In practice, how does the central server produce a model with accuracy $a(m_i^o) + \gamma_i(m_i)$? Is it guaranteed to be less than $a(\sum m)$?

Via FL, the server will train a model using all contributions $\sum m$ which will result in a model with accuracy $a(\sum m)$. In order to provide devices with lower model performance, such as $a(m_i^o) + \gamma_i(m_i)$, the server can degrade the model using a variety of methods. Some examples of ways to do this include using noisy perturbations in a controlled manner or returning a model midway through training which has lower performance.

We thank reviewer A7vi for their thoughtful review of our paper. Below we address the questions raised. We first address the "Weakness" section within the review. Equations referenced below correspond to our revised paper.

Novelty (Advantages) of our Work

We begin our rebuttal by detailing the novelty of our work. Our work is the first FL mechanism which more realistically models device utility (non-linear function of model accuracy) and provably improves device participation and contributions (eliminating the free-rider effect) without the need of a payment mechanism prior to training. We sought to design a foundational FL mechanism which improves upon previous FL mechanisms by:

1. Modeling device utility in a more realistic manner which enables flexible modeling of diverse device utilities that accommodate non-linear relationships between model accuracy and utility.
   • Allowing this non-linear relationship within device utility requires major changes to the accuracy-shaping procedure, which incentivizes increased contributions in exchange for higher model accuracy, at the heart of the incentive mechanism (Theorem 4).
   • The altered accuracy-shaping function and its provable guarantees in Theorem 3 are novel.
   • The accuracy-shaping function incorporates monetary rewards, which are another novel inclusion detailed in (3).
2. Not requiring data to be shared between devices and a central server. Data sharing is required in Karimireddy et al. (2022), our closest related mechanism, and it violates the true FL setting.
3. Not requiring design of a payment mechanism (like that in Contract Theory) which needs careful construction of the payment prior to training.
   • This is similar to Karimireddy et al. (2022), however we instead define the central server's own utility and showcase that our mechanism maximizes the server's utility.
   • Also unlike Karimireddy et al. (2022), we leverage our newly defined server utility to allow monetary rewards for participating devices. This is fully novel within the non-payment mechanism setting.
4. Demonstrating empirically (on real-world data) that RealFM succeeds in the goals laid out within our paper: server utility, device utility, and device contributions skyrocket while free-riding is negated when devices use RealFM.

---

Simplicity of Assumptions

(1) Accuracy is modeled to depend solely on the number of data points... devices may have data with different quality, diversity and noise. (2) The central server has to compute $m_i^o$ and $m_i^*$ based on the declared $\phi_i$ and $c_i$. Device $i$ may misreport the cost to get a better reward.

The overarching goal of our work is to create a foundational FL mechanism which solves many of the issues detailed in our paper as well as above. There remain many frontiers to improve how realistically device utility is modeled. Data and truthfulness are two of them. We agree that in practice devices have different data distributions and data quality can vary both inter- and intra-device. We also agree that devices can be dishonest and report untruthful costs in practice. Relaxing our assumptions on data quality and truthfulness is an important follow-up to our work. The literature provided by reviewer A7vi on data quality is a great place to begin tackling the data quality assumptions.

Hard to decide the difficulty of the learning task $k$ and the server would not have access to data for tuning (Sec. 6) before incentivization. As $a$ is an upper bound, the individual rationality for the upper bound does not translate to rationality for the expected/actual values.

The use of $a$ in our paper was, in part, to allow for empirical analysis of our mechanism. What is most important about $a$ is that it must hold under reasonable and mild assumptions: continuous, non-decreasing, and concave (along a certain interval) with respect to the amount of data $m$. As shown in empirical studies Sun et al. (2017), accuracy grows with the amount of data used (continuous and non-decreasing) yet the growth experiences diminishing returns (concave). In practice, $a$ can be tuned by the server to align with test accuracy curves (as the accuracy improves with more contributions and updates).

---

Paper Refinements

(1) There needs to be a deeper discussion about Shapley value based/collaborative fairness approaches including Xu et. al. (2021) and Wang et. al. (2020) (2) Some notations are used before they are defined or explained (e.g., $[\mathcal{M}^U(\cdot)]_i$ in Theorem 2). This makes the claims unclear and harder to understand.

We appreciate the review's feedback and have expanded our related works and fixed our mistaken claim in Appendix A. $[\mathcal{M}^U(\cdot)]_i$ is the utility received by a device $i$ participating in the mechanism. We added or moved definitions of notations to ensure they are defined when they first appear. We have fixed all minor suggestions.

We thank reviewer gdSK for their thoughtful review and look forward to our discussion. We begin by reaffirming the novelty of our work before addressing the questions raised.

Novelty of Contributions

Our work is the first FL mechanism which more realistically models device utility (non-linear function of model accuracy) and provably improves device participation and contributions (eliminating the free-rider effect) without the need of a payment mechanism prior to training. We sought to design a foundational FL mechanism which improves upon previous FL mechanisms by:

1. Modeling device utility in a more realistic manner which enables flexible modeling of diverse device utilities that accommodate non-linear relationships between model accuracy and utility.
   • Allowing this non-linear relationship within device utility requires major changes to the accuracy-shaping procedure, the process in which the server provides devices increased model accuracy in exchange for an increase in contributions, at the heart of the incentive mechanism (Theorem 4).
   • The altered accuracy-shaping function and its provable guarantees in Theorem 3 are novel.
   • The accuracy-shaping function incorporates monetary rewards, which are another novel inclusion detailed in (3).
2. Not requiring data to be shared between devices and a central server. Data sharing is required in Karimireddy et al. (2022), our closest related mechanism, and it violates the true FL setting.
3. Not requiring design of a payment mechanism (like that in Contract Theory) which needs careful construction of the payment prior to training.
   • This is similar to Karimireddy et al. (2022), however we instead define the central server's own utility and showcase that our mechanism maximizes the server's utility.
   • Also unlike Karimireddy et al. (2022), we leverage our newly defined server utility to allow monetary rewards for participating devices. This is fully novel within the non-payment mechanism setting.
4. Demonstrating empirically (on real-world data) that RealFM succeeds in the goals laid out within our paper: server utility, device utility, and device contributions skyrocket while free-riding is negated when devices use RealFM.

Data Quality Assumptions

The overarching goal of our work is to create a foundational FL mechanism which solves many of the issues detailed in our paper as well as highlighted at the beginning of this rebuttal. There remain many frontiers to improve how realistically device utility is modeled, one of which is allowing for different quality data. Relaxing our assumptions on data quality is an important frontier to further improve realistic device utility. The literature [Wang et al. (2020)] provided by reviewer A7vi on data quality is a great place to begin tackling the data quality assumptions (through the use of Federated Shapley Values).

As the authors mentioned, it is hard to bond the composition function $\phi$, and I am still not sure how, particularly with this framework, we can ensure increased data production leads to better payoffs. In principle, one has to factor in the quality of data or limit combinatorial properties.

Accuracy function $\hat{a}(m)$ is increasing with respect to the amount of data $m$ (due to its concavity). The accuracy-payoff function $\phi_i(a)$ is increasing with respect to accuracy $a$. Therefore, $\phi_i(a(m))$ is increasing with respect to $m$. This is how, given our assumptions on data quality, we ensure "increased data production leads to better payoffs".

Will it enjoy generalization to the non-i.i.d. case?

Currently our mechanism does not fully generalize to the non-i.i.d case. The reason stems from the fact that our assumptions on $\hat{a}(m)$, detailed above, may fail in the non-i.i.d case ($\hat{a}(m)$ may not necessarily increase with more non-i.i.d data). However, there may be scenarios where adding non-i.i.d data still allows $\hat{a}(m)$ to be increasing with respect to $m$. Under this scenario our mechanism would generalize to the non-i.i.d case.

We continue our rebuttal below and address the remaining questions within the review.

Parameter Clarifications

Some inconsistencies and incompleteness due to unclear representation. For instance, the authors mention generalizing $\phi_i$ to become a convex and increasing function (but in which variable), and also, in actuality, the utility is modeled as a concave function? Following that, Assumption 2 needs further clarity. Another concern is Fig. 2, which is not well-justified for the said "payoff function. I don't see this claim has been experimentally validated apart from numerical evaluation.

We provide clarification that (1) $\phi_i(a)$ is convex with respect to the accuracy $a$, however (2) $\phi_i(\hat{a}(m))$ must remain concave with respect to $m$.

As detailed in our paper, we can define the accuracy function $\hat{a}(m)$ as either Equation 1 or 40 and the accuracy-payoff function $\phi_i(a) := \frac{1}{(1-a)^2} - 1$ and this will satisfy both (1) and (2). There are other variants of $\hat{a}(m)$ and $\phi_i(a)$ which work, but these are backed up by generalization bounds (Proposition 1) and intuition respectively.

The convex and increasing requirement for $\phi_i(a)$ is intuitive as rational devices heavily desire models with accuracies approaching 100%. This is much more intuitive than a linear $\phi_i(a)$, as described in the paper, since rational devices would place much greater value in a model increasing in accuracy from 99 to 99.5% than 30 to 30.5%.

---

How is $a_{opt}$ derived/obtained?

In practice, $a_{opt}$ depends upon model architectures as well as the learning task at hand. In many cases, prior knowledge about the difficulty of the learning task can illuminate what an actual or approximate value of $a_{opt}$ should be (e.g., many well-trained neural networks for image classification can achieve 90%+ optimal accuracies). In situations where the optimal accuracy might be completely unknown, a value close to 100% for $a_{opt}$ can be used to be conservative and ensure no issues will arise within the mechanism.

---

If the profit margin of the central server, defined as $p_m$, is fixed and known by all devices, I am not sure why it is used after all. (in the later experiments, this is used to indicate the degree to which the server is greedy). Assuming this is unknown would be an interesting analysis. Also, the definition of profit margin should be made more rigorous.

The profit margin $p_m$ details the percent of utility kept by the server after federated training is complete. The remaining $(1-p_m)$ percent is distributed uniformly as a monetary reward to all participating devices. It is important for devices to know the profit margin $p_m$, since a smaller $p_m$ will result in larger rewards for each device and may provide further incentive to participate. As noted by the reviewer, we showcase that device utility and contributions increase even when the server is greedy and maintains all of its gained utility.

We agree with the reviewer that assuming an unknown profit margin would be interesting analysis and we leave this as important future research. As detailed at the beginning of the rebuttal, our main goal was to construct the first FL mechanism of its kind. Once planted, we aim to further relax some of the assumptions initially used.

We continue our rebuttal below and address the remaining questions within the review.

It is understandable that the authors cannot be blamed for weak baseline algorithms, as this paper is the first to aim at incentivizing device data contribution in a non-linear setting... it would be more valuable to have theoretical guarantees of data maximization to truly showcase the strength of RealFM, which the paper lacks, except for the linear setting.

As mentioned by the reviewer, due to the dearth of FL mechanisms that allow for non-linear relationships between model accuracy and utility we were unable to compare against other mechanisms. We believe this speaks volumes about the novelty and importance of our work.

As mentioned by the reviwer, we prove data maximization under linear settings in Corollary 1. We were unable to guarantee tight theoretical guarantees in other settings due to the non-linearity. This stems from the proof of Theorem 3, specifically relaxing Equation 29. In fact, we assume $\phi_i(a)$ is convex with respect to the accuracy $a$ in order to make the bound as tight as possible. Therefore, the accuracy-shaping function proposed in Theorem 3 is close to data maximizing but falls slightly short.

We also mention that our empirical results showcase major improvement (up to 7x more) in device contributions relative to the available baselines even when the profit margin is set to 100%. Our results are even stronger when the server is not completely greedy. We outperform all state-of-the-art mechanisms which is both novel and important.

...it would be interesting to explore whether the results can be generalized to accommodate more general accuracy functions.

As long as the accuracy function $a$ fulfills the mild and reasonable assumptions laid out in Assumption 1: continuous, non-decreasing, and concave (along a certain interval) with respect to the amount of data $m$. These requirements are intuitive and backed by empirical studies Sun et al. (2017): accuracy grows with the amount of data used (continuous and non-decreasing) yet experiences diminishing returns (concave).

We thank reviewer EigJ for their thoughtful review of our paper. Below we address the questions raised.

The assumption that the closed form of each device's utility function is known, which may not always be realistic.

We agree with the reviewer that assuming the form of $u_i$ can be unrealistic in some instances for each device. However, we believe that using a closed-form $u_i$ is an important first step towards realistic FL. Using a closed-form $u_i$ for each device is much more realistic than assuming that devices will always participate in federated training regardless of its costs. The majority of FL papers do not even attempt to model device or server utility, which is quite unrealistic. Furthermore, there is usage of closed-form utility functions in economics literature [Trout (1963) & Orsborn et al. (2009)] as well as with mechanism design in ML [Karimireddy et al. (2022) and Zhan et al. (2021; 2020b)] to name a few. Removing the closed-form assumption is a great future research direction.

This may raise questions about potential cheating. It would make more sense to depend on each device's marginal contribution to model accuracy, provided that it can be easily and accurately determined.

We are wary that many other avenues to determine each device's marginal contribution, like Federated Shapley Value Wang et al. (2020), can be cheated as well. The issues surrounding honesty are an important future research direction in FL. We set out to accomplish quite a bit in our work, as it is the first FL mechanism which more realistically models device utility (non-linear function of model accuracy) and provably improves device participation and contributions (eliminating the free-rider effect) without the need of a payment mechanism. Specific novelties are listed in our rebuttal for Reviewer A7vi.

In summary, we aim to address honesty in future works but we first wanted to establish a foundational base for FL mechanisms which incentivize device participation and contributions.

Theorem 4, which claims that RealFM eliminates the free-rider phenomena, may not be particularly thrilling. Designing a contract to incentivize individuals when their exact contribution is known is not a challenging task.

As mentioned within our paper, contract-theory approaches require construction of a payment mechanism. Pricing of the contracts is especially difficult and can often result in sub-optimal utility gained by both the devices and servers (too low of a reward does not incentivize devices to participate and too high of a reward can cause the server to attain low or negative utility).

The importance of our work is that our mechanism allows free-riding to be eliminated without having to construct a payment mechanism prior to training. Using accuracy shaping, devices are incentivized to contribute more data because they will achieve a higher-performing model than they would by training alone. Theory 4 provably eliminates free-riding while also guaranteeing that devices will increase their contributions under a new accuracy-shaping scheme, differing from Karimireddy et al. (2022), which enables flexible modeling of diverse device utilities that accommodate non-linear relationships between model accuracy and utility. Furthermore, this mechanisms allow for monetary rewards to be received by devices after training.

We thank reviewer jpGm for their thoughtful review and look forward to our discussion. Below we address the questions raised in their review.

Experimental Size

We want to note that our experiments were run in a truly parallel and federated setting. Within our compute cluster, we assigned each CPU/process as a device and utilized MPI to perform communication between CPUs and a server CPU. Furthermore, each CPU was pinned to a GPU on which gradient computations were performed.

In the experimental setting, the number of devices is not large, which is not very consistent with the actual application scenario.

Due to the amount of compute resources, we could only use 16 CPUs and 8 GPUs (2 CPUs pinned to 1 GPU). We do lack the resources to perform realistic federated training in the realms of hundreds or thousands of devices. Furthermore, many existing FL papers use a similar scale as our own. Finally, other FL mechanism papers either use a similar number of devices or do not perform truly federated experiments at all. Our work is one of the first to provide truly federated empirical evidence to back up the claims of our proposed mechanism.

We also lack sufficient amounts of data to be split amongst devices if we have thousands of devices. The number of unique samples in the MNIST dataset is 60k, and this is even smaller since a fraction needs to be removed to evaluate test accuracy. In future work, with the proper compute power, we would love to showcase the efficacy of our mechanism on thousands of devices with extremely large real-world data.

How will performance change when the number of devices increases?

Our mechanism should improve as the number of participating devices increases. The reason is that more devices means more data used during FL training. Through the mild assumptions on $a(m)$, increasing and concave, more overall data contributions $\mathbf{m}$ will result in higher final accuracies $a(\sum\mathbf{m})$. The higher final accuracy will create a larger window for accuracy shaping, $m_i^* := [ m ≥ m^o_i | a(m + \sum_{j \neq i} m_j) = a(m^o_i) + \gamma_i(m) ]$, which in turn will result in a stronger incentive for devices to contribute more.

Utility Explanation

Can you explain Server Utility and Average Data Contribution in simpler and more intuitive language?

Server utility is simply the net benefit gained by the server from having a trained model with accuracy $a$: $\phi_C(a)$. Within our paper, the accuracy is a function of the total data contributions $\mathbf{m}$, and thus the final server utility is $p_m \cdot \phi_C(a(\sum \mathbf{m}))$. $p_m$ is just the profit margin, or the percentage of utility kept by the server after federated training is complete. The remaining $(1-p_m)$ percent is distributed uniformly as a monetary reward to all participating devices.

Average data contribution is the average amount of data that each device has determined is optimal (i.e., when device utility is maximized) to contribute. We see experimentally that the average amount of data contributions when devices train locally is substantially smaller than the optimal amount when devices participate in our mechanism. Furthermore, the average device utility also dramatically increases when participating in our mechanism!

I may still not fully understand how Server Utility and Average Data Contribution are Numerized.

Following literature in economics, mechanism design, and the intersection of both in FL, utility is often defined as a real-valued number. This number denotes the "net benefit" that a device attains. A larger real value denotes a larger net benefit received by the device.

In particular, I don’t quite understand why Server Utility has been improved so much.

As detailed above, server utility drastically improves because our mechanism incentivizes devices to contribute more data. By contributing more data, the accuracy $a(\sum \mathbf{m})$ increases (due to our mild assumptions) which in turn increases server utility $\phi_C(a(\sum \mathbf{m}))$ since $\phi_C$ is also strictly increasing with respect to the accuracy $a$.