Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses

Yiannis Giannakopoulos (), Georgy Noarov () and Andreas S. Schulz ()
Additional contact information
Yiannis Giannakopoulos: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Georgy Noarov: Computer and Information Science, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Andreas S. Schulz: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany

Mathematics of Operations Research, 2022, vol. 47, issue 1, 643-664

Abstract: We present a deterministic polynomial-time algorithm for computing d d + o ( d ) -approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most d . This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms, that first had to transform the game itself. Our algorithm is an adaptation of the seminal algorithm by Caragiannis at al. [Caragiannis I, Fanelli A, Gravin N, Skopalik A (2011) Efficient computation of approximate pure Nash equilibria in congestion games. Ostrovsky R, ed. Proc. 52nd Annual Symp. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Los Alamitos, CA), 532–541; Caragiannis I, Fanelli A, Gravin N, Skopalik A (2015) Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Econom. Comput. 3(1):2:1–2:32.], but we utilize an approximate potential function directly on the original game instead of an exact one on a modified game. A critical component of our analysis, which is of independent interest, is the derivation of a novel bound of [ d / W ( d / ρ ) ] d + 1 for the price of anarchy (PoA) of ρ -approximate equilibria in weighted congestion games, where W is the Lambert-W function. More specifically, we show that this PoA is exactly equal to Φ d , ρ d + 1 , where Φ d , ρ is the unique positive solution of the equation ρ ( x + 1 ) d = x d + 1 . Our upper bound is derived via a smoothness-like argument, and thus holds even for mixed Nash and correlated equilibria, whereas our lower bound is simple enough to apply even to singleton congestion games.

Keywords: Primary: 91A14; secondary: 68W40; 68W25; atomic congestion games; computation of equilibria; price of anarchy; approximate equilibria; potential games (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1144 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:643-664

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().