Optimally computing all solutions of Stackelberg with parametric prices and of general monotonous gain functions on a tree

AbstractThis paper considers Hotelling's duopoly model on a tree with parametric service prices. Two competitors, the leader and the follower, sequentially place a server in a network. Users decide for a server according to the sum of distance and server price. The goal of the competitors is to maximize their profit induced by the total demand served. García and Pelegrín (2003) develop an algorithm with O(n3logn) running time to compute the Stackelberg set, i.e., the set of all optimal leader positions.In this paper we first provide an algorithm to compute the Stackelberg set and the relaxed Simpson set with worst case running time O(n). Second we suggest an algorithm to compute the optimal set for general monotonous gain functions. Its running time is O(nlogn) and we prove that this bound is tight even for computing the security set