Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games



Feldotto, M, Gairing, M, Kotsialou, G and Skopalik, A
(2017) Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games. In: Conference on Web and Internet Economics, 2017-12-17 - 2017-12-20, Bangalore, India.

[img] Text
WINE_2017_paper_53.pdf - Author Accepted Manuscript

Download (624kB)

Abstract

We study the computation of approximate pure Nash equilibria in Shapley value (SV) weighted congestion games, introduced in [19]. This class of games considers weighted congestion games in which Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We focus on the interesting subclass of such games with polynomial resource cost functions and present an algorithm that computes approximate pure Nash equilibria with a polynomial number of strategy updates. Since computing a single strategy update is hard, we apply sampling techniques which allow us to achieve polynomial running time. The algorithm builds on the algorithmic ideas of [7], however, to the best of our knowledge, this is the first algorithmic result on computation of approximate equilibria using other than proportional shares as player costs in this setting. We present a novel relation that approximates the Shapley value of a player by her proportional share and vice versa. As side results, we upper bound the approximate price of anarchy of such games and significantly improve the best known factor for computing approximate pure Nash equilibria in weighted congestion games of [7].

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-71924-5_14
Uncontrolled Keywords: cs.GT, cs.GT
Depositing User: Symplectic Admin
Date Deposited: 05 Oct 2017 08:36
Last Modified: 19 Jan 2023 06:53
DOI: 10.1007/978-3-319-71924-5_14
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3009775