×

Generalized minimum spanning tree games. (English) Zbl 1337.91030

Summary: The minimum-cost spanning tree game is a special class of cooperative games defined on a graph with a set of vertices and a set of edges, where each player owns a vertex. Solutions of the game represent ways to distribute the total cost of a minimum-cost spanning tree among all the players. When the graph is partitioned into clusters, the generalized minimum spanning tree problem is to determine a minimum-cost tree including exactly one vertex from each cluster. This paper introduces the generalized minimum spanning tree game and studies some properties of this game. The paper also describes a constraint generation algorithm to calculate a stable payoff distribution and presents computational results obtained using the proposed algorithm.

MSC:

91A43 Games involving graphs
91A12 Cooperative games
90C35 Programming involving graphs or networks
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bergantiños G, Gómez-Rúa M (2015) An axiomatic approach in minimum cost spanning tree problems with groups. Ann Oper Res 225(1):45-63 · Zbl 1320.91040 · doi:10.1007/s10479-012-1251-x
[2] Bird CG (1976) On cost allocation for a spanning tree: a game theory approach. Networks 6:335-350 · Zbl 0357.90083 · doi:10.1002/net.3230060404
[3] Bogomolnaia A, Moulin H (2010) Sharing a minimal cost spanning tree: beyond the Folk solution. Games Econ Behav 69:238-248 · Zbl 1230.91019 · doi:10.1016/j.geb.2009.11.001
[4] Chalkiadakis G, Elkind E, Wooldridge M (2011) Computational aspects of cooperative game theory. Morgan Claypool Publishers, San Rafael · Zbl 1258.91005
[5] Claus A, Kleitman DJ (1973) Cost allocation for a spanning tree. Networks 3:289-304 · Zbl 0338.90031 · doi:10.1002/net.3230030402
[6] Dror M, Haouari M, Chaouachi J (2000) Generalized spanning trees. Eur J Oper Res 120:583-592 · Zbl 0985.90076 · doi:10.1016/S0377-2217(99)00006-5
[7] Dutta B, Kar A (2004) Cost monotonicity, consistency and minimum cost spanning tree games. Games Econ Behav 48:223-248 · Zbl 1117.91308 · doi:10.1016/j.geb.2003.09.008
[8] Faigle U, Kern W (1992) The Shapley value for cooperative games under precedence constraints. Int J Game Theor 21:249-266 · Zbl 0779.90078 · doi:10.1007/BF01258278
[9] Faigle U, Kern W (1997) On the complexity of testing membership in the core of min-cost spanning tree games. Int J Game Theor 26:361-366 · Zbl 0885.90123 · doi:10.1007/BF01263277
[10] Feremans C, Labbé M, Laporte G (2002) A comparative analysis of several formulations for the generalized minimum spanning tree problem. Networks 39:29-34 · Zbl 1001.90066 · doi:10.1002/net.10009
[11] Fiestras-Janeiro MG, Garcia-Jurado I, Meca A, Mosquera MA (2011) Cooperative game theory and inventory management. Eur J Oper Res 210:459-466 · Zbl 1213.90048 · doi:10.1016/j.ejor.2010.06.025
[12] Frisk M, Göthe-Lundgren M, Jörnsten K, Rönnqvist M (2010) Cost allocation in collaborative forest transportation. Eur J Oper Res 205:448-458 · Zbl 1188.90154 · doi:10.1016/j.ejor.2010.01.015
[13] Granot D, Huberman G (1981) Minimum cost spanning tree games. Math Program 21:1-18 · Zbl 0461.90099 · doi:10.1007/BF01584227
[14] Gerla M, Frata L (1988) Tree structured fiber optics MAN’s. IEEE J Sel Areas Commun 6:934-943 · doi:10.1109/49.1956
[15] Golden B, Raghavan S, Stanojević D (2005) Heuristic search for the generalized minimum spanning tree problem. INFORMS J Comp 17:290-304 · Zbl 1239.90099 · doi:10.1287/ijoc.1040.0077
[16] Grabisch M (2013) The core of games on ordered structures and graphs. Ann Oper Res 204:33-64 · Zbl 1273.91032 · doi:10.1007/s10479-012-1265-4
[17] Horowitz E, Sahni S (1978) Fundamentals of computer algorithms. Computer Science Press, Maryland · Zbl 0442.68022
[18] Ihler E, Reich G, Widmayer P (1999) Class steiner trees and VLSI-design. Discret Appl Math 90:173-194 · Zbl 0921.68054 · doi:10.1016/S0166-218X(98)00090-0
[19] Kruskal JB (1956) On the shortest spanning tree of a graph and the travelling salesman problem. Proc Am Math Soc 7:48-50 · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[20] Maschler M, Solan E, Zamir S (2013) Game Theory. Cambridge University Press, Cambridge · Zbl 1403.91003 · doi:10.1017/CBO9780511794216
[21] Myerson RB (1977) Graphs and cooperation in games. Math Oper Res 2:225-229 · Zbl 0402.90106 · doi:10.1287/moor.2.3.225
[22] Myung YS, Lee CH, Tcha DW (1995) On the generalized minimum spanning tree problem. Networks 26:231-241 · Zbl 0856.90117 · doi:10.1002/net.3230260407
[23] Pop PC (2009) A survey of different integer programming formulations of the generalized minimum spanning tree problem. Carpathian J Math 25:104-118 · Zbl 1183.90343
[24] Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389-1401 · doi:10.1002/j.1538-7305.1957.tb01515.x
[25] Prisco JJ (1986) Fiber optic regional area networks in New York and Dallas. IEEE J Sel Areas Commun 4:750-757 · doi:10.1109/JSAC.1986.1146376
[26] Tijs S, Branzei R, Moretti S, Norde H (2006) Obligation rules for minimum cost spanning tree situations and their monotonicity properties. Eur J Oper Res 175:121-134 · Zbl 1137.90361 · doi:10.1016/j.ejor.2005.04.036
[27] Zverovich A (2002) GTSP instances. http://www.cs.rhul.ac.uk/home/zvero/GTSPLIB/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.