# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 2 Non-Approximability Results
Since \(\frac{\rho^{\prime}n|I^{*}|}{\rho_{2}n+\rho^{\prime}n|I_{p}|}\leq n^{1-2\varepsilon}\), we have that \(\left|\frac{|I^{*}|}{|I_{p}|}\right|\leq n^{1-2\varepsilon}\Big{(}1+\frac{ \rho_{2}}{\rho^{\prime}|I_{p}|}\Big{)}=O(n^{1-2\varepsilon})\), and, therefore, \(\mathcal{A}\) can be used to compute--in polynomial time--an \((n^{1-2\varepsilon})\)-approximate solution for the MIS problem instance. However, this contradicts the fact that the MIS problem is not approximable within a factor of \(n^{1-e^{\prime}}\), for any constant \(e^{\prime}>0\), unless \(\mathsf{P}=\mathsf{NP}\). Let \(e_{u}\) denote any leader's edge from a vertex \(u\) in the second layer to one of its copies in the third layer. For a pricing \(p\), let \(I_{p}\) denote the set of vertices \(u\) having some \(e_{u}\) with \(p(e_{u})>0\) being part of an SPT of \(G^{\prime}\). The edge \(e_{u}\) is contained in an SPT of \(G^{\prime}\) iff  
\[\forall v\in V\text{s.t.}\ (u,v)\in E,\quad p(r,u)+p(e_{u})\leq p(r,v)+\rho.\]  
Figure 1: An example of the reduction defined in Theorem 1 for the graph \(G\) on the left side. The DAG \(G^{\prime}\) restricted to the vertices \(u,v,v^{\prime}\) of \(G\) is shown on the right side. Dashed edges are fixed-cost edges while the other edges of \(G^{\prime}\) are owned by the leader. Observe that the distance from \(r\) to \(v^{\prime}\) does not depend on the price set on the edge \((r,v)\) but depends on the price set on the edge \((r,u)\). This is because \(\{v,v^{\prime}\}\) is an independent set of \(G\) while \(\{u,v\}\) is not. From the above inequalities, we have that \(e_{u}\) is contained in an SPT of \(G^{\prime}\) and \(p(e_{u})>0\) iff  
\[ \begin{cases}p(r,u)=\rho_{1},\\ p(e_{u})=\rho^{\prime}\\ p(r,v)=\rho_{2}\quad\quad\forall v\in V\text{ s.t. }(u,v)\in E.\end{cases}  \tag{2}\]  
This implies that, if edge \(e_{u}\) is in some SPT of \(G^{\prime}\) and \(p(e_{u})>0\), then no SPT of \(G^{\prime}\) contains the edge \(e_{v}\), for every vertex \(v\) such that \((u,v)\in E\). As a consequence, the set \(I_{p}\) always defines an independent set of \(G\). Moreover, observe that the revenue yielded by \(p\) is at most \(\rho_{2}n\) for the leader's edges outgoing from \(r\), and at most \(\rho^{\prime}n|I_{p}|\) for the other edges. Therefore, the total revenue yielded by \(p\) is at most \(\rho_{2}n+\rho^{\prime}n|I_{p}|\). To complete the proof, let \(I\) be an independent set of \(G\). The pricing \(p\) that satisfies the equalities in (2) for every \(e_{u}\) and for every \(u\in I\), yields a revenue of at least \(\rho^{\prime}n|I|\), and defines an independent set \(I_{p}\) such that \(I_{p}=I\). From the above theorem, we can easily derive the following general result:  
Theorem 4.2: _For every \(\epsilon>0\), the ASSPT game is not approximable within a factor of \(n^{1/2-\epsilon}\), unless \(P=\NP\), even on DAGs where fixed-cost edges have all cost 1._  
Proof: Consider the DAG \(G^{\prime}\) built in the reduction of Theorem 4.2 for the case \(\rho_{1}=\frac{n+1}{2}\) and \(\rho_{2}=n\), which implies \(\rho=1\). Build a graph \(G^{\prime\prime}\) from a copy of \(G^{\prime}\) by replacing every fixed-cost edge of cost \(k\) with \(k\) edges all having cost 1. Figure 2 shows an example of the reduction. Observe that \(G^{\prime\prime}\) still contains \(\Theta(n^{2})\) vertices. For a feasible pricing \(p\), let \(I_{p}\) denote the set of vertices \(u\) having some \(e_{u}\) with \(p(e_{u})>1\) being part of an SPT of \(G^{\prime}\). The edge \(e_{u}\) is contained in an SPT of \(G^{\prime}\) iff  
\[\forall v\in V\text{s.t. }(u,v)\in E,\quad\min\{\rho_{2},p(r,u)\}+p(e_{u}) \leq\min\{\rho_{2},p(r,v)\}+1.\]  
This implies that if edge \(e_{u}\) is in some SPT of \(G^{\prime}\) and \(p(e_{u})>1\), then no SPT of \(G^{\prime}\) contains the edge \(e_{v}\), for every vertex \(v\) such that \((u,v)\in E\). Therefore, \(I_{p}\) is an independent set of \(G\). Moreover, \(p\) yields a revenue of at most \(O(n^{2})+n^{2}|I_{p}|\).