Computing Approximate Nash Equilibria in Network Congestion Games
详细信息 查看全文
- 作者：Andreas Emil Feldmann ; Heiko R?glin ; Berthold V?cking
- 刊名：Lecture Notes in Computer Science
- 出版年：2008
- 出版时间：2008
- 年：2008
- 卷：5058
- 期：1
- 页码：209-220
- 全文大小：473.0 KB
文摘
We consider the problem of computing ε-approximate Nash equilibria in network congestion games. The general problem is known to be PLS-complete for every ε> 0, but the reductions are based on artificial and steep delay functions with the property that already two players using the same resource cause a delay that is significantly larger than the delay for a single player. We consider network congestion games with delay functions such as polynomials, exponential functions, and functions from queuing theory. We analyse which approximation guarantees can be achieved for such congestion games by the method of randomised rounding. Our results show that the success of this method depends on different criteria depending on the class of functions considered. For example, queuing theoretical functions admit good approximations if the equilibrium load of every resource is bounded away appropriately from its capacity.