ABSTRACT
The Shapley value is a very important point solution for cooperative games with transferable utility. On the one hand, it enjoys a lot of interesting fairness properties; on the other hand, it suffers from a high computational complexity.
In this survey, we collect some applications of game theory to real-world problems that share a low computational complexity for the Shapley value, exploiting the features of the problems.
We consider two groups of situations, namely problems defined on a linear resource and games that may be decomposed. In the former group, we collect the problems of managing airport, cleaning rivers, auctions and markets, while in the latter, we refer to sequencing games, maintenance cost games, microarray games and coverage games.
Our aim is to provide incentives for extending the classes of games for which it is simple to compute the Shapley value, and consequently, for improving the usage of the Shapley value in real-world applications.
