The minimum cost shortest-path tree game |
| |
Authors: | F R Fernández J Puerto |
| |
Institution: | 1. Institute of Mathematics (IMUS), Seville University, Seville, Spain
|
| |
Abstract: | 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 (Discrete Appl. Math. 65:275?C284, 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|