Indexed on: 28 Feb '18Published on: 28 Feb '18Published in: arXiv - Computer Science - Computer Science and Game Theory
We study a nonatomic routing game on a parallel link network in which link owners set tolls for travel so as to maximize profit. A central authority is able to regulate this competition by means of a (uniform) price cap. The first question we want to answer is how such a cap should be designed in order to minimize the total congestion. We provide an algorithm that finds an optimal price cap for networks with affine latency functions. Second, we consider the performance of an optimal price cap. We show that for duopolies, the congestion costs at the optimal price cap are at most twice the congestion costs of the optimal flow, under the condition that an uncapped subgame perfect Nash equilibrium exists. However, in general such an equilibrium need not exist and this fact can be used to show that optimal price caps can induce arbitrarily inefficient flows.