Network pricing: How to induce optimal flows under strategic link operators
Author
dc.contributor.author
Correa, José
Author
dc.contributor.author
Guzmán, Cristóbal
Author
dc.contributor.author
Lianeas, Thanasis
Author
dc.contributor.author
Nikolova, Evdokia
Author
dc.contributor.author
Schröder, Marc
Admission date
dc.date.accessioned
2019-05-31T15:20:00Z
Available date
dc.date.available
2019-05-31T15:20:00Z
Publication date
dc.date.issued
2018
Identifier
dc.identifier.other
10.1145/3219166.3219190
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/169424
Abstract
dc.description.abstract
Network pricing games provide a framework for modeling real-world se ings with two types of strategic
agents: owners (operators) of the network and users of the network. Owners of the network post a price for
usage of the link they own so as to a ract users and maximize pro t; users of the network select routes based
on price and level of use by other users. We point out that an equilibrium in these games may not exist, may
not be unique and may induce an arbitrarily ine cient network performance.
Our main result is to observe that a simple regulation on the network owners market solves all three issues
above. Speci cally, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators
can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users’
game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with
these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize
total users’ payments and we provide a linear program that does this. We obtain multiplicative approximation
results compared to the optimal total users’ payments for arbitrary networks with polynomial latencies of
bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of
the network. Lastly, we show how the same mechanism of se ing appropriate caps on the allowable prices
extends to the model of elastic demands.