The consistency principle in the reordering problem

We investigate implications of the consistency principle for the reordering problem, also known as the queueing problem with an initial queue. The consistency principle specifies how an allocation rule should respond when an agent leaves the problem. We introduce four different consistency properties for the reordering problem and characterize three allocations rules, the pairwise equal-splitting rule (Curiel et al. Eur J Operat Res 40:344-351, 1989), the maximum price rule and the minimum price rule. Balanced consistency requires that for each pair of agents i and j, the impact on agent i’s net utility when agent j leaves the initial queue and the agents behind her move forward by one position, should be equal to the impact on agent j’s net utility when agent i leaves the initial queue and the agents behind her move forward by one position. Balanced cost reduction requires that if an agent leaves the initial queue and the agents behind her move forward by one position, then the total net utilities of the remaining agents should be reduced by the amount equal to the net utility of the departing agent. Smallest-cost consistency (respectively, largest-cost consistency) requires that if an agent with the smallest (respectively, largest) unit waiting cost leaves the initial queue and the agents behind her move forward by one position, then the net utilities of the remaining agents should not be affected. We show that either balanced consistency or balanced cost reduction, together with the three basic properties of queue-efficiency, budget-balance and Pareto indifference, characterizes the pairwise equal-splitting rule. On the other hand, together with the three basic properties, smallest-cost consistency characterizes the maximum price rule and largest-cost consistency the minimum price rule.