# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 4 Dealing with Basic Network Topologies
### Unweighted Chains  
In this section we focus on instances where edges in \(C\) form a chain, and we show that while on DAGs the problem can be solved optimally, already the seemingly easy instance in which \(G\) is not a DAG but edges in \(C\) are unweighted becomes NP-hard. However, for such an instance we conjecture the existence of a constant-ratio approximation algorithm, and this is a subject of further research. Theorem 4.3: _The ASSPT game where the edges of \(C\) form a chain and \(G\) is a DAG can be solved in linear time._  
Proof: We compute \(d_{G_{C}}(r,u)\) for every \(u\) in linear time and we set the price of a priceable edge \((u,v)\) to \(p^{*}(u,v)=d_{G_{C}}(r,v)-d_{G_{C}}(r,u)\). Since priceable edges are all forward edges w.r.t. the fixed-cost path, it is easy to see that in any pricing we have that for every priceable edge \((u,v)\) the distance from \(u\) to \(v\) is upper bounded by \(p^{*}(u,v)\). This implies that the maximum revenue obtainable from \((u,v)\) is at most \(p^{*}(u,v)\). As a consequence, we have that the revenue we can obtain from priceable edges entering in the same node \(v\) is at most \(R(v):=\max_{u\mid(u,v)\in P}p^{*}(u,v)\). Now, the claim follows from the fact that in \(p^{*}\) the distance between any two nodes is equal to the distance in \(G_{C}\) between the same nodes, and hence for every node \(v\) which is the head of at least one priceable edge, we obtain revenue \(R(v)\). **Theorem 7**: _The ASSPT game where the edges of \(\mathcal{C}\) have unitary cost and form a chain is NP-hard._  
The reduction is again from SCP. Given an instance \(I=\langle O=\{o_{1},\ldots,o_{n}\},\mathcal{S}=\{S_{1},\ldots,S_{m}\}\rangle\) of SCP we build the following instance \(I^{\prime}\) of the ASSPT game. We have the root vertex \(r\), a node \(u_{j}\) for each \(S_{j}\), and a node \(v_{i}\) for each \(o_{i}\). Moreover, let \(N\) be an integer that we will fix later. We have \(N(n+m)\) additional nodes \(w^{i}_{j}\), \(i=1,\ldots,n+m,j=1,\ldots,N\), and \(n+m\) nodes \(x_{i}\), \(i=1,\ldots,n+m\). The fixed-cost edges have all cost \(1\) and form a path (spanning all nodes) from \(r\) to \(v_{n}\). The sequence of the nodes encountered when we traverse the path from \(r\) to \(v_{n}\) is the following: \(r,w^{1}_{1},\ldots,w^{1}_{N},\ldots,w^{n+m}_{1},\ldots,w^{n+m}_{N},x_{1},u_{ 1},x_{2},u_{2},\ldots,x_{m},u_{m},x_{m+1},v_{1},\ldots,x_{m+n},v_{n}\). The set \(P\) of preiche edges is partitioned into two sets, say \(P_{1}\) and \(P_{2}\). \(P_{1}\) is defined as follows: we have an edge \((r,x_{i})\) for each \(i\), and an edge \((x_{i},w^{i}_{j})\) for each \(i\) and each \(j\). \(P_{2}\) is defined similarly as in the reduction of Theorem 5, i.e., it contains an edge \((r,u_{j})\) for each \(u_{j}\) and an edge \((u_{j},v_{i})\) if and only if \(o_{i}\in S_{j}\) (see Figure 6). We have the following:  
**Lemma 3**: _In any optimal pricing \(p\) for the instance \(I^{\prime}\) of the ASSPT game, we have \(p(r,x_{i})=0\) and \(p(x_{i},w^{i}_{j})=d_{G_{\mathcal{C}}}(r,w^{i}_{j})\), for each \(i=1,\ldots,n+m\), and each \(j=1,\ldots,N\), when \(N>8(m+n)^{2}\)._  
Let \(p\) be an optimal pricing for \(I^{\prime}\) and assume by contradiction that the lemma is false. Let \(i\) be the minimum index for which the property of the lemma does not hold. Let \(F_{U}\) be the set of priceable edges entering in some \(w^{k}_{j}\), and let \(F_{D}=P\setminus F_{U}\). The idea is to build a strictly better pricing \(p^{\prime}\) from \(p\). The pricing \(p^{\prime}\) will lose some revenue from edges in \(F_{D}\) and will obtain more revenue from edges in \(F_{U}\). Let \(a=p(r,x_{i})\). We can assume that \(a>0\), otherwise \(p\) cannot be optimal since we can increase the revenue by simply increasing the price of every edge \((x_{i},w^{i}_{j})\) to \(d_{G_{\mathcal{C}}}(r,w^{i}_{j})\). Moreover, from the optimality of \(p\), it is clear that we can assume also that \((r,x_{i})\) is in \(H(p)\).