CMU-CS-13-109
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-13-109

Priority Pricing in Queues with a Continuous
Distribution of Customer Valuations

Sherwin Doroudi*, Mustafa Akan*, Mor Harchol-Balter,
Jeremy Karp*, Christian Borgs**, Jennifer T. Chayes**

May 2013

CMU-CS-13-109.pdf


Keywords: Queues, priority, pricing, mechanism design, incentives

We consider a service provider facing a continuum of delay-sensitive strategic customers. The service provider maximizes revenue by charging customers for the privilege of joining an M/G/1 queue and assigning them service priorities. Each customer has a valuation for the service, with a waiting cost per unit time that is proportional to their valuation; customer types are drawn from a continuous distribution and are unobservable to the service provider. We illustrate how to find revenue-maximizing incentive-compatible priority pricing menus, where the firm charges higher prices for higher queueing priority. We show that our proposed priority pricing scheme is optimal across all incentive-compatible pricing policies whenever the customer valuation distribution is regular. We compute the resulting price menus and priority allocations in closed form when customer valuations are drawn from Exponential, Uniform, or Pareto distributions. We find revenues in closed form for the special case of the M/M/1 queue, and compute revenues in the more general setting numerically. We compare our priority pricing scheme to the best fixed pricing scheme, as well as an idealized pricing scheme where customers always reveal their valuation. We observe the impact of service requirement variability on revenue and prices. We also illustrate how to create the optimal discrete priority pricing menu when the service provider is restricted to offering a finite number of priority classes.

35 pages

*Tepper School of Business, Carnegie Mellon University
**Microsoft Research



Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu