Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion Games



Gairing, Martin, Kollias, Kostas and Kotsialou, Grammateia
(2020) Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion Games. ACM Transactions on Economics and Computation, 8 (2).

This is the latest version of this item.

[img] Text
GeneralisedCG.pdf - Accepted Version
Available under License : See the attached licence file.

Download (803kB) | Preview

Abstract

This work studies the impact of cost-sharing methods on the existence and efficiency of (pure) Nash equilibria in weighted congestion games. We also study generalized weighted congestion games, where each player may control multiple commodities. Our results are fairly general; we only require that our cost-sharing method and our set of cost functions satisfy certain natural conditions. For general weighted congestion games, we study the existence of pure Nash equilibria in the induced games, and we exhibit a separation from the standard single-commodity per player model by proving that the Shapley value is the only cost-sharing method that guarantees existence of pure Nash equilibria. With respect to efficiency, we present general tight bounds on the price of anarchy, which are robust and apply to general equilibrium concepts. Our analysis provides a tight bound on the price of anarchy, which depends only on the used cost-sharing method and the set of allowable cost functions. Interestingly, the same bound applies to weighted congestion games and generalized weighted congestion games. 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 provide a somewhat 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. Again, our bounds on the price of stability are independent on whether players are single or multi-commodity.

Item Type: Article
Uncontrolled Keywords: existence of equilibria, price of anarchy, price of stability, congestion games, selfish routing, Shapley value, multi-commodity players
Depositing User: Symplectic Admin
Date Deposited: 13 Nov 2020 09:11
Last Modified: 11 Jun 2022 12:48
DOI: 10.1145/3391434
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3106620

Available Versions of this Item