IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v44y2010i4p524-536.html
   My bibliography  Save this article

Equilibrium Results for Dynamic Congestion Games

Author

Listed:
  • Frédéric Meunier

    (LVMT, ENPC, Université Paris-Est, Cité Descartes-Champs-sur-Marne, 77455 Marne-la-Vallée CEDEX 2, France)

  • Nicolas Wagner

    (LVMT, ENPC, Université Paris-Est, Cité Descartes-Champs-sur-Marne, 77455 Marne-la-Vallée CEDEX 2, France)

Abstract

Consider the following game. Given a network with a continuum of users at some origins, suppose users wish to reach specific destinations but they are not indifferent to the cost to reach them. They may have multiple possible routes but their choices modify the travel costs on the network. Hence, each user faces the following problem: Given a pattern of travel costs for the different possible routes that reach the destination, find a path of minimal cost. This kind of game belongs to the class of congestion games. In the traditional static approach, travel times are assumed constant during the period of the game.In this paper, we consider the so-called dynamic case where the time-varying nature of traffic conditions is explicitly taken into account. In transportation science, the question of whether there is an equilibrium and how to compute it for such a model is referred to as the dynamic user equilibrium problem.Until now, there was no general model for this problem. Our paper attempts to resolve this issue. We define a new class of games, dynamic congestion games, which capture this time-dependency aspect. Moreover, we prove that under some natural assumptions there is a Nash equilibrium. When we apply this result to the dynamic user equilibrium problem, we get most of the previous known results.

Suggested Citation

  • Frédéric Meunier & Nicolas Wagner, 2010. "Equilibrium Results for Dynamic Congestion Games," Transportation Science, INFORMS, vol. 44(4), pages 524-536, November.
    • Handle: RePEc:inm:ortrsc:v:44:y:2010:i:4:p:524-536
    DOI: 10.1287/trsc.1100.0329
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0329
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0329?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hart, Sergiu & Hildenbrand, Werner & Kohlberg, Elon, 1974. "On equilibrium allocations as distributions on the commodity space," Journal of Mathematical Economics, Elsevier, vol. 1(2), pages 159-166, August.
    2. Robin Lindsey, 2004. "Existence, Uniqueness, and Trip Cost Function Properties of User Equilibrium in the Bottleneck Model with Multiple User Classes," Transportation Science, INFORMS, vol. 38(3), pages 293-314, August.
    3. Igal Milchtaich, 2005. "Topological Conditions for Uniqueness of Equilibrium in Networks," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 225-244, February.
    4. Wu, J. H. & Chen, Y. & Florian, M., 1998. "The continuous dynamic network loading problem: a mathematical formulation and solution method," Transportation Research Part B: Methodological, Elsevier, vol. 32(3), pages 173-187, April.
    5. Terry L. Friesz & David Bernstein & Tony E. Smith & Roger L. Tobin & B. W. Wie, 1993. "A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem," Operations Research, INFORMS, vol. 41(1), pages 179-191, February.
    6. MERCHANT, Deepak K. & NEMHAUSER, George L., 1978. "A model and an algorithm for the dynamic traffic assignment problems," LIDAM Reprints CORE 346, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Daoli Zhu & Patrice Marcotte, 2000. "On the Existence of Solutions to the Dynamic User Equilibrium Problem," Transportation Science, INFORMS, vol. 34(4), pages 402-414, November.
    8. B. G. Heydecker & J. D. Addison, 2005. "Analysis of Dynamic Traffic Equilibrium with Departure Time Choice," Transportation Science, INFORMS, vol. 39(1), pages 39-57, February.
    9. Mounce, Richard, 2006. "Convergence in a continuous dynamic queueing model for traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 40(9), pages 779-791, November.
    10. Deepak K. Merchant & George L. Nemhauser, 1978. "A Model and an Algorithm for the Dynamic Traffic Assignment Problems," Transportation Science, INFORMS, vol. 12(3), pages 183-199, August.
    11. Y. W. Xu & J. H. Wu & M. Florian & P. Marcotte & D. L. Zhu, 1999. "Advances in the Continuous Dynamic Network Loading Problem," Transportation Science, INFORMS, vol. 33(4), pages 341-353, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Roberto Cominetti & José Correa & Omar Larré, 2015. "Dynamic Equilibria in Fluid Queueing Networks," Operations Research, INFORMS, vol. 63(1), pages 21-34, February.
    2. Han, Ke & Szeto, W.Y. & Friesz, Terry L., 2015. "Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance," Transportation Research Part B: Methodological, Elsevier, vol. 79(C), pages 16-49.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Luo, Shiaw-Shyan & Wang, Chung-Yung & Sung, Yi-Wei, 2018. "Time-dependent trip-chain link travel time estimation model with the first-in–first-out constraint," European Journal of Operational Research, Elsevier, vol. 267(2), pages 415-427.
    2. Friesz, Terry L. & Kim, Taeil & Kwon, Changhyun & Rigdon, Matthew A., 2011. "Approximate network loading and dual-time-scale dynamic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 176-207, January.
    3. Ban, Xuegang (Jeff) & Pang, Jong-Shi & Liu, Henry X. & Ma, Rui, 2012. "Modeling and solving continuous-time instantaneous dynamic user equilibria: A differential complementarity systems approach," Transportation Research Part B: Methodological, Elsevier, vol. 46(3), pages 389-408.
    4. Celikoglu, Hilmi Berk, 2013. "Reconstructing freeway travel times with a simplified network flow model alternating the adopted fundamental diagram," European Journal of Operational Research, Elsevier, vol. 228(2), pages 457-466.
    5. Malachy Carey & Y. E. Ge, 2005. "Alternative Conditions for a Well-Behaved Travel Time Model," Transportation Science, INFORMS, vol. 39(3), pages 417-428, August.
    6. Berliant, Marcus, 2017. "Commuting and internet traffic congestion," MPRA Paper 77378, University Library of Munich, Germany.
    7. André de Palma & Mogens Fosgerau, 2011. "Dynamic Traffic Modeling," Chapters, in: André de Palma & Robin Lindsey & Emile Quinet & Roger Vickerman (ed.), A Handbook of Transport Economics, chapter 9, Edward Elgar Publishing.
    8. Liu, Yang & Li, Yuanyuan & Hu, Lu, 2018. "Departure time and route choices in bottleneck equilibrium under risk and ambiguity," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 774-793.
    9. Friesz, Terry L. & Han, Ke & Neto, Pedro A. & Meimand, Amir & Yao, Tao, 2013. "Dynamic user equilibrium based on a hydrodynamic model," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 102-126.
    10. Ban, Xuegang (Jeff) & Pang, Jong-Shi & Liu, Henry X. & Ma, Rui, 2012. "Continuous-time point-queue models in dynamic network loading," Transportation Research Part B: Methodological, Elsevier, vol. 46(3), pages 360-380.
    11. Lu, Gongyuan & Nie, Yu(Marco) & Liu, Xiaobo & Li, Denghui, 2019. "Trajectory-based traffic management inside an autonomous vehicle zone," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 76-98.
    12. Malachy Carey & Y. E. Ge & Mark McCartney, 2003. "A Whole-Link Travel-Time Model with Desirable Properties," Transportation Science, INFORMS, vol. 37(1), pages 83-96, February.
    13. B. G. Heydecker & J. D. Addison, 2005. "Analysis of Dynamic Traffic Equilibrium with Departure Time Choice," Transportation Science, INFORMS, vol. 39(1), pages 39-57, February.
    14. Daoli Zhu & Patrice Marcotte, 2000. "On the Existence of Solutions to the Dynamic User Equilibrium Problem," Transportation Science, INFORMS, vol. 34(4), pages 402-414, November.
    15. Jin, Wen-Long, 2015. "On the existence of stationary states in general road networks," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 917-929.
    16. Nie, Xiaojian & Zhang, H.M., 2005. "Delay-function-based link models: their properties and computational issues," Transportation Research Part B: Methodological, Elsevier, vol. 39(8), pages 729-751, September.
    17. Ke Han & Gabriel Eve & Terry L. Friesz, 2019. "Computing Dynamic User Equilibria on Large-Scale Networks with Software Implementation," Networks and Spatial Economics, Springer, vol. 19(3), pages 869-902, September.
    18. Carey, Malachy & Ge, Y. E., 2003. "Comparing whole-link travel time models," Transportation Research Part B: Methodological, Elsevier, vol. 37(10), pages 905-926, December.
    19. Zhong, R.X. & Sumalee, A. & Friesz, T.L. & Lam, William H.K., 2011. "Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1035-1061, August.
    20. Malachy Carey & Y. E. Ge, 2005. "Convergence of a Discretised Travel-Time Model," Transportation Science, INFORMS, vol. 39(1), pages 25-38, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:44:y:2010:i:4:p:524-536. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.