论文标题
改善交通拥堵的近似纯纳什平衡
Improving approximate pure Nash equilibria in congestion games
论文作者
论文摘要
拥堵游戏构成了一类重要的游戏，可以模拟不同用户的资源分配。 Caragiannis等人一般可以计算精确的纯纳什平衡或什至近似纯纳什平衡。 （2011）提出了一种多项式时间算法，该算法计算A（$ 2 +ε$） - 具有线性成本函数的游戏的近似纯Nash Equilibria，以及多项式成本功能的进一步结果。我们表明，通过允许在最佳响应动力学期间使用的成本函数与整体目标函数不同，可以通过对其算法进行看似简单的修改，从而将该因素提高到$（1.61+ε）$，并通过对其算法进行看似简单的修改，进一步改善了多项式成本函数的结果。有趣的是，我们对算法的修改也扩展到有效地计算出具有任意非淘汰资源成本功能的游戏中的近似纯Nash平衡。此外，我们的分析还展示了一种有趣的方法，可以最佳地计算普遍的载荷税，并使用线性编程二元性二元性证明在普遍税收下对POA的紧密界限，例如，线性拥塞游戏为2.012，以及多项式成本功能的进一步结果。尽管我们的方法的结果比Bilò和Vinci（2016）中的结果弱，但我们指出，我们的成本功能在本地可以计算，与Bilò和Vinci（2016）相反，我们的成本功能与游戏的实际实例无关。
Congestion games constitute an important class of games to model resource allocation by different users. As computing an exact or even an approximate pure Nash equilibrium is in general PLS-complete, Caragiannis et al. (2011) present a polynomial-time algorithm that computes a ($2 + ε$)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to $(1.61+ε)$ and further improved results for polynomial cost functions, by a seemingly simple modification to their algorithm by allowing for the cost functions used during the best response dynamics be different from the overall objective function. Interestingly, our modification to the algorithm also extends to efficiently computing improved approximate pure Nash equilibria in games with arbitrary non-decreasing resource cost functions. Additionally, our analysis exhibits an interesting method to optimally compute universal load dependent taxes and using linear programming duality prove tight bounds on PoA under universal taxation, e.g, 2.012 for linear congestion games and further results for polynomial cost functions. Although our approach yield weaker results than that in Bilò and Vinci (2016), we remark that our cost functions are locally computable and in contrast to Bilò and Vinci (2016) are independent of the actual instance of the game.
