Fischer, Simon, Raecke, Harald and Voecking, Berthold. (2010) Fast convergence to wardrop equilibria by adaptive sampling methods. SIAM Journal on Computing, Vol.39 (No.8). pp. 3700-3735. ISSN 0097-5397

Full text not available from this repository.

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 > Computer Science
Journal or Publication Title:	SIAM Journal on Computing
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0097-5397
Date:	2010
Volume:	Vol.39
Number:	No.8
Number of Pages:	36
Page Range:	pp. 3700-3735
Identification Number:	10.1137/090746720
Status:	Peer Reviewed
Publication Status:	Published
Funder:	EU, DFG
Grant number:	001907 (DELIS), Vo889/1-2, 1-3
URI:	http://wrap.warwick.ac.uk/id/eprint/4551

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item