Abstract
This chapter presents a game theoretic framework for studying Stackelberg routing games on parallel transportation networks. A new class of latency functions is introduced to model congestion due to the formation of physical queues, inspired from the fundamental diagram of traffic. For this new class, some results from the classical congestion games literature (in which latency is assumed to be a nondecreasing function of the flow) do not hold. A characterization of Nash equilibria is given, and it is shown, in particular, that there may exist multiple equilibria that have different total costs. A simple polynomial-time algorithm is provided, for computing the best Nash equilibrium, i.e., the one which achieves minimal total cost. In the Stackelberg routing game, a central authority (leader) is assumed to have control over a fraction of the flow on the network (compliant flow), and the remaining flow responds selfishly. The leader seeks to route the compliant flow in order to minimize the total cost. A simple Stackelberg strategy, the non-compliant first (NCF) strategy, is introduced, which can be computed in polynomial time, and it is shown to be optimal for this new class of latency on parallel networks. This work is applied to modeling and simulating congestion mitigation on transportation networks, in which a coordinator (traffic management agency) can choose to route a fraction of compliant drivers, while the rest of the drivers choose their routes selfishly.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The latency in congestion ℓn(⋅, 1) is defined on the open interval \((0, x^{\max }_n)\). In particular, if xn = 0 or \(x_n = x^{\max }_n\) then the link is always considered to be in free-flow. When the link is empty (xn = 0), it is naturally in free-flow. When it is at maximum capacity (\(x_n = x^{\max }_n\)) it is in fact on the boundary of the free-flow and congestion regions, and we say by convention that the link is in free-flow.
- 2.
We note that a feasible flow assignment s of compliant flow may fail to induce a Nash equilibrium (t, m) and therefore is not considered to be a valid Stackelberg strategy.
- 3.
- 4.
Price of anarchy is defined as the ratio between the costs of the worst Nash equilibrium and the social optimum. For the case of nondecreasing latency functions, the price of anarchy and the price of stability coincide since all Nash equilibria have the same cost by the essential uniqueness property.
References
Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2004) The price of stability for network design with fair cost allocation. In: 45th annual IEEE symposium on foundations of computer science, Berkeley, pp 295–304
Aswani A, Tomlin C (2011) Game-theoretic routing of GPS-assisted vehicles for energy efficiency. In: American control conference (ACC). IEEE, San Francisco, pp 3375–3380
Babaioff M, Kleinberg R, Papadimitriou CH (2009) Congestion games with malicious players. Games Econ Behav 67(1):22–35
Beckmann M, McGuire CB, Winsten CB (1956) Studies in the economics of transportation. Yale University Press, New Haven
Benaïm M (2015) On gradient like properties of population games, learning models and self reinforced processes. Springer, Cham, pp 117–152
Blackwell D (1956) An analog of the minimax theorem for vector payoffs. Pac J Math 6(1):1–8
Blum A, Even-Dar E, Ligett K (2006) Routing without regret: on convergence to Nash equilibria of regret-minimizing algorithms in routing games. In: Proceedings of the twenty-fifth annual ACM symposium on principles of distributed computing (PODC’06). ACM, New York, pp 45–52
Blume LE (1993) The statistical mechanics of strategic interaction. Games Econ Behav 5(3): 387–424
Boulogne T, Altman E, Kameda H, Pourtallier O (2001) Mixed equilibrium for multiclass routing games. IEEE Trans Autom Control 47:58–74
Caltrans (2010) US 101 South, corridor system management plan. http://www.dot.ca.gov/hq/tpp/offices/ocp/pp_files/new_ppe/corridor_planning_csmp/CSMP_outreach/US-101-south/2_US-101_south_CSMP_Exec_Summ_final_22511.pdf
Cesa-Bianchi N, Lugosi G (2006) Prediction, learning, and games. Cambridge University Press, Cambridge
Dafermos S (1980) Traffic equilibrium and variational inequalities. Transp Sci 14(1):42–54
Dafermos SC, Sparrow FT (1969) The traffic assignment problem for a general network. J Res Natl Bur Stand 73B(2):91–118
Daganzo CF (1994) The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res B Methodol 28(4):269–287
Daganzo CF (1995) The cell transmission model, part II: network traffic. Transp Res B Methodol 29(2):79–93
Drighès B, Krichene W, Bayen A (2014) Stability of Nash equilibria in the congestion game under replicator dynamics. In: 53rd IEEE conference on decision and control (CDC), Los Angeles, pp 1923–1929
Evans CL (1998) Partial differential equations. Graduate studies in mathematics. American Mathematical Society, Providence
Farokhi F, Johansson HK (2015) A piecewise-constant congestion taxing policy for repeated routing games. Transp Res B Methodol 78:123–143
Fischer S, Vöcking B (2004) On the evolution of selfish routing. In: Algorithms–ESA 2004. Springer, Berlin, pp 323–334
Fischer S, Räcke H, Vöcking B (2010) Fast convergence to Wardrop equilibria by adaptive sampling methods. SIAM J Comput 39(8):3700–3735
Fox MJ, Shamma JS (2013) Population games, stable games, and passivity. Games 4(4):561–583
Friesz TL, Mookherjee R (2006) Solving the dynamic network user equilibrium problem with state-dependent time shifts. Transp Res B Methodol 40(3):207–229
Greenshields BD (1935) A study of traffic capacity. Highw Res Board Proc 14:448–477
Hannan J (1957) Approximation to Bayes risk in repeated plays. Contrib Theory Games 3:97–139
Hofbauer J, Sandholm WH (2009) Stable games and their dynamics. J Econ Theory 144(4):1665–1693.e4
Kleinberg R, Piliouras G, Tardos E (2009) Multiplicative updates outperform generic no-regret learning in congestion games. In: Proceedings of the 41st annual ACM symposium on theory of computing, Bethesda, pp 533–542. ACM
Korilis YA, Lazar AA, Orda A (1997a) Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans Netw 5:161–173
Korilis YA, Lazar AA, Orda A (1997b) Capacity allocation under noncooperative routing. IEEE Trans Autom Control 42:309–325
Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: Proceedings of the 16th annual conference on theoretical aspects of computer science. Springer, Heidelberg, pp 404–413
Krichene S, Krichene W, Dong R, Bayen A (2015a) Convergence of heterogeneous distributed learning in stochastic routing games. In: 53rd annual allerton conference on communication, control and computing, Monticello
Krichene W, Drighès B, Bayen A (2015b) Online learning of Nash equilibria in congestion games. SIAM J Control Optim (SICON) 53(2):1056–1081
Krichene W, Castillo MS, Bayen A (2016) On social optimal routing under selfish learning. IEEE Trans Control Netw Syst PP(99):1–1
Lam K, Krichene W, Bayen A (2016) On learning how players learn: estimation of learning dynamics in the routing game. In: 7th international conference on cyber-physical systems (ICCPS), Vienna
Lebacque JP (1996) The Godunov scheme and what it means for first order traffic flow models. In: International symposium on transportation and traffic theory, Lyon, pp 647–677
LeVeque RJ (2007) Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems. Classics in applied mathematics. Society for Industrial and Applied Mathematics, Philadelphia
Lighthill MJ, Whitham GB (1955) On kinematic waves. II. A theory of traffic flow on long crowded roads. Proc R Soc Lond A Math Phys Sci 229(1178):317
Lo HK, Szeto WY (2002) A cell-based variational inequality formulation of the dynamic user optimal assignment problem. Transp Res B Methodol 36(5):421–443
Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14(1):124–143
Ozdaglar A, Srikant R (2007) Incentives and pricing in communication networks. In: Nisan N, Roughgarden T, Tardos E, Vazirani V (eds) Algorithmic game theory. Cambridge University Press, Cambridge
Papageorgiou M, Blosseville JM, Hadj-Salem H (1989) Macroscopic modelling of traffic flow on the Boulevard Périphérique in Paris. Transp Res B Methodol 23(1):29–47
Papageorgiou M, Blosseville J, Hadj-Salem H (1990) Modelling and real-time control of traffic flow on the southern part of boulevard peripherique in paris: part I: modelling. Transp Res A Gen 24(5):345–359
Richards PI (1956) Shock waves on the highway. Oper Res 4(1):42–51
Roughgarden T (2001) Stackelberg scheduling strategies. In: Proceedings of the thirty-third annual ACM symposium on theory of computing, Heraklion, pp 104–113. ACM
Roughgarden T, Tardos E (2002) How bad is selfish routing? J ACM (JACM) 49(2):236–259
Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ Behav 47(2):389–403
Sandholm WH (2001) Potential games with continuous player sets. J Econ Theory 97(1):81–108
Sandholm WH (2010) Population games and evolutionary dynamics. MIT Press, Cambridge
Schmeidler D (1973) Equilibrium points of nonatomic games. J Stat Phys 7(4):295–300
Shamma JS (2015) Learning in games. Springer, London, pp 620–628
Swamy C (2007) The effectiveness of Stackelberg strategies and tolls for network congestion games. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms (SODA’01), New Orleans. Society for Industrial and Applied Mathematics, Philadelphia, pp 1133–1142
Thai J, Hariss R, Bayen A (2015) A multi-convex approach to latency inference and control in traffic equilibria from sparse data. In: American control conference (ACC), Chicago, pp 689–695
Wang Y, Messmer A, Papageorgiou M (2001) Freeway network simulation and dynamic traffic assignment with METANET tools. Transp Res Rec J Transp Res Board 1776(-1):178–188
Wardrop JG (1952) Some theoretical aspects of road traffic research. In: ICE proceedings: engineering divisions, vol 1, pp 325–362
Weibull JW (1997) Evolutionary game theory. MIT Press, Cambridge
Work DB, Blandin S, Tossavainen OP, Piccoli B, Bayen AM (2010) A traffic model for velocity data assimilation. Appl Math Res eXpress 2010(1):1
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this entry
Cite this entry
Krichene, W., Reilly, J.D., Amin, S., Bayen, A.M. (2018). Stackelberg Routing on Parallel Transportation Networks. In: Başar, T., Zaccour, G. (eds) Handbook of Dynamic Game Theory. Springer, Cham. https://doi.org/10.1007/978-3-319-44374-4_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-44374-4_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44373-7
Online ISBN: 978-3-319-44374-4
eBook Packages: Mathematics and StatisticsReference Module Computer Science and Engineering