A Panting Rule in Minimum Cost Spanning Tree Problems with Multiple Sources
Consider that a group of agents is interested in some service which is provided by several suppliers, also called sources. The connections have associated a cost and agents do not care whether they are connected directly or indirectly to such sources, but they want to be connected to all of them. This situation is a generalization of the classical minimum cost spanning tree problem where there is a unique source. Given a cost spanning tree problem with multiple sources, the first issue to solve is to look for the least costly connection (a tree) that provides all the agents with the resource. Such tree can be obtained, in polynomial time, using the same algorithms as in the classical problem (for instance, Kruskal (1956) and Prim (1957)). The second question we must answer is how to allocate the cost of the obtained tree among the agents. This issue has been studied in the economic literature for similar problems. For the case that is studied in this research, Bergantiños et al (2016) extend different definitions of the folk rule, a well‐known and widely studied solution for classical minimum cost spanning tree problems, to this new context. In Bergantiños and Lorenzo (2016) a set of several rules obtained through Kruskal's algorithm is defined and
characterized. Under a general framework of connection problems involving a single source, Bergantiños et al (2014) propose a cost distribution rule, called the painting rule. In addition to analyzing the properties of this rule and characterizing it, they show that for the painting rule coincides with the folk rule on the classical minimal cost spanning tree problem. The objective of this work is to extend the painting rule, considering the same model as in Bergantiños et al (2016) and to prove that it coincides with the folk rule in the case of multiple sources.
-
Adriana Navarro Ramos Universidade de Vigo, Spain
