Appointment Games in Fixed-Route Traveling Salesman Problems and the Shapley Value

Starting from her home, a service provider visits several customers, following a predetermined route, and returns home after all customers are visited. The problem is to find a fair allocation of the total cost of this tour among the customers served. A transferable-utility cooperative game can be associated with this cost allocation problem. We introduce a new class of games, which we refer as the fixed-route traveling salesman games with appointments. We study the Shapley Value in this class and show that it is in the core. Our first characterization of the Shapley value involves a property which requires that sponsors do not benefit from mergers, or splitting into a set of sponsors. Our second theorem involves a property which requires that the cost shares of two sponsors who get connected are equally effected. We also show that except for our second theorem, none of our results for appointment games extend to the class of routing games (Potters et al, 1992).