Differential Join Prices for Parallel Queues: Social Optimality, Dynamic Pricing Algorithm and Applications to Internet Pricing

V. Borkar, P. Dube, D. Manjunath


We consider a system of identical parallel queues served by a single server and distinguished only by the price charged at entry. A Poisson stream of customers joins the queue by a greedy policy that minimizes a `disutility' that combines price and congestion. A special case of linear disutility is analyzed for which it is shown that the individually optimal greedy queue join policy is nearly socially optimal. For this queueing system, a Markov decision theoretic framework is formulated for dynamic pricing in the general case. This queueing system has application in the pricing of Internet services.