  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 from their source to sink. We study the
counter-intuitive phenomenon that the use of negative prices by the leader may
in fact increase his profit. In doing so, we answer the following two
questions. First, how much more profit can the leader earn by setting negative
prices? Second, for which network topologies can the profit be increased by
using negative prices? Our main result shows that the profit with negative
prices can be a factor $\Theta(\log (m\cdot\bar k))$ larger than the maximum
profit with positive prices, where $m$ is the number of priceable edges in the
graph and $\bar k \leq 2^m$ the number of followers. In particular, this factor
cannot be bounded for the single follower case, and can even grow linearly in
$m$ if the number of followers is large. Our second result shows that
series-parallel graphs with a single follower and Stackelberg games with
matroid followers are immune to the negative price paradox.
