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 arepartitioned into two sets: a set C of edges with a fixednon-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">0, unless p=p, 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 px-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.