## 5 Multi-Sided Ascending-Price Auction Mechanism
Generally, if the bandwidth sum of the root node, i.e., the user, is greater than the bandwidth sum of its children, i.e., the service providers, the price charged for the users is increased so that some user would leave the market. In the opposite situation, wherein the price charged for the service providers is increased (equally, the price paid for the service providers is decreased) so that some service providers would leave the market. A desirable property of Algorithm 5 is that the chosen subset contains exactly one price for each path from a root a leaf. Recall that the initial price sum in all recipes is set to be the same. By simultaneously increasing the prices in the chosen subset, the price sum in all recipes remains the same. ```
0: A set of categories \(G\), a set of remaining participants \(\mathcal{N}_{g}\) for all \(g\in G\), a recipe tree \(\mathcal{R}\), the values and bandwidths of all remaining participants. 0: A subset of \(G\) containing categories whose prices are to be increased. 1. Initialization: For each category \(g\in G\), define \(m_{g}:=\sum_{i\in\mathcal{N}_{g}}r_{i}\)=the bandwidth sum of participants of \(\mathcal{N}_{g}\) who remain in the market. 2. Denote \(g_{0}\) as the root category:

If \(g_{0}\) has no children or \(m_{g_{0}}>\sum_{g^{\prime}\in Children(g)}m_{g^{\prime}}\), return \(\{g_{0}\}\);

Else for each child \(g^{\prime}\) of \(g_{0}\), apply Algorithm 5 on the sub-tree rooted at \(g^{\prime}\) recursively and take the union set of the outcome \(I_{g^{\prime}}\), i.e., return \(\cup_{g^{\prime}\in Children(g)}I_{g^{\prime}}\). ```
**Algorithm 5** The subset selection for price ascending

At some time step, the price sum of a recipe crosses zero, which triggers the termination of the price ascending process. To maintain the strong budget balance, the increased prices are reset so that the price sum of a recipe is exactly zero, as shown in Step 3 of Algorithm 5. After the auction is terminated and the price vector is finalized, the final trade scheme is further determined by Algorithm 6. ```
0: A set of categories \(G\), a set of remaining participants \(\mathcal{N}_{g}\) for all \(g\in G\), a recipe tree \(\mathcal{R}\), the values and bandwidths of all remaining participants. 0: The procurement sets \(\mathcal{S}\). 1. If the recipe tree has a single root node \(g\):  Return the remaining participants in category \(g\), with the original participant identity reversed from the recorded participant identity set. 2. Else, if the recipe tree has a single root node \(g\) and a single child \(g_{c}\):  If \(m_{g}>m_{g_{c}}\), i.e., the bandwidth sum requested by the users is larger than the bandwidth resource provided by the service providers:  Remove the participant in \(\mathcal{N}_{g}\) in a random order until \(m_{g}\leq m_{g_{c}}\);  Randomly order the participants in \(\mathcal{N}_{g}\) and \(\mathcal{N}_{g_{c}}\);  Do a vertical contraction of \(g_{c}\) into \(g\) by Algorithm 1;  Go back to step 1. ```
**Algorithm 6** The trade scheme determination

Since, pick an arbitrary leaf \(g_{l}\). 4. If \(g_{l}\) is the single child of its parent \(g_{p}\):  Randomly order the participants in \(\mathcal{N}_{g_{l}}\) and \(\mathcal{N}_{g_{l}}\);  Do a vertical contraction of \(g_{l}\) into \(g_{p}\) by Algorithm 1;  Go back to step 1. 5. Else, choose a sibling \(g_{s}\) of \(g_{l}\):  Randomly order the participants in \(\mathcal{N}_{g_{l}}\) and \(\mathcal{N}_{g_{s}}\);  Do a horizontal contraction of \(g_{l}\) into \(g_{s}\) by Algorithm 2;  Go back to step 1. ```  
**Algorithm 7** The trade scheme determination  
Since the supply and demand of bandwidth resources may not be balanced after the auction terminates, some participants must be removed from the market in the trade scheme determination. To avoid non-truthful and strategic behaviors, the selection of the remaining participants is independent of the values but conducted in a random fashion, as shown in Algorithm 6.