Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

Matthias  Feldotto; Martin Gairing; Grammateia Kotsialou; Alexander  Skopalik

doi:10.1007/978-3-319-71924-5_14

Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

Matthias Feldotto, Martin Gairing, Grammateia Kotsialou, Alexander Skopalik

Political Economy

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

10 Citations (Scopus)

153 Downloads (Pure)

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

Original language	English
Title of host publication	Web and Internet of Economics (WINE)
Publisher	Springer
Pages	191-204
DOIs	https://doi.org/10.1007/978-3-319-71924-5_14
Publication status	E-pub ahead of print - 25 Nov 2017

Access to Document

10.1007/978-3-319-71924-5_14

Computing Approximate Pure Nash_FELDOTTO_Accepted26September2017_GREEN AAMAccepted author manuscript, 610 KB

Cite this

@inbook{0f7ad2a121e241d4bbf0e0dfaadc3f78,

title = "Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games",

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

author = "Matthias Feldotto and Martin Gairing and Grammateia Kotsialou and Alexander Skopalik",

year = "2017",

month = nov,

day = "25",

doi = "10.1007/978-3-319-71924-5_14",

language = "English",

pages = "191--204",

booktitle = "Web and Internet of Economics (WINE)",

publisher = "Springer",

}

TY - CHAP

T1 - Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

AU - Feldotto, Matthias

AU - Gairing, Martin

AU - Kotsialou, Grammateia

AU - Skopalik, Alexander

PY - 2017/11/25

Y1 - 2017/11/25

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

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

U2 - 10.1007/978-3-319-71924-5_14

DO - 10.1007/978-3-319-71924-5_14

M3 - Conference paper

SP - 191

EP - 204

BT - Web and Internet of Economics (WINE)

PB - Springer

ER -

Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

Abstract

Access to Document

Fingerprint

Cite this