Characterizing the Existence of Potential Functions in Weighted Congestion Games

Tobias Harks, Max Klimm, and Rolf H. Möhring

not available

Game Theory, Potential Functions, Weighted Congestion Games, Cournot Games

Since the pioneering paper of Rosenthal a lot of work has been done in order to determine classes of games that admit a potential. First, we study the existence of potential functions for weighted congestion games. Let W be an arbitrary set of locally bounded functions and let G(W) be the set of weighted congestion games with cost functions in W. We show that every weighted congestion game G in the set G(W) admits an exact potential if and only if W contains only affine functions. We also give a similar characterization for b-potentials with the difference that W consists either of affine functions or of certain exponential functions.

Second, we introduce a generalization of weighted congestion games that we call dynamic congestion games. Here players are allowed to choose both a subset of the set of facilities and an intensity that describes the degree of exploitation of the facilities. We derive a characterization of the existence of potentials that also establishes existence of pure Nash equilibria. Moreover, we present an asymptotically tight analysis of the price of anarchy for an important special case of dynamic congestion games.

Download as [PDF]