Shapley value approximation via machine learning in cooperative games for traffic equilibrium

Estimating the importance of arcs and nodes in a network is a major issue in various applications, from movement analysis to traffic management and wildfire fighting. This can be done by exploiting the Shapley value, a concept from cooperative games with transferable utility, as a measure of the significance of each player in such games. To this end, one can define games in which the players are network elements (e.g., arcs or nodes). However, for large networks, the exact evaluation of the Shapley value is computationally demanding. Here, an approach for its approximate computation is investigated. The network is parameterized by one or more quantities of interest (e.g., the traffic demand). Smoothness properties of the Shapley value as a function of such parameters are investigated and exploited to apply machine learning techniques for its approximate computation. The methodology is tested on two networks: the one on which the so-called Braess’ paradox (i.e., adding a resource may in some cases deteriorate, instead of improving, the overall network performance) was first observed and the Sioux-Falls network, a benchmark for network analysis and design, having realistic topology and demands. Numerical results show the effectiveness of the proposed machine learning approximations of the Shapley value.