Cooperative games for minimum cost spanning tree problems

Bergantiños, Gustavo and Vidal-Puga, Juan (2020): Cooperative games for minimum cost spanning tree problems.

Abstract

Minimum cost spanning tree problems are well known problems in the Operations Research literature. Some agents, located at different geographical places, want a service provided by a common supplier. Agents will be served through costly connections. Some part of the literature has focused, mainly, in studying how to allocate the connection cost among the agents. We review the papers that have addressed the allocation problem using cooperative game theory.

• Item Type: MPRA Paper
• Language: English
• Keywords: minimum cost spanning tree problems; cooperative games; core; Shapley value
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Aarts, H. (1994). Minimum cost spanning tree games and set games. PhD thesis, University of Twente.

Aarts, H. and Driessen, T. (1993). The irreducible core of a minimum cost spanning tree game. Methods and Models of Operations Research, 38:163–174.

Ando, K. (2012). Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases. Japan Journal of Industrial and Applied Mathematics, 29(3):385–400.

Ando, K. and Kato, S. (2010). Reduction of ultrametric minimum cost spanning tree games to cost allocation games on rooted trees. Journal of the Operations Research Society of Japan, 53(1):62–68.

Aumann, R. J. and Maschler, M. (1985). Game theoretic analysis of a bankruptcy problem from the Talmud. Journal of Economic Theory, 36:195–213.

Bahel, E. and Trudeau, C. (2017). Minimum incoming cost rules for arborescences. Social Choice and Welfare, 49(2):287–314.

Bergantiños, G., Chun, Y., Lee, E., and Lorenzo, L. (2020). The folk rule for minimum cost spanning tree problems with multiple sources. Mimeo, Repec.

Bergantiños, G. and Gómez-Rúa, M. (2010). Minimum cost spanning tree problems with groups. Economic Theory, 43(2):227–262.

Bergantiños, G. and Gómez-Rúa, M. (2015). An axiomatic approach in minimum cost spanning tree problems with groups. Annals of Operations Research, 225(1):45–63.

Bergantiños, G., Gómez-Rúa, M., Llorca, N., Pulido, M., and Sánchez-Soriano, J. (2012). A cost allocation rule for k-hop minimum cost spanning tree problems. Operations Research Letters, 40(1):52–55.

Bergantiños, G., Gómez-Rúa, M., Llorca, N., Pulido, M., and Sánchez-Soriano, J. (2014). A new rule for source connection problems. European Journal of Operational Research, 234(3):780–788.

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

Bergantiños, G. and Lorenzo, L. (2004). A non-cooperative approach to the cost spanning tree problem. Mathematical Methods of Operations Research, 59(3):393–403.

Bergantiños, G. and Lorenzo, L. (2005). Optimal equilibria in the non-cooperative game associated with cost spanning tree problems. Annals of Operations Research, 137(1):101–115.

Bergantiños, G. and Lorenzo, L. (2008). Non cooperative cost spanning tree problems with budget restrictions. Naval Research Logistics, 55(8):747–757.

Bergantiños, G. and Lorenzo, L. (2020). Cost additive rules in minimum cost spanning tree problems with multiple sources. Annals of Operations Research, forthcoming.

Bergantiños, G., Lorenzo, L., and 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., and 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. and Lorenzo-Freire, S. (2008). A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems. Economic Theory, 35(3):523–538.

Bergantiños, G. and Lorenzo-Freire, S. (2008). “Optimistic” weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research, 185(1):289–298.

Bergantiños, G. and Moreno-Ternero, J. D. (2015). The axiomatic approach to the problem of sharing the revenue from museum passes. Games and Economic Behavior, 89:78–92.

Bergantiños, G. and Moreno-Ternero, J. D. (2020). Sharing the revenues from broadcasting sport events. Management Science, 66(6):2417–2431.

Bergantiños, G. and Navarro-Ramos, A. (2019). A characterization of the folk rule for multi-source minimal cost spanning tree problems. Operations Research Letters, 47:366–370.

Bergantiños, G. and Navarro-Ramos, A. (2019). The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources. Mathematical Social Sciences, 99:43–48.

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

Bergantiños, G. and Vidal-Puga, J. (2007). The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory, 36(2):223–239.

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

Bergantiños, G. and Vidal-Puga, J. (2010). Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms. European Journal of Operational Research, 201(3):811–820.

Bergantiños, G. and Vidal-Puga, J. (2011). The folk solution and Boruvka’s algorithm in minimum cost spanning tree problems. Discrete Applied Mathematics, 159(12):1279–1283.

Bergantiños, G. and Vidal-Puga, J. (2015). Characterization of monotonic rules in minimum cost spanning tree problems. International Journal of Game Theory, 44(4):835–868.

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

Bogomolnaia, A. and Moulin, H. (2010). Sharing a minimal cost spanning tree: Beyond the folk solution. Games and Economic Behavior, 69(2):238–248.

Borm, P., Hamers, H., and Hendrickx, R. (2001). Operations research games: a survey. Top, 9(2):139–216.

Borůvka, O. (1926). O jistém problému minimálnı́m (about a certain minimal problem). Práce moravské přı́rodovědecké společnosti v Brne, 3:37–58. In Czech.

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

Chun, Y. and Lee, J. (2012). Sequential contributions rules for minimum cost spanning tree problems. Mathematical Social Sciences, 64(2):136–143. Bargaining, Evolution and Networks: A Special Issue in Honor of Hans Haller.

Ciftci, B. and Tijs, S. (2009). A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations. Top, 17(2):440–453.

Claus, A. and Kleitman, D. (1973). Cost allocation for a spanning tree. Networks, 3(4):289–304.

Curiel, I. (1997). Minimum cost spanning tree games. In Curiel, I., editor, Cooperative Game Theory and Applications: Cooperative Games Arising from Combinatorial Optimization Problems, volume 16 of Theory and Decision Library, chapter 6, pages 129–148. Academic Publishers, Boston, MA.

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

Dutta, B. and Mishra, D. (2012). Minimum cost arborescences. Games and Economic Behavior, 74(1):120–143.

Estévez-Fernández, A. and Reijnierse, H. (2014). On the core of cost-revenue games: Minimum cost spanning tree games with revenues. European Journal of Operational Research, 237(2):606–616.

Faigle, U., Kern, W., and Kuipers, J. (1998). Computing the nucleolus of min-cost spanning tree games is NP-hard. International Journal of Game Theory, 27(3):443–450.

Feltkamp, V. (1995). Cooperation in controlled network structures. PhD thesis, Tilburg University, The Netherlands.

Feltkamp, V., Tijs, S., and Muto, S. (1994). On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. Technical Report 106, CentER DP 1994, Tilburg University, The Netherlands.

Feltkamp, V., Tijs, S., and Muto, S. (2000). Bird’s tree allocation revisited. In Patrone, Garcı́a-Jurado, and Tijs, editors, Game practice: Contributions from applied game theory, pages 75–89. Kluwer.

Fernández, F. R., Hinojosa, M. A., and Puerto, J. (2004). Multi-criteria minimum cost spanning tree games. European Journal of Operational Research, 158(2):399–408. Methodological Foundations of Multi-Criteria Decision Making.

Giménez-Gómez, J.-M., Peris, J. E., and Subiza, B. (2020). An egalitarian approach for sharing the cost of a spanning tree. PLoS ONE, 15(7):e0236058–.

Ginsburgh, V. and Zang, I. (2003). The museum pass game and its value. Games and Economic Behavior, 43:322–325.

Gómez-Rúa, M. and Vidal-Puga, J. (2011). Merge-proofness in minimum cost spanning tree problems. International Journal of Game Theory, 40(2):309–329.

Gómez-Rúa, M. and Vidal-Puga, J. (2017). A monotonic and merge-proof rule in minimum cost spanning tree situations. Economic Theory, 63:813–826.

Granot, D. and Huberman, G. (1981). Minimum cost spanning tree games. Mathematical Programming, 21(1):1–18.

Granot, D. and Huberman, G. (1984). On the core and nucleolus of minimum cost spanning tree problems. Mathematical Programming, 29(3):323–347.

Hernández, P., Peris, J. E., and Vidal-Puga, J. (2020). A non-cooperative approach to the folk rule in minimum cost spanning tree problems. Mimeo, Universidade de Vigo.

Kalai, E. and Samet, D. (1987). On weighted Shapley values. International Journal of Game Theory, 16(3):205–222.

Kar, A. (2002). Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior, 38(2):265–277.

Kobayashi, M. and Okamoto, Y. (2014). Submodularity of minimum-cost spanning tree games. Networks, 63(3):231–238.

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

Kuipers, J. (1993). On the core of information graph games. International Journal of Game Theory, 21(4):339–350.

Littlechild, S. and Owen, G. (1973). A simple expression for the Shapley value in a special case. Management Science, 20(3):370–372.

Lorenzo, L. and Lorenzo-Freire, S. (2009). A characterization of Kruskal sharing rules for minimum cost spanning tree problems. International Journal of Game Theory, 38(1):107–126.

Megiddo, N. (1978). Cost allocation for Steiner trees. Networks, 8(1):1–6.

Moretti, S., Gök, S. Z. A., Branzei, R., and Tijs, S. (2011). Connection situations under uncertainty and cost monotonic solutions. Computers and Operational Research, 38(11):1638–1645.

Moretti, S., Norde, H., Pham Do, K. H., and Tijs, S. (2002). Connection problems in mountains and monotonic allocation schemes. Top, 10(1):83–99.

Norde, H. (2019). The degree and cost adjusted folk solution for minimum cost spanning tree games. Games and Economic Behavior, 113:734–742.

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

Núñez, M. and Vidal-Puga, J. (2020). Stable cores in information graph games. Working paper, Universidade de Vigo.

O’Neill, B. (1982). A problem of rights arbitration from the Talmud. Mathematical Social Sciences, 2(4):345–371.

Owen, G. (1977). Values of games with a priori unions. In Henn, R. and Moeschlin, O., editors, Mathematical Economics and Game Theory, volume 141 of Lecture Notes in Economics and Mathematical Systems, pages 76–88. Springer-Verlag, Berlin.

Prim, R. (1957). Shortest connection networks and some generalizations. Bell Systems Technology Journal, 36(6):1389–1401.

Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics, 17(6):1163–1170.

Shapley, L. S. (1953). Additive and non-additive set functions. PhD thesis, Princeton University.

Shapley, L. S. (1953). A value for n-person games. In Kuhn, H. and Tucker, A., editors, Contributions to the theory of games, volume II of Annals of Mathematics Studies, pages 307–317. Princeton University Press, Princeton NJ.

Skorin-Kapov, D. (1995). On the core of the minimum cost Steiner tree game in networks. Annals of Operations Research, 57:233–249.

Skorin-Kapov, D. and Skorin-Kapov, J. (2012). A note on Steiner tree games. Networks, 59(2):215–225.

Streekstra, L. and Trudeau, C. (2020). Stable source connection and assignment problems as multi-period shortest path problems. Discussion Papers on Business and Economics 7/2020, University of Southern Denmark.

Subiza, B., Giménez-Gómez, J.-M., and Peris, J. E. (2016). Folk solution for simple minimum cost spanning tree problems. Operations Research Letters, 44(5):598–601.

Sziklai, B., Fleiner, T., and Solymosi, T. (2016). On the core and nucleolus of directed acyclic graph games. Mathematical Programming, 163(1):243–271.

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

Tijs, S., Moretti, S., Branzei, R., and Norde, H. (2006). The Bird core for minimum cost spanning tree problems revisited: Monotonicity and additivity aspects. In Seeger, A., editor, Recent Advances in Optimization, volume 563 of Lecture Notes in Economics and Mathematical Systems, pages 305–322. Springer, Berlin Heidelberg.

Trudeau, C. (2012). A new stable and more responsible cost sharing solution for mcst problems. Games and Economic Behavior, 75(1):402–412.

Trudeau, C. (2013). Characterizations of the Kar and folk solutions for minimum cost spanning tree problems. International Game Theory Review, 15(2):1340003–16.

Trudeau, C. (2014). Characterizations of the cycle-complete and folk solutions for minimum cost spanning tree problems. Social Choice and Welfare, 42(4):941–957.

Trudeau, C. (2014). Linking the Kar and folk solutions through a problem separation property. International Journal of Game Theory, 43:845–870.

Trudeau, C. (2014). Minimum cost spanning tree problems with indifferent agents. Games and Economic Behavior, 84:137–151.

Trudeau, C. and Vidal-Puga, J. (2017). On the set of extreme core allocations for minimal cost spanning tree problems. Journal of Economic Theory, 169:425–452.

Trudeau, C. and Vidal-Puga, J. (2019). The Shapley value in minimum cost spanning tree problems. In Algaba, E., Fragnelli, V., and Sánchez-Soriano, J., editors, Chapters in Game Theory: The Shapley value, chapter 24. CRC Press, Taylor & Francis Group.

Trudeau, C. and Vidal-Puga, J. (2020). Clique games: A family of games with coincidence between the nucleolus and the shapley value. Mathematical Social Sciences, 103:8–14.

Vidal-Puga, J. (2004). Bargaining with commitments. International Journal of Game Theory, 33(1):129–144.

von Neumann, J. and Morgenstern, O. (1944). Theory of games and economic behavior. Princeton UP, first edition.

Weber, R. (1988). Probabilistic values for games. In Roth, A. E., editor, The Shapley value: Essays in honour of Lloyds S. Shapley, pages 101–119. Cambridge University Press, Cambridge.