# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 1 Introduction
### Our Results  
Throughout the paper, we analyze the ASSPT game under several respects. More precisely, we first study the complexity of the game, and we show that finding an optimal pricing for the leader's edges is an extremely difficult task, even under strongly restrictive assumptions. Indeed, we show that for every \(e>0\), the ASSPT game is not approximable within a factor of \(n^{1/2-\epsilon}\), unless \(\mathsf{P}=\mathsf{NP}\). Then, we turn our attention to the _unweighted_ ASSPT game, i.e., the one in which \(c(e)=1\) for any \(e\in C\), while \(p:e\in P\to\{1,+\infty\}\), and we prove that, for every \(e>0\), the game is not approximable within a factor of \(n^{1/3-\epsilon}\), unless \(\mathsf{P}=\mathsf{NP}\).  
Then, we turn our attention to the development of an approximation algorithm for the ASSPT game, and we devise a pricing strategy that in \(O(m+n\log n)\) time returns an \((n-1)\)-approximation of the optimal leader's revenue. Although our algorithm leaves an \(O(\sqrt{n})\) gap open with the corresponding inapproximability result, remarkably, its running time is _strongly polynomial_ (i.e., it does not depend on the magnitude of the costs of the edges in \(C\)). Therefore, it compares favorably with the powerful but non-strongly polynomial _single-price algorithm_[11], which has a provably logarithmic approximation ratio for _any_ symmetric SNPGs in which \(f_{2}\) is of the form (1), while in contrast we show that for the ASSPT game it can only guarantee an \(\Omega(n)\) factor.  
Finally, motivated by practical applications, we study the ASSPT game when edges in \(C\) are unweighted and happen to form two popular network communication topologies, namely _stars_ and _chains_. As far as the star topology is concerned, we first show an equivalence of the ASSPT game with the well-studied _Rooted Maximum Leaf Outbranching (RMLO)_ problem, which asks for finding a spanning arborescence rooted at some prescribed vertex of a digraph with the maximum number of leaves. This problem is known to be \(\mathsf{NP}\)-hard already on _directed acyclic graphs (DAGs)_, as well as 92-approximable [21; 22]. Thus, these results immediately extend to the ASSPT game on unweighted stars. Moreover, we show the APX-hardness of such a game even if \(G\) is actually a DAG, and this inapproximability carries over to the RMLO problem on DAGs, as is shown below, which is a result of independent interest. Concerning the chain topology, we show that, if \(G\) is a DAG, then our approximation algorithm returns an optimal pricing, even in the weighted case. On the other hand, if \(G\) is not a DAG, then we prove the ASSPT game becomes \(\mathsf{NP}\)-hard, and so the problem of finding a constant-ratio approximation algorithm, for which we conjecture the existence, remains a challenging open problem.  
The rest of the paper is organized as follows. Section 2 contains inapproximability results. Section 3 presents our approximation algorithm, along with a bad instance example for the single-price algorithm. Section 4 deals with the star and the chain topology. Section 5 concludes the paper and suggests possible future work.