2006 | OriginalPaper | Buchkapitel
Price of Anarchy for Polynomial Wardrop Games
verfasst von : Dominic Dumrauf, Martin Gairing
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this work, we consider
Wardrop games
where traffic has to be routed through a shared
network
. Traffic is allowed to be split into arbitrary pieces and can be modeled as network flow. For each edge in the network there is a latency function that specifies the time needed to traverse the edge given its congestion. In a
Wardrop equilibrium
, all used paths between a given source-destination pair have equal and minimal latency.
In this paper, we allow for
polynomial latency functions
with an upper bound
d
and a lower bound
s
on the degree of all monomials that appear in the polynomials. For this environment, we prove upper and lower bounds on the
price of anarchy
.