Dual bounds of a service level assignment problem with applications to efficient pricing

We extend the classical continuous assignment problem to allow for the assignment of multiple service levels. This formulation encompasses an important class of lead-time allocation problems in queues where congestion may impact feasible assignments of customers to service levels. Through analysis of the dual program we show a number of results which include existence of welfare maximizing prices for a more general set of operational settings than previously reported. Further, we show that the duality gap provides a bound on welfare loss that can be calculated from operational information in a service system with priced service levels. For systems where total expected delay is a convex function of the customer arrival rate, this bound is shown to be an upper bound on the difference between current and maximum welfare and provide a sufficient condition for maximizing welfare. We demonstrate how this bound may be used to evaluate and improve a current set of prices through use as a measure to guide an adaptive pricing algorithm. The adaptive pricing algorithm is shown through computational experiments to find pricing schemes which deliver near optimal welfare.