Negative prices in network pricing games

Operations Research Letters, vol. 50, pp. 99–106

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 Θ(log⁡(m⋅k¯)) larger than the maximum profit with only positive prices, where m is the number of priceable edges and k¯≤2m the number of followers. In particular, this factor cannot be bounded for a single follower.

Authors 2

1. Andrés Cristi

   University of Chile

   Affiliation as printed

   Department of Industrial Engineering, Universidad de Chile, Santiago, Chile

   University of Chile

2. Marc Schröder corresponding Aachen

   RWTH Aachen University · Maastricht University

   Affiliation as printed

   School of Business and Economics, Maastricht University, Maastricht, Netherlands

   RWTH Aachen University