Informed-user Algorithms that Converge to Nash Equilibrium in Traffic Games

This paper considers a group of self-interested agents (drivers) trying to optimize their utility by choosing the route with the least travel time and proposes an algorithm that converges to a pure Nash equilibrium almost surely in traffic games. Weakly acyclic games, which generalize potential and dominance solvable games, are closely related to multi-agent systems through the existence of a global objective function and its alignment to the local utilities of each agent. The authors show that in a multi-agent distributed traffic routing problem with both linear and non-linear link cost functions, in the form of a congestion game, the achievement of pure Nash equilibrium is possible even if the agents use only the utility information of the previous action. The authors propose a fast and adaptive algorithm for the informed-user problem that provides almost sure convergence to a pure Nash equilibrium in any weakly acyclic game.

• Record URL:
  https://doi.org/10.1016/j.sbspro.2012.09.762
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S1877042812042243
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/18770428
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier.
• Authors:
  • MIYAGI, TOSHIHIKO
  • Peque Jr., Genaro C
• Conference:
  • 15th Meeting of the EURO Working Group on Transportation
  • Location: Paris , France
  • Date: 2012-9-10 to 2012-9-13
• Publication Date: 2012-10-4

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References;
• Pagination: pp 438-449
• Serial:
  • Procedia - Social and Behavioral Sciences
  • Volume: 54
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 1877-0428
  • Serial URL: http://www.sciencedirect.com/science/journal/18770428/53
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Algorithms; Route choice; Traffic flow; Travel time
• Uncontrolled Terms: Nash equilibrium
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01487375
• Record Type: Publication
• Files: TRIS
• Created Date: Jul 3 2013 1:35PM