Speaker: Marc Schröder, RWTH Aachen
A Stackelberg network pricing game is a two-stage game, in which, in the first stage, a leader sets prices for a given subset of edges so as to maximize profit (all other edges have a fixed cost), and, in the second stage, one or multiple followers choose a shortest path from their source to their sink. Counterintuitively, the usage of negative prices by the leader may in fact increase his profit. We consider the following two main questions. First, for which network topologies can the leader increase profit by using negative prices? Second, how much extra profit can the leader obtain by setting negative prices? We show that only series-parallel graphs are immune to this paradox, and that the profit achievable with negative prices can be a factor Θ(logn) larger than the maximum profit with non-negative prices, where n is the number of nodes in the graph. We relate this result to allowing for bundling strategies. This is joint work with Andres Cristi.