---
res:
bibo_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].@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Matthias
foaf_name: Feldotto, Matthias
foaf_surname: Feldotto
foaf_workInfoHomepage: http://www.librecat.org/personId=14052
orcid: 0000-0003-1348-6516
- foaf_Person:
foaf_givenName: Martin
foaf_name: Gairing, Martin
foaf_surname: Gairing
- foaf_Person:
foaf_givenName: Grammateia
foaf_name: Kotsialou, Grammateia
foaf_surname: Kotsialou
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.1007/978-3-319-71924-5_14
dct_date: 2017^xs_gYear
dct_language: eng
dct_title: Computing Approximate Pure Nash Equilibria in Shapley Value Weighted
Congestion Games@
...