联盟结构和交流网络限制下合作博弈的Shapley值研究进展

doi:10.16381/j.cnki.issn1003-207x.2024.1662

摘要/Abstract

摘要：

合作博弈通过指定所有潜在局中人联盟的价值来描述现实中的分配问题，它的解旨在将最大联盟的价值公平地分配给所有局中人。 Shapley值是合作博弈最重要的解概念之一，本文关注联盟结构和交流网络限制下合作博弈的Shapley值。Shapley值在联盟博弈和网络博弈中都有多种扩展。文中首先对Shapley值在联盟博弈和网络博弈中的扩展进行梳理总结。联盟博弈部分，不仅关注传统联盟结构，还关注联盟组合和层次结构这两种推广形式。网络博弈部分，不仅关注传统交流网络，还关注超网络这一推广形式。随后，进一步梳理Shapley值在联盟结构和交流网络双重限制下合作博弈中的扩展。不仅关注联盟结构和交流网络相互独立的联盟网络博弈，还关注二者相互关联的两层网络博弈。研究结果厘清了Shapley值在各领域的发展脉络，可为现实中的分配问题提供决策参考。

关键词: 合作博弈, 联盟结构, 交流网络, Shapley值

Abstract:

A cooperative game describes real-world allocation problems by specifying the worth of all potential coalitions of players. A solution of cooperative games aims to distribute the worth of the grand coalition among all players fairly. The Shapley value is one of the most important solution concepts in cooperative game theory. The paper focuses on the Shapley values for cooperative games with a coalition structure or a communication network. A coalition structure is a partition of the player set， where each component acts as an intermediary node during the allocation process. The Aumann-Drèze value， the Owen value， and the two-step Shapley value are well-known extensions of the Shapley value to cooperative games with a coalition structure. A communication network consists of nodes and edges， where nodes and edges represent players and communication relationships between players， respectively. Only connected players in the network can communicate with each other. The Myerson value， the position value， and the average tree solution are well-known extensions of the Shapley value to cooperative games with a communication graph. The underlying paper aims to review these extensions. For coalition games， both the traditional coalition structure and the extended forms of coalition configurations and level structure are concerned. For network games， the extended form of hyper-network is also studied. Moreover， the extensions of the Shapley value to cooperative games with both a coalition structure and a communication network are also reviewed， where two cases are considered： 1） coalition network games in which the coalition structure and the communication network are independent； 2） two-layer network games in which the two are interrelated. According to these reviews， the relationship between different Shapley value extensions are more clear， which may support decision making in reality.

Key words: Cooperative game, coalition structure, communication network, Shapley value

中图分类号:

C931

胡勋锋, 单而芳, 李登峰. 联盟结构和交流网络限制下合作博弈的Shapley值研究进展[J]. 中国管理科学, 2025, 33(1): 140-152.

Xunfeng Hu, Erfang Shan, Dengfeng Li. The Shapley Values for Cooperative Games with a Communication Ggraph or a Coalition Structure： A Survey[J]. Chinese Journal of Management Science, 2025, 33(1): 140-152.

参考文献 76

1	von Neumann J， Morgenstern O. Theory of games and economic behavior［M］. Princeton： Princeton University Press， 1944.
2	Shapley L S. A value for n -person games［M］// Kuhn H W， Tucker A W. Contributions to the theory of games II. Princeton： Princeton University Press， 1953：307-317.
3	Myerson R B. Graphs and cooperation in games［J］. Mathematics of Operations Research， 1977， 2（3）：225-229.
4	Aumann R J， Drèze J H. Cooperative games with coalition structures［J］. International Journal of Game Theory， 1974， 3（4）：217-237.
5	Vazquez-Brage M， Garcia-Jurado I， Carreras F. The owen value applied to games with graph-restricted communication［J］. Games and Economic Behavior， 1996， 12（1）：42-53.
6	Kongo T. Value of games with two-layered hypergraphs［J］. Mathematical Social Sciences， 2011， 62（2）：114-119.
7	Kamijo Y. A two-step shapley value for cooperative games with coalition structures［J］. International Game Theory Review， 2009， 11（2）：207-214.
8	Shapley L S. Additive and non-additive set functions［D］. Princeton： Princeton University， 1953.
9	Kamijo Y. The collective value： A new solution for games with coalition structures［J］. TOP， 2013， 21（3）：572-589.
10	Slikker M， van den Nouweland A. Social and economic networks in cooperative game theory［M］. New York： Springer US， 2001.
11	van den Brink R， Khmelnitskaya A， van der Laan G. An efficient and fair solution for communication graph games［J］. Economics Letters， 2012， 117（3）：786-789.
12	Hu X F， Xu G J， Li D F. The egalitarian efficient extension of the Aumann-Drèze value［J］. Journal of Optimization Theory and Applications， 2019， 181（3）：1033-1052.
13	Wiese H. Measuring the power of parties within government coalitions［J］. International Game Theory Review， 2007， 9（2）：307-322.
14	Casajus A. Outside options， component efficiency， and stability［J］. Games and Economic Behavior， 2009， 65（1）：49-61.
15	Alonso-Meijide J M， Carreras F， Costa J， et al. The proportional partitional shapley value［J］. Discrete Applied Mathematics， 2015， 187：1-11.
16	Tutic A， Pfau S， Casajus A. Experiments on bilateral bargaining in markets［J］. Theory and Decision， 2011， 70（4）：529-546.
17	Casajus A， Tutic A. Nash bargaining， shapley threats， and outside options［J］. Mathematical Social Sciences， 2013， 66（3）：262-267.
18	Owen G， Values of games with a priori unions［M］. Henn R， Moeschlin O. Essays in Mathematical Economics and Game Theory. Berlin： Springer-Verlag， 1977： 76-88.
19	Gomez-Rua M， Vidal-Puga J. The axiomatic approach to three values in games with coalition structure［J］. European Journal of Operational Research， 2010， 207（2）：795-806.
20	Levy A， McLean R P. Weighted coalition structure values［J］. Games and Economic Behavior， 1989， 1（3）：234-249.
21	Vidal-Puga J. The harsanyi paradox and the “right to talk” in bargaining among coalitions［J］. Mathematical Social Sciences， 2012， 64（3）：214-224.
22	Alonso-Meijide J M， Fiestras-Janeiro M G. Modification of the banzhaf value for games with a coalition structure［J］. Annals of Operations Research， 2002， 109（1）：213-227.
23	Amer R， Carreras F， Gimenez J M. The modified Banzhaf value for games with coalition structure： An axiomatic characterization［J］. Mathematical Social Sciences， 2002， 43（1）：45-54.
24	Calvo E， Gutierrez E. The shapley-solidarity value for games with a coalition structure［J］. International Game Theory Review， 2013， 15（1）：1350002.
25	Hu X F. The weighted Shapley-egalitarian value for cooperative games with a coalition structure［J］. TOP， 2019， 28（1）：193-212.
26	Albizuri M J， Aurrecoechea J， Zarzuelo J M. Configuration values： Extensions of the coalitional owen value［J］. Games and Economic Behavior， 2006， 57（1）：1-17.
27	Albizuri M J， Aurrekoetxea J. Coalition configurations and the banzhaf index［J］. Social Choice and Welfare， 2006， 26（3）：571-596.
28	Albizuri J， Vidal-Puga J. Values and coalition configurations［J］. Mathematical Methods of Operations Research， 2015， 81（1）：3-26.
29	Chalkiadakis G， Elkind E， Markakis E， et al. Cooperative games with overlapping coalitions［J］. Journal of Artificial Intelligence Research， 2010， 39：179-216.
30	Mahdiraji H A， Razghandi E， Hatami-Marbini A. Overlapping coalition formation in game theory： A state-of-the-art review［J］. Expert Systems with Applications， 2021， 174： 114752.
31	Agbaglah M. Overlapping coalitions， bargaining and networks［J］. Theory and Decision， 2016， 82（3）：435-459.
32	Myerson R B. Conference structures and fair allocation rules［J］. International Journal of Game Theory， 1980， 9（3）：169-182.
33	Winter E. A value for cooperative games with levels structure of cooperation［J］. International Journal of Game Theory， 1989， 18（2）：227-240.
34	Gomez-Rua M， Vidal-Puga J. Balanced per capita contributions and level structure of cooperation［J］. TOP， 2011， 19（1）：167-176.
35	Besner M. Weighted shapley hierarchy levels values［J］. Operations Research Letters， 2019， 47（2）：122-126.
36	胡勋锋，李登峰. 带层次结构效用可转移合作对策的多步Shapley值［J］. 系统工程理论与实践， 2016， 36（7）：1863-1870.
	Hu X F， Li D F. The multi-step Shapley value of transferable utility cooperative games with a level structure［J］. Systems Engineering-Theory and Practice， 2016， 36（7）：1863-1870.
37	胡勋锋，李登峰. 带层次结构效用可转移合作对策的collective值［J］. 系统科学与数学， 2017， 37（1）：172-185.
	Hu X F， Li D F. The collective value of transferable utility cooperative games with a level structure［J］. Journal of Systems Science and Mathematical Sciences， 2017， 37（1）：172-185.
38	李登峰，胡勋锋. 层次结构合作博弈的单值解［M］. 北京：科学出版社， 2023.
	Li D F， Hu X F. Values for cooperative games with a level structure［M］. Beijing： China Science Publishing and Media Ltd， 2023.
39	Beal S， Casajus A， Huettner F. Efficient extensions of the myerson value［J］. Social Choice and Welfare， 2015， 45（4）：819-827.
40	Meessen R. Communication games［D］. Nijmegen： Nijmegen University Press， 1988.
41	Demange G. On group stability in hierarchies and networks［J］. Journal of Political Economy， 2004， 112（4）：754-778.
42	Baron R， Beal S， Remila E， et al. Average tree solutions and the distribution of harsanyi dividends［J］. International Journal of Game Theory， 2011， 40（2）：331-349.
43	Herings J J， Laan G， Talman D. The average tree solution for cycle-free graph games［J］. Games and Economic Behavior， 2008， 62（1）： 77-92.
44	Herings P， van der Laan G， Talman A， et al. The average tree solution for cooperative games with communication structure［J］. Games and Economic Behavior， 2010， 68（2）：626-633.
45	Kang L， Khmelnitskaya A， Shan E F， et al. The two-step average tree value for graph and hypergraph games［J］. Annals of Operations Research， 2023， 323（1-2）：109-129.
46	Beal S， Remila E， Solal P. Compensations in the Shapley value and the compensation solutions for graph games［J］. International Journal of Game Theory， 2012， 41（1）：157-178.
47	Beal S， Casajus A， Huettner F. On the existence of efficient and fair extensions of communication values for connected graphs［J］. Economics Letters， 2016， 146：103-106.
48	Hu X F， Li D F， Xu G J. Fair distribution of surplus and efficient extensions of the myerson value［J］. Economics Letters， 2018， 165：1-5.
49	Beal S， Remila E， Solal P. Fairness and fairness for neighbors： The difference between the myerson value and component-wise egalitarian solutions［J］. Economics Letters， 2012， 117（1）：263-267.
50	Shan E， Han J， Shi J. The efficient proportional myerson values［J］. Operations Research Letters， 2019， 47（6）：574-578.
51	Li D L， Shan E. Efficient quotient extensions of the Myerson value［J］. Annals of Operations Research， 2020， 292（1）：171-181.
52	Hamiache G. A matrix approach to TU games with coalition and communication structures［J］. Social Choice and Welfare， 2012， 38（1）：85-100.
53	Xu G， Driessen T S， Sun H. Matrix analysis for associated consistency in cooperative game theory［J］. Linear Algebra and its Applications， 2006， 428（7）：1571-1586.
54	胡勋锋，李登峰，张庆. 基于矩阵方法的Myerson值的一种规范化［J］. 应用数学学报， 2017， 40（3）：321-330.
	Hu X F， Li D F， Zhang Q. A normalization of the <Myerson value with the matrix approach［J］. Acta Mathematicae Applicatae Sinica， 2017， 40（3）：321-330.
55	Beal S， Casajus A， Huettner F. Efficient extensions of communication values［J］. Annals of Operations Research， 2018， 264（1-2）：41-56.
56	单而芳，谢娜娜，张广. 基于平均树值的无圈图博弈有效解［J］. 运筹与管理， 2017， 26（10）：20-26.
	Shan E F， Xie N N， Zhang G. An efficient solution of cycle-free graph games based on AT value［J］. Operations Research and Management Science， 2017， 26（10）：20-26.
57	van den Nouweland A， Borm P， Tijs S. Allocation rules for hypergraph communication situations［J］. International Journal of Game Theory， 1992， 20（3）：255-268.
58	Shan E， Zhang G， Shan X. The degree value for games with communication structure［J］. International Journal of Game Theory， 2018， 47（3）：857-871.
59	Li D L， Shan E. A new value for communication situations［J］. Mathematical Methods of Operations Research， 2024， 100：535-551.
60	Kang L， Khmelnitskaya A， Shan E， et al. The average tree value for hypergraph games［J］. Mathematical Methods of Operations Research， 2021， 94（3）：437-460.
61	Wang G， Cai L， Shan E. The efficient proportional myerson values for hypergraph games［J］. Mathematical Problems in Engineering， 2021， 2021（29）：1-5.
62	单而芳，曾晗，韩佳玉. 无圈超图对策上的有效平均树解［J］. 系统工程理论与实践， 2021， 41（3）：781-789.
	Shan E F， Zeng H， Han J Y. The efficient average tree solution for cycle-free hypergraph games［J］. Systems Engineering-Theory and Practice， 2021， 41（3）：781-789.
63	Alonso-Meijide J M， Alvarez Mozos M， Fiestras-janeiro M G. Values of games with graph restricted communication and a priori unions［J］. Mathematical Social Sciences， 2009， 58（2）：202-213.
64	van den Brink R， van der Laan G， Moes N. Values for transferable utility games with coalition and graph structure［J］. TOP， 2015， 23（1）：1-23.
65	Shan E， Shi J， Lyu W. The efficient partition surplus owen graph value［J］. Annals of Operations Research， 2023， 320（1）：379-392.
66	Tejada O， Alvarez-Mozos M. Graphs and （levels of） cooperation in games： Two ways how to allocate the surplus［J］. Mathematical Social Sciences， 2018， 93：114-122.
67	Khmelnitskaya A. Values for games with two-level communication structures［J］. Discrete Applied Mathematics， 2024， 166：34-50.
68	van den Brink R， Khmelnitskaya A， van der Laan G. An owen-type value for games with two-level communication structure［J］. Annals of Operations Research， 2016， 243（1-2）：179-198.
69	Beal S， Khmelnitskaya A， Solal P. Two-step values for games with two-level communication structure［J］. Journal of combinatorial optimization， 2018， 35（2）：563-587.
70	Slikker M， van den Nouweland A. Communication situations with asymmetric players［J］. Mathematical Methods of Operations Research， 2000， 52（1）：39-56.
71	徐梦秋. 公平的类别与公平中的比例［J］. 中国社会科学， 2001（1）：35-43.
	Xu M Q. The classification of fairness and the proportions in different kinds of fairness［J］. Social Science in China， 2001（1）：35-43.
72	易小明. 分配正义的两个基本原则［J］. 中国社会科学， 2015（3）：4-22.
	Yi X M. The two basic principles of distributive justice［J］. Social Science in China， 2015（3）：4-22.
73	Schmeidler D. The nucleolus of a characteristic function game［J］. SIAM Journal on Applied Mathematics， 1969， 17（6）：1163-1170.
74	Meng F Y， Chen X H， Zhang Q. A coalitional value for games on convex geometries with a coalition structure［J］. Applied Mathematics and Computation， 2015， 266：205-214.
75	Meng F Y， Tang J， Ma B， et al. Proportional coalition values for monotonic games on convex geometries with a coalition structure［J］. Journal of Computational and Applied Mathematics， 2018， 348（1）：34-47.
76	Meng F Y， Zhang Q. Cooperative games on convex geometries with a coalition structure［J］. Journal of Systems Science and Complexity， 2012， 25（5）：909-925.

[1]	饶卫振,苗晓河,刘露. 考虑企业配送能力约束的协作配送模型及成本分摊影响研究[J]. 中国管理科学, 2024, 32(7): 106-116.
[2]	陶良彦,王丽,齐晓霞,陈顶,刘思峰. 武器装备体系贡献率评估灰色Shapley值模型[J]. 中国管理科学, 2024, 32(4): 89-96.
[3]	杨洁, 戴幼玲, 赖礼邦, 李登峰. 具有优先结盟的多层级联盟结构合作博弈及其在跨界流域治理中的应用[J]. 中国管理科学, 2024, 32(12): 300-311.
[4]	刘舰, 方希荣, 张双枣. 中小无车承运人集中化运输合作[J]. 中国管理科学, 2024, 32(11): 136-143.
[5]	单而芳,史纪磊,蔡蕾. 具有联盟和概率图结构合作对策的分配规则及其应用[J]. 中国管理科学, 2024, 32(1): 137-145.
[6]	单而芳. 河流洪水风险控制的合作博弈分析[J]. 中国管理科学, 2023, 31(9): 45-51.
[7]	倪宣明, 邱语宁, 赵慧敏. 私募基金市场融资缺口的形成机理与解决路径研究[J]. 中国管理科学, 2023, 31(7): 91-102.
[8]	耿心宇, 秦开大. 基于多物品委托拍卖的供应链协调研究[J]. 中国管理科学, 2023, 31(5): 260-268.
[9]	戴前智,徐晓迟,雷西洋,赵茜. 基于动态非合作博弈超效率DEA的成本补偿激励方法研究[J]. 中国管理科学, 2023, 31(12): 185-192.
[10]	南江霞, 魏骊晓, 李登峰, 张茂军. 具有联盟优先关系的模糊合作博弈的目标规划求解模型[J]. 中国管理科学, 2022, 30(7): 231-240.
[11]	梁开荣, 李登峰. 竞合模式对平台供应链线上分销策略的影响研究*[J]. 中国管理科学, 2022, 30(12): 305-316.
[12]	谢隽阳, 乐为, 郭本海. 基于生产者责任延伸的新能源汽车动力电池回收帕累托均衡[J]. 中国管理科学, 2022, 30(11): 309-320.
[13]	冯海荣, 曾银莲, 周杰. 碳交易机制下零售商合作的费用分配研究[J]. 中国管理科学, 2021, 29(5): 108-116.
[14]	南江霞, 王盼盼, 李登峰. 非合作-合作两型博弈的Shapley值纯策略纳什均衡解求解方法[J]. 中国管理科学, 2021, 29(5): 202-210.
[15]	王树强, 刘赫, 徐娜, 孟娣. 大气污染物排放权初始分配的区际协调方法研究[J]. 中国管理科学, 2021, 29(3): 37-48.