Adaptive Learning Algorithms for Traffic Games with Naive Users

In this paper, we consider a traffic game where many atomic agents try to optimize their utilities by choosing the route with the least travel cost, and propose an actor-critic-based adaptive learning algorithm that converges to ɛ-Nash equilibrium with high probability in traffic games. The model consists of an N-person repeated game where each player knows his action space and the realized payoffs he has experienced but is unaware of the information about the action(s) he did not select. We formulate this traffic game as a stochastic congestion game and propose a naive user algorithm for finding a pure Nash equilibrium. An analysis of the convergence is based on Markov chain. Finally, using a single origin-destination network connected by some overlapping paths, the validity of the proposed algorithm is tested.