The Shapley value, a well-established concept in cooperative game theory, serves as a metric for assessing the significance of each player in a transferable utility game. Recently, it has found application in gauging the importance of individual nodes or arcs within a network. However, in this context, the exact evaluation of the Shapley value is often computationally expensive, particularly in the case of extensive networks. This study delves into the challenge of approximating the Shapley value in a transferable utility game defined on a network, wherein the characteristics of the network are parameterized by a variable of interest (e.g., the traffic demand). We examine the smoothness of the Shapley value with respect to this parameter and leverage such smoothness to theoretically justify the adoption of machine-learning techniques for its approximate computation. Additionally, we present potential extensions for further research in this area.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Approximation of the Shapley Value via Machine Learning in Transportation Network Cooperative Games

  • Giorgio Gnecco,
  • Yuval Hadas,
  • Mauro Passacantando,
  • Marcello Sanguineti

摘要

The Shapley value, a well-established concept in cooperative game theory, serves as a metric for assessing the significance of each player in a transferable utility game. Recently, it has found application in gauging the importance of individual nodes or arcs within a network. However, in this context, the exact evaluation of the Shapley value is often computationally expensive, particularly in the case of extensive networks. This study delves into the challenge of approximating the Shapley value in a transferable utility game defined on a network, wherein the characteristics of the network are parameterized by a variable of interest (e.g., the traffic demand). We examine the smoothness of the Shapley value with respect to this parameter and leverage such smoothness to theoretically justify the adoption of machine-learning techniques for its approximate computation. Additionally, we present potential extensions for further research in this area.