Besner, Manfred (2020): Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations. Published in: Discrete Applied Mathematics , Vol. 1, No. 309 (March 2022): pp. 85109.
This is the latest version of this item.
Preview 
PDF
MPRA_paper_101464.pdf Download (573kB)  Preview 
Abstract
Exponential runtimes of algorithms for values for games with transferable utility like the Shapley value are one of the biggest obstacles in the practical application of otherwise axiomatically convincing solution concepts of cooperative game theory. We investigate to what extent the hierarchical structure of a level structure improves runtimes compared to an unstructured player set. Representatively, we examine the Shapley levels value, the nested Shapley levels value, and, as a new value for level structures, the nested Owen levels value. For these values, we provide polynomialtime algorithms (under normal conditions) which are exact and therefore not approximation algorithms. Moreover, we introduce relevant coalition functions where all coalitions that are not relevant for the payoff calculation have a Harsanyi dividend of zero. Our results shed new light on the computation of values of the Harsanyi set as the Shapley value and many values from extensions of this set.
Item Type:  MPRA Paper 

Original Title:  Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations 
Language:  English 
Keywords:  Cooperative game · Polynomialtime algorithm · Level structure · (Nested) Shapley/Owen (levels) value · Harsanyi dividends 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games 
Item ID:  112329 
Depositing User:  Manfred Besner 
Date Deposited:  11 Mar 2022 11:13 
Last Modified:  11 Mar 2022 11:13 
References:  Algaba, E., Bilbao, J., Fernández, J., Jim´ enez, N., & López, J. (2007). Algorithms for computing the myerson value by dividends. Discrete Mathematics Research Progress, 1–13. ÁlvarezMozos, M., & Tejada, O. (2011). Parallel characterizations of a generalized Shapley value and a generalized Banzhaf value for cooperative games with level structure of cooperation. Decision Support Systems, 52(1), 21–27. ÁlvarezMozos, M., van den Brink, R., van der Laan, G., & Tejada, O. (2017). From hierarchies to levels: new solutions for games with hierarchical structure. International Journal of Game Theory, 1–25. Aumann, R.J., Dr` eze, J., 1974. Cooperative games with coalition structures. International Journal of Game Theory 3, 217–237. Banzhaf, J.F. (1965). Weighted voting does not work: a mathematical analysis. Rutgers Law Review 19, 317–343. Béal, S., Ferrières, S., Rémila, E., & Solal, P. (2018) The proportional Shapley value and applications. Games and Economic Behavior 108, 93–112. Besner, M. (2019a). Axiomatizations of the proportional Shapley value. Theory and Decision, 86(2), 161–183. Besner, M. (2019b). Weighted Shapley hierarchy levels values. Operations Research Letters 47, 122–126. Besner, M. (2020). Value dividends, the Harsanyi set and extensions, and the proportional Harsanyi solution. International Journal of Game Theory, 1–23. Brightwell, G., & Winkler, P. (1991, January). Counting linear extensions is #Pcomplete. In Proceedings of the twentythird annual ACM symposium on Theory of computing (pp. 175–181). Van den Brink, R., & van der Laan, G. (1998). Axiomatizations of the normalized Banzhaf value and the Shapley value. Social Choice and Welfare, 15(4), 567–582. Calvo, E., Lasaga, J. J., & Winter, E. (1996). The principle of balanced contributions and hierarchies of cooperation, Mathematical Social Sciences, 31(3), 171–182. Van Campen, T., Hamers, H., Husslage, B., & Lindelauf, R. (2018). A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack. Social Network Analysis and Mining, 8(3). Castro, J., Gómez, D., & Tejada, J. (2009). Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 36(5),1726–1730. Chantreuil, F. (2001). Axiomatics of level structure values. In: Holler M.J., Owen G. (eds) Power Indices and Coalition Formation (pp. 45–62). Springer, Boston, MA. Deng, X., & Papadimitriou, C. H. (1994) On the Complexity of Cooperative Solution Concepts, Mathematics of Operations Research, 19(2), 257–266. Derks, J., Haller, H., & Peters, H. (2000). The selectope for cooperative games. International Journal of Game Theory, 29(1), 23–38. Driessen, T. S. H., & Funaki, Y. (1991). Coincidence of and collinearity between game theoretic solutions. OperationsResearchSpektrum, 13(1), 15–30. Faigle, U., & Kern, W. (1992). The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory, 21(3), 249–266. Fatima, S. S., Wooldridge, M., & Jennings, N. R. (2008). A linear approximation method for the Shapley value. Artificial Intelligence, 172(14), 1673–1699. Futia, C. (1977). The complexity of economic decision rules. Journal of Mathematical Economics, 4(3), 289–299. GómezRúa, M., & VidalPuga, J. (2011). Balanced per capita contributions and level structure of cooperation. Top, 19(1), 167–176. Hammer, P. L., Peled, U. N., & Sorensen, S. (1977). Pseudoboolean functions and game theory. I. Core elements and Shapley value. Cahiers du CERO, 19, 159–176. Harsanyi, J. C. (1959). A bargaining model for cooperative nperson games. In: A. W. Tucker & R. D. Luce (Eds.), Contributions to the theory of games IV (325–355). Princeton NJ: Princeton University Press. Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings of the 6th ACM conference on Electronic commerce, pp. 193–202. Kalai, E., & Stanford, W. (1988). Finite rationality and interpersonal complexity in repeated games. Econometrica: Journal of the Econometric Society, 397–410. Kamijo, Y. (2009). A twostep Shapley value for cooperative games with coalition structures. International Game Theory Review, 11(02), 207–214. Kamijo, Y. (2013). The collective value: a new solution for games with coalition structures. Top, 21(3), 572–589. Khachiyan, L. G. (1979). A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR 244, 1093–1096 (translated in Soviet Mathematics Doklady 20, 191–194, 1979). Knuth, D. E. (1976). Big omicron and big omega and big theta. ACM Sigact News, 8(2), 18–24. Littlechild, S. C., & Owen, G. (1973). A simple expression for the Shapley value in a special case. Management Science, 20(3), 370–372. Maafa, K., Nourine, L., & Radjef, M. S. (2018). Algorithms for computing the Shapley value of cooperative games on lattices. Discrete Applied Mathematics, 249, 91–105. Mann, I., & Shapley, L. S. (1960) Values of large games. IV: Evaluating the Electoral College by Monte Carlo Techniques. The RAND Corporation, Memorandum RM2651 Michalak, T. P., Aadithya, K. V., Szczepanski, P. L., Ravindran, B., & Jennings, N. R. (2013). Efficient computation of the Shapley value for gametheoretic network centrality. Journal of Artificial Intelligence Research, 46, 607–650. Moriarity, S. (1975). Another approach to allocating joint costs. International The Accounting Review, 50(4), 791–795. Myerson, R. B. (1980). Conference structures and fair allocation rules. International Journal of Game Theory, 9(3), 169–182. Van den Nouweland, A., Borm, P., van Golstein Brouwers, W., Groot Bruinderink, R., & Tijs, S. (1996). A game theoretic approach to problems in telecommunication. Management Science, 42(2), 294–303. Owen, G. (1972). Multilinear extensions of games. Management Science, 18(5–part–2), 64–79. Owen, G. (1977). Values of games with a priori unions. In Essays in Mathematical Economics and Game Theory, Springer, Berlin Heidelberg, 76–88. Rubinstein, A. (1986). Finite automata play the repeated prisoner’s dilemma. Journal of economic theory, 39(1), 83–96. SánchezSánchez, F., & VargasValencia, M. (2018) Games with nested constraints given by a level structure. Journal of Dynamics & Games, 5(2), 95. Sastre, M., & Trannoy, A. (2002). Shapley inequality decomposition by factor components: Some methodological issues. Journal of Economics, 9, 51–89. Shapley, L. S. (1953a). Additive and nonadditive set functions. Princeton University. Shapley, L. S. (1953b). A value for nperson games. H. W. Kuhn/A. W. Tucker (eds.), Contributions to the Theory of Games, Vol. 2, Princeton University Press, Princeton, 307–317. Simon, H. A. (1972). Theories of bounded rationality. Decision and organization, 1(1), 161–176. Stanojevic, R., Laoutaris, N., & Rodriguez, P. (2010) On economic heavy hitters: Shapley value analysis of 95thpercentile pricing. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, 75–80. Sutherland, J. (2001). Inventing and Reinventing SCRUM in five Companies. Cutter IT journal, 14, 5–11. Takeuchi, H., & Nonaka, I. (1986). The new new product development game. Harvard business review, 64(1), 137–146. Vasil’ev, V. A. (1975). The Shapley value for cooperative games of bounded polynomial variation. Optimizacija Vyp, 17, 5–27. Vasil’ev, V. A. (1978). Support function of the core of a convex game. Optimizacija Vyp, 21, 30–35. Vasil’ev, V., & van der Laan, G. (2002). The Harsanyi set for cooperative TUgames. Siberian Advances in Mathematics 12, 97–125. Winter, E. (1989). A value for cooperative games with levels structure of cooperation. International Journal of Game Theory, 18(2), 227–240. Zlotkin, G., & Rosenschein, J. S. (1994). Coalition, cryptography, and stability: Mechanisms for coalition formation in task oriented domains. In Proceedings of the twelfth national conference on artificial in telligence, vol 1, AAAI ’94, Menlo Park, CA, USA. American association for artificial intelligence, (pp. 432–437) 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/112329 
Available Versions of this Item

Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations. (deposited 30 Mar 2020 11:18)

Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations. (deposited 05 Jul 2020 18:57)
 Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations. (deposited 11 Mar 2022 11:13) [Currently Displayed]

Values for level structures with polynomialtime algorithms, relevant coalition functions, and general considerations. (deposited 05 Jul 2020 18:57)