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

• Published in: Theoretical computer science 2009-03, Vol.410 (8), p.745-755
• Main Authors: Kaporis, A.C., Spirakis, P.G.
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Computer systems performance. Reliability; Coordination ratio; Exact sciences and technology; Geometry; Information retrieval. Graph; Mathematics; Miscellaneous; Price of optimum; Sciences and techniques of general use; Software; Stackelberg; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2008.11.002

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 ≤ 1 α 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].