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

Duygu Yengin ()
Additional contact information
Duygu Yengin: School of Economics, University of Adelaide

No 2009-28, School of Economics and Public Policy Working Papers from University of Adelaide, School of Economics and Public Policy

Abstract: 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).

Keywords: fixed-route traveling salesman games; routing games; appointment games; the Shapley value; the core; transferable-utility games; merging and splitting proofness; equal impact; networks; cost allocation. (search for similar items in EconPapers)
Pages: 36 pages
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://media.adelaide.edu.au/economics/papers/doc/wp2009-28.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:adl:wpaper:2009-28

Access Statistics for this paper

More papers in School of Economics and Public Policy Working Papers from University of Adelaide, School of Economics and Public Policy Contact information at EDIRC.
Bibliographic data for series maintained by Qazi Haque ().