Stackelberg thresholds in network routing games or the value of altruism

Abstract

Noncooperative network routing games are a natural model of userstrying to selfishly route flow through a network in order to minimize their own delays. It is well known that the solution resulting from this selfish routing (called the Nash equilibrium) can have social cost strictly higher than the cost of the optimum solution. One way to improve the quality of the resulting solution is to centrally control a fraction of the flow. A natural problem for the network administrator then is to route the centrally controlled flow in such a way that the overall cost of the solution is minimized after the remaining fraction has routed itself selfishl.