A convergence analysis of the price of anarchy in atomic congestion games

• 成果类型: Article
• 署名作者: Wu, Zijun; Moehring, Rolf H.; Ren, Chunying; Xu, Dachuan
• 署名单位: Hefei University; Technical University of Berlin; Beijing University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01853-0
• 发表日期: 2023
• 页码: 937-993
• 关键词: equilibria; INEFFICIENCY; networks

摘要

We analyze the convergence of the price of anarchy (PoA) of Nash equilibria in atomic congestion games with growing total demand T. When the cost functions are polynomials of the same degree, we obtain explicit rates for a rapid convergence of the PoAs of pure and mixed Nash equilibria to 1 in terms of 1/T and d(max)/T, where d(max) is the maximum demand controlled by an individual. Similar convergence results carry over to the random inefficiency of the random flow induced by an arbitrary mixed Nash equilibrium. For arbitrary polynomial cost functions, we derive a related convergence rate for the PoA of pure Nash equilibria (if they exist) when the demands fulfill certain regularity conditions and d(max) is bounded as T -> infinity. In this general case, also the PoA of mixed Nash equilibria converges to 1 as T -> infinity when d(max) is bounded. Our results constitute the first convergence analysis for the PoA in atomic congestion games and show that selfish behavior is well justified when the total demand is large.