## 4 Optimal Trade Mechanism
An example of the procurement sets generated by the optimal trade mechanism for Figure 2b is shown in Table 4. Note that a single user may be served by multiple network services as long as the sum of the served bandwidth is equal to the requested amount. For example, the user with a value of 17 is served in three procurement sets, as shown in the first three lines in Table 4. In the first line of Table 4, a bandwidth value of 1 is provided by the RAN and WAN providers together. In the second line of Table 4, a bandwidth value of 2 is provided by the satellite network provider solely. And, in the third line of Table 4, a bandwidth value of 2 is provided by the RAN and WAN providers together, in which the RAN provider has a higher price than the RAN provider in the first line. A service provider's bandwidth resource may not be fully utilized. For example, only half of the bandwidth resource from the WAN provider with a value of \(-4\) is utilized. Two theorems are presented to conclude this section. Theorem 1 demonstrates that the trade scheme generated by Algorithm 3 is optimal. Theorem 2 demonstrates that Algorithm 3 runs with a polynomial time complexity. ```
0: A sorted value vector \(\mathbf{v}_{l}\) and a corresponding bandwidth vector \(\mathbf{r}_{l}\) of the participants \(\mathcal{N}_{S_{l}}\) from the leaf node, a sorted value vector \(\mathbf{v}_{s}\) and a corresponding bandwidth vector \(\mathbf{r}_{s}\) of the participants \(\mathcal{N}_{S_{s}}\) from the sibling node. 0: A sorted value vector \(\mathbf{v}_{o}\), a corresponding bandwidth vector \(\mathbf{r}_{o}\), and a corresponding participant identity set \(\mathcal{N}_{S_{o}}\). 1. Initialization:\(\mathbf{v}_{o}=\emptyset\), \(\mathbf{r}_{o}=\emptyset\), \(\mathcal{N}_{S_{o}}=\emptyset\). 2. If \(|\mathbf{v}_{l}|==0\) and \(|\mathbf{v}_{s}|==0\): return\(\mathbf{v}_{o}\), \(\mathbf{r}_{o}\) and \(\mathcal{N}_{S_{o}}\). 3. If \(|\mathbf{v}_{s}|==0\) or the first element of \(\mathbf{v}_{l}\) is smaller than the first element of \(\mathbf{v}_{s}\), i.e., \(\mathbf{v}_{l}[0]<\mathbf{v}_{s}[0]\): Add \(\mathbf{v}_{l}[0]\) to \(\mathbf{v}_{o}\); Add \(\mathbf{r}_{l}[0]\) to \(\mathbf{r}_{o}\); Add \(\mathcal{N}_{S_{l}}[0]\) to \(\mathcal{N}_{S_{o}}\); Remove \(\mathbf{v}_{l}[0]\) from \(\mathbf{v}_{l}\); Remove \(\mathbf{r}_{l}[0]\) from \(\mathbf{r}_{l}\); Remove \(\mathcal{N}_{S_{l}}[0]\) from \(\mathcal{N}_{S_{l}}\); Go back to step 2. 4. Else, if \(|\mathbf{v}_{l}|==0\) or \(\mathbf{v}_{l}[0]>\mathbf{v}_{s}[0]\): Add \(\mathbf{v}_{s}[0]\) to \(\mathbf{v}_{o}\); Add \(\mathbf{r}_{s}[0]\) to \(\mathbf{r}_{o}\); Add \(\mathcal{N}_{S_{g}}[0]\) to \(\mathcal{N}_{S_{o}}\); Remove \(\mathbf{v}_{s}[0]\) from \(\mathbf{v}_{s}\); Remove \(\mathbf{r}_{s}[0]\) from \(\mathbf{r}_{s}\); Remove \(\mathcal{N}_{S_{g}}[0]\) from \(\mathcal{N}_{S_{g}}\); Go back to step 2. 5. Else: Add \(\mathbf{v}_{l}[0]\) to \(\mathbf{v}_{o}\); Add \(\mathbf{r}_{l}[0]+\mathbf{r}_{s}[0]\) to \(\mathbf{r}_{o}\); Add a new participant identity \(\mathcal{N}_{S_{l}}[0]\cup\mathcal{N}_{S_{l}}[0]\) to \(\mathcal{N}_{S_{o}}\); Remove \(\mathbf{v}_{l}[0]\) from \(\mathbf{v}_{l}\); Remove \(\mathbf{r}_{l}[0]\) from \(\mathbf{r}_{l}\); Remove \(\mathcal{N}_{S_{l}}[0]\) from \(\mathcal{N}_{S_{l}}\); Remove \(\mathbf{v}_{s}[0]\) from \(\mathbf{v}_{s}\); Remove \(\mathbf{r}_{s}[0]\) from \(\mathbf{r}_{s}\); Remove \(\mathbf{\lambda}_{S_{g}}[0]\) from \(\mathcal{N}_{S_{s}}\). Go back to step 2. ```  
**Algorithm 2** The horizontal contraction  
Theorem 1: _The trade scheme of Algorithm 3 is optimal, i.e., with the maximum gain from trade over all trade schemes._  
**Input:** A set of categories \(G\), a set of participants \(\mathcal{N}_{g}\) for all \(g\in G\), a recipe tree, the values and bandwidths of all participants. **Output:** A sorted value vector \(\mathbf{v}_{o}\), a corresponding bandwidth vector \(\mathbf{r}_{o}\), and a corresponding participant identity set \(\mathcal{N}_{S_{o}}\). 1.