Computational Aspects of Multimarket Price Wars

We consider the complexity of decision making with regards to predatory pricing in multimarket oligopoly models. Specifically, we present multimarket extensions of the classical single-market models of Bertrand, Cournot and Stackelberg, and introduce the War Chest Minimization Problem. This is the natural problem of deciding whether a firm has a sufficiently large war chest to win a price war. On the negative side we show that, even with complete information, it is hard to obtain any multiplicative approximation guarantee for this problem. Moreover, these hardness results hold even in the simple case of linear demand, price, and cost functions. On the other hand, we give algorithms with arbitrarily small additive approximation guarantees for the Bertrand and Stackelberg multimarket models with linear demand, price, and cost functions. Furthermore, in the absence of fixed costs, this problem is solvable in polynomial time in all our models.