论文标题
$ \fracρ{1-ε} $ - 加权拥塞游戏及其运行时的近似纯纳什均衡算法
$\fracρ{1-ε}$-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes
论文作者
论文摘要
本文涉及在加权拥堵游戏中计算近似纯纳什均衡，这已被证明是PLS完整的。借助$ \hatψ$游戏剂和近似潜在功能，我们根据最佳响应动态提出了两种算法，并证明它们有效地计算了$ \fracρ{1-ε} $ - 近似纯nash Equilibria $ $ρ= D！ W+D+1} \ le {D+1} $分别是加权拥塞游戏具有多项式潜伏期函数，最多最多为$ d \ ge 1 $，并且玩家的权重以常数$ w \ ge 1 $限制。这改善了Feldotto等人的最新工作。[2017]和Giannakopoulos等。 [2022]显示了用于计算$ d^{d+o（d）} $的有效算法 - 近似纯净的nash平衡。
This paper concerns computing approximate pure Nash equilibria in weighted congestion games, which has been shown to be PLS-complete. With the help of $\hatΨ$-game and approximate potential functions, we propose two algorithms based on best response dynamics, and prove that they efficiently compute $\fracρ{1-ε}$-approximate pure Nash equilibria for $ρ= d!$ and $ρ=\frac{2\cdot W\cdot(d+1)}{2\cdot W+d+1}\le {d + 1}$, respectively, when the weighted congestion game has polynomial latency functions of degree at most $d \ge 1$ and players' weights are bounded from above by a constant $W \ge 1$. This improves the recent work of Feldotto et al.[2017] and Giannakopoulos et al. [2022] that showed efficient algorithms for computing $d^{d+o(d)}$-approximate pure Nash equilibria.
