The Library
Sensitivity of wardrop equilibria
Tools
Englert, Matthias, Franke, T. and Olbrich, L.. (2010) Sensitivity of wardrop equilibria. Theory of Computing Systems, Volume 47 (Number 1). pp. 314. ISSN 14324350
PDF
fulltext18.pdf  Published Version Restricted to Repository staff only  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (420Kb) 
Official URL: http://dx.doi.org/10.1007/s0022400991964
Abstract
We study the sensitivity of equilibria in the wellknown game theoretic traffic model due to Wardrop. We mostly consider singlecommodity networks. Suppose, given a unit demand flow at Wardrop equilibrium, one increases the demand by ε or removes an edge carrying only an εfraction of flow. We study how the equilibrium responds to such an εchange.
Our first surprising finding is that, even for linear latency functions, for every ε>0, there are networks in which an εchange causes every agent to change its path in order to recover equilibrium. Nevertheless, we can prove that, for general latency functions, the flow increase or decrease on every edge is at most ε.
Examining the latency at equilibrium, we concentrate on polynomial latency functions of degree at most p with nonnegative coefficients. We show that, even though the relative increase in the latency of an edge due to an εchange in the demand can be unbounded, the path latency at equilibrium increases at most by a factor of (1+ε) p . The increase of the price of anarchy is shown to be upper bounded by the same factor. Let us remark that all our bounds are tight.
For the multicommodity case, we present examples showing that neither the change in edge flows nor the change in the path latency can be bounded.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Series Name:  Lecture Notes in Computer Science  
Journal or Publication Title:  Theory of Computing Systems  
Publisher:  Springer New York LLC  
ISSN:  14324350  
Official Date:  1 July 2010  
Dates: 


Volume:  Volume 47  
Number:  Number 1  
Page Range:  pp. 314  
Identification Number:  10.1007/s0022400991964  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  Deutsche Forschungsgemeinschaft (DFG)  
Grant number:  WE 2842/1 (DFG), GK/1298 “AlgoSyn” (DFG)  
Version or Related Resource:  A preliminary version of this paper appeared in Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), 2008.  
URI:  http://wrap.warwick.ac.uk/id/eprint/47511 
Request changes or add full text files to a record
Actions (login required)
View Item 