Stackelberg Routing in Atomic Network Games

We consider network games with atomic players, which indicates that some players control a positive amount of flow. Instead of studying Nash equilibria as previous work has done, we consider that players with considerable market power will make decisions before the others because they can predict the decisions of players without market power. This description fits the framework of Stackelberg games, where those with market power are leaders and the rest are price-taking followers. As Stackelberg equilibria are difficult to characterize, we prove bounds on the inefficiency of the solutions that arise when the leader uses a heuristic that approximate its optimal strategy.