文章基本信息

标题：Informed-user Algorithms that Converge to Nash Equilibrium in Traffic Games
本地全文：下载
作者：Toshihiko Miyagi ; Toshihiko Miyagi ; Genaro C. Peque 等
期刊名称：Procedia - Social and Behavioral Sciences
印刷版ISSN：1877-0428
出版年度：2012
卷号：54
页码：438-449
DOI：10.1016/j.sbspro.2012.09.762
语种：English
出版社：Elsevier
摘要：AbstractThis 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. We 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. We 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.
关键词：Traffic games;pure Nash equilibrium;weakly acyclic game