The Library
Sensitivity of wardrop equilibria
Tools
Englert, Matthias, Franke, T. and Olbrich, L. (2008) Sensitivity of wardrop equilibria. In: Monien, Burkhard and Schroeder, Ulf-Peter, (eds.) Algorithmic game theory. Lecture Notes in Computer Science, Volume 4997 . Springer Verlag, pp. 158-169. ISBN 9783540793083
|
PDF
fulltext21.pdf - Requires a PDF viewer. Download (506Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-540-79309-0_15
Abstract
We study the sensitivity of equilibria in the well-known game theoretic traffic model due to Wardrop. We mostly consider single-commodity 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 multi-commodity 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, Engineering and Medicine > 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, Ulf-Peter | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Volume 4997 | ||||
Page Range: | pp. 158-169 | ||||
DOI: | 10.1007/978-3-540-79309-0_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 |