Computing approximate pure nash equilibria in shapley value weighted congestion games

Matthias Feldotto, Martin Gairing, Grammateia Kotsialou, Alexander Skopalik

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

6 Citations (Scopus)

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 languageEnglish
Title of host publicationWeb and Internet Economics
Subtitle of host publication13th International Conference, WINE 2017, Bangalore, India, December 17–20, 2017, Proceedings
EditorsNikhil R. Devanur, Pinyan Lu
PublisherSpringer
Pages191-204
Number of pages14
ISBN (Electronic)978-3-319-71924-5
ISBN (Print)978-3-319-71923-8
DOIs
Publication statusPublished - 2017
Externally publishedYes
Event13th International Conference on Web and Internet Economics, WINE 2017 - Indian Institute of Science, Bangalore, India
Duration: 17 Dec 201720 Dec 2017
Conference number: 13
http://lcm.csa.iisc.ernet.in/wine2017/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10660
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Web and Internet Economics, WINE 2017
Abbreviated titleWINE
CountryIndia
CityBangalore
Period17/12/1720/12/17
Internet address

Keywords

  • Approximate price of anarchy
  • Approximate pure nash equilibria
  • Computation
  • Shapley cost-sharing
  • Weighted congestion games

Fingerprint Dive into the research topics of 'Computing approximate pure nash equilibria in shapley value weighted congestion games'. Together they form a unique fingerprint.

Cite this