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 TU-values 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 discuss how the hierarchical structure of a level structure improves the runtimes compared to an unstructured set of players. As examples, we examine the Shapley levels value, the nested Shapley levels value, and, as a new LS-value, the nested Owen levels value. Polynomial-time algorithms for these values (under ordinary conditions) are provided. Furthermore, we introduce relevant coalition functions where all coalitions which are not relevant for the payoff calculation have a Harsanyi dividend of zero. By these coalition functions, our results shed new light on the computation of values of the Harsanyi set 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.

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).

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.

Driessen, T. S. H., & Funaki, Y. (1991). Coincidence of and collinearity between game theoretic solutions. Operations-Research-Spektrum, 13(1), 15–30.

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.

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.

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.

Winter, E. (1989). A value for cooperative games with levels structure of cooperation. International Journal of Game Theory, 18(2), 227–240.