Information Design in Bayesian Routing Games

Routing games model the behavior of a large number of strategic users travelling in a transportation network. Each link of the network is endowed with a delay function that describes the travel time as a function of the flow, and users aim at selecting routes with minimum total travel time. An equilibrium of the game is a flow assignment whereby that no users have an incentive to deviate from their chosen route. This thesis is focused on Bayesian routing games, in which delays are stochastic functions that depend on a random variable representing the state of the world. In particular, we investigate how a central planner who observes the state of the world should provide information to the users in order to influence their routing behavior, possibly stirring it towards a system optimum. This problem is called in the literature Information design. It is known that revealing the true state of the network, and more in general public signaling policies, are inefficient in minimizing the system cost. Moreover, the signal space can be restricted to route recommendations such that users have no incentive in deviating from the received recommendation, which is known as obedience constraint. For these reasons, this thesis is focused on private signaling, i.e., when users receive different route recommendations at the same time. The fundamental assumption of this Bayesian model is that the prior distribution of the state of the network and the signal policy are common knowledge to the users, who make decisions based on their posterior belief on both the state of the network and the information that other users after receiving the recommendation. We analyse the properties of the problem, showing that it is convex if the network is binary with two parallel routes and the delay functions are affine. This gives us necessary and sufficient condition for optimality. We find sufficient conditions on the support of the unknown parameters of the delay functions and on their moments under which the price of anarchy is minimized. Interestingly, we observe that a large variance of the unknown parameters is beneficial for the system cost under the optimal policy. Moreover, we study the structure of the optimal policy when the price of anarchy is strictly larger than 1, that is when the obedience constraints are not satisfied under the optimal policy that minimizes the objective function without considering the constraints. In particular, we show that it is not possible under the optimal policy that all the users that receive different recommendations are incentivized in deviating at the same time.