On the Existence of Pure Nash Equilibria in Weighted Congestion Games

On the Existence of Pure Nash Equilibria in Weighted Congestion Games

0.00 Avg rating0 Votes
Article ID: iaor20124856
Volume: 37
Issue: 3
Start Page Number: 419
End Page Number: 436
Publication Date: Aug 2012
Journal: Mathematics of Operations Research
Authors: ,
Keywords: congestion, Nash equilibrium
Abstract:

We study the existence of pure Nash equilibria in weighted congestion games. Let 𝒞 denote a set of cost functions. We say that 𝒞 is consistent if every weighted congestion game with cost functions in 𝒞 possesses a pure Nash equilibrium. Our main contribution is a complete characterization of consistency of continuous cost functions. We prove that a set 𝒞 of continuous functions is consistent for two‐player games if and only if 𝒞 contains only monotonic functions and for all nonconstant functions c 1, c 2 ∈ 𝒞, there are constants a, b ∈ ℝ such that c 1(x) = a c 2(x) + b for all x ∈ ℝ≥0. For games with at least three players, we prove that 𝒞 is consistent if and only if exactly one of the following cases holds: (a) 𝒞 contains only affine functions; (b) 𝒞 contains only exponential functions such that c(x) = ac eφx + bc for some ac, bc , φ ∈ ℝ, where ac and bc may depend on c, while φ must be equal for every c ∈ 𝒞. The latter characterization is even valid for three‐player games. Finally, we derive several characterizations of consistency of cost functions for games with restricted strategy spaces, such as weighted network congestion games or weighted congestion games with singleton strategies.

Reviews

Required fields are marked *. Your email address will not be published.