图博弈的过程比例解

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

运筹学学报 ›› 2021, Vol. 25 ›› Issue (4): 101-110.doi: 10.15960/j.cnki.issn.1007-6093.2021.04.009

图博弈的过程比例解

张广¹, 肖文君², 邬冬华²^,*()

1. 上海理工大学管理学院, 上海 200093
2. 上海大学理学院, 上海 200444

收稿日期:2019-03-21 出版日期:2021-12-15 发布日期:2021-12-11
通讯作者: 邬冬华 E-mail:dhwu@staff.shu.edu.cn
作者简介:邬冬华, E-mail: dhwu@staff.shu.edu.cn
基金资助:
国家自然科学基金(71901145);上海市哲学社会科学规划课题(2019EGL010)

The procedural proportional solution for graph games

Guang ZHANG¹, Wenjun XIAO², Donghua WU²^,*()

1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
2. College of Sciences, Shanghai University, Shanghai 200444, China

Received:2019-03-21 Online:2021-12-15 Published:2021-12-11
Contact: Donghua WU E-mail:dhwu@staff.shu.edu.cn

摘要/Abstract

摘要：

本文对具有图结构合作博弈（图博弈）进行了研究，采用比例原则和过程化分配方法，定义了比例分配过程，并对其性质进行了分析。随后，针对比例分配过程的超有效情况，运用等比例妥协的方式给出满足有效性的过程比例解，并研究了稳定性。最后，将比例分配过程与过程比例解应用到破产问题中，得到图博弈过程比例解与破产问题比例规则等价的结论。

关键词: 合作博弈, 图结构, 比例分配过程, 稳定性

Abstract:

This paper studies cooperative games with graph structure, shortly graph games. By applying the proportional rule and procedural method in feasible coalitions, a so-called proportional procedure is defined and studied regarding concepts and properties. And then, according to the over-efficiency of the proposed procedure, an efficient solution concept, the procedural proportional solution, is provided by compromising with equalratio. Moreover, the stability of the solution is also investigated. Finally, the bankruptcy problems is discussed by using the proportional procedure and the procedural proportional solution, and we obtain that the proposed solution of the related graph game coincides with the proportional rule of the bankruptcy problem.

Key words: cooperative game, graph structure, proportional procedure, stability

中图分类号:

O225
F224.32

张广, 肖文君, 邬冬华. 图博弈的过程比例解[J]. 运筹学学报, 2021, 25(4): 101-110.

Guang ZHANG, Wenjun XIAO, Donghua WU. The procedural proportional solution for graph games[J]. Operations Research Transactions, 2021, 25(4): 101-110.

图/表 3

图1

表1

表2

参考文献 15

1	Myerson R B . Graphs and cooperation in games[J]. Mathematics of Operations Research, 1997, 2, 225- 229.
2	Slikker M . A characterization of the position value[J]. International Journal of Game Theory, 2005, 33, 505- 514. doi: 10.1007/s00182-005-0211-y
3	Herings P , van der Laan G , Talman A J J . The average tree solution for cycle-free graph games[J]. Games and Economic Behavior, 2008, 62, 77- 92. doi: 10.1016/j.geb.2007.03.007
4	Slikker M . Bidding for surplus in network allocation problems[J]. Journal of Economic Theory, 2007, 137, 493- 511. doi: 10.1016/j.jet.2007.01.010
5	Béal S , Rémila E , Solal P . Fairness and fairness for neighbors: The difference between the Myerson value and component-wise egalitarian solutions[J]. Economics Letters, 2012, 117, 263- 267. doi: 10.1016/j.econlet.2012.05.020
6	Haeringer G . Weighted Myerson value[J]. International Game Theory Review, 1999, 1, 187- 192. doi: 10.1142/S021919899900013X
7	Ghintran A . Weighted position values[J]. Mathematical Social Sciences, 2013, 65, 157- 163. doi: 10.1016/j.mathsocsci.2013.01.003
8	Béal S , Rémila E , Solal P . Weighted component fairness[J]. Mathematical Social Sciences, 2012, 64, 144- 151. doi: 10.1016/j.mathsocsci.2012.03.004
9	单而芳, 张广. 准许树博弈的权重准许分支公平和准许树限制核~[J]. 系统工程理论与实践, 2017, 7, 1732- 1760.
10	Shan E , Zhang G , Dong Y . Component-wise proportional solutions for communication graph games[J]. Mathematical Social Sciences, 2017, 106, 179- 187.
11	Dietzenbacher B , Borm P , Hendrickx R . The procedural egalitarian solution[J]. Games and Economic Behavior, 2017, 106, 179- 187. doi: 10.1016/j.geb.2017.10.001
12	Sun P , Hou D , Sun H , et al. Process and optimization implementation of the $\alpha$-ENSC value[J]. Mathematical Methods of Operations Research, 2017, 86, 293- 308. doi: 10.1007/s00186-017-0595-z
13	Hu X , Li D , Xu G . Fair distribution of surplus and efficient extensions of the Myerson value[J]. Economics Letters, 2018, 165, 1- 5. doi: 10.1016/j.econlet.2018.01.025
14	Shan E , Han J , Shi J . The efficient proportional Myerson values[J]. Operations Research Letters, 2019, 47, 574- 578. doi: 10.1016/j.orl.2019.10.001
15	O'Neill B . A problem of rights arbitration from the Talmud[J]. Mathematical Social Sciences, 1982, 2, 345- 371. doi: 10.1016/0165-4896(82)90029-4

$ S(\in C^L(N)) $	$ \{1\} $	$ \{2\} $	$ \{3\} $	$ \{1, 2\} $	$ \{1, 3\} $	$ \{1, 2, 3\} $
$ v(S) $	$ 0 $	$ 4 $	$ 0 $	$ 6 $	$ 0 $	$ 7 $
$ \chi^{1} $	$ (0, \cdot, \cdot) $^*	$ (\cdot, \underline{4}, \cdot) $	$ (\cdot, \cdot, 0) $	$ (3, 3, \cdot) $	$ (0, \cdot, 0) $	$ (\frac{7}{4}, \frac{7}{4}, \frac{14}{4}) $
$ \chi^{2} $	$ (0, \cdot, \cdot) $	$ (\cdot, \boldsymbol{4}, \cdot) $	$ (\cdot, \cdot, 0) $	$ (\underline{2}, {\boldsymbol{4}}, \cdot) $	$ (0, \cdot, 0) $	$ (1, \boldsymbol{4}, 2) $
$ \chi^{3} $	$ (\boldsymbol{2}, \cdot, \cdot) $	$ (\cdot, \boldsymbol{4}, \cdot) $	$ (\cdot, \cdot, 0) $	$ (\boldsymbol{2}, \boldsymbol{4}, \cdot) $	$ (\boldsymbol{2}, \cdot, -2) $	$ (\boldsymbol{2}, \boldsymbol{4}, \underline{1}) $
$ \gamma^{3} $						$ (\boldsymbol{2}, \boldsymbol{4}, \boldsymbol{1}) $

$ S(\in C^L(N)) $	$ \{1\} $	$ \{2\} $	$ \{3\} $	$ \{1, 2\} $	$ \{1, 3\} $	$ \{1, 2, 3\} $
$ v(S) $	$ 0 $	$ 4 $	$ 2 $	$ 6 $	$ 0 $	$ 7 $
$ \chi^{1} $	$ (0, \cdot, \cdot) $	$ (\cdot, \underline{4}, \cdot) $	$ (\cdot, \cdot, 2) $	$ (3, 3, \cdot) $	$ (0, \cdot, 0) $	$ (\frac{7}{4}, \frac{7}{4}, \frac{14}{4}) $
$ \chi^{2} $	$ (0, \cdot, \cdot) $	$ (\cdot, \bf{4}, \cdot) $	$ (\cdot, \cdot, 2) $	$ (\underline{2}, \bf{4}, \cdot) $	$ (0, \cdot, 0) $	$ (1, {\bf}, 2) $
$ \chi^{3} $	$ (\bf{2}, \cdot, \cdot) $	$ (\cdot, {\bf4}, \cdot) $	$ (\cdot, \cdot, \underline{2}) $	$ (\bf{2}, \bf{4}, \cdot) $	$ ({\bf 2}, \cdot, -2) $	$ ({\bf2}, {\bf4}, 1) $
$ \chi^{4} $	$ ({\bf2}, \cdot, \cdot) $	$ (\cdot, {\bf4}, \cdot) $	$ (\cdot, \cdot, \bf{2}) $	$ ({\bf2}, {\bf4}, \cdot) $	$ ({\bf2}, \cdot, {\bf2}) $	$ ({\bf2}, {\bf4}, \bf{2}) $

[1]	宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.
[2]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[3]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[4]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.
[5]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[6]	王磊, 林崇, 谷岩, 刘翠, 高红伟. 无限阶段网络博弈中合作解的策略稳定性[J]. 运筹学学报, 2018, 22(1): 77-86.
[7]	陈拼博, 王能发, 丘小玲, 王春. 可行策略对应的图像拓扑下广义博弈Nash平衡的稳定性[J]. 运筹学学报, 2017, 21(3): 77-85.
[8]	杨光惠, 杨辉, 向淑文. 有限理性下参数最优化问题解的稳定性[J]. 运筹学学报, 2016, 20(4): 1-10.
[9]	王春, 丘小玲, 王能发, 陈拼博. 关于非凸的有限理性的稳定性[J]. 运筹学学报, 2016, 20(3): 107-120.
[10]	甄孟可, 高红伟, 刘树清, 纪海强. 二元稳定网络的算法及模型[J]. 运筹学学报, 2016, 20(3): 1-10.
[11]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[12]	邓喜才，向淑文，左羽. 不确定性下强Berge均衡的存在性[J]. 运筹学学报, 2013, 17(3): 101-107.

图博弈的过程比例解

The procedural proportional solution for graph games

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 15

相关文章 12

编辑推荐

Metrics

本文评价