Cost-Sharing in Generalised Selfish Routing

We study a generalisation of atomic selfish routing games where each player may control multiple flows which she routes seeking to minimise their aggregate cost. Such games emerge in various settings, such as traffic routing in road networks by competing ride-sharing applications or packet routing in communication networks by competing service providers who seek to optimise the quality of service of their customers. We study the existence of pure Nash equilibria in the induced games and we exhibit a separation from the single-commodity per player model by proving that the Shapley value is the only cost-sharing method that guarantees it. We also prove that the price of anarchy and price of stability is no larger than in the single-commodity model for general cost-sharing methods and general classes of convex cost functions. We close by giving results on the existence of pure Nash equilibria of a splittable variant of our model.