Iterative Recommendations Based on Monte Carlo Sampling and Trust Estimation in Multi-Stage Vehicular Traffic Routing Games

The shortest-time route recommendations offered by modern navigation systems fuel selfish routing in urban vehicular traffic networks and are therefore one of the main reasons for the growth of congestion. In contrast, intelligent transportation systems (ITS) prefer to steer driver-vehicle systems (DVS) toward system-optimal route recommendations, which are primarily designed to mitigate network congestion. However, due to misalignment in motives, drivers may exhibit a lack of trust in the ITS. This paper models the interaction between a DVS and an ITS as a novel, multi-stage routing game where the DVS exhibits dynamics in its trust towards the recommendations of the ITS based on counterfactual and observed game outcomes. Specifically, the DVS and ITS are modeled as a travel-time minimizer and network congestion minimizer, respectively, each having nonidentical prior beliefs about the network state. A novel approximate algorithm to compute the Bayesian Nash equilibrium, called ROSTER (Recommendation Outcome Sampling with Trust Estimation and Re-evaluation), is proposed based on Monte Carlo sampling with trust belief updating to determine the best response route recommendations of the ITS at each stage of the game. Results of simulations between an ITS and a single additional DVS in a traffic network demonstrate that the developed algorithm is able to both mitigate network congestion and reduce driver travel times more effectively than baseline single-stage route recommendation strategies, while the error in the ITS's prediction of DVS's trust converges to zero as the number of interaction stages increases.