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

ABSTRACT

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 [12, 26]. 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 [23] 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 needed by a Leader to induce M's optimum cost, as well as his optimal strategy.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<over>α 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.

REFERENCES

• 1: T. Basar and G. J. Olsder. Dynamic Noncooperative Game Theory. Academic Press, London and San Diego, 1995.
• 2: Ron Cocchi , Scott Shenker , Deborah Estrin , Lixia Zhang, Pricing in computer networks: motivation, formulation, and example, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.614-627, Dec. 1993 [doi>10.1109/90.266050]
• 3: A. Czumaj. Selfish routing on the Internet. In J. Leung, editor, Handbook of Scheduling. CRC Press, Boca Raton, FL, 2004.
• 4: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 5: S. C. Dafermos and F. T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, 73 B(2):91--118, 1969.
• 6: Pradeep Dubey, Inefficiency of Nash equilibria, Mathematics of Operations Research, v.11 n.1, p.1-8, Feb. 1986 [doi>10.1287/moor.11.1.1]
• 7: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 8: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 9: Y. A. Korilis , A. A. Lazar , A. Orda, The designer's perspective to noncooperative networks, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2)-Volume, p.562, April 02-06, 1995
• 10: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 11: Y. A. Korilis, A. A. Lazar, and A. Orda. Capacity allocation under noncooperative routing. IEEE Transactions on Automatic Control, 42:161--173, 1997.
• 12: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. (STACS '99) Lecture Notes in Computer Science, 1563:404--413, 1999.
• 13: V. S. Anil Kumar , Madhav V. Marathe, Improved Results for Stackelberg Scheduling Strategies, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.776-787, July 08-13, 2002
• 14: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 15: R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 16: N. Nisan. Algorithms for selfish agents: Mechanism design for distributed computation. In 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 1--15, Trier, Germany, 1999. Springer-Verlag. Lecture Notes in Computer Science, LNCS 1563.
• 17: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 18: M. Osborne and A. Rubinstein. A course in Game Theory. MIT Press.
• 19: G. Owen. Game Theory. Academic Press, Orlando, FL, third edition, 1995.
• 20: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 21: C. Papadimitriou, Game Theory and Mathematical Economics: A Theoratical Computer Scientist's Introduction, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.4, October 14-17, 2001
• 22: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 23: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 24: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 25: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 26: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 27: Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
• 28: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 29: H. von Stackelberg. Marktform und Gleichgewicht. Springer-Verlag, 1934.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics

Keywords:
coordination ratio, price of optimum, stackelberg