Traffic congestion pricing via network congestion game approach

Jing Zhang; Jianquan Lu; Jinde Cao; Wei Huang; Jianhua Guo; Yun Wei

doi:10.3934/dcdss.2020378

Article Contents

2021, Volume 14, Issue 4: 1553-1567. Doi: 10.3934/dcdss.2020378

This issue Previous Article Fully distributed consensus for higher-order nonlinear multi-agent systems with unmatched disturbances Next Article Fault-tolerant anti-synchronization control for chaotic switched neural networks with time delay and reaction diffusion

Traffic congestion pricing via network congestion game approach

1.
School of Mathematics, Southeast University, Jiangsu Provincial Key Laboratory of Networked Collective Intelligence, Nanjing 210096, China
2.
Jiangsu Provincial Key Laboratory of Networked Collective Intelligence, School of Mathematics, Southeast University, Nanjing 210096, China
3.
Intelligent Transportation System Research Center, Southeast University, Nanjing 210096, China
4.
Beijing Urban Construction Design and Development Group Co., Ltd, Beijing 100000, China

^* Corresponding author: Jianquan Lu
^* Corresponding author: Jianquan Lu

Received: January 2020

Revised: March 2020

Early access: May 2020

Published: April 2021

This work was supported by the National Natural Science Foundation of China under Grant No. 61973078, the Natural Science Foundation of Jiangsu Province of China under Grant no. BK20170019, "333 Engineering" Foundation of Jiangsu Province of China under Grant BRA2019260, and Jiangsu Provincial Key Laboratory of Networked Collective Intelligence under Grant No. BM2017002

Abstract Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

This paper investigates the optimization of traffic congestion systems via network congestion game approach. Firstly, using the semi-tensor product(STP) of matrices, the matrix expression of network congestion game is obtained. Secondly, a necessary and sufficient condition is proposed to guarantee that the traffic systems can be transformed into network congestion game with given performance criterion as its weighted potential function. Then an algorithm is provided to design the traffic congestion price in the case that conversion can be established. Thirdly, by designing proper learning rule, the optimization of traffic systems can be achieved when individuals optimize their own utility function. Moreover, two special cases which make our results more accord with reality and rich. Finally, an example is exploited to demonstrate the effectiveness of our obtained results.

Keywords:

Mathematics Subject Classification: Primary: 91A14, 91A80.

Citation:

Full Text(HTML)

Figure 1. The approach of network congestion game

Download: Full-size image PowerPoint slide

Figure 2. The traffic network graph

Download: Full-size image PowerPoint slide

Table 1. system objective function $ P(a) $

a 111 112 121 122 211 212 221 222

$ P(a) $ 63 70 72 71 72 71 72 62

| Show Table

DownLoad: CSV

Table 2. Utility matrix of network congestion game

u\s 111 112 121 122 211 212 221 222

$ u_1 $ 8 18 20 26 26 20 20 8

$ u_2 $ 8 18 26 20 20 26 20 8

$ u_3 $ 41 48 46 45 46 45 49 40

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	O. Candogan, A. Ozdaglar and P. A. Parrilo, Dynamics in near potential games, Games and Economic Behavior, 82 (2013), 66-90. doi: 10.1016/j.geb.2013.07.001.
[2]	D. Cheng, H. Qi and Y. Zhao, An Introduction to Semi-Tensor Product of Matrices and Its Applications Networks, World Scientific Singapore, 2012.
[3]	D. Cheng, F. He, H. Qi and T. Xu, Modeling, analysis and control of networked evolutionary games, IEEE Transactions on Automatic Control, 60 (2015), 2402-2415. doi: 10.1109/TAC.2015.2404471.
[4]	D. Cheng, H. Qi and Z. Li, Analysis and control of Boolean Networks - A Semi-tensor Product Approach, London: Springer, 2011.
[5]	D. Cheng, On finite potential games, Automatic, 50) (2014), 1793-1801. doi: 10.1016/j.automatica.2014.05.005.
[6]	X. Ding, H. Li and Q. Yang, Stochastic stability and stabilization of n-person random evolutionary Boolean games, Applied Mathematics and Computation, 306 (2017), 1-12. doi: 10.1016/j.amc.2017.02.020.
[7]	P. Dubey, Inefficiency of nash equilibria, Mathematics of Operations Research, 11 (1986), 1-8. doi: 10.1287/moor.11.1.1.
[8]	J. Eliasson, L. Hultkrantz, L. Nerhagen and L. S. Rosqvist, The stockholm congestion-charging trial 2006: Overview of effects, Transportation Research Part A: Policy and Practice, 43 (2009), 240-250. doi: 10.1016/j.tra.2008.09.007.
[9]	J. Fuglestvedt, T. Berntsen, G. Myhre, K. Rypdal and R. B. Skeie, Climate forcing from the transport sectors, Proceedings of the National Academy of Sciences of the United States of America, 105 (2008), 454-458. doi: 10.1073/pnas.0702958104.
[10]	R. Gopalakrishnan, J. R. Marden and A. Wierman, An architectural view of game theoretic control, ACM Sigmetrics Performance Evaluation Review, 38 (2011), 31.
[11]	Y. Hao, S. Pan, Y. Qiao and D. Cheng, Cooperative control via congestion game approach, IEEE Transactions on Automatic Control, 63 (2018), 4361-4366. doi: 10.1109/TAC.2018.2824978.
[12]	C. Huang, J. Lu, G. Zhai, J. Cao, G. Lu and M. Perc, Stability and stabilization in probability of probabilistic boolean networks, IEEE Transactions on Neural Networks and Learning Systems, (2020), 1–11. doi: 10.1109/TNNLS.2020.2978345.
[13]	K. Hymel, Does traffic congestion reduce employment growth?, Journal of Urban Economics, 65 (2009), 127-135. doi: 10.1016/j.jue.2008.11.002.
[14]	T. Liu, J. Wang and D. Cheng, Game theoretic control of multi-agent systems, SIAM J. Control Optimization, 57 (2019), 1691-1709. doi: 10.1137/18M1177615.
[15]	C. Li, F. He, H. Qi and D. Cheng, Potential games design using local information, 2018 IEEE Conference on Decision and Control (CDC), 2018, arXiv: 1807.05779v1. doi: 10.1109/CDC.2018.8619561.
[16]	S. Le, Y. Wu and X. Sun, Congestion games with player-specific utility functions and its application to NFV networks, IEEE Transactions on Automation Science and Engineering, 16 (2019), 1870-1881. doi: 10.1109/TASE.2019.2899504.
[17]	B. Li, Y. Liu, K.I. Kou and L. Yu, Event-triggered control for the disturbance decoupling problem of Boolean control networks, IEEE Transactions on Cybernetics, 48 (2018), 2764-2769. doi: 10.1109/TCYB.2017.2746102.
[18]	H. Li, X. Ding, A. Alsaedi and F. E. Alsaadi, Stochastic set stabilization of n-person random evolutionary Boolean games and its applications, IET Control Theory Application, 11 (2017), 2152-2160. doi: 10.1049/iet-cta.2017.0047.
[19]	L. Lin, J. Cao and L. Rutkowski, Robust event-triggered control invariance of probabilistic Boolean control networks, IEEE Transactions on Neural Networks and Learning Systems, 31 (2020), 1060-1065. doi: 10.1109/TNNLS.2019.2917753.
[20]	J. Lu, L. Sun, Y. Liu, D. W. C. Ho and J. Cao, Stabilization of Boolean control networks under aperiodic sampled-data control, SIAM Journal on Control and Optimization, 56 (2018), 4385-4404.
[21]	J. Lu, M. Li, T. Huang, Y. Liu and J. Cao, The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices, Automatica, 96 (2018), 393-397. doi: 10.1016/j.automatica.2018.07.011.
[22]	S. Le, Y. Wu and X. Sun, A Generalization of weighted congestion game and its nash equilibrium seeking, Proceeding of the 37th Chinese Control Conference, 2018. doi: 10.23919/ChiCC.2018.8483432.
[23]	I. Milchtaich, Representation of finite games as network congestion games, Int J Game Theory, 42 (2013), 1085-1096. doi: 10.1007/s00182-012-0363-5.
[24]	D. Monderer and L. S. Shapley, Potential games, Games and Economic behavior, 14 (1996), 124-143. doi: 10.1006/game.1996.0044.
[25]	H. Qi, Y. Wang, T. Liu and D. Cheng, Vector space structure of finite evolutionary games and its application to strategy profile convergence, Journal of Systems Science & Complexity, 29 (2016), 602-628. doi: 10.1007/s11424-016-4192-7.
[26]	R. W. Rosenthal, A class of games possessing pure-strategy nash equilibria, International Journal of Game Theory, 2 (1973), 65-67. doi: 10.1007/BF01737559.
[27]	R. W. Rosenthal, The network equilibrium problem in integers, Networks, 3 (1973), 53-59. doi: 10.1002/net.3230030104.
[28]	L. Wang, M. Fang, Z. Wu and J. Lu, Necessary and sufficient condition on pinning stabilization for stochastic Boolean networks, IEEE Transactions on Cybernetics, 2019, 1–10. doi: 10.1109/TCYB.2019.2931051.
[29]	Y. Wu and T. Shen, Policy iteration algorithm for optimal control of stochastic logical dynamical systems, IEEE Transactions on Neural Networks and Learning Systems, 29 (2018), 2031-2036. doi: 10.1109/TNNLS.2017.2661863.
[30]	M. Xu, Y. Liu, J. Lou, Z. Wu and J. Zhong, Set stabilization of probabilistic Boolean control networks: A sampled-data control approach, IEEE Transactions on cybernetics, 2019, 1–8. doi: 10.1109/TCYB.2019.2940654.
[31]	M. B. Yildirim and D. W. Hearn, A first best toll pricing framework for variable demand traffic assignment problems, Transportation Research Part B, 39 (2005), 659-678. doi: 10.1016/j.trb.2004.08.001.
[32]	H. Yang and X. Wang, Managing network mobility with tradable credits, Transportation Research Part B, 45 (2011), 580-594. doi: 10.1016/j.trb.2010.10.002.
[33]	H. Yang and X. Zhang, Multi-class network toll design problem with social and spatial equity constraints, Journal of Transportation Engineering, 128 (2002), 420-428.
[34]	H. Yang and X. Zhang, Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors, Transportation Research Part B, 42 (2010), 99-112.
[35]	X. Zhang, H. Yang and H. Huang, Multi-class multicriteria mixed equilibrium on networks and uniform link tolls for system optimum, European Journal of Operational Research, 189 (2008), 146-158. doi: 10.1016/j.ejor.2007.05.004.
[36]	J. Zhong, B. Li, Y. Liu and W. Gui, Output feedback stabilizer design of Boolean networks based on network structure, Frontiers of Information Technology Electronic Engineering, 21 (2020), 247-259. doi: 10.1631/FITEE.1900229.
[37]	J. Zhong, D. W. C. Ho and J. Lu, Pinning controllers for activation output tracking of Boolean network under one-bit perturbation, IEEE Transactions on Cybernetics, 49 (2019), 3398-3408. doi: 10.1109/TCYB.2018.2842819.
[38]	S. Zhu, J. Lu and Y. Liu, Asymptotical stability of probabilistic Boolean networks with state delays, IEEE Transactions on Automatic Control, 65 (2020), 1779-1784. doi: 10.1109/TAC.2019.2934532.
[39]	S. Zhu, J. Lu, Y. Liu, T. Huang and J. Kurths, Output tracking of probabilistic Boolean networks by output feedback control, Information Sciences, 483 (2019), 96-105. doi: 10.1016/j.ins.2018.12.087.