# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 3 A Strongly Polynomial \(O(n)\)-Approximation Algorithm  
For symmetric SNPGs, [PERSON] et al. [11] proved the existence of an algorithm, called the _single-price algorithm_, that guarantees an approximation of \((1+\epsilon)(\mathcal{H}_{k}+\mathcal{H}_{|P|})\), where \(k\) denotes the number of followers. Notice that this result implies an \(O(\log n)\)-approximation for the symmetric version of the Stackelberg SPT game studied in [19]. Therefore, a simple question is whether the single-price algorithm provides a good approximation also for the ASSPT game. Not surprisingly, this is not the case, as illustrated in Figure 4, where we give an instance for which the single-price algorithm returns an \((n-3)\)-approximate solution. Thus, the power of the single-price algorithm seems to rely on the alignment of the leader's and follower's objective functions. Figure 3: An example of the reduction defined in Theorem 3 for the graph \(G\) on the left side. The reduction is an extension of the reduction of Theorem 2. The paths \(\pi_{u},\pi_{v}\), and \(\pi_{v^{\prime}}\) contains \(n\) priceable edges each. Besides being only \(\Omega(n)\)-approximating, the single-price algorithm has also another drawback, namely it is not _strongly polynomial_, since it is polynomial in the input size, but its running time depends on the given edge costs. Indeed, for our problem, it requires the testing of \(1+\frac{\log[c_{0}]}{\log(1+\epsilon)}\) different weights for the priceable edges, where \(c_{0}\) is the cost of a cheapest feasible solution not containing leader's edges. Therefore, in an effort to improve on that, we develop the following simple strategy the leader can play in order to get in strongly polynomial-time an \((n-1)\)-approximation of the maximum achievable revenue. Actually, the goal of closing the \(O(\sqrt{n})\) gap left open w.r.t. the corresponding inapproximability result remains a challenging open problem. For the _ASSPT problem_, the pricing function \(p\) that prices each edge \(e=(u,v)\in P\) with \(p(e)=\max\{0,d_{G_{\mathrm{C}}}(r,v)-d_{G_{\mathrm{C}}}(r,u)\}\) is computable in \(O(m+n\log n)\) time and yields a revenue of at least \(\frac{1}{n-1}R^{*}\), where \(d_{G_{\mathrm{C}}}\) denotes distances computed in \(G_{\mathrm{C}}=(V,C)\) and \(R^{*}\) denotes the revenue yielded by an optimal pricing. Proof. : Let \(p^{*}\) be a pricing such that \(f_{1}(p^{*},H(p^{*}))=R^{*}\). For a path \(\pi\), we denote by \(\mathtt{revenue}(\pi)\) the value \(\sum_{e\in E(\pi)\cap P}p^{*}(e)\). Let \(\pi\) be a path in \(H(p^{*})\) outgoing from \(r\) such that \(\mathtt{revenue}(\pi)\geq\mathtt{revenue}(\pi^{\prime})\), for every other path \(\pi^{\prime}\) of \(H(p^{*})\) outgoing from \(r\). Clearly, \(\mathtt{revenue}(\pi)\geq\frac{1}{n-1}R^{*}\). In what follows, we show that \(f_{1}(p,H(p))\geq\mathtt{revenue}(\pi)\). Let \(e_{1},\ldots,e_{k}\) denote the edges of \(E(\pi)\cap P\) in the order in which they appear if we traverse \(\pi\) starting from \(r\). Let \(e_{i}=(u_{i},v_{i})\), for every \(i=1,\ldots,k\). Moreover, for every \(i=1,\ldots,k\), let us denote by \(\ell_{i}\) the length of the (fixed-cost) subpath of \(\pi\) going from \(v_{i-1}\) to \(u_{i}\), where \(v_{0}=r\). We have that  
\[\forall i=1,\ldots,k-1,\,d_{G_{\mathrm{C}}}(r,v_{i})+\ell_{i+1}\geq d_{G_{ \mathrm{C}}}(r,u_{i+1}).\]  
Summing over all is, adding up the two equalities \(d_{G_{\mathrm{C}}}(r,u_{1})=\ell_{1}\) and \(d_{G_{\mathrm{C}}}(r,v_{k})=d_{G_{\mathrm{C}}}(r,v_{k})\), and rearranging the terms, we obtain  
\[\sum_{i=1}^{k}\left(d_{G_{\mathrm{C}}}(r,v_{i})-d_{G_{\mathrm{C}}}(r,u_{i}) \right)\geq d_{G_{\mathrm{C}}}(r,v_{k})-\sum_{i=1}^{k}\ell_{i}. \tag{3}\]  
Figure 4: An example where the single-price algorithm, i.e., the algorithm that eventually will price all the edges with a same value \(\sigma\geq 0\), does not return a better than \((n-3)\)-approximate solution. Dashed edges are fixed-cost edges, while the other edges are owned by the leader.