区间合作博弈Shapley值的矩阵计算方法

doi:10.12341/jssms22210

系统科学与数学 ›› 2023, Vol. 43 ›› Issue (2): 342-355.DOI: 10.12341/jssms22210

区间合作博弈Shapley值的矩阵计算方法

李志强¹, 李文鸽², 崔春生²

1. 河南财经政法大学数学与信息科学学院, 郑州 450046;
2. 河南财经政法大学计算机与信息工程学院, 郑州 450046

收稿日期:2022-03-29 修回日期:2022-07-14 出版日期:2023-02-25 发布日期:2023-03-16
通讯作者: 李志强,Email:lizhiqiang@amss.ac.cn
基金资助:
国家自然科学基金(11872175,62073122),河南省高等学校重点科研项目(20A120003,21A120001,22A880007),河南财经政法大学国家一般项目培育项目,河南财经政法大学青年拔尖人才资助课题.

PDF ( 4 ) 引用

李志强,李文鸽,崔春生. 区间合作博弈Shapley值的矩阵计算方法[J]. 系统科学与数学, 2023, 43(2): 342-355.

LI Zhiqiang, LI Wenge, CUI Chunsheng. Matrix Approach to Calculation of Shapley Value for Interval Cooperative Games[J]. Journal of Systems Science and Mathematical Sciences, 2023, 43(2): 342-355.

Matrix Approach to Calculation of Shapley Value for Interval Cooperative Games

LI Zhiqiang¹, LI Wenge², CUI Chunsheng²

1. School of Mathematics and Information Science, Henan University of Economics and Law, Zhengzhou 450046;
2. School of Computer and Information Engineering, Henan University of Economics and Law, Zhengzhou 450046

Received:2022-03-29 Revised:2022-07-14 Online:2023-02-25 Published:2023-03-16

在合作博弈中,Shapley单点解按照参与者对联盟的边际贡献率对联盟的收益进行分配.联盟收益具有不确定性,往往不能用精确数值表示,更多学者关注特征函数取值为有限区间的合作博弈(区间合作博弈)的收益分配.文章利用矩阵半张量积,研究区间合作博弈中含有折扣因子的Shapley区间值的矩阵计算.首先利用矩阵的半张量积将合作博弈的特征函数表示为矩阵形式,得到特征函数区间矩阵.然后通过构造区间合作博弈Shapley矩阵,将区间合作博弈的Shapley值(区间)计算转化为矩阵形式.最后利用区间合作博弈Shapley值矩阵公式计算分析航空公司供应链联盟收益的Shapley值.文章给出的区间合作博弈Shapley值的矩阵计算公式形式简洁,为区间合作博弈的研究提供了新的思路.

关键词： 矩阵半张量积, 区间合作博弈, Shapley值, 区间矩阵, 折扣因子

In the cooperative game, the Shapley value solution provides the expected marginal income of the largest alliance formed by each player in random ordering. Due to the uncertainty of alliance profits, alliance interests cannot often be expressed by exact values. Thus, more scholars pay attention to the benefits allocation of the interval cooperative game. In this paper, the algebraic formula for the Shapley value of the interval cooperation game with discount factor is provided by using the semi-tensor product of the matrices. Firstly, the characteristic function of interval cooperative game is transformed into its algebraic representation by using the semitensor product of matrices, and the interval characteristic matrix is obtained. Then the Shapley matrix is constructed, and the formula of Shapley value for interval cooperative game is expressed as the product of characteristic function matrix and Shapley matrices. Finally, the formula obtained in this paper is used to calculate the Shapley value of airline supply chain alliance. The matrix form of Shapley value obtained in this paper simplifies the calculation and also provides a new idea for the research of interval cooperative game.

Key words: Semi-tensor product of matrices, interval cooperative game, Shapley value, interval matrix, discount factor

MR(2010)主题分类:

91A06
91A10

分享此文:

[1] Shapley L S. A Value for n-Person Games. Princeton:Princeton University Press, 1953.
[2] Branzei R, Dimitrov D, Tijs S. 合作博弈理论模型. 北京:科学出版社, 2011. (Branzei R, Dimitrov D, Tijs S. Models in Cooperative Game Theory. Beijing:Science Press, 2011.)
[3] Jean D, Hans H, Hans P. The selectope for cooperative games. International Journal of Game Theory, 2000, 29(1):23-38.
[4] Gillies D B. Solutions to general non-zero-sum games. Eds. by Tucker A W & Luce R D, Contributions to the Theory of Games IV, 47-85. Princeton N J:Princeton University Press, 1959.
[5] 胡石清. 社会合作中利益如何分配?——超越夏普利值的合作博弈"宗系解". 管理世界, 2018, 34(6):83-93. (Hu S Q. How to Distribute the benefits in social cooperation? "The Clique Solution" of cooperative game surpassing Shapley value. Management World, 2018, 34(6):83-93.)
[6] Yuan J, Peter B, Pieter R. The consensus value: A new solution concept for cooperative games. Social Choice and Welfare, 2007, 28(4):685-703.
[7] Cheng D Z, Xu T T. Application of STP to cooperative games. Proceedings of 10th IEEE International Conference on Control and Automation (ICCA), 2013, 1680-1685.
[8] Wang Y, Alsaadi F E, Liu Z, et al. Matrix expression of Shapley value in graphical cooperative games. Mathematical Problems in Engineering, 2020, Article ID 2045654.
[9] Li H T, Wang S L, Liu A X, et al. Simplification of Shapley value for cooperative games via minimum carrier. Control Theory & Applications, 2021, 19(2):157-169.
[10] Branzei R, Dimitrov D, Tijs S. Shapley-like values for interval bankruptcy games. Economics Bulletin, 2003, 3(8):1-8.
[11] Yager R R, Kreinovich V. Fair division under interval uncertainty. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2000, 8(5):611-618.
[12] Palanci O, Alparslan Gök S Z A, Olgun M O, et al. Transportation interval situations and related games. OR Spectrum, 2016, 38(1):119-136.
[13] 高作峰, 邹正兴, 马栋, 等. 区间合作对策在增广系统上的区间Shapley值. 模糊系统与数学, 2013, 27(4):148-156. (Gao Z F, Zou Z X, Ma D. Interval Shapley value for cooperative interval game on augmenting systems. Fuzzy System and Mathematics, 2013, 27(4):148-156.)
[14] Han W B, Sun H, Xu G J. A new approach of cooperative interval games:The interval core and Shapley value revisited. Operations Research Letters, 2012, 40(6):462-468.
[15] Moore R E. Methods and Applications of Interval Analysis. Philadelphia:Society for Industrial and Applied Mathematics, 1979.
[16] 于晓辉, 周鸿, 邹正兴, 等. 基于区间与模糊Shapley值的合作收益分配策略. 运筹与管理, 2018, 27(8):149-154. (Yu X H, Zhou H, Zou Z X. Allocation scheme based on interval and fuzzy Shapley value. Operations Research and Management Science, 2018, 27(8):149-154.)
[17] Bilbao J M, Ordóñez M. Axiomatizations of the Shapley value for games on augmenting systems. European Journal of Operational Research, 2009, 196(3):1008-1014.
[18] Palanci O, Alparalan Gök S Z, Ergün S, et al. Cooperative grey games and the grey Shapley value. Optimization, 2015, 64(8):1657-1668.
[19] Alparslan Gök S Z, Miquel S, Tijs S H. Cooperation under interval uncertainty. Mathematical Methods of Operations Research, 2009, 69(1):99-109.
[20] Fei W, Li D F, Ye Y F. An approach to computing interval-valued discounted Shapley values for a class of cooperative games under interval data. International Journal of General Systems, 2018, 47(8):794-808.
[21]Brink R, Funaki Y. Implementation and axiomatization of discounted Shapley values. Social Choice Welfare, 2015, 45:329-344.
[22]Brink R. Null or nullifying players:The difference between the Shapley value and equal division solutions. Journal of Economic Theory, 2007, 136(1):767-775.
[23] Zhang X, Cheng D Z. Profile-dynamic based fictitious play. Science China Information Sciences, 2021, 64(6):169-202.
[24] Wang Y H, Cheng D Z. On coset weighted potential game. Journal of the Franklin Institute, 2020, 357(9):5523-5540.
[25] Li C X, He F H, Liu T, et al. Symmetry-based decomposition of finite games. Science China Information Sciences, 2019, 62(1):1-13.
[26] Cheng D Z, W Y H, Zhao G D, et al. A comprehensive survey on STP approach to finite games. Journal of Systems Science and Complexity, 2021, 34(5):1666-1680.
[27] Cheng D Z, Qi H S, Zhao Y. An Introduction to Semi-Tensor Product of Matrices and Its Applications. Singapore:World Scientific, 2012.
[28] Cheng D Z, Qi H S. Semi-Tensor Product of Matrix-Theory and Applications. Beijin:Science Press, 2007.
[29] Li D F. Models and Methods for Interval-Valued Cooperative Games in Economic Management. Switzerland:Springer International Publishing, 2016.
[30] Liu Y, Fang Z G, Liu S F. Grey Shapley model and its application in cooperative game. Journal of Grey System, 2011, 23(2):183-192.
[31] 王英, 鲍新中. 基于夏普利值的第三方物流集成供应成本分摊研究. 经济问题探索, 2014, 35(3):68-72. (Wang Y, Bao X Z. Research on cost allocation of integrated supply of third party logistics based on Shapley value. Inquiry into Economic Issues, 2014, 35(3):68-72.)
[32] 陈剑, 刘运辉. 数智化使能运营管理变革:从供应链到供应链生态系统. 管理世界, 2021, 37(11):227-240. (Chen J, Liu Y H. Operations management innovation enabled by digitalization and intellectualization:From Supply chain to supply chain ecosystem. Journal of Management World, 2021, 37(11):227-240.)

[1]	沈宇桐, 徐勇. 概率布尔网络的牵制鲁棒镇定[J]. 系统科学与数学, 2022, 42(6): 1454-1466.
[2]	延卫军, 张利军, 毕冬瑶. A^*算法的代数表示[J]. 系统科学与数学, 2022, 42(6): 1478-1489.
[3]	陈昊东, 李露露, 胡博森. 基于事件触发的延时概率布尔网络的输出跟踪[J]. 系统科学与数学, 2022, 42(10): 2847-2858.
[4]	梁开荣，李登峰，余高峰. 基于两型博弈的双边链路形成策略优化研究[J]. 系统科学与数学, 2020, 40(9): 1550-1563.
[5]	胡勋锋，李登峰. 带层次结构效用可转移合作对策的collective值[J]. 系统科学与数学, 2017, 37(1): 172-185.
[6]	贾光钰，冯俊娥. 三种单节点摄动对混合值逻辑网络极限集的影响[J]. 系统科学与数学, 2016, 36(3): 426-436.
[7]	李泉林，杨碧蕊，鄂成国，段灿. 大型并行服务系统的利润分配机制设计[J]. 系统科学与数学, 2016, 36(2): 169-.
[8]	胡勋峰，李登峰. 带层次结构效用可转移合作对策的Shapley值及其简化计算方法[J]. 系统科学与数学, 2016, 36(11): 1913-1921.
[9]	李泉林，黄亚静，鄂成国. 农超对接下农业合作社联盟的排队网络型合作博弈研究[J]. 系统科学与数学, 2016, 36(11): 1972-1985.
[10]	程代展，刘挺，王元华. 博弈论中的矩阵方法[J]. 系统科学与数学, 2014, 34(11): 1291-1305.
[11]	王莹莹，梅生伟，刘峰. 混合电力系统合作博弈规划的分配策略研究[J]. 系统科学与数学, 2012, 32(4): 418-428.
[12]	程代展，齐洪胜. 矩阵半张量积的基本原理与适用领域[J]. 系统科学与数学, 2012, 32(12): 1488-1496.
[13]	程代展，赵寅，徐听听. 演化博弈与逻辑动态系统的优化控制[J]. 系统科学与数学, 2012, 32(10): 1226-1238.
[14]	舒彤, 刘纯霞, 陈收, 张喜征. 考虑中断情况的三级供应链利润分配优化策略[J]. 系统科学与数学, 2011, 31(10): 1197-1208.
[15]	苏春华;刘思峰. 具有时变区间参数的不确定随机线性系统的均方鲁棒稳定性[J]. 系统科学与数学, 2010, 30(3): 289-295.

阅读次数

全文

摘要