Congestion Games with Random Participation

Since demand in transportation networks is uncertain, commuters need to anticipate different traffic conditions. We capture this uncertainty by assuming that each commuter may make the trip or not with a fixed probability, creating an atomic congestion game with Bernoulli demands. We first prove that the resulting game is potential. Then we compute the parameterised price of anarchy to characterise the impact of demand uncertainty on the efficiency of the transportation network. It turns out that the price of anarchy as a function of the maximum participation probability is a nondecreasing function. For the case of affine costs, we provide an analytic expression for the parameterized price of anarchy. Our work can be interpreted as providing a continuous transition between the price of anarchy of nonatomic and atomic games, which are the extremes of the price of anarchy function we characterise.​

 

Joint with Roberto Cominetti, Marco Scarsini and Nicolas Stier-Moses

 

Recording: To view the seminar recording, click here.