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).

There is a more recent version of this item available.

Text
GeneralisedCG.pdf - Author Accepted Manuscript
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:	21 Feb 2020 10:08
Last Modified:	19 Jan 2023 00:02
DOI:	10.1145/3391434
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3075560