## 4 Optimal Trade Mechanism  
Before presenting the proposed multi-sided ascending price algorithm, an optimal trade mechanism with a polynomial time complexity is described in this section as an upper bound for all possible solutions to the mechanism design problem in Section 3.2. In this optimal trade mechanism, only the trade scheme is returned as the output regardless of the price vector and without considering the participant's strategic behavior. The optimal trade mechanism is calculated assuming all bandwidths and values are known by the market operator. The algorithm for calculating the optimal trade scheme is based on the basic operations of _vertical contraction_ and _horizontal contraction_ with the recipe tree structure shown in Figure 2a. The participants in each category are ordered with a decreasing value first. The vertical contraction operation is used to combine the network service providers that cannot meet the end-to-end slice request solely, for example, the RAN service providers in \(\mathcal{N}_{3}\) and the WAN service providers in \(\mathcal{N}_{4}\). In Figure 1, \(\mathcal{N}_{3}\) and \(\mathcal{N}_{4}\) are two nodes and the purpose of vertical contraction is to combine them into a new node \(\mathcal{N}_{3}\wedge\mathcal{N}_{4}\). New values and bandwidths are also calculated by the vertical contraction operation for \(\mathcal{N}_{3}\wedge\mathcal{N}_{4}\), as shown in Figure 3. The vertical contraction is used to combine a leaf node that is a single child with its parent node with the process shown in Algorithm 1. The combination process for the participants from the leaf node and its parent node is conducted iteratively. The combined values and bandwidths in the combined node are seen as \"new participants\" in the follow-up operations until only one node remains in the recipe tree. An example of the vertical contraction algorithm following Figure 2b is shown in Figure 3.  
The horizontal contraction operation is used to combine the network service providers that can meet the end-to-end slice request into a single set, e.g., the satellite network service providers in \(\mathcal{N}_{2}\) and the combined node \(\mathcal{N}_{3}\wedge\mathcal{N}_{4}\). The new node is denoted as \(\mathcal{N}_{2}\cup(\mathcal{N}_{3}\wedge\mathcal{N}_{4})\), with new values and bandwidths calculated by the horizontal contraction operation shown in Figure 4. Similarly to the vertical contraction, the horizontal contraction is used to combine two sibling leaves into a new node with the process shown in the Algorithm 2. An example of the horizontal contraction algorithm following Figure 3 is shown in Figure 4. When there are more than two sibling leaves, a pairwise horizontal contraction can be conducted with two nodes combined in each operation. One may easily find that the combined result as one final node is irrelevant to the order of the pairwise horizontal contraction operations. Figure 4: The example of the horizontal contraction algorithm. (**a**) The result of the recipe tree after the horizontal contraction. (**b**) The result of combined values and bandwidths. Figure 3: The example of the vertical contraction algorithm: (**a**) The result of the recipe tree after the vertical contraction; and (**b**) The result of combined values and bandwidths. Based on the vertical and horizontal contraction operations, the algorithm to find the optimal trade scheme is shown in Algorithm 3. After the recipe tree is contracted to a single root node, only the participants with a positive value are incorporated in the output trade scheme. It would be easier to calculate the gain from trade for the trade scheme by adding the values multiplied by the served bandwidths, i.e., \(GFT=\sum_{i}v_{i}\times r_{i}\), where \(v\) and \(r\) are the outputs of Algorithm 3. It is not difficult to generate the procurement sets by referring to the recorded participant identity sets and decomposing the combined values and bandwidths to the corresponding original users and service providers.