# Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game +
## 1 Introduction
### Stackelberg Network Pricing Games  
Network games can be easily regarded as Stackelberg games, as soon as a situation arises in which a subset of dominant players controls a higher-level decision phase in which part of the game instance is set, for example by routing a substantial amount of a network flow [2] or by deciding the cost of a subset of network arcs. In particular, games of this latter type, which are of interest for this paper, are widely known as _Stackelberg Network Pricing Games_ (SNPGs). A SNPG can be formalized as follows: We are given either a directed or an undirected graph \(G=(V,E=C\cup P,C\cap P=\emptyset)\), with an edge cost function \(c:e\in C\to\mathbb{R}_{\geq 0}\), while edges in \(P\) need to be priced by the leader. In the following, we assume that \(n=|V|\) and \(m=|C|+|P|\). As usual, we also permit the existence of parallel pairs of weighted and priceable edges. Then, the leader moves first and chooses a pricing function \(p:e\in P\to\mathbb{R}_{\geq 0}\) for her edges, in an attempt to _maximize_ her objective function \(f_{1}(p,H(p))\), where \(H(p)\) denotes the decision which will be taken by the follower, consisting in the choice of a subgraph of \(G\). This notation stresses the fact that the leader's problem is implicit in the follower's decision. Once observed the leader's choice, the follower reacts by selecting a subgraph \(H(p)=(V^{\prime},E^{\prime})\) of \(G\) which _minimizes_ his objective function \(f_{2}(p,H)\), parameterized in \(p\). Note that the leader's strategy affects both the follower's objective function and the set of feasible decisions, while the follower's choice only affects the leader's objective function. Throughout the paper, we naturally assume that \(f_{1}\) is _price-additive_, i.e., \(f_{1}(p,H(p))=\sum_{e\in P\cap E^{\prime}}p(e)\). This means the leader decides edge prices having in mind that her revenue equals the overall price of her selected edges. The most immediate SNPG is that in which we are given two specified nodes in \(G\), say \(s,t\), and the follower wants to travel along a shortest path in \(G\) between \(s\) and \(t\) (see [3] for a survey). This problem has been shown to be APX-hard [4], as well as not approximable within a factor of \(2-o(1)\) unless \(P=\NP\)[5], while an \(O(\log|P|)\)-approximation is provided in [6]. For the case of multiple followers (each with a specific source-destination pair), [PERSON] et al. [7] derived a bilevel LP formulation of the problem (and proved \(\NP\)-hardness), while [PERSON] et al. [8] presented algorithms for a restricted shortest path problem on parallel edges. Another basic SNPG is that in which the follower wants to use a _minimum spanning tree_ of \(G\) (now considered as undirected). For this game, in [9], the authors proved the APX-hardness already when the number of possible edge costs is \(2\) and gave an \(O(\log n)\)-approximation algorithm. Better approximations are possible when the leader can also choose the positions of her edges [10]. All the above examples fall within the class of SNPGs handled by the general model proposed in [11], which encompasses all the cases where each follower aims at optimizing a polynomial-time network optimization problem in which the cost of the network is given by the sum of prices and costs of contained edges, namely  
\[f_{2}(p,H)=\sum_{e\in P\cap E(H)}p(e)+\sum_{e\in C\cap E(H)}c(e). \tag{1}\]  
Thus, in this model, we have that \(f_{1}\) coincides with \(f_{2}\) once this is restricted to the leader's edges. To this respect, the leader's and follower's maximization and minimization functions are therefore _symmetric_. The authors showed that all SNPGs in this class can be tightly approximated within \((1+\epsilon)(\mathcal{H}_{k}+\mathcal{H}_{|P|})\), for any \(\epsilon>0\), where \(k\) denotes the number of followers, while \(\mathcal{H}_{i}\) is the \(i\)-th harmonic number. In recent years, the framework of Stackelberg pricing games has been applied on top of several fundamental optimization problems [12; 13; 14; 15; 16; 17; 18].