×

Power measures and solutions for games under precedence constraints. (English) Zbl 1362.91006

Summary: Games under precedence constraints model situations, where players in a cooperative transferable utility game belong to some hierarchical structure, which is represented by an acyclic digraph (partial order). In this paper, we introduce the class of precedence power solutions for games under precedence constraints. These solutions are obtained by allocating the dividends in the game proportional to some power measure for acyclic digraphs. We show that all these solutions satisfy the desirable axiom of irrelevant player independence, which establishes that the payoffs assigned to relevant players are not affected by the presence of irrelevant players. We axiomatize these precedence power solutions using irrelevant player independence and an axiom that uses a digraph power measure. We give special attention to the hierarchical solution, which applies the hierarchical measure. We argue how this solution is related to the known precedence Shapley value, which does not satisfy irrelevant player independence, and thus is not a precedence power solution. We also axiomatize the hierarchical measure as a digraph power measure.

MSC:

91A12 Cooperative games
91A43 Games involving graphs

Software:

Stony Brook

References:

[1] Myerson, R.B.: Graphs and cooperation in games. Math. Oper. Res. 2, 225-229 (1977) · Zbl 0402.90106 · doi:10.1287/moor.2.3.225
[2] Gilles, R.P., Owen, G., van den Brink, R.: Games with permission structures: the conjunctive approach. Int. J. Game Theory 20, 277-293 (1992) · Zbl 0764.90106 · doi:10.1007/BF01253782
[3] Faigle, U., Kern, W.: The Shapley value for cooperative games under precedence constraints. Int. J. Game Theory 21, 249-266 (1992) · Zbl 0779.90078 · doi:10.1007/BF01258278
[4] Algaba, E., Bilbao, M., van den Brink, R., Jiménez-Losada, A.: Cooperative games on antimatroids. Math. Methods Oper. Res. 282, 1-15 (2004) · Zbl 1086.91007
[5] Bilbao, J.M., Edelman, P.H.: The Shapley value on convex geometries. Discrete Appl. Math. 103, 33-40 (2000) · Zbl 0955.91002 · doi:10.1016/S0166-218X(99)00218-8
[6] Bilbao, J.M.: Cooperative games under augmenting systems. SIAM J. Discrete Math. 17, 122-133 (2003) · Zbl 1066.91009 · doi:10.1137/S0895480102402745
[7] Honda, A., Grabisch, M.: Entropy of capacities on lattices and set systems. Inf. Sci. 176, 3472-3489 (2006) · Zbl 1106.94014 · doi:10.1016/j.ins.2006.02.011
[8] Lange, F., Grabisch, M.: Values on regular games under Kirchhoff’s laws. Math. Soc. Sci. 58, 322-340 (2009) · Zbl 1190.91022 · doi:10.1016/j.mathsocsci.2009.07.003
[9] Algaba, E., Bilbao, M., Borm, P., López, J.: The position value for union stable systems. Math. Methods Oper. Res. 52, 221-236 (2000) · Zbl 1103.91310 · doi:10.1007/s001860000060
[10] Algaba, E., Bilbao, M., Borm, P., López, J.: The Myerson value for union stable structures. Math. Methods Oper. Res. 54, 359-371 (2001) · Zbl 1059.91006 · doi:10.1007/s001860100159
[11] Grabisch, M., Sudhölter, P.: The bounded core for games with precedence constraints. Ann. Oper. Res. 201, 251-264 (2012) · Zbl 1272.91023 · doi:10.1007/s10479-012-1228-9
[12] Grabisch, M., Sudhölter, P.: Characterizations of solutions for games with precedence constraints. Int. J. Game Theory 45, 269-290 (2016) · Zbl 1388.91025 · doi:10.1007/s00182-015-0465-y
[13] Skiena, S.S.: The Algorithm Design Manual, 2nd edn. Springer, Berlin (2010) · Zbl 0885.68002
[14] Fiestras-Janeiro, M.G., Sánchez-Rodríguez, E., Schuster, M.: A precedence constraint value revisited. TOP. 24, 156-170 (2016) · Zbl 1341.91011 · doi:10.1007/s11750-015-0380-1
[15] Gould, R.V.: Measures of betweenness in non-symmetric networks. Soc. Netw. 9, 277-282 (1987) · doi:10.1016/0378-8733(87)90023-2
[16] White, D.R., Borgatti, S.P.: Betweenness centrality measures for directed graphs. Soc. Netw. 16, 335-346 (1994) · doi:10.1016/0378-8733(94)90015-9
[17] Brink, R., van den, R., Gilles, R.P.: Measuring domination in directed networks. Soc. Netw. 22, 1141-1157 (2000)
[18] van den Brink, R., Borm, P.: Digraph competitions and cooperative games. Theory Decis. 53, 327-342 (2002) · Zbl 1112.91007 · doi:10.1023/A:1024162419357
[19] Borm, P., van den Brink, R., Slikker, M.: An iterative procedure for evaluating digraph competitions. Ann. Oper. Res. 109, 61-75 (2002) · Zbl 1007.91003 · doi:10.1023/A:1016339832755
[20] Herings, P.J.J., van der Laan, G., Talman, A.J.J.: The positional power of nodes in digraphs. Soc. Choice Welf. 24, 439-454 (2005) · Zbl 1088.90505 · doi:10.1007/s00355-003-0308-9
[21] del Pozo, M., Manuel, C., González-Arangüena, E., Owen, G.: Centrality in directed social networks. A game theoretic approach. Soc. Netw. 33, 191-200 (2011) · Zbl 1040.91089 · doi:10.1016/j.socnet.2011.04.001
[22] Harsanyi, JC; Tucker, AW (ed.); Luce, RD (ed.), A bargaining model for cooperative \[n\] n-person games, 325-355 (1959), Princeton · Zbl 0084.36501
[23] Shapley, LS; Kuhn, HW (ed.); Tucker, AW (ed.), A value for \[n\] n-person games, No. 2, 307-317 (1953), Princeton · Zbl 0050.14404
[24] Algaba, E., Bilbao, M., van den Brink, R., Jiménez-Losada, A.: Axiomatizations of the Shapley value for games on antimatroids. Math. Methods Oper. Res. 57, 49-65 (2003) · Zbl 1060.91006 · doi:10.1007/s001860200250
[25] Bilbao, J.M., Ordoñez, M.: Axiomatizations of the Shapley value for games on augmenting systems. Eur. J. Oper. Res. 196, 1008-1014 (2009) · Zbl 1176.91005 · doi:10.1016/j.ejor.2008.04.028
[26] Algaba, E., Bilbao, J.M., Slikker, M.: A value for games restricted by augmenting systems. SIAM J. Discrete Math. 24, 992-1010 (2010) · Zbl 1232.91024 · doi:10.1137/080719170
[27] Ambec, S., Sprumont, Y.: Sharing a river. J. Econ. Theory 107, 453-462 (2002) · Zbl 1033.91503 · doi:10.1006/jeth.2001.2949
[28] Dong, B., Ni, D., Wang, Y.: Sharing a polluted river network. Environ. Resour. Econ. 53, 367-387 (2012) · doi:10.1007/s10640-012-9566-2
[29] Gugat, M.: Contamination source determination in water distribution networks. SIAM J. Appl. Math. 72, 1772-1791 (2012) · Zbl 1260.49005 · doi:10.1137/110859269
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.