Abstract
Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: users of the network and owners (operators) of the network. Owners of the network post a price for usage of the link they own; users of the network select routes based on price and level of use by other users. The challenge in these games is that there are two levels of competition: one, among the owners to attract users to their link so as to maximize profit; and second, among users of the network to select routes that are cheap yet not too congested. Interestingly, we observe that: (i) an equilibrium may not exist; (ii) it might not be unique; and (iii) the network performance at equilibrium can be arbitrarily inefficient.
Our main result is to observe that a slight regulation on the network owners market solves all three issues above. Specifically, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge then: the game among the link operators has a unique 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. We then ask, can we compute great tolls that minimize total users’ payments? We show that this optimization problem reduces to a linear program in the case of single-commodity series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a surprising bound, which only depends on the topology of the network.