Negative prices in network pricing games

Abstract

In a Stackelberg network pricing game a leader sets prices for a given subset of edges so as to maximize profit, after which one or multiple followers choose a shortest path. Our main result shows that the profit when allowing for negative prices can be a factor Theta(log(m . (k) over bar)) larger than the maximum profit with only positive prices, where m is the number of priceable edges and (k) over bar <= 2(m) the number of followers. In particular, this factor cannot be bounded for a single follower.