Pricing and Congestion Management in a Network With Heterogeneous Users

We consider an economic model for a communication network with utility-maximizing elastic users who adapt to congestion by adjusting their fl ows. Users are heterogeneous with respect to both the utility they attach to different levels of flow and their sensitivity to delay or other measures of congestion. Following Kelly at al [4], we introduce dynamical rate-control algorithms, based on the users' utility functions and delay sensitivities, as well as tolls charged by the system, and examine their behavior. We show that allowing heterogeneity with respect to delay sensitivity introduces a fundamental non-convexity into the congestion-cost functions. As a result, there are typically multiple stationary points. Hence marginal-cost pricing - equating users' marginal utilities to their marginal costs - may identify a local maximum or even a saddle point, rather than a global maximum. We present a simple example in which the only interior stationary point is a saddlepoint, which is dominated by all the single-user optimal allocations. Thus, heterogeneity of users can lead to class dominance: a situation in which the system is dominated by a single user or class of users under an optimal flow allocation. The dynamical-system rate-control algorithm may converge to a local rather than global maximum, depending on the starting point