A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 1 Issue 1
Jan.  2014

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 19.2, Top 1 (SCI Q1)
    CiteScore: 28.2, Top 1% (Q1)
    Google Scholar h5-index: 95， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2014  >  1(1): 31-39
Nan Xiao, Xuehe Wang, Lihua Xie, Tichakorn Wongpiromsarn, Emilio Frazzoli and Daniela Rus, "Road Pricing Design Based on Game Theory and Multi-agent Consensus," IEEE/CAA J. of Autom. Sinica, vol. 1, no. 1, pp. 31-39, 2014.
Citation: Nan Xiao, Xuehe Wang, Lihua Xie, Tichakorn Wongpiromsarn, Emilio Frazzoli and Daniela Rus, "Road Pricing Design Based on Game Theory and Multi-agent Consensus," IEEE/CAA J. of Autom. Sinica, vol. 1, no. 1, pp. 31-39, 2014.
shu

Road Pricing Design Based on Game Theory and Multi-agent Consensus

  • 1. Singapore-MIT Alliance for Research and Technology Centre, Singapore 138602, Singapore;

  • 2. EXQUISITUS, Centre for ECity, School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798, Singapore;

  • 3. Ministry of Science and Technology, Bangkok 10400, Thailand;

  • 4. Massachusetts Institute of Technology, Cambridge MA 02139, USA

Funds:

This work was supported by the National Research Foundation Singapore through the Singapore-MIT Alliance for Research and Technology's Future Urban Mobility IRG Research Programme.

    Abstract
  • Consensus theory and noncooperative game theory respectively deal with cooperative and noncooperative interactions among multiple players/agents. They provide a natural framework for road pricing design, since each motorist may myopically optimize his or her own utility as a function of road price and collectively communicate with his or her friends and neighbors on traffic situation at the same time. This paper considers the road pricing design by using game theory and consensus theory. For the case where a system supervisor broadcasts information on the overall system to each agent, we present a variant of standard fictitious play called average strategy fictitious play (ASFP) for large-scale repeated congestion games. Only a weighted running average of all other players' actions is assumed to be available to each player. The ASFP reduces the burden of both information gathering and information processing for each player. Compared to the joint strategy fictitious play (JSFP) studied in the literature, the updating process of utility functions for each player is avoided. We prove that there exists at least one pure strategy Nash equilibrium for the congestion game under investigation, and the players' actions generated by the ASFP with inertia (players' reluctance to change their previous actions) converge to a Nash equilibrium almost surely. For the case without broadcasting, a consensus protocol is introduced for individual agents to estimate the percentage of players choosing each resource, and the convergence property of players' action profile is still ensured. The results are applied to road pricing design to achieve socially local optimal trip timing. Simulation results are provided based on the real traffic data for the Singapore case study.

     

    • FullText(HTML)
  • loading
    • References(32)
  • [1]
    Deakin E, Harvey G, Pozdena R, Yarema G. Transportation Pricing Strategies for California:An Assessment of Congestion, Emissions, Energy, and Equity Impacts, Technical Report, UCTC, No.434, Transportation Center, University of California, USA, 1996
    [2]
    Menon A. ERP in Singapore:a perspective one year on. Traffic Engineering and Control, 2000, 41(2):40-45
    [3]
    Olszewski P, Xie L T. Modelling the effects of road pricing on traffic in Singapore. Transportation Research Part A:Policy and Practice, 2005, 39(7-9):755-772
    [4]
    Tsekeris T, Voβ S. Design and evaluation of road pricing:state-of-the-art and methodological advances. Netnomics, 2009, 10(1):5-52
    [5]
    Button K J, Verhoef E T. Road Pricing, Traffic Congestion and the Environment:Issues of Efficiency and Social Feasibility. Cheltenham, UK, and Northampton, MA:Edward Elgar Publishing, 1998
    [6]
    Gibbons R. A Primer in Game Theory. New York:FT Prentice Hall, 1992
    [7]
    Basar T, Olsder G J. Dynamic Noncooperative Game Theory (Second edition). Philadelphia:Society for Industrial and Applied Mathematics, 1999
    [8]
    Fudenberg D, Levine D. The Theory of Learning in Games. New York:MIT Press, 1998
    [9]
    Shapley L. Some topics in two-person games. Advances in Game Theory, 1964, 52:1-29
    [10]
    Jordan J S. Three problems in learning mixed-strategy Nash equilibria. Games and Economic Behavior, 1993, 5(3):368-386
    [11]
    Shamma J S, Arslan G. Unified convergence proofs of continuous-time fictitious play. IEEE Transactions on Automatic Control, 2004, 49(7):1137-1142
    [12]
    Monderer D, Shapley L. Potential games. Games and Economic Behavior, 1996, 14(1):124-143
    [13]
    Marden J, Arslan G, Shamma J. Joint strategy fictitious play with inertia for potential games. IEEE Transactions on Automatic Control, 2009, 54(2):208-220
    [14]
    Olfati-Saber R, Fax J A, Murray R M. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 2007, 95(1):215-233
    [15]
    Tahbaz-Salehi A, Jadbabaie A. A necessary and sufficient condition for consensus over random networks. IEEE Transactions on Automatic Control, 2008, 53(3):791-795
    [16]
    Qu Z H. Cooperative Control of Dynamical Systems. New York:Springer, 2009
    [17]
    Kingston D B, Beard R W. Discrete-time average-consensus under switching network topologies. In:Proceedings of the 2006 American Control Conference. Minneapolis, MN:IEEE, 2006. 3551-3556
    [18]
    Ren W, Beard R W. Distributed Consensus in Multi-Vehicle Cooperative Control:Theory and Applications. New York:Springer, 2008
    [19]
    Cao M, Morse A S, Anderson B D. Reaching a consensus in a dynamically changing environment:a graphical approach. SIAM Journal on Control and Optimization, 2008, 47(2):575-600
    [20]
    Cao M, Morse A S, Anderson B D. Reaching a consensus in a dynamically changing environment:convergence rates, measurement delays, and asynchronous events. SIAM Journal on Control and Optimization, 2008, 47(2):601-623
    [21]
    Bauso D, Giarré L, Pesenti R. Consensus in noncooperative dynamic games:a multiretailer inventory application. IEEE Transactions on Automatic Control, 2008, 53(4):998-1003
    [22]
    Bauso D, Giarré L, Pesenti R. Distributed consensus in noncooperative inventory games. European Journal of Operational Research, 2009, 192(3):866-878
    [23]
    Patriksson M. The Traffic Assignment Problem:Models and Methods. Utrecht:VSP, 1994
    [24]
    Como G, Savla K, Acemoglu D, Dahleh M, Frazzoli E. Robust distributed routing in dynamical flow networks-Part II:strong resilience, equilibrium selection and cascaded failures. IEEE Transactions on Automatic Control, 2013, 58(2):333-348
    [25]
    Wongpiromsarn T, Xiao N, You K Y, Sim K, Xie L H, Frazzoli E, Rus D. Road pricing for spreading peak travel:modeling and design. In:Proceedings of the 17th International Conference of Hong Kong Society for Transportation Studies. Hong Kong, China:The Hong Kong Institution of Engineers, 2012. 291-298
    [26]
    Rosenthal R. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 1973, 2(1):65-67
    [27]
    Xiao N, Wang X H, Wongpiromsarn T, You K Y, Xie L H, Frazzoli E, Rus D. Average strategy fictitious play with application to road pricing. In:Proceedings of the 2013 American Control Conference. Washington, DC, USA:IEEE, 2013. 1920-1925
    [28]
    Wang X H, Xiao N, Wongpiromsarn T, Xie L H, Frazzoli E, Rus D. Distributed consensus in noncooperative congestion games:an application to road pricing. In:Proceedings of the 10th IEEE International Conference on Control and Automation. Hangzhou, China:IEEE, 2013. 1668-1673
    [29]
    Ben-Akiva M, De-Palma A, Kaysi I. Dynamic network models and driver information systems. Transportation Research Part A:General, 1991, 25(5):251-266
    [30]
    Roughgarden T. Potential functions and the inefficiency of equilibria. In:Proceedings of the 2006 International Congress of Mathematicians. Madrid, Spain:European Mathematical Society, 2006. 1071-1094
    [31]
    Bell M, Iida Y. Transportation Network Analysis. New York:John Wiley & Sons, 1997
    [32]
    Garavello M, Piccoli B. Traffic Flow on Networks. Portage Ave, Palo Alto, CA:American Institute of Mathematical Sciences, 2006
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1372) PDF downloads(27) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return