nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

5. The Price of Anarchy for a Network of Queues in Heavy Traffic

verfasst von : Shaler Stidham

Erschienen in: Essays in Production, Project Planning and Scheduling

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The price of anarchy (POA) in a congestion network refers to the ratio of the individually optimal total cost to the socially optimal total cost. An extensive literature on this subject has focussed mostly on deriving upper bounds on the POA that are independent of the topology of the network and (to a lesser extent) the form of the cost functions at the facilities of the network. This paper considers congestion networks in which the cost functions at the facilities display qualitative characteristics found in the waiting-time function for queue with an infinite waiting room. For a network of parallel M/M/1 queues an explicit expression exists for the POA, which, unlike the bounds in the literature, remains finite in heavy traffic. We show that a similar explicit expression holds in heavy traffic for parallel GI/GI/1 queues and, in some cases, in more general networks as well.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Refined EM Method for Solving Linearly Constrained Global Optimization Problems

Nächstes Kapitel A Comparative Study of Procedures for the Multinomial Selection Problem

This abstract characterization of a network is sufficiently general to include both classical models of networks of queues and road traffic networks, as well as more recent models of communication networks. In queueing-network models (e.g., a Jackson network), each queue (service facility) is modeled as a node, with a directed arc from node j to node k if service at queue j may be followed immediately by service at queue k. In communication-network models it is more common (and more natural) to consider each transmission link as a service facility, with a queue of jobs (messages or packets) at the node (router/server) at the head of the link, waiting to be transmitted. In road traffic networks, both nodes (intersections) and links (road segments between intersections) are service facilities in the sense that they are potential sources of congestion and waiting.

Beckmann, M., McGuire, C., & Winsten, C. (1956). Studies in the economics of transportation. New Haven: Yale University Press.

Bertsekas, D. (1998).Network optimization: Continuous and discrete models. Nashua:Athena Scientific.

Chau, C., & Sim, K. (2003). The price of anarchy for nonatomic congestion games with symmetric cost maps and elastic demands. Operational Research Letters, 31, 327–334.

Correa, J., Schulz, A., & Stier-Moses, N. (2004a). Computational complexity, fairness, and the price of anarchy of the maximum latency problem. Integer Programming and Combinatorial Optimization (Vol. 3064, p. 59–73). Springer Berlin/Heidelberg, Lecture Notes in Computer Science.

Correa, J., Schulz, A. & Stier-Moses, N. (2004b). Selfish routing in capacitated networks. Mathematics of Operations Research, 29, 961–976.

Correa, J., Schulz A., & Stier-Moses, N. (2005). On the inefficiency of equilibria in congestion games. M. Junger & V. Kaibel (eds.), IPCO 2005, LNCS 3509, (p. 167–181). Berlin: Springer-Verlag.

Crabill, T., Gross D., & Magazine, M. (1977). A classified bibliography of research on optimal design and control of queues. Operations Research, 25, 219–232.

Dafermos S. (1980). Traffic equilibrium and variational inequalities. Trans- portation Science, 14, 42–54.

Dafermos, S., & Nagourney, A. (1984). On some traffic equilibrium theory paradoxes. Transportation Research, 18B, 101–110.

Dafermos, S., & Sparrow, F. (1969). The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, 73B, 91–118.

El-Taha, M. & Stidham, S. (1998). Sample-path analysis of queueing systems. Boston: Kluwer Academic Publishing.

Hassin, R. & Haviv, M. (2003). To queue or not to queue equilibrium behavior in queueing systems. Boston: Kluwer Academic Publishers.

Kelly, F. (1979). Reversibility and stochastic networks. Chichester: John Wiley.

Kitaev, M., & Rykov, V. (1995). Controlled queueing systems. Boca Raton: CRC Press.

Naor, P. (1969). On the regulation of queue size by levying tolls. Econometrica, 37, 15–24.

Perakis, G. (2004). The price of anarchy under nonlinear and asymmetric costs. Integer Programming and Combinatorial Optimization (Vol. 3064, p. 46–58). Springer Berlin/Heidelberg, Lecture Notes in Computer Science.

Roughgarden T. (2002). The price of anarchy is independent of the network topology. Proceedings of ACM Symposium on Theory of Computing (Vol. 34, p. 428–437).

Roughgarden, T. (2005). Selfish Routing and the Price of Anarchy. Cambridge: MIT Press.

Roughgarden, T. (2006). On the severity of Braesss paradox: Designing networks for selfish users is hard. Journal of Computer and System Science, 72, 922–953.

Roughgarden, T., & Tardos E. (2002). How bad is selfish routing? Journal of the Association of Computer Machinery, 49, 236–259.

Schulz, A., & Stier-Moses, N. (2003). On the performance of user equilibria in traffic networks. Proceeding of ACM-SIAM Symposium on Discrete Algorithms (Vol. 14, p. 86–87). Baltimore.

Serfozo, R. (1981). Optimal control of random walks, birth and death processes, and queues. Advances in Applied Probability, 13, 61–83.

Shanthikumar, G., & Xu, S. (1997). Asymptotically optimal routing and service rate allocation in a multi server queueing system. Operations Research, 45, 464–469.

Shanthikumar, G, & Xu, S. (2000). Strongly asymptotically optimal design and control of production and service systems. IIE Transactions, 32, 881–890.

Sobel, M. (1974). Optimal operation of queues. A. B. Clarke (ed.), Mathematical methods in queueing theory (Vol. 98, p. 145–162, Berlin: Springer-Verlag, Lecture Notes in Economics and Mathematical Systems.

Stidham, S. (1971). Stochastic design models for location and allocation of public service facilities: Part I. Technical Report, Department of Environmental Systems Engineering, College of Engineering, Cornell University.

Stidham, S. (1978). Socially and individually optimal control of arrivals to a GI/M/1 queue. Management Science, 24, 1598–1610.

Stidham, S. (1984). Optimal control of admission, routing, and service in queues and networks of queues: A tutorial review. Proceedings ARO Workshop: Analytic and Computational Issues in Logistics R and D (p. 330–377). George Washington University.

Stidham, S. (1985). Optimal control of admission to a queueing system. The IEEE Transactions on Automatic Control, 30, 705–713.

Stidham, S. (1988). Scheduling, routing, and ow control in stochastic networks. In W. Fleming, P. L. Lions (eds.), Stochastic Differential Systems, Stochastic Control Theory and Applications (Vol. IMA-10, p. 529–561). New York: Springer-Verlag.

Stidham, S. (2008). The price of anarchy for a single-class network of queues. Technical Report, Department of Statistics and Operations Research. University of North Carolina at Chapel Hill.

Stidham, S. (2009) Optimal design of queueing systems. Boca Raton, FL: CRC Press, Taylor and Francis Group (A Chapman & Hall Book).

Stidham, S., & Prabhu, N. (1974). Optimal control of queueing systems. In A. B. Clarke (ed.), Mathematical methods in queueing theory (Vol. 98, p. 263–294). Berlin:Springer-Verlag. Lecture Notes in Economics and Mathematical Systems.

Wardrop, J. (1952). Some theoretical aspects of road traffic research. Proceeding of the Institution of Civil Engineers, Part II, 1, 325–378.

Titel: The Price of Anarchy for a Network of Queues in Heavy Traffic
verfasst von: Shaler Stidham
Verlag: Springer US
Buch: Essays in Production, Project Planning and Scheduling
Print ISBN: 978-1-4614-9055-5

Electronic ISBN: 978-1-4614-9056-2

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-1-4614-9056-2_5