Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations

Besner, Manfred (2020): Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations.

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 polynomial-time 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
• Language: English
• Keywords: Cooperative game · Polynomial-time 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

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.

Álvarez-Mozos, 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.

Álvarez-Mozos, 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 #P-complete. In Proceedings of the twenty-third 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. Operations-Research-Spektrum, 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ómez-Rúa, M., & Vidal-Puga, 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). Pseudo-boolean 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 n-person 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 two-step 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 RM-2651

Michalak, T. P., Aadithya, K. V., Szczepanski, P. L., Ravindran, B., & Jennings, N. R. (2013). Efficient computation of the Shapley value for game-theoretic 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ánchez-Sánchez, F., & Vargas-Valencia, 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 non-additive set functions. Princeton University.

Shapley, L. S. (1953b). A value for n-person 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 95th-percentile 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 TU-games. 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)