# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 4 Dealing with Basic Network Topologies
### Unweighted Chains
Given a pricing \(p^{\prime\prime}\) and a node \(v\), we will denote by \(d_{p^{\prime\prime}}(v)\) the distance of \(v\) from \(r\) in \(H(p^{\prime\prime})\). At the beginning, \(p^{\prime}\) is defined as \(p\) except that \(p^{\prime}(r,x_{i})=0\) and \(p^{\prime}(e)=+\infty\) for every edge \(e\) not belonging to \(H(p)\). Notice that, for every vertex \(v\), \(d_{p^{\prime}}(v)\geq d_{p}(v)-a\). We first modify prices of the edges in \(F_{D}\). We repeatedly perform the following. If there is a node \(v\) such that \(\delta:=d_{p}(v)-d_{p^{\prime}}(v)<a\), we consider the path \(P\) from \(r\) to \(v\) in \(H(p)\). Let \(e_{1},\ldots,e_{h}\) be the edges of \(F_{D}\) along the path \(P\) in the order we encounter them when we traverse \(P\) from \(r\) to \(v\). If \(\sum_{j=1}^{h}p^{\prime}(e_{j})\leq\delta\), then we set \(p^{\prime}(e_{j})=0\) for every \(e_{j}\). Otherwise, let \(k\) be the minimum index such that \(\sum_{j=1}^{k}p^{\prime}(e_{j})>\delta\), we first decrease \(p^{\prime}(e_{k})\) by \(\delta-\sum_{j=1}^{k-1}p^{\prime}(e_{j})\), and then we set \(p^{\prime}(e_{j})=0\) for each \(j<k\). We stop when there is no edge left to be decreased. Notice that, when this happens, we have decreased each edge in \(F_{D}\) at most by \(a\) and it is easy to see that the revenue of \(p^{\prime}\) obtained from edges in \(F_{D}\) decreases by at most \(2n(m+n)\) since all the edges belonging to a path in \(H(p)\) which was decreased by at least \(a\) will still be selected by the follower. Figure 6: The reduction of Theorem 7. The unweighted fixed-cost path (in bold) is directed from \(r\) to \(v_{n}\). For the sake of clarity, only priceable edges in \(P_{1}\) are shown. We then consider edges in \(F_{U}\). First of all we set \(p^{\prime}(x_{i},w_{j}^{i})\) to \(d_{G_{C}}(r,w_{j}^{i})\), for every \(j=1,\ldots,N\). Let \(F\subseteq F_{U}\) be the set of edges entering in some vertex \(w_{j}^{k}\) with \(k>i\). For any pricing \(p^{\prime\prime}\), we use \(F(p^{\prime\prime})\) to denote the set \(F\cap H(p^{\prime\prime})\). Observe that \(F(p^{\prime})\subseteq F(p)\), since priceable edges in \(F\setminus F(p)\) are priced to infinity. We now modify \(p^{\prime}\) in order to guarantee that \(F(p^{\prime})=F(p)\). We repeatedly perform the following. Consider the first node \(w_{j}^{k}\) when we traverse the fixed-cost path from \(r\) to \(v_{n}\) such that \(d_{p^{\prime}}(w_{j}^{k})<d_{p}(w_{j}^{k})\). Since we have decreased the prices of edges in \(F_{D}\), we have \((x_{k},w_{j}^{k})\) belongs to \(H(p^{\prime})\). Then, we increase the price of \((x_{k},w_{j}^{k})\) by \(d_{p}(w_{j}^{k})-d_{p^{\prime}}(w_{j}^{k})\). Moreover, observe that for the same reason, we have that \((x_{k},w_{j}^{k})\) still belongs to the new SPT computed by the follower and, since the paths that are increasing their length are paths using the edge \((x_{k},w_{j}^{k})\), then no other edge \((x_{k^{\prime}},w_{j}^{k^{\prime}})\) exits from the SPT. We repeatedly use this argument until for every node \(w_{j}^{k}\) we have \(d_{p^{\prime}}(w_{j}^{k})\geq d_{p}(w_{j}^{k})\). Now, it is easy to see that \(F(p^{\prime})\) must be equal to \(F(p)\). We are now ready to bound the revenue of \(p^{\prime}\). We have already observed that the revenue we may lose from edges in \(F_{D}\) is upper bounded by \(2a(m+n)\), while we do not lose revenue from edges in \(F_{U}\). On the other hand, we can now bound the increment \(R_{i}\) of the revenue we obtain from all the edges \((x_{i},w_{1}^{i}),\ldots,(x_{i},w_{N}^{i})\). Notice that every edge \((x_{i},w_{j}^{i})\) is now selected in \(p^{\prime}\). We consider two cases:  
**Case \(i>1\)**: Since \((r,x_{i})\) is in \(H(p)\) and since \(p(r,x_{i-1})=0\), we have \(a\leq 2\). Moreover, since the price of every edge \((x_{i},w_{j}^{i})\) increased by at least \(a\), we have that \(R_{i}\geq Na\) which is strictly greater than \(2a(m+n)\) when \(N>2(m+n)\). **Case \(i=1\)**: When \(a>N\), no edge \((x_{1},w_{j}^{1})\) was selected in \(H(p)\).