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