direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2009

Characterizing the Existence of Potential Functions in Weighted Congestion Games
Zitatschlüssel Report-011-2009
Autor Tobias Harks and Max Klimm and Rolf H. Möhring
Jahr 2009
Nummer 011
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag