Computing approximate equilibria in weighted congestion games via best-responses

DOI10.1287/MOOR.2021.1144zbMATH Open1489.91014arXiv1810.12806OpenAlexW3200955463MaRDI QIDQ5076717FDOQ5076717

Authors: Yiannis Giannakopoulos, Georgy Noarov, Andreas S. Schulz 

Publication date: 17 May 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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 et al. [FOCS'11, TEAC 2015], 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/mathcalW(d/ho){]}^{d+1}$ for the Price of Anarchy (PoA) of $ho$-approximate equilibria in weighted congestion games, where $mathcalW$ is the Lambert-W function. More specifically, we show that this PoA is exactly equal to $Ph{i}_{d,ho}^{d+1}$, where $Ph{i}_{d,ho}$ is the unique positive solution of the equation $ho(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, while our lower bound is simple enough to apply even to singleton congestion games.

Full work available at URL: https://arxiv.org/abs/1810.12806

Recommendations

• Efficient computation of approximate pure Nash equilibria in congestion games
• On approximate pure Nash equilibria in weighted congestion games with polynomial latencies
• Approximate pure Nash equilibria in weighted congestion games
• The price of stability of weighted congestion games
• The price of stability of weighted congestion games

zbMATH Keywords

price of anarchypotential gamescomputation of equilibriaatomic congestion gamesaproximate equilibria

Mathematics Subject Classification ID

Approximation algorithms (68W25) Equilibrium refinements (91A11) Potential and congestion games (91A14) Algorithmic game theory and complexity (91A68)

Cites Work

• Non-cooperative games
• Algorithmic Game Theory
• On the Lambert \(w\) function
• Worst-case equilibria
• A class of games possessing pure-strategy Nash equilibria
• Potential games
• Selfish unsplittable flows
• On the existence of pure Nash equilibria in weighted congestion games
• On the impact of combinatorial structure on congestion games
• Title not available (Why is that?)
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• Convergence to approximate Nash equilibria in congestion games
• Restoring Pure Equilibria to Weighted Congestion Games
• Network design with weighted players
• Efficient computation of approximate pure Nash equilibria in congestion games
• Atomic resource sharing in noncooperative networks
• On the performance of approximate equilibria in congestion games
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• Bounding the potential function in congestion games and approximate pure Nash equilibria
• Approximate pure Nash equilibria in weighted congestion games
• Exact price of anarchy for polynomial congestion games
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• Intrinsic robustness of the price of anarchy
• On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies
• The price of stability of weighted congestion games
• Twenty lectures on algorithmic game theory
• Game theory, alive
• On the impact of singleton strategies in congestion games
• Computing approximate pure Nash equilibria in Shapley value weighted congestion games

Cited In (10)

• Computing approximate pure Nash equilibria in Shapley value weighted congestion games
• Improving approximate pure Nash equilibria in congestion games
• On approximate pure Nash equilibria in weighted congestion games with polynomial latencies
• On best response dynamics in weighted congestion games with polynomial delays
• On the performance of approximate equilibria in congestion games
• Equilibrium computation in atomic splittable singleton congestion games
• Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
• Efficient computation of approximate pure Nash equilibria in congestion games
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
• Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions

This page was built for publication: Computing approximate equilibria in weighted congestion games via best-responses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5076717)