Nonempty Core of Minimum Cost Spanning Tree Games with Revenues

A minimum cost spanning tree problem analyzes the way to efficiently connect agents to a source when they are located at different places. Once the efficient tree is obtained, the total cost should be allocated among the involved agents in a fair and stable manner. It is well known that there always exist allocations in the core of the cooperative game associated to the minimum cost spanning tree problem (Bird, 1976; Granot and Huberman, 1981). Est´evez-Fern´andez and Reijnierse (2014) investigate minimum cost spanning tree problems with revenues and show that the cost-revenue game may have empty core. They provide a sufficient condition to ensure the non-emptiness of the r -core for elementary cost problems; that is, minimum cost spanning tree problems in which every connection cost can take only two values (low or high cost). We show that this condition is not necessary and obtain a family of cost-revenue games ( simple problems, Subiza et al. (2016)) in which the non-emptiness of the r -core is ensured