The minimum cost shortest‐path tree game

A minimum cost shortest‐path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum. In this paper, we adapt the algorithm of Hansen and Zheng (1996) to the case of acyclic directed graphs to find a minimum cost shortest‐path tree in order to be applied to the cost allocation problem associated with a cooperative minimum cost shortest‐path tree game. In addition, we analyze a non‐cooperative game based on the connection problem that arises in the above situation. We prove that the cost allocation given by an ‘à la’ Bird rule provides a core solution in the former game and that the strategies that induce those payoffs in the latter game are Nash equilibrium.