A non-cooperative approach to the folk rule in minimum cost spanning tree problems

This paper deals with the problem of finding a way to distribute the cost of a minimum cost spanning tree problem between the players. A rule that assigns a payoff to each player provides this distribution. An optimistic point of view is considered to devise a cooperative game. Following this optimistic approach, a sequential game provides this construction to define the action sets of the players. The main result states the existence of a unique cost allocation in subgame perfect equilibria. This cost allocation matches the one suggested by the folk rule.Agencia Estatal de Investigación | Ref. ECO2017-82241-RAgencia Estatal de Investigación | Ref. ECO2016-77200- PAgencia Estatal de Investigación | Ref. ECO2017-87245-RAgencia Estatal de Investigación | Ref. PID2021-128228NB-I00Generalitat Valenciana | Ref. AICO/2021/257Xunta de Galicia | Ref. ED431B 2019/3