  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > DETAIL:

Paper:

TR09-112 | 3rd November 2009 17:27

Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game TR09-112
Authors: Davide Bilò, Luciano Gualà, Guido Proietti
Publication: 7th November 2009 23:35
Consider a communication network represented by a directed graph $G=(V,E)$ 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 $\epsilon > 0$, unless $\p=\np$, the problem is not approximable within $n^{1/2-\epsilon}$, 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 $n^{1/3-\epsilon}$. 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.