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.
|Place of Publication||Tilburg|
|Number of pages||18|
|Publication status||Published - 2003|
|Name||CentER Discussion Paper|
- game theory
- traveling salesman problem