Cost-sharing in generalised selfish routing



Gairing, M, Kollias, K and Kotsialou, G
(2017) Cost-sharing in generalised selfish routing. .

[img] Text
multiCameraReady.pdf - Accepted Version

Download (294kB)

Abstract

© Springer International Publishing AG 2017. We study a generalisation of atomic selfish routing games where each player may control multiple flows which she routes seek-ing to minimise their aggregate cost. Such games emerge in various set-tings, 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 cus-tomers. 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.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 19 May 2017 15:11
Last Modified: 01 Mar 2022 08:10
DOI: 10.1007/978-3-319-57586-5_23
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007552