An Improved Algorithm for Computing Approximate Equilibria in Weighted Congestion Games

Yiannis Giannakopoulos, Georgy Noarov, Andreas S. SchulzarXiv 2018 · arXiv · OpenReview

Abstract

We present a deterministic polynomial-time algorithm for computing $d^{d+o(d)}$-approximate (pure) Nash equilibria in weighted congestion games with polynomial cost functions of degree at most $d$. This represents an exponential improvement over the previous best deterministic approximation factor of $d^{2d+o(d)}$. Our algorithm utilizes best-improvement steps directly on the original game, rather than transforming the game into an auxiliary version. We achieve this by employing an approximate potential function based on Faulhaber’s formula. Additionally, we derive a novel, tight bound for the Price of Anarchy (PoA) of $\rho$-approximate equilibria, showing it to be exactly $\Phi_{d,\rho}^{d+1}$, where $\Phi_{d,\rho}$ is the unique positive solution to $\rho (x+1)^d=x^{d+1}$.

Introduction

Congestion games are a fundamental framework in algorithmic game theory used to model scenarios where selfish agents compete for shared resources, such as drivers choosing routes in a traffic network. In unweighted congestion games, where every player has an equal impact on resource cost, a pure Nash equilibrium (PNE) is guaranteed to exist and can be found via potential function minimizers. However, the landscape changes significantly when players are "weighted" (e.g., trucks vs. cars).

In weighted congestion games, a PNE may not exist at all, and even when it does, finding it is often PLS-complete. Consequently, research has shifted toward finding approximate equilibria. In a $\rho$-approximate equilibrium, no player can reduce their cost by more than a factor of $\rho$ by unilaterally switching strategies. This paper provides a more efficient and effective way to reach these stable states.

The Challenge of Weighted Players

Previous state-of-the-art deterministic algorithms for weighted congestion games were limited in two ways. First, the approximation factor they achieved was relatively high ($d^{2d+o(d)}$). Second, they were often "unnatural"—requiring the game to be transformed into a different, artificial version to perform calculations before mapping the results back to the original game.

This paper addresses these limitations by providing a deterministic, polynomial-time algorithm that operates directly on the original game while significantly tightening the approximation guarantee to $d^{d+o(d)}$.

Methodology: Direct Best-Response and Potential Functions

The authors' approach is an evolution of the seminal work by Caragiannis et al. (2011), but introduces two critical technical innovations:

1. Direct Best-Response Dynamics

Unlike previous methods that relied on auxiliary games with modified cost functions, this algorithm performs best-improvement steps directly in the original game. This makes the process more intuitive and suggests that simple learning dynamics—where players react to their current environment—can lead to stable outcomes efficiently.

2. Faulhaber’s Potential

Weighted congestion games lack an exact potential function. To overcome this, the authors utilize Faulhaber’s potential as an approximate potential function. They demonstrate that this function is "cost-revealing" enough to track the game's progress toward equilibrium. By executing the algorithm in phases—fixing the strategies of certain "packets" of players once their costs stabilize—they prevent the infinite loops that typically hinder best-response dynamics in weighted settings.

Price of Anarchy and the Lambert-W Function

A significant theoretical contribution of this work is the derivation of a novel bound for the Price of Anarchy (PoA) in $\rho$-approximate equilibria. The PoA measures the ratio between the total cost of a decentralized equilibrium and the total cost of an optimal centralized solution.

Using a smoothness-like argument, the authors show that the PoA is exactly $\Phi_{d,\rho}^{d+1}$, where $\Phi_{d,\rho}$ is the unique positive solution to the equation: $$\rho (x+1)^d=x^{d+1}$$

This bound is further simplified using the Lambert-W function, providing a clear mathematical relationship between the degree of the cost polynomial ($d$) and the approximation factor ($\rho$). Because this is derived via smoothness, the bound applies not only to pure Nash equilibria but also to mixed Nash and correlated equilibria.

Key Results and Impact

  • Exponential Improvement: The algorithm achieves a $d^{d+o(d)}$ approximation, an exponential jump in quality over the previous $d^{2d+o(d)}$ benchmark.
  • Computational Efficiency: The algorithm is guaranteed to run in polynomial time relative to the number of players and the game's description, even in games with exponentially large strategy spaces, such as network routing.
  • Tight Theoretical Bounds: The work provides the most precise characterization to date of the Price of Anarchy for approximate equilibria in these games.

Conclusion and Future Work

While this paper represents a major step forward, a gap remains between existence and computation. It is known that $d$-approximate equilibria always exist in weighted congestion games, yet the most efficient algorithm currently reaches $d^d$. Closing this gap remains a primary challenge for the field. Additionally, while this work focuses on polynomial cost functions, extending these tight bounds to more general cost structures is a promising avenue for future research.

Summary updated

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/\mathcal{W}(d/\rho)]^{d+1}$ for the Price of Anarchy (PoA) of $\rho$-approximate equilibria in weighted congestion games, where $\mathcal{W}$ is the Lambert-W function. More specifically, we show that this PoA is exactly equal to $\Phi_{d,\rho}^{d+1}$, where $\Phi_{d,\rho}$ is the unique positive solution of the equation $\rho (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.
BibTeX
@misc{giannakopoulos2018improved,
  author = {Yiannis Giannakopoulos and Georgy Noarov and Andreas S. Schulz},
  title = {{An Improved Algorithm for Computing Approximate Equilibria in Weighted Congestion Games}},
  year = {2018},
  eprint = {1810.12806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.12806},
}
Figure