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

PDF
MPRA_paper_104911.pdf Download (436kB)  Preview 
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 

Original Title:  Cooperative games for minimum cost spanning tree problems 
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 
Item ID:  104911 
Depositing User:  Juan VidalPuga 
Date Deposited:  23 Dec 2020 15:05 
Last Modified:  23 Dec 2020 15:05 
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: #Phardness 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ómezRúa, M. (2010). Minimum cost spanning tree problems with groups. Economic Theory, 43(2):227–262. Bergantiños, G. and GómezRú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ómezRúa, M., Llorca, N., Pulido, M., and SánchezSoriano, J. (2012). A cost allocation rule for khop minimum cost spanning tree problems. Operations Research Letters, 40(1):52–55. Bergantiños, G., GómezRúa, M., Llorca, N., Pulido, M., and SánchezSoriano, 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 noncooperative 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 noncooperative 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 LorenzoFreire, 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 LorenzoFreire, 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 LorenzoFreire, 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 LorenzoFreire, 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 MorenoTernero, 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 MorenoTernero, J. D. (2020). Sharing the revenues from broadcasting sport events. Management Science, 66(6):2417–2431. Bergantiños, G. and NavarroRamos, A. (2019). A characterization of the folk rule for multisource minimal cost spanning tree problems. Operations Research Letters, 47:366–370. Bergantiños, G. and NavarroRamos, 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 VidalPuga, J. (2007). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137(1):326–352. Bergantiños, G. and VidalPuga, 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 VidalPuga, J. (2009). Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics, 45(12):38–42. Bergantiños, G. and VidalPuga, J. (2010). Realizing fair outcomes in minimum cost spanning tree problems through noncooperative mechanisms. European Journal of Operational Research, 201(3):811–820. Bergantiños, G. and VidalPuga, 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 VidalPuga, 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 Pvalue 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évezFernández, A. and Reijnierse, H. (2014). On the core of costrevenue 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 mincost spanning tree games is NPhard. 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ı́aJurado, 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). Multicriteria minimum cost spanning tree games. European Journal of Operational Research, 158(2):399–408. Methodological Foundations of MultiCriteria Decision Making. GiménezGó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ómezRúa, M. and VidalPuga, J. (2011). Mergeproofness in minimum cost spanning tree problems. International Journal of Game Theory, 40(2):309–329. GómezRúa, M. and VidalPuga, J. (2017). A monotonic and mergeproof 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 VidalPuga, J. (2020). A noncooperative 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 minimumcost 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 LorenzoFreire, 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 VidalPuga, 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. SpringerVerlag, 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 nonadditive set functions. PhD thesis, Princeton University. Shapley, L. S. (1953). A value for nperson 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. SkorinKapov, D. (1995). On the core of the minimum cost Steiner tree game in networks. Annals of Operations Research, 57:233–249. SkorinKapov, D. and SkorinKapov, 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 multiperiod shortest path problems. Discussion Papers on Business and Economics 7/2020, University of Southern Denmark. Subiza, B., GiménezGó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 cyclecomplete 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 VidalPuga, 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 VidalPuga, J. (2019). The Shapley value in minimum cost spanning tree problems. In Algaba, E., Fragnelli, V., and SánchezSoriano, J., editors, Chapters in Game Theory: The Shapley value, chapter 24. CRC Press, Taylor & Francis Group. Trudeau, C. and VidalPuga, J. (2020). Clique games: A family of games with coincidence between the nucleolus and the shapley value. Mathematical Social Sciences, 103:8–14. VidalPuga, 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. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/104911 