1−ρǫ-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes

作     者：Ren, Chunying Wu, Zijun Xu, Dachuan Yang, Xiaoguang 

作者机构：Department of Operations Research and Information Engineering Beijing University of Technology Pingleyuan 100 Beijing100124 China Department of Artificial Intelligence and Big Data Hefei University Jinxiu 99 Anhui Hefei230601 China Academy of Mathematics and System Science University of Chinese Academy of Sciences Beijing100190 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2022年

核心收录：

主　　题：Computer games 

摘      要：This paper concerns computing approximate pure Nash equilibria in weighted congestion games, which has been shown to be PLS-complete. With the help of Ψ-game and approximate potential functions, we propose two algorithms based on best response dynamics, and prove that they efficiently compute 1−ρǫ-approximate pure Nash equilibria for ρ = d! and ρ = 22··WW·+(dd+1)+1 ≤ d+1, respectively, when the weighted congestion game has polynomial latency functions of degree at most d ≥ 1 and players’ weights are bounded from above by a constant W ≥ 1. This improves the recent work of Feldotto et al. [2017] and Giannakopoulos et al. [2022] that showed efficient algorithms for computing dd+o(d)approximate pure Nash equilibria. © 2022, CC BY.