On the Core of Multiple Longest Traveling Salesman Games

M.A. Estevez Fernandez, P.E.M. Borm, H.J.M. Hamers

Research output: Working paperDiscussion paperOther research output

266 Downloads (Pure)

Abstract

In this paper we introduce multiple longest traveling salesman (MLTS) games. An MLTS game arises from a network in which a salesman has to visit each node (player) precisely once, except its home location, in an order that maximizes the total reward.First it is shown that the value of a coalition of an MLTS game is determined by taking the maximum of suitable combinations of one and two person coalitions.Secondly it is shown that MLTS games with ¯ve or less players have a nonempty core.However, a six player MLTS game may have an empty core.For the special instance where the reward between a pair of nodes is equal to 0 or 1, we provide relations between the structure of the core and the underlying network.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages18
Volume2003-127
Publication statusPublished - 2003

Publication series

NameCentER Discussion Paper
Volume2003-127

Keywords

  • game theory
  • traveling salesman problem
  • games
  • core

Cite this

Estevez Fernandez, M. A., Borm, P. E. M., & Hamers, H. J. M. (2003). On the Core of Multiple Longest Traveling Salesman Games. (CentER Discussion Paper; Vol. 2003-127). Operations research.