# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 2 Non-Approximability Results  
In this section, we prove that the ASSPT game along with some basic variants of it are very hard to approximate. For the sake of simplifying the presentation, we first analyze a _binary pricing_ version of the game, denoted as \(\operatorname{ASSPT}(\{\rho_{1},\rho_{2}\})\), in which the leader is constrained to price her edges either \(\rho_{1}\) or \(\rho_{2}\). Then, we start by proving the following:  
**Theorem 1**: _For every \(\rho_{2}>\rho_{1}\geq 0\), with \(\rho_{2}/\rho_{1}=O(1)\), and for every constant \(\epsilon>0\), the \(\operatorname{ASSPT}(\{\rho_{1},\rho_{2}\})\) game is not approximable within a factor of \(n^{1/2-\epsilon}\), unless \(\mathsf{P}=\mathsf{NP}\), even on DAGs._  
Proof. : The reduction is from the _Maximum Independent Set (MIS)_ problem, i.e., the problem of finding a maximum cardinality set \(I\) of vertices of a given undirected graph \(G\) of \(n\) vertices such that no pair of vertices in \(I\) is linked by an edge of \(G\). More precisely, we describe how a graph \(G\) of \(n\) vertices--which is provided as an instance of the MIS problem--can be transformed into an instance of the \(\operatorname{ASSPT}(\{\rho_{1},\rho_{2}\})\) on a graph \(G^{\prime}\) of \(N=\Theta(n^{2})\) vertices. The claim then follows from the fact that the MIS problem is notapproximable within a factor of \(n^{1-e^{\prime}}\) for every constant \(e^{\prime}>0\), unless \(\mathsf{P}=\mathsf{NP}\), even if \(G\) is a connected graph ([PERSON] and [PERSON], 2011). The reduction works as follows. From a given undirected connected graph \(G=(V,E)\) of \(n\) vertices, we build a three-layered DAG \(G^{\prime}\). The first layer of \(G^{\prime}\) contains the root vertex \(r\) (w.l.o.g., we can assume that \(r\
ot\in V\)), the second layer of \(G^{\prime}\) contains a copy of all the vertices of \(G\), while the third layer of \(G^{\prime}\) contains \(n\) copies of all the vertices of \(G\). We observe that \(G^{\prime}\) has \(N=\Theta(n^{2})\) vertices. The set of fixed-cost edges is the following: there is an edge of cost \(\rho_{2}\) from \(r\) to every vertex in the second layer, and there is an edge of cost \(\rho=\max\{0,2\rho_{1}-\rho_{2}\}\) from a vertex \(u\) in the second layer to all the copies of vertex \(v\) in the third layer iff \((u,v)\in E\). The set \(P\) of leader's edges is the following: there is an edge from \(r\) to every vertex in the second layer, and every vertex \(u\) in the second layer has an outgoing edge towards each of its copies in the third layer. An example of the reduction is shown in Figure 1.  
By the connectivity property of \(G\), there is a fixed-cost path of length \(\rho_{2}\) from \(r\) to every vertex in the second layer, and a fixed-cost path of length \(\rho_{2}+\rho\) from \(r\) to every vertex in the third layer. Let \(\rho^{\prime}\) be equal to \(\rho_{1}\) if \(\rho_{1}>0\), and \(\rho_{2}\) otherwise. In what follows, we prove that every pricing \(p:P\to\{\rho_{1},\rho_{2}\}\) defines an independent set \(I_{p}\) of \(G\), and yields a revenue of at most \(\rho_{2}n+\rho^{\prime}n|I_{p}|\). Moreover, we also prove that for every independent set \(I\) of \(G\), there exists a pricing \(p\) yielding a revenue of at least \(\rho^{\prime}n|I|\), and such that \(I_{p}=I\). The claim then follows from the non-approximability result of the MIS problem and because \(G^{\prime}\) has \(N=\Theta(n^{2})\) vertices. Indeed, for the sake of contradiction, assume that \(\operatorname{ASSPT}(\{\rho_{1},\rho_{2}\})\) is approximable within a factor of \(N^{1/2-\varepsilon}=n^{1-2\varepsilon}\), for some constant \(\varepsilon>0\), by a polynomial-time algorithm \(\mathcal{A}\). Let \(p^{*}\) be an optimal pricing such that \(I_{p^{*}}=I^{*}\) is a maximum independent set of \(G\) and let \(p\) be the pricing computed by \(\mathcal{A}\). The revenue yielded by \(p^{*}\) is of at least \(\rho^{\prime}n|I^{*}|\), while the revenue yielded by \(p\) is of at most \(\rho_{2}n+\rho^{\prime}n|I_{p}|\).