Competitive routing over time |
| |
Authors: | Martin Hoefer Vahab S. Mirrokni |
| |
Affiliation: | a Department of Computer Science, RWTH Aachen University, Germanyb Google Research New York, USAc Department of Computer Science, University of Bonn, Germanyd Computer Science Department, University of Southern California, USA |
| |
Abstract: | Congestion games are a fundamental and widely studied model for selfish allocation problems like routing and load balancing. An intrinsic property of these games is that players allocate resources simultaneously and instantly. This is particularly unrealistic for many network routing scenarios, which are one of the prominent application scenarios of congestion games. In many networks, load travels along routes over time and allocation of edges happens sequentially. In this paper, we consider two frameworks that enhance network congestion games with a notion of time. We introduce temporal network congestion games that are based on coordination mechanisms — local policies that allow to sequentialize traffic on the edges. In addition, we consider congestion games with time-dependent costs, in which travel times are fixed but quality of service of transmission varies with load over time. We study existence and complexity properties of pure Nash equilibria and best-response strategies in both frameworks for the special case of linear latency functions. In some cases our results can be used to characterize convergence properties of various improvement dynamics, by which the population of players can reach equilibrium in a distributed fashion. |
| |
Keywords: | Nash equilibrium Coordination Mechanism Routing Network Congestion Games Convergence Equilibrium Computation |
本文献已被 ScienceDirect 等数据库收录! |
|