On existence and properties of approximate pure nash equilibria in bandwidth allocation games

Maximilian Drees*, Matthias Feldotto, Sören Riechers, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

In bandwidth allocation games (BAGs), the strategy of a player consists of various demands on different resources. The player’s utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can prove her utility by more than some fixed factor α through unilateral strategy changes. There is a threshold αδ (where δ is a parameter that limits the demand of each player on a specific resource) such that α-approximate pure Nash equilibria always exist for α ≥ αδ, but not for α < αδ. We give both upper and lower bounds on this threshold αδ and show that the corresponding decision problem is NP-hard. We also show that the α-approximate price of anarchy for BAGs is α+1. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory - 8th International Symposium, SAGT 2015
EditorsMartin Hoefer, Martin Hoefer
PublisherSpringer
Pages178-189
Number of pages12
ISBN (Electronic)978-3-662-48433-3
ISBN (Print)978-3-662-48432-6
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event8th International Symposium on Algorithmic Game Theory, SAGT 2015 - Saarbrucken, Germany
Duration: 28 Sep 201530 Sep 2015
Conference number: 8
http://sagt2015.mpi-inf.mpg.de/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9347
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Symposium on Algorithmic Game Theory, SAGT 2015
Abbreviated titleSAGT 2015
CountryGermany
CitySaarbrucken
Period28/09/1530/09/15
Internet address

Fingerprint

Dive into the research topics of 'On existence and properties of approximate pure nash equilibria in bandwidth allocation games'. Together they form a unique fingerprint.

Cite this