Fast convergence to wardrop equilibria by adaptive sampling methods
Fischer, Simon, Raecke, Harald and Voecking, Berthold. (2010) Fast convergence to wardrop equilibria by adaptive sampling methods. SIAM Journal on Computing, Volume 39 (Number 8). pp. 3700-3735. ISSN 0097-5397Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/090746720
We study the question of whether a large population of agents in a traffic network is able to converge to an equilibrium quickly. To that end, we consider a round-based variant of the Wardrop model. Every agent is allowed to reroute its traffic once in a while with the aim of finding a path with minimal latency. As a first result we find that using a replication policy which allows agents to imitate others gives rise to a bicriterial approximate equilibrium very quickly. In particular, the time bound depends logarithmically on the ratio between minimum and maximum latency but is otherwise independent of the network size. In the single-commodity case, this bicriteria approximate equilibrium has an intuitive interpretation as a state in which almost all agents are almost happy. This kind of approximate equilibrium, however, is transient. In order to reach a global approximation, we need to add an exploration component which enables the agents to explore the strategy space independently of the other agents. Although it can be shown that, when used exclusively, exploration policies imply an exponential lower bound, applying exploration carefully allows the population to approximate the global Wardrop equilibrium in polynomial time. Since the distributed and concurrent fashion of our policies bears the risk of oscillating behavior, we must take into account the steepness of the latency functions. We show that the relevant parameter is elasticity, a parameter closely related to the polynomial degree. This improves significantly over earlier results which depend on the absolute slope and therefore have a pseudopolynomial flavor.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science|
|Library of Congress Subject Headings (LCSH):||Adaptive routing (Computer network management), Equilibrium (Economics), Network analysis (Planning) -- Mathematical models, Routers (Computer networks), Convergence (Telecommunication)|
|Journal or Publication Title:||SIAM Journal on Computing|
|Publisher:||Society for Industrial and Applied Mathematics|
|Number of Pages:||36|
|Page Range:||pp. 3700-3735|
|Funder:||Sixth Framework Programme (European Commission) (FP6), Deutsche Forschungsgemeinschaft (DFG)|
|Grant number:||001907 (FP6), Vo889/1-2, 1-3 (DFG)|
Actions (login required)