Pricing a Congestible Network: Efficiency and Implementability

Welfare-efficient pricing of congestible resources is particularly difficult in a network setting. Conceptually, deriving the optimal prices can be thought of as a two-step process: First, one determines the optimal allocation of network resources to service requests. Second, one computes the optimal price for each job as the marginal congestion externality that it imposes on all other users (evaluated at the optimal allocation.) These steps require knowledge of the resource's delay performance function and cost structure, and information about demand functions and delay sensitivities. Therefore, the information required to set the optimal prices dramatically increases in a network with multiple resources and multiple heterogeneous customer types, compared to the single-resource case. Even if the optimal (efficient) prices can be formulated in theory, it is not clear how (or even whether) they can be computed and implemented in practice. An important issue in (data) network pricing research therefore is to further examine the nature of this trade-off between optimality and implementability. Existing research in network pricing is commonly divided into centralized and decentralized approaches. The former assumes the presence of a provider who quotes prices, the latter operates as a market in which individuals bid for services. While the decentralized approach can solve the information problem in theory, it imposes a substantial computational burden on network users, whose bids are potentially very complex, as they depend not only on their willingness-to-pay but also on their delay sensitivities. Further, in auction-based mechanisms the task of determining the optimal prices is computationally more intense, and the structure of the resulting charges is likely to be more complex than in quote-based schemes. Since transaction values are small in data communication settings, and the computational burden for each transaction may be substantial, it is unclear whether the decentralized approach is justified. This suggests that research efforts should continue to also be devoted to quote-based pricing. Broadly, the task is to evaluate under what conditions the centralized approach yields a (near-)optimal allocation under reasonable information requirements. This paper contributes to this task by studying the question: How implementable is quote-based efficient pricing for a congestible network? We consider a network performance model for a reservationless, packet-switched data communications network (such as the current Internet) consisting of multiple single-server finite-capacity resources. There are multiple customer classes, which may differ in their demand curve (which are general decreasing), their delay cost structure, and the set of network resources they demand. Customers generate Poisson message streams at rates that depend on their valuations of data messages, their delay-sensitivities, and on the prices and delay levels in the system. The marginal cost of service is zero for given capacity. Resource capacity costs are linear. In this setting, we derive the optimal prices and network allocation under full information of demand curves and delay cost structures. We then examine the implementability of the optimal prices using the criteria of information availability, simplicity and separability. The welfare-efficient prices are found to be the same as in the absence of delay costs, and therefore require no knowledge of the demand functions, the delay cost structure, or the optimal congestion level. The price of a job is equal to the sum of the marginal link capacity costs along its path. These prices therefore satisfy the information availability and the simplicity criterion. They are also fully separable, since the per-link charges are the same as if each link were operating in isolation.