## 4 Optimal Design of Efficiency-Aware Incentive Mechanism
### Efficiency Score Function Design
According to the above analysis, we first designed an iterative algorithm to determine all incentivized edge servers and then characterized the training process of FedNow, which enables the edge servers to personally determine their local training rounds; we used the Monte Carlo method to obtain a better (near-optimal) response for the platform, including the incentivized set \(\mathcal{J}^{*}\) and corresponding \(\{s_{j}^{*},p_{j}^{*}\}_{j\in\mathcal{J}^{*}}\). With \(\mathcal{J}^{*}\) and \(\{s_{j}^{*},p_{j}^{*}\}_{j\in\mathcal{J}^{*}}\), the incentivized edge servers will honestly complete model training to compute the optimal global model parameters. The details of searching for feasible solutions are shown in Algorithm 1. The platform first calculates all edge servers' AMEC (Line 2-4), then sorts the edge servers based on their AMEC in ascending order and searches for the threshold type \(x^{\prime}\) (Line 5-18). The time complexity of calculating \(\tilde{e}_{j}\) (Line 4) is \(O(\mathcal{J})\), while the time complexity for checking whether the feasibility condition holds (Line 11) is also \(O(\mathcal{J})\). Therefore, the time complexity of Algorithm 1 is \(O(\mathcal{J}^{2})\). ```
Input \(\overline{\theta},c_{j},\,l_{j},\,P(r_{j}^{\prime}|r_{j}),\,\forall j\in \mathcal{J};r_{j},r_{j}^{\prime}\in\mathcal{R}\). Output \(x^{\prime}\), \(\mathcal{J}^{\prime}\). 1 Compute contract items \(\Phi=(s_{j},p_{j}),\forall j\in\mathcal{J}\); for\(j\) in range \([1,l]\)do
2 Calculate \(\mathbb{E}(r_{j})\) of type-\(j\) edge servers based on Formula (15);
3 Calculate \(\tilde{e}_{j}\) of type-\(j\) edge servers based on Formula (16);
4 Sort edge servers according to \(\tilde{e}_{j}\) in ascending order; for\(j\) in range \([1_{x},j]\)do
5 Initialize \(x^{\prime}=j\);
6 Insert \(x^{\prime}\) into \(\mathcal{J}^{\prime}\);
7 Check if Formula (10) holds;
8 ifyesthen
9 Check if \(U_{S}(\mathcal{J}^{\prime}\cup\{j+1\}_{\tilde{e}})>\overline{U_{S}}\);
10 ifyesthen
11 Record \(x^{\prime}\);
12 break;
13
14
15 else
16 continue;
17
18
19 else
20
21\(j++\);
```  
**Algorithm 1** Calculation of the feasible solution \((x^{\prime},\mathcal{J}^{\prime})\). Algorithm 2 describes the training process of FedNow when computing the optimal model parameters. The time complexity of the Monte Carlo method is \(O(N)\), where \(N\) means the number of sampling times. For a strongly convex objective \(F(\omega)\), the general upper bound of global iterations is expressed as \(T_{\text{ite}}(\kappa,\zeta)=\frac{O(\log(1/\sigma))}{1-\frac{\sigma}{\zeta}}\)[43], which is affected by both global accuracy \(\kappa\) and local accuracy \(\zeta\). Given a fixed global accuracy \(\sigma\), the upper bound of the local iterations, i.e., \(O(\log(1/\sigma))\), can be normalized to 1 so that \(T_{\text{ite}}(\zeta)=\frac{1}{1-\zeta}\)[16]. We represent the time used for one global iteration of FEL as \(T_{\text{glob}}\left(\overline{\zeta}\right)\); the upper bound of the time complexity for Algorithm 2 is \(O\Big{(}max\{N,\frac{1}{1-\zeta}\cdot T_{glob}(\zeta)\}\Big{)}\). ```
Input:\(t_{w},\mathcal{I},\mathcal{J},\,T,\,\eta,\,x^{\prime},\overline{\theta}\) and \(N\). Output:\(\omega^{T}\).