On the Existence of Pure Nash Equilibria in Weighted Congestion Games

Tobias Harks and Max Klimm

not available

weighted congestion games, existence of pure Nash equilibria

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

Download as [PDF]