Tight bounds for worst-case equilibria

ABSTRACT

We study the problem of traffic routing in noncooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore, their behavior does not have to lead to optimal performance of the entire network. In this article we investigate the worst-case coordination ratio, which is a game-theoretic measure aiming to reflect the price of selfish routing.

Following a line of previous work, we focus on the most basic networks consisting of parallel links with linear latency functions. Our main result is that the worst-case coordination ratio on m parallel links of possibly different speeds is

Θ(log m/log log log m).

In fact, we are able to give an exact description of the worst-case coordination ratio, depending on the number of links and ratio of speed of the fastest link over the speed of the slowest link. For example, for the special case in which all m parallel links have the same speed, we can prove that the worst-case coordination ratio is Γ⁽⁻¹⁾ (m) + Θ(1), with Γ denoting the Gamma (factorial) function. Our bounds entirely resolve an open problem posed recently by Koutsoupias and Papadimitriou [1999].

REFERENCES

• 1: Czumaj, A., Krysta, P., and Vöcking B. 2002. Selfish traffic allocation for server farms. In Proceedings of 34th Annual ACM Symposium on Theory of Computing. 287--296.
• 2: Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. The structure and complexity of Nash equilibria for a selfish routing game. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Springer Verlag, Berlin. 123--134.
• 3: Gonnet, G. 1981. Expected length of the longest probe sequence in hash code searching. J. Assoc. Comput. Mach. 28, 2, 289--304.
• 4: Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 301 (Mar.), 13--30.
• 5: Koutsoupias, E., and Papadimitriou, C. H. 1999. Worst-Case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. Springer Verlag, Berlin. 404--413.
• 6: Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. Approximate equilibria and ball fusion. In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity.
• 7: Mavronicolas, M., and Spirakis, P. 2001. The price of selfish routing. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. 510--519.
• 8: Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, New York.
• 9: Nash, J. F., Jr. 1951. Non-Cooperative games. Ann. Math. 54, 2, 286--295.
• 10: Papadimitriou, C. H. 2001a. Algorithms, games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. 749--753.
• 11: Papadimitriou, C. H. 2001b. Game theory and mathematical economics: A theoretical computer scientist's introduction (tutorial). In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 4--8.
• 12: Papadimitriou, C. H., and Yannakakis, M. 1994. On complexity as bounded rationality. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing. 726--733.
• 13: Roughgarden, T. 2003. The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 2 (Sept.), 341--364.
• 14: Roughgarden, T., and Tardos, É. 2002. How bad is selfish routing? J. Assoc. Comput. Mach. 49, 2 (Mar.), 236--259.

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.0 General
          Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
Coordination ration, Nash equilibria, noncooperative networks, selfish strategies, traffic routing