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

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 6.171, Top 11% (SCI Q1)
    CiteScore: 11.2, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
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.

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


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.

  • 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.


  • loading
  • [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
    Menon A. ERP in Singapore:a perspective one year on. Traffic Engineering and Control, 2000, 41(2):40-45
    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
    Tsekeris T, Voβ S. Design and evaluation of road pricing:state-of-the-art and methodological advances. Netnomics, 2009, 10(1):5-52
    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
    Gibbons R. A Primer in Game Theory. New York:FT Prentice Hall, 1992
    Basar T, Olsder G J. Dynamic Noncooperative Game Theory (Second edition). Philadelphia:Society for Industrial and Applied Mathematics, 1999
    Fudenberg D, Levine D. The Theory of Learning in Games. New York:MIT Press, 1998
    Shapley L. Some topics in two-person games. Advances in Game Theory, 1964, 52:1-29
    Jordan J S. Three problems in learning mixed-strategy Nash equilibria. Games and Economic Behavior, 1993, 5(3):368-386
    Shamma J S, Arslan G. Unified convergence proofs of continuous-time fictitious play. IEEE Transactions on Automatic Control, 2004, 49(7):1137-1142
    Monderer D, Shapley L. Potential games. Games and Economic Behavior, 1996, 14(1):124-143
    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
    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
    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
    Qu Z H. Cooperative Control of Dynamical Systems. New York:Springer, 2009
    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
    Ren W, Beard R W. Distributed Consensus in Multi-Vehicle Cooperative Control:Theory and Applications. New York:Springer, 2008
    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
    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
    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
    Bauso D, Giarré L, Pesenti R. Distributed consensus in noncooperative inventory games. European Journal of Operational Research, 2009, 192(3):866-878
    Patriksson M. The Traffic Assignment Problem:Models and Methods. Utrecht:VSP, 1994
    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
    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
    Rosenthal R. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 1973, 2(1):65-67
    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
    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
    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
    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
    Bell M, Iida Y. Transportation Network Analysis. New York:John Wiley & Sons, 1997
    Garavello M, Piccoli B. Traffic Flow on Networks. Portage Ave, Palo Alto, CA:American Institute of Mathematical Sciences, 2006


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

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

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

    Article Metrics

    Article views (1057) PDF downloads(4) Cited by()


    DownLoad:  Full-Size Img  PowerPoint