# 5G Price Competition with Social Equilibrium Optimality for Social Networks
## 5 The Algorithm  
Here, we provide a continuous-time algorithm, in which all the variables are functions of time. For brevity, we write \(r_{nm}(t)\) and \(b_{m}(t)\) as \(r_{nm}\) and \(b_{m}\), respectively. Then we write their time derivatives \(\frac{\partial r_{nm}}{\partial t}\) and \(\frac{\partial b_{m}}{\partial t}\) as \(r_{nm}^{*}\) and \(b_{m}\). Note that \(r^{*}\) is the SWO's unique maximizer, while the corresponding Lagrange multiplier vector is \(b^{*}\). According to Theorem 2, we know that the supplier competition game's unique SPE is \((b^{*},r^{*})\), and its values are invariant. Given the demand vector \(r_{n}(t)\), we write user \(N^{\prime}\)s marginal utility according to \(r_{nm}\) as \(\psi_{nm}(t)\) or simply \(\psi_{nm}\). \[\psi_{nm}=\frac{\partial u_{n}(r_{n})}{\partial r_{nm}}=c_{nm}\frac{\partial u _{n}(y)}{\partial y}|_{y=y_{n}=\sum_{m=1}^{M}r_{nm}c_{nm}}. \tag{7}\]  
Here, we denote \(\psi_{nm}(t)\)'s value evaluated at \(r^{*}_{n}\) as \(\psi^{*}_{nm}\). Then we define column vectors: \(\
abla u_{n}(r_{n})=[\psi_{n1},\ldots,\psi_{nM}]^{\mathrm{T}}\) and \(\
abla u_{n}(r^{*}_{n})=[\psi^{*}_{n1},\ldots,\psi^{*}_{nM}]^{\mathrm{T}}\). Next, \((y)^{+}=\max(0,y)\) is defined, so that  
\[(y)^{+}_{x}{=}\left\{ \begin{array}{ll}y&x>0\\ (y)^{+}&x\leq 0.\end{array} \right.\]In the following, the standard primal-dual variable update algorithm is motivated by the work in [25]:  
\[\dot{r}_{mn}=k^{r}_{nm}(\psi_{nm}-b_{m})^{+}_{r_{nm}},n\in\mathcal{N},m\in \mathcal{M} \tag{8}\]  
\[b_{m}=k^{b}_{m}(\sum_{n=1}^{N}r_{nm}-R_{m})^{+}_{b_{m}},m\in\mathcal{M}. \tag{9}\]  
Here, \(k^{r}_{nm}\) and \(k^{b}_{m}\) are the constants that represent update rates. It is ensured that a variable of interest (\(r_{nm}\) or \(b_{m}\)) will not turn negative when it is zero, even if the update's direction is negative. We define the tuple \((r(t),b(t))\) controlled by Equations (8) and (9) as the differential equations' solution trajectory. Users only need to be given the prices that suppliers request. The providers do not need to be given other suppliers' demands of the users, except for that of their resources. Only user \(n\) needs to know \(c_{nm},m\in\mathcal{M}\). The procedure of bipartite graph representation is as follows. First of all, for every undecided node \(n\in\tilde{\mathcal{N}}\), calculate the checksum \(\Lambda_{n}\gets y^{*}_{n}\). Then, for every supplier \(m\in\tilde{\mathcal{M}}\) calculate the checksum \(\Gamma_{m}\gets R_{m}-\sum_{n:(n,m)\
otin\tilde{\mathcal{M}}}r^{*}_{nm}, \forall m\in\tilde{\mathcal{M}}\). Next, for every \(r^{*}_{nm}>0\), add edge \((n,m)\) to the edge set \(E\). And we have two steps in the loop. Step 1, Find a leaf node \(l\) and associated edge \((n,m)\), if the leaf node is a user node, then \(r^{*}_{nm}\leftarrow\frac{\Lambda_{n}}{c_{nm}}\), else \(r^{*}_{nm}\leftarrow\Gamma_{n}\). Step 2, Let \(\Lambda_{n}\leftarrow(\Lambda_{n}-r^{*}_{nm}c_{nm})\) and \(\Gamma_{n}\leftarrow(\Gamma_{n}-r^{*}_{nm})\), remove edge \((n,m)\). Keep doing these two steps until \(E\in\mathcal{O}\). To find the unique optimal \(r^{*}_{n}\) for undecided users, the algorithm provides detailed procedures. Here, \(E\), \(\left(\tilde{\mathcal{N}}\right)\), and \(\left(\tilde{\mathcal{M}}\right)\) are sets of edges, user nodes, and supplier nodes separately. Using the algorithm, we can find the demand of undecided users. Because the probability that a BGR has no loops is 1, suppose that the BGR is an unrooted tree. Then an uncomplicated iterative algorithm can remove a node with a single associated edge, which we define as a leaf node and its incoming edge at each iteration. First, a leaf node is found in the BGR. Second, the demand of the leaf node's incoming line is given from BGR Feature (1) or (2). Third, the parent node's check-sum is updated with this value. Finally, the leaf node and incoming edge are removed. This process is one iteration. Iterate until no edges exist in the graph.