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. |