# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 4 Dealing with Basic Network Topologies
### Unweighted Stars
Moreover, we have a priceable edge \((r,u_{j})\) for each \(u_{j}\), and a priceable edge \((u_{j},v_{i})\) if and only if \(o_{i}\in S_{j}\) (see Figure 5). We have the following:  
Lemma 2: _The instance of the ASSPT game has a pricing yielding a revenue of at least \(n+m-k\) if and only if \(I\) admits a cover of size at most \(k\)._  
Proof: Let \(\mathcal{C}\) be a cover of size \(k\) for \(I\). Then, define the following pricing: set \(p(r,u_{j})=0\) for each \(S_{j}\in\mathcal{C}\), while all the other priceable edges are set to \(1\). It is easy to see that we obtain a unit of revenue for each \(v_{i}\), and a unit of revenue for each \(u_{j}\) with \(S_{j}\
otin\mathcal{C}\), which provides a total revenue of \(n+m-k\). Conversely, let \(p\) be a pricing yielding a revenue \(R\geq n+m-k\), and let \(S\) be the SPT computed by the follower according to \(p\). We define two sets of nodes. Let \(X\) be the set containing every \(u_{j}\) which has in \(S\) at least one outgoing priceable edge, and let \(Y\) be the set containing every \(v_{i}\) which has in \(S\) an ingoing priceable edge. Then, since every node has a distance from \(r\) of at most 1, an upper bound for \(R\) is:  
\[R=\sum_{e\in E(S)\cap P}p(e)\leq\sum_{v_{i}\in Y}d_{S}(r,v_{i})+\sum_{u_{j} \
otin X}\max\{1,p(r,u_{j})\}\leq|Y|+m-|X|.\]  
Figure 5: The reduction of Theorem 4.1. Dashed edges are fixed-cost edges, while the other edges are owned by the leader. In this example, \(o_{i}\) is in \(S_{j}\), but \(o_{\ell}\) is not. We now define a pricing \(p^{\prime}\) as follows: \(p^{\prime}(r,u_{j})=0\) for each \(u_{j}\in X\), while all other edges are priced at \(1\). Hence, it is easy to see that \(p^{\prime}\) yields a revenue of at least \(|Y|+m-|X|\), since now each \(v_{i}\in Y\) is at distance \(1\) from \(r\) (and there is a path of priceable edges with length \(1\)), and since every \(u_{j}\
otin X\) has an ingoing leader's edge with price \(1\). Now, we modify \(p^{\prime}\) in such a way that: (i) the revenue does not change; and (ii) in the corresponding SPT \(S^{\prime}\) computed by the follower, every \(v_{i}\) has an ingoing priceable edge with price \(1\). We repeatedly perform the following. Consider any \(v_{i}\) that is not reached in \(S^{\prime}\) by a priceable edge with price \(1\), and consider a node \(u_{j}\) such that \(\alpha_{i}\in S_{j}\). We change \(p^{\prime}(r,u_{j})\) from \(1\) to \(0\). This does not change the revenue, since we lose a unit of revenue from the edge \((r,u_{j})\), while we obtain an additional unit of revenue from the edge \((u_{j},v_{i})\) which is now selected by the follower. Finally, we define a cover for \(I\) by selecting every \(S_{j}\) corresponding to a node \(u_{j}\) having distance \(0\) in \(p^{\prime}\). Since the revenue of \(p^{\prime}\) is at least \(n+m-k\), and since in \(S^{\prime}\) every \(v_{i}\) is reached by a priceable edge with price \(1\), it follows that the size of the cover is at most \(k\). This concludes the proof. To prove the APX-hardness, we restrict ourselves to instances of the SCP in which each subset has cardinality at most \(3\), and \(m\geq n\). Even in this case, the SCP is APX-hard [26]. We show that a \((1+\epsilon)\)-approximate algorithm for the ASSPT game would imply a \((1+\epsilon^{\prime})\)-approximate algorithm for the SCP, for a suitable \(\epsilon^{\prime}\). Assume that we have a \((1+\epsilon)\)-approximate algorithm for the ASSPT, and let \(k^{*}\) be the size of an optimum set cover for \(I\). We have that the algorithm returns a pricing \(p\) with revenue \(R\geq(m+n-k^{*})/(1+\epsilon)\). In the proof of Lemma 2, we show that \(p\) can be modified in order to yield a revenue of at least \(\lceil R\rceil\). Let \(k\) be the integer such that \(\lceil R\rceil=m+n-k\). Hence, from Lemma 2, we have that \(p\) induces a set cover of size \(k\).