Learning an Unknown Network State in Congestion Games

Wednesday, November 20, 2019 - 4:00pm to Thursday, November 21, 2019 - 4:55pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Manxi Wu



Building and Room Number

LIDS Lounge


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. 


Manxi Wu is a doctoral student working with Prof. Saurabh Amin in the Institute for Data, Systems, and Society (IDSS) at MIT. Previously, she obtained a B.S. in Applied Math from Peking University and M.S. in Transportation from MIT.