Gairing, M, Kollias, K and Kotsialou, G
(2017)
Cost-sharing in generalised selfish routing.
.
Text
multiCameraReady.pdf - Author Accepted Manuscript 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: | 19 Jan 2023 07:04 |
DOI: | 10.1007/978-3-319-57586-5_23 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007552 |