TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

On the Existence of Pure Nash Equilibria in Weighted Congestion Games
Citation key Report-001-2010
Author Tobias Harks and Max Klimm
Year 2010
Number 001
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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 to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe