On the Coincidence of the Shapley Value and the Nucleolus in Queueing Problems

Abstract

Given a group of agents to be served in a facility, the

queueing problem is concerned with finding the order to serve

agents and the (positive or negative) monetary compensations

they should receive. As shown in Maniquet (2003), the minimal

transfer rule coincides with the Shapley value of the game

obtained by defining the worth of each coalition to be the

minimum total waiting cost incurred by its members under the

assumption that they are served before the non-coalitional

members. Here, we show that it coincides with the nucleolus of

the same game. Thereby, we establish the coincidence of the

Shapley value and the nucleolus for queueing problems. We also

investigate the relations between the minimal transfer rule and

other rules discussed in the literature.