# QuoTa: An Online Quality-Aware Incentive Mechanism for Fast Federated Learning
## 4 Design of QuoTa
### Data Owner Selection and Payment
1\(\mathbf{p}\leftarrow\mathbf{0}\), \(\mathbf{S}\leftarrow\overline{\partial}\);
2 forcommunication round \(t\) = 1,2,... do
3 // Data Owner Selection ;
4 compute \(\mathcal{S}^{t}\) by Formulas (16) and (17);
5 deliver global model \(w^{t-1}\) to \(i\in\mathcal{S}^{t}\);
6 for\(i\in\mathcal{S}^{t}\) in paralleldo
7 \(w_{k}^{t}\leftarrow\) local model training by \(w^{t-1}\);
8 // Model Quality Detection;
9 calculate the detection value \(v_{i}^{t}=\left[(GA^{t}-LA_{i}^{t})-\epsilon_{1}^{t}\right]-\left[(GA^{t}-GA^{t }_{-i})-\epsilon_{2}^{t}\right]\);
10 calculated direct reputation \(rep_{i}^{t}\) by (10), (11) ;
11 update comprehensive reputation \(Rep_{i}^{t}\) by Formula (12);
12 calculate the aggregated weight \(a_{i}^{t}=\frac{LA_{i}^{t}}{\sum_{i\in\mathcal{S}^{t}}(LA_{i}^{t})}\);
13 // Model Training Time Prediction;
14 calculate average CPU frequency \(\tilde{f}_{i}^{t}=\frac{\sum_{t=0}^{t}\tilde{f}_{i}^{t}*x_{i}^{t}}{n_{i}^{t}}\);
15 update estimated computing capability \(\tilde{C}_{i}^{t}\) by Formulas (14) and (15);
16 aggregate global model \(w^{t}=a_{i}^{t}\sum_{k=1}^{|\mathcal{S}^{t}|}w_{k}^{t}\);
17 // Payment Decision;
18 for\(i\in\mathcal{S}^{t}\), \(\mathcal{N}^{\prime}\leftarrow\mathcal{N}\)do
19\(\mathcal{N}^{\prime}\leftarrow\mathcal{N}^{\prime}\) / \(i\);
20 Find an alternative data owner \(i^{*}\) with the smallest claimed cost \(b_{i^{*}}\);
21\(p_{i}=\min(\frac{B^{t}}{|\mathcal{S}^{t}|},b_{i^{*}})\);
22 return(\(\boldsymbol{S,p}\));
```  
**Algorithm 1**QuoTa Mechanism  
Theorem 1 (). : _The proposed QuoTa mechanism satisfies truthfulness, individual rationality, and budget balance._  
Proof. : We first prove that QuoTa is truthful. A winner with a smaller claimed bid is still selected because their bid is yet smallest among all candidate data owners. Hence, we show the monotonicity. In addition, according to line 21, when they claim a smaller bid \(\tilde{b}_{i}\), they still obtain the unchanged payment because the received payment is only related to the alternative data owner's bid, and thus their utility is never improved. Conversely, when he reports a higher bid, \(\tilde{b}_{i}\geq b_{i^{*}}\), another data owner will replace them as the new winner. Hence, their utility becomes zero. To this end, he has no incentive to misreport their cost. Similarly, when they report a larger local data amount \(\hat{d}_{i}\geq d_{i}\), they would still be selected and obtain the same payment. But, a smaller amount makes them lose. For \(fre_{i}\), any misreporting about it would never improve their utility. Thus, QuoTa achieves truthfulness on multiple-dimensional claimed resources. For any data owner who loses, their utility is zero. Additionally, for any winning data owner \(i\in\mathcal{S}^{t}\), their payment is \(p_{i}=\min(\frac{B^{t}}{|\mathcal{S}^{t}|},b_{i^{*}})\geq b_{i}=c_{i}\) in terms of truthfulness. Therefore, each data owner is individual rational. Finally, since the total payment is \(\sum_{i}p_{i}=|\mathcal{S}^{t}|\min(\frac{B^{t}}{|\mathcal{S}^{t}|},b_{i^{*}}) \leq B^{t}\), QuoTa also achieves budget balance.