A payoff-based learning procedure and its application to traffic games

• 成果类型: Article
• 署名作者: Cominetti, Roberto; Melo, Emerson; Sorin, Sylvain
• 署名单位: Universidad de Chile; Universidad de Chile; Universidad de Chile; Sorbonne Universite; heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; Ecole Polytechnique
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.11.012
• 发表日期: 2010
• 页码: 71-83
• 关键词: games; learning; Adaptive dynamics; Stochastic algorithms; Congestion games

摘要

A stochastic process that describes a payoff-based learning procedure and the associated adaptive behavior of players in a repeated game is considered. The process is shown to converge almost surely towards a stationary state which is characterized as an equilibrium for a related game. The analysis is based on techniques borrowed from the theory of stochastic algorithms and proceeds by studying an associated continuous dynamical system which represents the evolution of the players' evaluations. An application to the case of finitely many users in a congested traffic network with parallel links is considered. Alternative descriptions for the dynamics and the corresponding rest points are discussed, including a Lagrangian representation. (C) 2008 Elsevier Inc. All rights reserved.