Congestion Games with Player-Specific Constants

Marios Mavronicolas, Igal Milchtaich, Burkhard Monien, Karsten Tiemann

We consider a special case of weighted congestion games with player-specific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the player-specific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group. In this way, we obtain the class of (weighted) congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance (weighted) congestion games. We focus on pure Nash equilibria for congestion games with player-specific constants; for these equilibria, we study questions of existence, computational complexity and convergence via improvement or best-reply steps of players. Our findings are as follows:

• Games on parallel links:
  • Every unweighted congestion game has an ordinal potential; hence, it has the Finite Improvement Property and a pure Nash equilibrium.
  • There is a weighted congestion game with 3 players on 3 parallel links that does not have the Finite Best-Reply Property (and hence neither the Finite Improvement Property).
  • There is a particular best-reply cycle for general weighted congestion games with player-specific latency functions and 3 players whose outlaw implies the existence of a pure Nash equilibrium. This cycle is indeed outlawed for dominance (weighted) congestion games with 3 players -- and hence for (weighted) congestion games with player-specific constants and 3 players. Hence, (weighted) congestion games with player-specific constants and 3 players have a pure Nash equilibrium.
• Network congestion games:\\ For unweighted symmetric network congestion games with player-specific additive constants, it is PLS-complete to find a pure Nash equilibrium.
• Arbitrary (non-network) congestion games:\\ Every weighted congestion game with linear delay functions and player-specific additive constants (and hence with affine player-specific latency functions) has an ordinal potential; hence, it has the Finite Improvement Property and a pure Nash equilibrium.