Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators

Abstract

Network pricing games provide a framework for modeling real-world settŠings with two types of strategicagents: owners (operators) of the network and users of the network. Owners of the network post a price forusage of the link they own so as to attŠract users and maximize profi€t; users of the network select routes basedon price and level of use by other users. We point out that an equilibrium in these games may not exist, maynot be unique and may induce an arbitrarily inefficient network performance.Our main result is to observe that a simple regulation on the network owners market solves all three issuesabove. Speci€fically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operatorscan 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 withthese properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimizetotal users’ payments and we provide a linear program that does this. We obtain multiplicative approximationresults compared to the optimal total users’ payments for arbitrary networks with polynomial latencies ofbounded degree, while in the single-commodity case we obtain a bound that only depends on the topology ofthe network. Lastly, we show how the same mechanism of settŠing appropriate caps on the allowable pricesextends to the model of elastic demands.