×

On the core and nucleolus of directed acyclic graph games. (English) Zbl 1366.91038

Summary: We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game – including monotonic minimum cost spanning tree games – can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.

MSC:

91A43 Games involving graphs
91A12 Cooperative games
05C05 Trees
05C57 Games on graphs (graph-theoretic aspects)
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bergantiños, G., Vidal-Puga, J.J.: A fair rule in minimum cost spanning tree problems. J. Econ. Theory 137, 326-352 (2007) · Zbl 1132.91366
[2] Bird, C.: On cost allocation for a spanning tree: a game theoretic approach. Networks 6, 335-350 (1976) · Zbl 0357.90083
[3] Bjørndal, E., Koster, M., Tijs, S.: Weighted allocation rules for standard fixed tree games. Math. Methods Oper. Res. 59(2), 249-270 (2004) · Zbl 1106.91007
[4] Bogomolnaia, A., Moulin, H.: Sharing a minimal cost spanning tree: beyond the folk solution. Games Econ. Behav. 69, 238-248 (2010) · Zbl 1230.91019
[5] Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. J. Comb. Optim. 18(1), 64-86 (2009) · Zbl 1188.91024
[6] Faigle, U., Kern, W., Hochstättler, W., Fekete, S.: On the complexity of testing membership in the core of min-cost spanning tree games. Int. J. Game Theory 26(3), 361-366 (1997) · Zbl 0885.90123
[7] Faigle, U., Kern, W., Kuipers, J.: Computing the nucleolus of min-cost spanning tree games is np-hard. Int. J. Game Theory 27, 443-450 (1998) · Zbl 1058.91511
[8] Granot, D., Granot, F.: Computational complexity of a cost allocation approach to a fixed cost spanning forest problem. Math. Oper. Res. 17(4), 765-780 (1992) · Zbl 0783.90128
[9] Granot, D., Huberman, G.: Minimum cost spanning tree games. Math. Program. 21, 1-18 (1981) · Zbl 0461.90099
[10] Granot, D., Huberman, G.: On the core and nucleolus of minimum cost spanning tree games. Math. Program. 29(3), 323-347 (1984) · Zbl 0541.90099
[11] Granot, D., Maschler, M.: Spanning network games. Int. J. Game Theory 27, 467-500 (1998) · Zbl 1058.91518
[12] Granot, D., Granot, F., Zhu, W.R.: Characterization sets for the nucleolus. Int. J. Game Theory 27(3), 359-374 (1998) · Zbl 0960.91009
[13] Huberman, G.; Bensoussan, A. (ed.); Lions, JL (ed.), The nucleolus and essential coalitions, No. 28, 416-422 (1980), Amsterdam
[14] Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53. Elsevier, North-Holland (1992) · Zbl 0774.05001
[15] Kuipers, J.: Minimum cost forest games. Int. J. Game Theory 26, 367-377 (1997) · Zbl 0880.90157
[16] Maschler, M., Peleg, B., Shapley, L.: Geometric properties of the kernel, nucleolus and related solution concepts. Math. Oper. Res. 4, 303-338 (1979) · Zbl 0426.90097
[17] Maschler, M., Potters, J., Reijnierse, H.: The nucleolus of a standard tree game revisited: a study of its monotonicity and computational properties. Int. J. Game Theory 39(1-2), 89-104 (2010) · Zbl 1211.91083
[18] Megiddo, N.: Computational complexity of the game theory approach to cost allocation for a tree. Math. Oper. Res. 3(3), 189-196 (1978) · Zbl 0397.90111
[19] Potters, J.A.M., Sudhölter, P.: Airport problems and consistent allocation rules. Math. Soc. Sci. 38, 83-102 (1999) · Zbl 1111.91310
[20] Reijnierse, H., Potters, J.A.M.: The \[{\cal B}B\]-nucleolus of tu-games. Games Econ. Behav. 24, 77-96 (1998) · Zbl 0910.90275
[21] Rosenthal, E.C.: The minimum cost spanning forest game. Econ. Lett. 23, 355-357 (1987) · Zbl 1328.91039
[22] Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17, 1163-1170 (1969) · Zbl 0191.49502
[23] Skorin-Kapov, D., Skorin-Kapov, J.: A note on steiner tree games. Networks 59(2), 215-225 (2012) · Zbl 1241.90024
[24] Solymosi, T., Sziklai, B.: Characterization sets for the nucleolus in balanced games. Oper. Res. Lett. 44, 520-524 (2016) · Zbl 1380.91019
[25] Sziklai, B.: On the computation of the nucleolus of cooperative transferable utility games. Ph.d. thesis, Eötös Loránd University, Budapest (2015) · Zbl 1132.91366
[26] Sziklai B, Fleiner T, Solymosi T (2014) On the core of directed acyclic graph games. IEHAS Discussion Papers MT-DP 2014/18 · Zbl 1366.91038
[27] Trudeau, C.: A new stable and more responsive cost sharing solution for minimum cost spanning tree problems. Games Econ. Behav. 75, 402-412 (2012) · Zbl 1280.91099
[28] van den Nouweland, A., Tijs, S., Maschler, M.: Monotonic games are spanning network games. Int. J. Game Theory 21(4), 419-427 (1993) · Zbl 0795.90094
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.