The Library
Fast convergence to wardrop equilibria by adaptive sampling methods
Tools
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. doi:10.1137/090746720 ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/090746720
Abstract
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, Engineering and Medicine > 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 | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Volume 39 | ||||
Number: | Number 8 | ||||
Number of Pages: | 36 | ||||
Page Range: | pp. 3700-3735 | ||||
DOI: | 10.1137/090746720 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Funder: | Sixth Framework Programme (European Commission) (FP6), Deutsche Forschungsgemeinschaft (DFG) | ||||
Grant number: | 001907 (FP6), Vo889/1-2, 1-3 (DFG) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |