具有超图合作结构的Banzhaf值

doi:10.15960/j.cnki.issn.1007-6093.2023.03.013

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 159-168.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.013

具有超图合作结构的Banzhaf值

吕文蓉¹, 单而芳¹^,*()

1. 上海大学管理学院, 上海 200444

收稿日期:2019-10-08 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 单而芳 E-mail:efshan@shu.edu.cn
作者简介:单而芳, E-mail: efshan@shu.edu.cn
基金资助:
国家自然科学基金(11971298)

The Banzhaf value for hypergraph communication situations

Wenrong LYU¹, Erfang SHAN¹^,*()

1. School of Management, Shanghai University, Shanghai 200444, China

Received:2019-10-08 Online:2023-09-15 Published:2023-09-14
Contact: Erfang SHAN E-mail:efshan@shu.edu.cn

摘要/Abstract

摘要：

2006年，Alonso-Meijide和Fiestras-Janeiro考虑了以图作为合作结构的可转移效用对策模型（简称为图对策），提出了图对策Banzhaf值，它是经典Banzhaf值的一类推广。本文进一步将Banzhaf值推广到超图对策中，定义了超图对策Banzhaf值。其次，证明了超图对策Banzhaf值满足分支可分解性、分支总贡献性、公平性、平衡贡献性以及隔离性，并给出了该值的两种公理性刻画。最后，举例分析了超图对策Banzhaf值所满足的性质。

关键词: TU-对策, 图对策, 超图, 超图对策, Banzhaf值

Abstract:

Alonso-Meijide and Fiestras-Janeiro(2006) introduced TU games with restricted cooperative structure represented by an undirected graph, or simple graph games, and present the Banzhaf value of the graph game, that extend the Banzhaf value. In this paper, we first generalize the Banzhaf value to the hypergraph game, define the Banzhaf value of the hypergraph game. Secondly, we prove that the Banzhaf value of the hypergraph game satisfies the property of component decomposability, component total contribution, fairness, balanced contribution, and isolation, and propose two characterizations of this value. Finally, we give an example to illustrate the properties satisfied by the Banzhaf value of the hypergraph game.

Key words: TU-game, graph game, hypergraph, hypergraph game, Banzhaf value

中图分类号:

F224.32

吕文蓉, 单而芳. 具有超图合作结构的Banzhaf值[J]. 运筹学学报, 2023, 27(3): 159-168.

Wenrong LYU, Erfang SHAN. The Banzhaf value for hypergraph communication situations[J]. Operations Research Transactions, 2023, 27(3): 159-168.

图/表 2

1	Branzei R , Dimitrov D , Tijs S . Models in Cooperative Game Theory[M]. Berlin: Springer, 2008.
2	Myerson R B . Graphs and cooperation in games[J]. Mathematics of Operations Research, 1977, 2 (3): 225- 229. doi: 10.1287/moor.2.3.225
3	Shapley L S. A value for n-person games [M]// Contributions to the Theory of Games. Princeton: Princeton University Press, 1953: 307-317.
4	Myerson R B . Conference structures and fair allocation rules[J]. International Journal of Game Theory, 1980, 9 (3): 169- 182. doi: 10.1007/BF01781371
5	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. doi: 10.1007/BF01253780
6	Calvo E , Lasaga J , van den Nouweland A . Values of games with probabilistic graphs[J]. Mathematical Social Sciences, 1999, 37 (1): 79- 95. doi: 10.1016/S0165-4896(98)00013-4
7	González-Arangjena E , Manuel C M , Pozo M D . Values of games with weighted graphs[J]. European Journal of Operational Research, 2015, 243 (1): 248- 257. doi: 10.1016/j.ejor.2014.11.033
8	Khmelnitskaya A , Selçuk Ö , Talman D . The Shapley value for directed graph games[J]. Operations Research Letters, 2016, 44 (1): 143- 147. doi: 10.1016/j.orl.2015.12.009
9	Owen G . Values of graph-restricted games[J]. Society for Industrial and Applied Mathematics, 1986, 7 (2): 210- 220.
10	Owen G . Multilinear extensions and the Banzhaf value[J]. Naval Research Logistics Quarterly, 1975, 22 (4): 741- 750. doi: 10.1002/nav.3800220409
11	Alonso-Meijide J M , Fiestras-Janeiro M G . The Banzhaf value and communication situations[J]. Naval Research Logistics, 2006, 53 (3): 198- 203. doi: 10.1002/nav.20132
12	Lehrer E . An axiomatization of the Banzhaf value[J]. International Journal of Game Theory, 1988, 17 (2): 89- 99. doi: 10.1007/BF01254541
13	Gómez D , González-Arangüena E , Manuel C , et al. Centrality and power in social networks: A game theoretic approach[J]. Mathematical Social Sciences, 2003, 46 (1): 27- 54. doi: 10.1016/S0165-4896(03)00028-3
14	李思文, 赵加贵, 单而芳. 超网络博弈的位置值的公理化刻画[J]. 运筹学学报, 2019, 23 (4): 165- 174.

[1]	余桂东, 袁慧, 谢欣宇. 给定直径的超树的第二大无符号拉普拉斯半径[J]. 运筹学学报（中英文）, 2025, 29(4): 241-248.
[2]	吴志伟, 康丽英. 可消去超图p-谱半径的极值问题[J]. 运筹学学报（中英文）, 2025, 29(2): 194-200.
[3]	刘欣恬, 朱文兴. 超图平衡二划分的离散迭代优化算法[J]. 运筹学学报（中英文）, 2025, 29(2): 128-140.
[4]	杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.
[5]	王蝶, 康丽英. 一般超图的张量谱性质[J]. 运筹学学报, 2023, 27(1): 138-148.
[6]	韩佳玉, 于志强, 赵加贵, 单而芳. 超图对策的组内和组间位置值[J]. 运筹学学报, 2022, 26(4): 107-118.
[7]	赵静, 单而芳, 赵加贵. 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021, 25(1): 123-131.
[8]	童林肯, 单而芳. 超图的限制边连通度与最优限制边连通[J]. 运筹学学报, 2020, 24(4): 145-152.
[9]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报（中英文）, 2019, 23(3): 77-90.
[10]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[11]	李姗, 单而芳, 张琳. 5-正则图的全控制数的一个注记[J]. 运筹学学报, 2017, 21(1): 125-128.
[12]	林苡, 倪振羽, 单而芳. 5-一致超图的全横贯[J]. 运筹学学报, 2016, 20(2): 97-104.
[13]	张欣玥, 黄正海, 李志明. 基于判别超图和非负矩阵分解的人脸识别方法[J]. 运筹学学报, 2015, 19(3): 108-115.
[14]	聂翠平, 张强. 模糊联盟合作对策的平均树解[J]. 运筹学学报, 2012, 16(4): 77-85.
[15]	王文文, 孙浩, 韩卫彬. 图限制下合作对策的t值[J]. 运筹学学报, 2011, 15(4): 75-84.

具有超图合作结构的Banzhaf值

The Banzhaf value for hypergraph communication situations

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

相关文章 15

编辑推荐

Metrics

本文评价