On the Existence of Pure Nash Equilibria in Weighted Congestion Games

• 成果类型: Article
• 署名作者: Harks, Tobias; Klimm, Max
• 署名单位: Maastricht University; Technical University of Berlin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0543
• 发表日期: 2012
• 页码: 419-436
• 关键词: Network design; price; complexity

摘要

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 pure Nash equilibrium. Our main contribution is a complete characterization of consistency of continuous cost functions. We prove that a set C of continuous functions is consistent for two-player games if and only if C contains only monotonic functions and for all nonconstant functions c(1), c(2) is an element of C, there are constants a, b is an element of R such that c(1) (x) = a c(2)(x) + b for all x is an element of R->= 0. For games with at least three players, we prove that C is consistent if and only if exactly one of the following cases holds: (a) C contains only affine functions; (b) C contains only exponential functions such that c(x) = a(c)e(phi x) + b(c) for some a(c), b(c), phi is an element of R, where a(c) and b(c) may depend on c, while phi must be equal for every c is an element of 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.