King's College London

Research portal

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

Research output: Contribution to journalArticle

Martin Gairing, Kostas Kollias, Grammateia Kotsialou

Original languageEnglish
JournalACM Transactions on Economics and Computation
Accepted/In pressFeb 2020

King's Authors

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454