Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game

Consider a communication network represented by a directed graph G=(VE) of n nodes and m edges. Assume that edges in E are partitioned into two sets: a set C of edges with a fixed non-negative real cost, and a set P of edges whose \emph{price} should instead be set by a \emph{leader}. This is done with the final intent of \emph{maximizing} the payment she will receive for their use by a \emph{follower}, whose goal is to select for his communication purposes a \emph{minimum-cost} (w.r.t. to a given objective function) subnetwork of G. In this paper, we study the natural setting in which the follower computes a \emph{single-source shortest paths tree} of G, and then returns to the leader a payment equal to the \emph{sum} of the selected priceable edges. Thus, the problem can be modeled as a one-round two-player \emph{Stackelberg Network Pricing Game (SNPG)}, with the additional complication that the objective functions of the two players are \emph{asymmetric}. Indeed, the revenue provided to the leader by any of her selected edges is simply its price, while the cost of such an edge in the minimization function of the follower is given by its price multiplied by the number of paths (emanating from the source) it belongs to. As we will see, this asymmetry makes the problem much harder than other previously studied symmetric SNPGs. More precisely, we show that for any 0, unless \p=\np, the problem is not approximable within n12− , while if G is unweighted and the leader can only decide which of her edges enter in the solution, then the problem is not approximable within n13− . On the positive side, when edges in C happen to form the common \emph{unweighted star network} topology, then we show the problem becomes \apx-hard, and admits a 92-approximation algorithm. Furthermore, for general instances, we devise a \emph{strongly} polynomial-time O(n)-approximation algorithm, which favorably compares against the powerful \emph{single-price} algorithm.