×

Efficient computation of the Shapley value for large-scale linear production games. (English) Zbl 1437.91035

Summary: The linear production game is concerned with allocating the total payoff of an enterprise among the owners of the resources in a fair way. With cooperative game theory providing a mathematical framework for sharing the benefit of the cooperation, the Shapley value is one of the widely used solution concepts as a fair measurement in this area. Finding the exact Shapley value for linear production games is, however, challenging when the number of players exceeds 30. This paper describes the use of linear programming sensitivity analysis for a more efficient computation of the Shapley value. The paper also proposes a stratified sampling technique to estimate the Shapley value for large-scale linear production games. Computational results show the effectiveness of the proposed methods compared to others.

MSC:

91A12 Cooperative games
91A80 Applications of game theory
91B38 Production theory, theory of the firm
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ando, K., Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases, Japan Journal of Industrial and Applied Mathematics, 29, 385-400 (2012) · Zbl 1254.91020 · doi:10.1007/s13160-012-0078-9
[2] Bertsimas, D.; Tsitsiklis, JN, Introduction to linear optimization (1997), Belmont, MA: Athena Scientific, Belmont, MA
[3] Bilbao, JM; Fernandez, JR; Losada, AJ; Lopez, JJ, Generating functions for computing power indices efficiently, Top, 8, 2, 191-213 (2000) · Zbl 0991.91005 · doi:10.1007/BF02628555
[4] Bjorndal, E.; Jornsten, K., Lower and upper bounds for linear production games, European Journal of Operational Research. Production, Manufacturing and Logistics, 196, 2, 476-486 (2009) · Zbl 1163.90450
[5] Borm, P.; Hamers, H.; Hendrickx, R., Operations research games: A survey, TOP, 9, 2, 139-216 (2001) · Zbl 1006.91009 · doi:10.1007/BF02579075
[6] Castro, J.; Gómez, D.; Monila, E.; Tejada, J., Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation, Computers and Operations Research, 82, 180-188 (2017) · Zbl 1394.91024 · doi:10.1016/j.cor.2017.01.019
[7] Castro, J.; Gómez, D.; Tejada, J., Polynomial calculation of the Shapley value based on sampling, Computers and Operations Research, 36, 5, 1726-1730 (2009) · Zbl 1177.91021 · doi:10.1016/j.cor.2008.04.004
[8] Cochran, WG, Sampling Techniques (2007), Hoboken: Wiley, Hoboken
[9] Deng, X.; Papadimitriou, CH, On the complexity of cooperative solution concepts, Mathematics of Operations Research, 19, 2, 257-266 (1994) · Zbl 0824.90146 · doi:10.1287/moor.19.2.257
[10] Fernández, FR; Fiestras-Janeiro, MG; Garca-Jurado, I.; Puerto, J., Competition and cooperation in non-centralized linear production games, Annals of Operations Research, 137, 1, 91-100 (2005) · Zbl 1138.91307 · doi:10.1007/s10479-005-2247-6
[11] Gómez, D.; González-Arangüena, E.; Manuel, C.; Owen, G.; Pozo, M.; Tejada, J., Centrality and power in social networks: A game theoretic approach, Mathematical Social Sciences, 46, 1, 27-54 (2003) · Zbl 1040.91089 · doi:10.1016/S0165-4896(03)00028-3
[12] Granot, D., A generalized linear production model: A unifying model, Mathematical Programming, 34, 212-222 (1986) · Zbl 0604.90142 · doi:10.1007/BF01580585
[13] Granot, D.; Huberman, G., Minimum cost spanning tree games, Mathematical Programming, 21, 1-18 (1981) · Zbl 0461.90099 · doi:10.1007/BF01584227
[14] Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 58, 301, 13-30 (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[15] Lozano, S., DEA production games, European Journal of Operational Research, 231, 2, 405-413 (2013) · Zbl 1317.90106 · doi:10.1016/j.ejor.2013.06.004
[16] Maleki, S., Tran, T. L., Hines, G., Rahwan, T., & Rogers, A. (2013). Bounding the estimation error of sampling-based shapley value approximation. In CoopMAS 2014, AAMAS 14.
[17] Mann, I., & Shapley, L. S. (1960). Values for large games, IV: Evaluating the Electoral College by Monte Carlo Techniques. The Rand Corporation, technical report.
[18] Michalak, TP; Aadithya, KV; Szczepanski, PL; Ravindran, B.; Jennings, NR, Efficient computation of the shapley value for game-theoretic network centrality, Journal of Artificial Intelligence Research, 46, 607-650 (2013) · Zbl 1280.91035 · doi:10.1613/jair.3806
[19] Nishizaki, I.; Hayashida, T.; Shintomi, Y., A core-allocation for a network restricted linear production game, Annals of Operations Research, 238, 1, 389-410 (2016) · Zbl 1347.91075 · doi:10.1007/s10479-016-2109-4
[20] O’Brien, G.; El Gamal, A.; Rajagopal, R., Shapley value estimation for compensation of participants in demand response programs, IEEE Transactions on Smart Grid, 6, 6, 2837-2844 (2015) · doi:10.1109/TSG.2015.2402194
[21] Owen, G., On the core of linear production games, Mathematical Programming, 9, 358-370 (1975) · Zbl 0318.90060 · doi:10.1007/BF01681356
[22] Shapley, L. S. (1953). A value for n-person games. Contributions to the theory of Games II (pp. 307-317). Princeton University Press. · Zbl 0050.14404
[23] Shapley, LS; Shubik, M., A method for evaluating the distribution of power in a committee system, American Political Science Review, 48, 787-792 (1954) · doi:10.2307/1951053
[24] Shapley, LS; Shubik, M., The assignment game I: The core, International Journal of Game Theory, 1, 111-130 (1971) · Zbl 0236.90078 · doi:10.1007/BF01753437
[25] Tamir, A., On the core of network synthesis games, Mathematical Programming, 50, 1, 123-135 (1991) · Zbl 0722.90091 · doi:10.1007/BF01594930
[26] Weber, RJ; Roth, A., Probabilistic values for games, The Shapley value: Essays in honor of Lloyd S. Shapley, 101-119 (1988), Cambridge: Cambridge University Press, Cambridge · Zbl 0707.90100
[27] Wolsey, LA; Nemhauser, GL, Integer and combinatorial optimization (1999), Hoboken: Wiley, Hoboken · Zbl 0944.90001
[28] Young, HP, Monotonic solutions of cooperative games, International Journal of Game Theory, 14, 2, 65-72 (1985) · Zbl 0569.90106 · doi:10.1007/BF01769885
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.