Games with a permission structure – a survey on generalizations and applications. (English) Zbl 1414.91037
Summary: In the field of cooperative games with restricted cooperation, various restrictions on coalition formation are studied. The most studied restrictions are those that arise from restricted communication and hierarchies. This survey discusses several models of hierarchy restrictions and their relation with communication restrictions. In the literature, there are results on game properties, Harsanyi dividends, core stability, and various solutions that generalize existing solutions for TU-games. In this survey, we mainly focus on axiomatizations of the Shapley value in different models of games with a hierarchically structured player set, and their applications. Not only do these axiomatizations provide insight in the Shapley value for these models, but also by considering the types of axioms that characterize the Shapley value, we learn more about different network structures. A central model of games with hierarchies is that of games with a permission structure where players in a
cooperative transferable utility game are part of a permission structure in the sense that there are players that need permission from other players before they are allowed to cooperate. This permission structure is represented by a directed graph. Generalizations of this model are, for example, games on antimatroids, and games with a local permission structure. Besides discussing these generalizations, we briefly discuss some applications, in particular auction games and hierarchically structured firms.
MSC:
| 91A12 | Cooperative games |
| 91A43 | Games involving graphs |
| 91A65 | Hierarchical games (including Stackelberg games) |
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
Keywords:
cooperative TU-game; hierarchy; permission structure; antimatroid; local permission structure; applicationsReferences:
| [1] | Albizuri MJ, Santos JC, Zarzuelo JM (2002) On the serial cost sharing method. Int J Game Theory 31:437-446 · Zbl 1083.91059 · doi:10.1007/s001820300129 |
| [2] | Algaba E, Bilbao JM, Borm P, López JJ (2000) The position value for union stable systems. Math Methods Oper Res 52:221-236 · Zbl 1103.91310 · doi:10.1007/s001860000060 |
| [3] | Algaba E, Bilbao JM, Borm P, López JJ (2001) The Myerson value for union stable structure. Math Methods Oper Res 54:359-371 · Zbl 1059.91006 · doi:10.1007/s001860100159 |
| [4] | Algaba E, Bilbao JM, López JJ (2001) A unified approach to restricted games. Theory Decis 50:333-345 · Zbl 1039.91003 · doi:10.1023/A:1010344404281 |
| [5] | Algaba E, Bilbao JM, van den Brink R, Jimé nez-Losada A, (2003a) Axiomatizations of the Shapley value for cooperative games on antimatroids. Math Methods Oper Res 57:49-65 · Zbl 1060.91006 |
| [6] | Algaba E, Bilbao JM, van den Brink R, Jiménez-Losada A (2003b) An axiomatization of the Banzhaf value for cooperative games on antimatroids. Math Methods Oper Res 59:147-166 · Zbl 1083.91012 |
| [7] | Algaba E, Bilbao JM, van den Brink R, Jiménez-Losada A (2004) Cooperative games on antimatroids. Discrete Math 282:1-15 · Zbl 1086.91007 · doi:10.1016/j.disc.2003.10.019 |
| [8] | Algaba E, Bilbao JM, Slikker M (2010) A value for games restricted by augmenting systems. SIAM J Discrete Math 24:992-1010 · Zbl 1232.91024 · doi:10.1137/080719170 |
| [9] | Álvarez-Mozos M, van den Brink R, van der Laan G, Tejada O (2015) From hierarchies to levels: new solutions for games. TI Discussion paper 15-072/II, Tinbergen Institute Amsterdam · Zbl 1411.91036 |
| [10] | Banzhaf JF (1965) Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev 19:317-343 |
| [11] | Bilbao JM (2003) Cooperative games under augmenting systems. SIAM J Discrete Math 17:122-133 · Zbl 1066.91009 · doi:10.1137/S0895480102402745 |
| [12] | Bilbao JM, Jiménez-Losada A, Lebrón E, Chacón C (2005) Values for interior operator games. Ann Oper Res 137:141-160 · Zbl 1138.91318 · doi:10.1007/s10479-005-2251-x |
| [13] | Bilbao JM, Ordoñez M (2009) Axiomatizations of the Shapley value for games on augmenting systems. Eur J Oper Res 196:1008-1014 · Zbl 1176.91005 · doi:10.1016/j.ejor.2008.04.028 |
| [14] | Bjorndal E, Hamers H, Koster M (2004) Cost allocation in a bank ATM network. Math Methods Oper Res 59:405-418 · Zbl 1148.91324 |
| [15] | Bondareva O (1963) Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernetiki 10:119-139 (In Russian) · Zbl 1013.91501 |
| [16] | Brânzei R, Fragneli V, Tijs S (2002) Tree connected peer group situations and peer group games. Math Methods Oper Res 55:93-106 · Zbl 1052.91013 · doi:10.1007/s001860200176 |
| [17] | Brânzei R, Solymosi T, Tijs S (2005) Strongly essential coalitions and the nucleolus of peer group games. Int J Game Theory 33:447-460 · Zbl 1121.91009 · doi:10.1007/s00182-005-0213-9 |
| [18] | Casajus A (2014) Collusion, quarrel, and the Banzhaf value. Int J Game Theory 43:1-11 · Zbl 1336.91013 · doi:10.1007/s00182-012-0364-4 |
| [19] | Dehez P, Ferey S (2013) How to share joint liability: a cooperative game approach. Math Soc Sci 66:44-50 · Zbl 1280.91133 · doi:10.1016/j.mathsocsci.2013.02.003 |
| [20] | Demange G (1994) Intermediate preferences and stable coalition structures. J Math Econ 23:45-58 · Zbl 0791.90078 · doi:10.1016/0304-4068(94)90035-3 |
| [21] | Demange G (2004) On group stability in hierarchies and networks. J Polit Econ 112:754-778 · doi:10.1086/421171 |
| [22] | Derks JJM, Gilles RP (1995) Hierarchical organization structures and constraints on coalition formation. Int J Game Theory 24:147-163 · Zbl 0831.90139 · doi:10.1007/BF01240039 |
| [23] | Dilworth RP (1940) Lattices with unique irreducible decompositions. Ann Math 41:771-777 · JFM 66.0101.05 · doi:10.2307/1968857 |
| [24] | Dong B, Ni D, Wang Y (2012) Sharing a polluted river network. Environ Resour Econ 53:367-387 · doi:10.1007/s10640-012-9566-2 |
| [25] | Dubey P, Shapley LS (1979) Mathematical properties of the Banzhaf Power Index. Math Oper Res 4:99-131 · Zbl 0409.90008 · doi:10.1287/moor.4.2.99 |
| [26] | Edelman PH, Jamison RE (1985) The theory of convex geometries. Geom Dedicata 19:247-270 · Zbl 0577.52001 · doi:10.1007/BF00149365 |
| [27] | Faigle U, Kern W (1992) The Shapley value for cooperative games under precedence constraints. Int J Game Theory 21:249-266 · Zbl 0779.90078 · doi:10.1007/BF01258278 |
| [28] | Gallardo JM, Jiménez N, Jiménez-Losada A, Lebrón E (2014) Games with fuzzy permission structure: a conjunctive approach. Inf Sci 278:510-519 · Zbl 1354.91014 · doi:10.1016/j.ins.2014.03.068 |
| [29] | Gilles RP, Owen G, van den Brink R (1992) Games with permission structures: the conjunctive approach. Int J Game Theory 20:277-293 · Zbl 0764.90106 · doi:10.1007/BF01253782 |
| [30] | Gilles RP (2010) The cooperative game theory of networks and hierarchies. Springer, Berlin · Zbl 1198.91005 · doi:10.1007/978-3-642-05282-8 |
| [31] | Gilles RP, Owen G (1994) Games with permission structures: the disjunctive approach. Virginia Polytechnic Institute and State University, Blacksburg, Virginia, Mimeo, Department of Economics |
| [32] | Gillies DB (1953) Some theorems on \[n\] n-person games, Ph.D. thesis. Princeton University Press, Princeton · Zbl 1013.91501 |
| [33] | 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 |
| [34] | Graham DA, Marshall RC, Richard JF (1990) Differential payments within a bidder coalition and the Shapley value. Am Econ Rev 80:493-510 |
| [35] | Graham D, Marshall R (1987) Collusive behavior at single-object second-price and English auctions. J Polit Econ 95:1217-1239 · doi:10.1086/261512 |
| [36] | Haller H (1994) Collusion properties of values. Int J Game Theory 23:261-281 · Zbl 0864.90138 · doi:10.1007/BF01247318 |
| [37] | Harsanyi, JC; Tucker, AW (ed.); Luce, RD (ed.), A Bargaining model for cooperative n-person games, 325-355 (1959), Princeton · Zbl 0084.36501 |
| [38] | Hart O, Moore J (1990) Property rights and the nature of the firm. J Polit Econ 98:1119-1158 · doi:10.1086/261729 |
| [39] | Herings PJJ, van der Laan G, Talman AJJ (2008) The average tree solution for cycle-free graph games. Games Econ Behav 62:77-92 · Zbl 1135.91316 · doi:10.1016/j.geb.2007.03.007 |
| [40] | Hofstede G (1980) Culture’s consequences. international differences in work-related values. Sage Publications, Thousand Oaks · Zbl 1319.91049 |
| [41] | Honda A, Grabisch M (2006) Entropy of capacities on lattices and set systems. Inf Sci 176:3472-3489 · Zbl 1106.94014 · doi:10.1016/j.ins.2006.02.011 |
| [42] | Jackson MO, Rodriguez-Barraquer T, Tan X (2012) Social capital and social quilts: network patterns of favor exchange. Am Econ Rev 102:1857-1897 · doi:10.1257/aer.102.5.1857 |
| [43] | Jiménez-Losada Fernández JR, Ordoñez M, Grabisch M (2010) Games on fuzzy communication structures with choquet players. Eur J Oper Res 207:836-847 · Zbl 1205.91041 · doi:10.1016/j.ejor.2010.06.014 |
| [44] | Kaneko M, Wooders M (1982) Cores of partitioning games. Math Soc Sci 3:313-327 · Zbl 0493.90089 · doi:10.1016/0165-4896(82)90015-4 |
| [45] | Korte B, Lóvasz L, Schrader R (1991) Greedoids. Springer, New York · Zbl 0733.05023 · doi:10.1007/978-3-642-58191-5 |
| [46] | Lange F, Grabisch M (2009) Values on regular games under Kirchhoffs laws. Math Soc Sci 58:322-340 · Zbl 1190.91022 · doi:10.1016/j.mathsocsci.2009.07.003 |
| [47] | Le Breton G, Owen G, Weber S (1992) Strongly balanced cooperative games. Int J Game Theory 20:419-427 · Zbl 0763.90103 · doi:10.1007/BF01271134 |
| [48] | Littlechild SC, Owen G (1973) A simple expression for the Shapley value in a special case. Manag Sci 20:370-372 · Zbl 0307.90095 · doi:10.1287/mnsc.20.3.370 |
| [49] | Malawski M (2002) Equal treatment, symmetry and Banzhaf value axiomatizations. Int J Game Theory 31:47-67 · Zbl 1083.91025 · doi:10.1007/s001820200107 |
| [50] | Milgrom P, Roberts J (1994) The economics of modern manufacturing: technology, strategy and organization. Am Econ Rev 80:511-528 |
| [51] | Moulin H, Shenker S (1992) Serial cost sharing. Econometrica 60:1009-1037 · Zbl 0766.90013 · doi:10.2307/2951537 |
| [52] | Myerson RB (1977) Graphs and cooperation in games. Math Oper Res 2:225-229 · Zbl 0402.90106 · doi:10.1287/moor.2.3.225 |
| [53] | Ni D, Wang Y (2007) Sharing a polluted river. Games Econ Behav 60:176-186 · Zbl 1155.91449 · doi:10.1016/j.geb.2006.10.001 |
| [54] | Oishi T, Nakayama M, Hokari T, Funaki Y (2016) Duality and anti-duality in TU games applied to solutions, axioms, and axiomatizations. J Math Econ 63:44-53 · Zbl 1368.91016 · doi:10.1016/j.jmateco.2015.12.005 |
| [55] | Owen G (1975) Multilinear extensions and the Banzhaf value. Naval Res Logist Q 22:741-750 · Zbl 0333.90056 · doi:10.1002/nav.3800220409 |
| [56] | Rajan RG, Zingales L (1998) Power in a theory of the firm. Q J Econ 113:387-432 · Zbl 0936.91038 · doi:10.1162/003355398555630 |
| [57] | Ruys, PHM; Brink, R.; Semenov, R.; Menard, C. (ed.), Values and governance systems, 422-446 (2000), Northampton |
| [58] | Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163-1170 · Zbl 0191.49502 · doi:10.1137/0117107 |
| [59] | Shapley LS (1953) A value for \[n\] n-person games. In: Tucker AW (ed) Annals of Mathematics Studies, vol. 28 (Contributions to the Theory of Games Vol.2). Princeton University Press, Princeton, pp 307-317 · Zbl 0050.14404 |
| [60] | Shapley LS (1967) On balanced sets and cores. Naval Res Logist Q 14:453-460 · doi:10.1002/nav.3800140404 |
| [61] | van den Brink R (1997) An axiomatization of the disjunctive permission value for games with a permission structure. Int J Game Theory 26:27-43 · Zbl 0872.90118 |
| [62] | van den Brink R (1999) An axiomatization of the conjunctive permission value for games with a hierarchical permission structure. In: de Swart H (ed) Logic, game theory and social choice, pp 125-139 |
| [63] | van den Brink R (2008) Vertical wage differences in hierarchically structured firms. Soc Choice Welfare 30:225-243 · Zbl 1133.91458 · doi:10.1007/s00355-007-0230-7 |
| [64] | van den Brink R (2010) Axiomatizations of Banzhaf permission values for games with a permission structure. Int J Game Theory 39:445-466 · Zbl 1211.91052 · doi:10.1007/s00182-009-0221-2 |
| [65] | van den Brink R (2012) On hierarchies and communication. Soc Choice Welfare 39:721-735 · Zbl 1287.91022 · doi:10.1007/s00355-011-0557-y |
| [66] | van den Brink R, Borm P (2002) Digraph competitions and cooperative games. Theory Decis 53:327-342 · Zbl 1112.91007 · doi:10.1023/A:1024162419357 |
| [67] | van den Brink R, Dietz C (2014) Games with a local permission structure: separation of authority and value generation. Theory Decis 76:343-361 · Zbl 1302.91040 · doi:10.1007/s11238-013-9372-5 |
| [68] | van den Brink R, Gilles RP (1996) Axiomatizations of the conjunctive permission value for games with permission structures. Games Econ Behav 12:113-126 · Zbl 0846.90130 · doi:10.1006/game.1996.0008 |
| [69] | van den Brink R, Gilles RP (2000) Measuring domination in directed networks. Soc Netw 22:1141-1157 |
| [70] | van den Brink R, Ruys PHM (2008) Technology driven organizational structure of the firm. Ann Financ 4:481-503 · Zbl 1233.91167 · doi:10.1007/s10436-007-0087-x |
| [71] | van den Brink R, Katsev I, van der Laan G (2010) An algorithm for computing the nucleolus of disjunctive non-negative additive games with an acyclic permission structure. Eur J Oper Res 207:817-826 · Zbl 1205.91026 · doi:10.1016/j.ejor.2010.05.028 |
| [72] | van den Brink R, Katsev I, van der Laan G (2011a) A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure. Int J Game Theory 40:591-616 · Zbl 1274.91058 · doi:10.1007/s00182-010-0257-3 |
| [73] | van den Brink R, Katsev I, van der Laan G (2011b) Axiomatizations of two types of Shapley values for games on union closed systems. Econ Theory 47:175-188 · Zbl 1213.91038 · doi:10.1007/s00199-010-0530-5 |
| [74] | van den Brink R, Dietz C, van der Laan G, Xu G (2016) Comparable characterizations of four solutions for permission tree games. Econ Theory. doi:10.1007/s00199-016-0966-3 · Zbl 1401.91027 · doi:10.1007/s00199-016-0966-3 |
| [75] | van den Brink R, Herings PJJ, van der Laan G, Talman AJJ (2015) The average tree permission value for games with a permission tree. Econ Theory 58:99-123 · Zbl 1319.91049 · doi:10.1007/s00199-013-0796-5 |
| [76] | van den Nouweland A, Borm P (1992) On the convexity of communication games. Int J Game Theory 19:421-430 · Zbl 0734.90126 · doi:10.1007/BF01766431 |
| [77] | Williamson OE (1967) Hierarchical control and optimum firm size. J Polit Econ 75:123-138 · doi:10.1086/259258 |
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.
