direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints

On the Existence of Pure Nash Equilibria in Weighted Congestion Games
Zitatschlüssel Report-001-2010
Autor Tobias Harks and Max Klimm
Jahr 2010
Nummer 001
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We study the existence of pure Nash equilibria in weighted congestion games. Let C denote a set of cost functions. We say that C is consistent if every weighted congestion game with cost functions in C possesses a PNE. We say that C is FIP-consistent if every weighted congestion game with cost functions in C possesses the Finite Improvement Property. Our contribution is the following: 1. Let C be a nonempty set of continuous functions. If C is consistent, then C may only contain monotonic functions. This characterization is even valid for singleton games. 2. Let C be a nonempty set of twice continuously differentiable functions. Then, C is consistent for two-player games if and only if C contains only monotonic functions and for all c_1,c_2 in C, there are constants a,b in R such that c_1=a c_2+b. 3. Under the same assumptions as in 2., we show that C is consistent for games with at least 3 players if and only if exactly one of the following cases hold: (i) C contains only affine functions; (ii) C contains only exponential functions such that c(ell)=a_c e^phi ell+b_c for some a_c,b_c, phi in R, where a_c and b_c may depend on c, while φ must be equal for every c in C. This characterization is even valid for 3-player games, thus, closing the gap to 2-player games considered above. Finally, we discuss implications of our characterizations for weighted network congestion games.
Link zur Publikation Download Bibtex Eintrag