Competitive location and pricing on a line with metric transportation costs

Consider a three-level non-capacitated location/pricing problem: a firm first decides which facilities to open, out of a finite set of candidate sites, and sets service prices with the aim of revenue maximization; then a second firm makes the same decisions after checking competing offers; finally, customers make individual decisions trying to minimize costs that include both purchase and transportation. A restricted two-level problem can be defined to model an optimal reaction of the second firm to known decision of the first. For non-metric costs, the two-level problem corresponds to Envy-free Pricing or to a special Network Pricing problem, and is APX-complete even if facilities can be opened at no fixed cost. Our focus is on the metric 1-dimensional case, a model where customers are distributed on a main communica- tion road and transportation cost is proportional to distance. We describe polynomial-time algorithms that solve two- and three-level problems with opening costs and single 1st level facility. Quite surprisingly, however, even the two-level problem with no opening costs becomes N P-hard when two 1st level facilities are considered.