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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

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