# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 1 Introduction
### Asymmetric SNPGs  
In this paper, we focus on a natural _asymmetric_ SNPG, namely that in which the follower aims at building a _single-source shortest paths tree (SPT)_ of \(G\) rooted at a given node \(r\). More formally, our game, which we call _Asymmetric Stackelberg Shortest Paths Tree (ASSPT)_, can be described as the following bilevel optimization problem (all the paths are assumed to be directed):  
* _Instance:_ A directed graph \(G=(V,E=C\cup P,C\cap P=\emptyset)\), a function \(c:e\in C\to\mathbb{R}^{+}\), and a source node \(r\in V\).
* _Leader feasible solution:_ A pricing \(p:e\in P\to\mathbb{R}^{+}\).
* _Follower feasible solution:_ A spanning arborescence \(T=(V,E(T))\) of \(G\) rooted at \(r\) (after edges in \(P\) have been priced).
* _Follower objective:_ Find a feasible solution minimizing the sum of all the path costs in \(T\) from \(r\) to any node in \(G\), namely, denoting by \(||e||\) the number of paths in \(T\) emanating from \(r\) and using \(e\), minimize \[f_{2}(p,T)=\sum_{e\in P\cap E(T)}p(e)\cdot||e||+\sum_{e\in C\cap E(T)}c(e)\cdot ||e||.\]
* _Leader objective:_ Find a feasible pricing maximizing the revenue w.r.t. an optimal solution, say \(T(p)\), selected by the follower, namely minimize \[f_{1}(p,T(p))=\sum_{e\in P\cap E(T(p))}p(e).\] This game is clearly asymmetric, since \(f_{1}\) does not coincide with \(f_{2}\) once this is restricted to priced edges, and finds its motivation in SPT-based routing on the Internet. Here, an _Autonomous System_ (i.e., the leader) controlling part of the underlying network infrastructure could suitably adjust the costs of her edges in order to influence the choice of a follower in selecting a subnetwork satisfying his specific connectivity requirements. Actually, if the follower needs to provide a broadcasting service from a source to a set of destination nodes (i.e., final users which will in their turn pay for the service a cost proportional to the sum of the edge costs along a corresponding path from the source node), then buying an SPT rooted at the source allows the follower to certify the usage of a cheapest routing path.  
With the study of the ASSPT game, we continue in the effort of analyzing the computational aspects of SPT pricing games, which started in [19; 20] with the symmetric version of the game (i.e., that in which the leader's revenue for each selected edge is given by its price multiplied by the number of paths--emanating from the source--it belongs to). For this game, [PERSON] et al. [19] proved that finding an optimal pricing for the leader's edges is NP-hard, as soon as \(|P|=\Theta(n)\), while it is polynomial-time solvable when \(|P|\) is constant. A faster algorithm for the latter case was improved by [PERSON] [20]. In the following, as usual, we assume that, when multiple optimal solutions are available for the follower, he selects an optimal solution maximizing the leader's revenue (At a first glance, this rule looks in contrast with the antagonistic nature of the game. However, if this rule is relaxed, then it is easy to see that an optimal solution for the leader can only be reached within any arbitrary small subtractive term.).