Gairing, Martin, Kollias, Konstantinos and Kotsialou, Grammateia
(2015)
Tight Bounds for Cost-Sharing in Weighted Congestion Games.
In: 42nd International Colloquium, ICALP 2015, 2015-7-6 - 2015-7-10, Kyoto, Japan,.
This is the latest version of this item.
Text
general.pdf - Author Accepted Manuscript Download (279kB) |
Abstract
This work studies the price of anarchy and the price of stability of cost-sharing methods in weighted congestion games. We require that our cost-sharing method and our set of cost functions satisfy certain natural conditions and we present general tight price of anarchy bounds, which are robust and apply to general equilibrium concepts. We then turn to the price of stability and prove an upper bound for the Shapley value cost-sharing method, which holds for general sets of cost functions and which is tight in special cases of interest, such as bounded degree polynomials. Also for bounded degree polynomials, we close the paper with a somehow surprising result, showing that a slight deviation from the Shapley value has a huge impact on the price of stability. In fact, for this case, the price of stability becomes as bad as the price of anarchy.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | Cost Function, Tight Bound, Congestion Game, Potential Game, Pure Nash Equilibrium |
Subjects: | ?? QA76 ?? |
Depositing User: | Symplectic Admin |
Date Deposited: | 07 Feb 2017 15:53 |
Last Modified: | 19 Jan 2023 07:30 |
DOI: | 10.1007/978-3-662-47666-6_50 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3003315 |
Available Versions of this Item
-
Tight Bounds for Cost-Sharing in Weighted Congestion Games. (deposited 30 Nov 2015 17:30)
-
Tight Bounds for Cost-Sharing in Weighted Congestion Games. (deposited 01 Dec 2015 11:19)
- Tight Bounds for Cost-Sharing in Weighted Congestion Games. (deposited 07 Feb 2017 15:53) [Currently Displayed]
-
Tight Bounds for Cost-Sharing in Weighted Congestion Games. (deposited 01 Dec 2015 11:19)