Learning an Unknown Network State in Congestion Games

We study learning dynamics induced by myopic players who repeatedly play a congestion game on a network with an unknown state. The state impacts the cost functions of one or more edges of the network. In each stage, players choose equilibrium strategies based on Bayesian estimation of the state. The state estimation is updated in each stage based on the edge loads and realized costs on the used edges according to Bayes’ rule. We show that the sequence of state estimation and edge load vectors generated by the repeated play converge almost surely. In any resting point, players have no incentive to deviate from the chosen strategies and accurately learn the true costs on the used edges. However, the costs on edges that are not used may not be accurately learned. Thus, learning can be incomplete in that the edge load vector at rest point and complete information equilibrium can be different. We present sufficient conditions for complete learning and illustrate situations when such an outcome is not guaranteed.