The Library
Sensitivity of wardrop equilibria
Tools
Englert, Matthias, Franke, T. and Olbrich, L. (2008) Sensitivity of wardrop equilibria. In: Monien, Burkhard and Schroeder, UlfPeter, (eds.) Algorithmic game theory. Lecture Notes in Computer Science, Volume 4997 . Springer Verlag, pp. 158169. ISBN 9783540793083

PDF
fulltext21.pdf  Requires a PDF viewer. Download (506Kb)  Preview 
Official URL: http://dx.doi.org/10.1007/9783540793090_15
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. Both bounds are shown to be tight.
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:  Book Item  

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  
Publisher:  Springer Verlag  
ISBN:  9783540793083  
Book Title:  Algorithmic game theory  
Editor:  Monien, Burkhard and Schroeder, UlfPeter  
Official Date:  2008  
Dates: 


Volume:  Volume 4997  
Page Range:  pp. 158169  
DOI:  10.1007/9783540793090_15  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year