Improving Approximate Pure Nash Equilibria in Congestion Games

Vipin Ravindran Vijayalakshmi*, Alexander Skopalik

*Corresponding author for this work

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

Abstract

Congestion games constitute an important class of games to model resource allocation by different users. As computing an exact [18] or even an approximate [34] pure Nash equilibrium is in general PLS-complete, Caragiannis et al. [9] present a polynomial-time algorithm that computes a (2 + ϵ)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to (1.61 + ϵ) and further improved results for polynomial cost functions, by a seemingly simple modification to their algorithm by allowing for the cost functions used during the best response dynamics be different from the overall objective function. Interestingly, our modification to the algorithm also extends to efficiently computing improved approximate pure Nash equilibria in games with arbitrary non-decreasing resource cost functions. Additionally, our analysis exhibits an interesting method to optimally compute universal load dependent taxes and using linear programming duality prove tight bounds on the PoA under universal taxation, e.g., 2.012 for linear congestion games and further results for polynomial cost functions. Although our approach yield weaker results than that in Bilò and Vinci [6], we remark that our cost functions are locally computable and in contrast to [6] are independent of the actual instance of the game.

Original languageEnglish
Title of host publicationWeb and Internet Economics
Subtitle of host publication16th International Conference, WINE 2020, Proceedings
EditorsXujin Chen, Nikolai Gravin, Martin Hoefer, Ruta Mehta
PublisherSpringer
Pages280-294
Number of pages15
ISBN (Electronic)978-3-030-64946-3
ISBN (Print)978-3-030-64945-6
DOIs
Publication statusPublished - 6 Dec 2020
Event16th International Conference on Web and Internet Economics, WINE 2020 - Virtual, Beijing, China
Duration: 7 Dec 202011 Dec 2020
Conference number: 16
https://econcs.pku.edu.cn/wine2020/

Publication series

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

Conference

Conference16th International Conference on Web and Internet Economics, WINE 2020
Abbreviated titleWINE 2020
CountryChina
CityBeijing
Period7/12/2011/12/20
Internet address

Keywords

  • Approximate pure Nash equilibria
  • Congestion games
  • Price of anarchy
  • Universal taxes

Fingerprint Dive into the research topics of 'Improving Approximate Pure Nash Equilibria in Congestion Games'. Together they form a unique fingerprint.

Cite this