On the stackelberg fuel pricing problem

We consider the Stackelberg fuel pricing problem in which a company has to decide the fuel selling price at each of its gas stations in order to maximize its revenue, assuming that the selling prices of the competitors and the customers' preferences are known in advance. We show that, even in the basic case in which the road network is modeled by an undirected planar graph and the competitors discriminate on two different selling prices only, the problem is APX-hard. On the positive side, we design a polynomial time algorithm for instances in which the number of gas stations owned by the company is constant, while, in the general case, we show that the single-price algorithm (which provides the best-known solutions for essentially all the Stackelberg pricing problems studied in the literature up to date) achieves an approximation ratio which is logarithmic in some parameters of the input instance. This result, in particular, is tight and holds for a much more general class of Stackelberg network pricing problems.