The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources

Bergantiños, Gustavo and Navarro, Adriana (2019): The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources.

Abstract

We consider minimum cost spanning tree problems with multiple sources. We propose a cost allocation rule based on a painting procedure. Agents paint the edges on the paths connecting them to the sources. We prove that the painting rule coincides with the folk rule. Finally, we provide an axiomatic characterization.

• Item Type: MPRA Paper
• Language: English
• Keywords: }minimum cost spanning tree problems with multiple sources, painting rule, axiomatic characterization.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Bergantiños, G., Chun, Y., Lee, E., Lorenzo, L., 2017. The folk rule for minimum cost spanning tree problems with multiple sources. Mimeo, Universidade de Vigo.

Bergantiños, G., Gomez-Rua, M., Llorca, N., Pulido, M., Sanchez-Soriano, J., 2014. A new rule for source connection problems. European Journal of Operational Research 234 (3), 780–788.

Bergantiños, G., Kar, A., 2010. On obligation rules for minimum cost spanning tree problems. Games and Economic Behavior 69 (2), 224–237.

Bergantiños, G., Lorenzo, L., Lorenzo-Freire, S., 2010. The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Social Choice and Welfare 34 (4), 695–710.

Bergantiños, G., Lorenzo, L., Lorenzo-Freire, S., 2011. A generalization of obligation rules for minimum cost spanning tree problems. European Journal of Operational Research 211 (1), 122–129.

Bergantiños, G., Vidal-Puga, J., 2007. A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137 (1), 326–352.

Bergantiños, G., Vidal-Puga, J., 2009. Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics 45 (1-2), 38–42.

Bird, C. G., 1976. On cost allocation for a spanning tree: a game theoretic approach. Networks 6 (4), 335–350.

Branzei, R., Moretti, S., Norde, H., Tijs, S., 2004. The p-value for cost sharing in minimum cost spanning tree situations. Theory and Decision 56 (1), 47–61.

Dutta, B., Kar, A., 2004. Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior 48 (2), 223–248.

Kruskal, J. B., 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society 7 (1), 48–50.

Kuipers, J., 1997. Minimum cost forest games. International Journal of Game Theory 26 (3), 367–377.

Norde, H., Moretti, S., Tijs, S., 2004. Minimum cost spanning tree games and population monotonic allocation schemes. European Journal of Operational Research 154 (1), 84–97.

Prim, R. C., 1957. Shortest connection networks and some generalizations. Bell Labs Technical Journal 36 (6), 1389–1401.

Rosenthal, E. C., 1987. The minimum cost spanning forest game. Economics Letters 23 (4), 355–357.

Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175 (1), 121–134.