Large the price of routing unsplittable flow

ABSTRACT

The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. The unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.In this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. We show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. These results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. We also show that for polynomials of degree d edge latency functions the price of anarchy is d^δ(d). Our results hold also for mixed strategies.Previous results of Roughgarden and Tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). Note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.

REFERENCES

• 1: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.383, October 23-25, 1995
• 2: B. Awerbuch, Y. Azar, Y. Richter, and D. Tsur. Tradeoffs in worst-case equilibria. In Proceedings of 1st WAOA, pages 41--52, 2003.
• 3: M. Beckmann, C.B. McGuire, and C.B. Winsten. Studies in Economics of Transportation. Yale University Press, 1956.
• 4: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 5: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Proceedings of the 4th ACM conference on Electronic commerce, p.98-107, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779941]
• 6: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, Pricing network edges for heterogeneous selfish users, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780618]
• 7: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 8: 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
• 9: 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]
• 10: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 11: D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplittable flows. In International Colloquium on Automata, Languages and Programming - ICALP '04.
• 12: M. Gairing, T. Lücking, M. Mavronicolas, and B. Monien. The price of anarchy for polynomial social cost. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pages 574--585, 2004.
• 13: M. Gairing, T. Lücking, M.Mavronicolas, B. Monien, and M. Rode. Nash equilibria in discrete routing games with convex latency functions. In Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), pages 645--657, 2004.
• 14: E. Koutsoupias and C.H. Papadimitriou. Worst-case equilibria. In Proc. 16th Symp. on Theoretical Aspects of Comp. Science, pages 404--413, 1999.
• 15: T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. In Proc. of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), pages 547--558, 2004.
• 16: 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]
• 17: J. F. Nash. Equilibrium points in n-person games. In Proceedings of National Academy of Sciences, volume 36, pages 48--49, 1950.
• 18: G. Owen. Game Theory. Academic Press, third edition, 1995.
• 19: 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]
• 20: R. W. Rosenthal. A class of games possesing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 21: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 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, 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]
• 24: 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
• 25: Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007941]
• 26: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Pt. II, volume 1, pages 325--378, 1952.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
game theory, nash equilibria, selfish routing, unsplittable flow