The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions

Let M be a single s–t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [E. Koutsoupias, C. Papadimitriou, Worst-case equilibria, in: 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS, vol. 1563, 1999, pp. 404–413; T. Roughgarden, É. Tardos, How bad is selfish routing? in: 41st IEEE Annual Symposium of Foundations of Computer Science, FOCS, 2000, pp. 93–102]. A Leader can decrease the coordination ratio by assigning flow αr on M, and then all Followers assign selfishly the (1−α)r remaining flow. This is a Stackelberg Scheduling Instance (M,r,α),0≤α≤1. It was shown [T. Roughgarden, Stackelberg scheduling strategies, in: 33rd Annual Symposium on Theory of Computing, STOC, 2001, pp. 104–113] that it is weakly NP-hard to compute the optimal Leader’s strategy.For any such network M we efficiently compute the minimum portion βM of flow r>0 needed by a Leader to induce M’s optimum cost, as well as her optimal strategy. This shows that the optimal Leader’s strategy on instances (M,r,α≥βM) is in P.Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess’s Paradox graph, such that no strategy controlling αr flow can induce times the optimum cost. However, we show that our main result also applies to any s–t net G. We take care of the Braess’s graph explicitly, as a convincing example. Finally, we extend this result to k commodities.A conference version of this paper has appeared in [A. Kaporis, P. Spirakis, The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual ACM symposium on Parallelism in Algorithms and Architectures, SPAA, 2006, pp. 19–28]. Some preliminary results have also appeared as technical report in [A.C. Kaporis, E. Politopoulou, P.G. Spirakis, The price of optimum in stackelberg games, in: Electronic Colloquium on Computational Complexity, ECCC, (056), 2005].