Coincidence of the Shapley value and the Nucleolus in the Appointment Problem

Abstract

The fixed-route traveling salesman problem with appointments, simply the appointment problem, is concerned with the following situation. A traveler makes a scheduled trip along a set of sponsors. If a sponsor in the route cancels, the traveler returns home and moves on to the next scheduled place from home. The cost of her trip has to be shared by the sponsors. We are interested in finding a way of dividing the total cost of this appointment problem among sponsors by applying solutions developed in the cooperative game theory. On this class of problems, we show the coincidence of three well-known solutions of the cooperative game theory, the nucleolus, the Shapley value, and the τ-value.