双边配给问题的Shapley解及其在博物馆通票问题中的应用

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 45-54.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.004

双边配给问题的Shapley解及其在博物馆通票问题中的应用

宫豆豆¹, 徐根玖¹^,*(), 侯东爽¹

1. 西北工业大学数学与统计学院, 陕西西安 710072

收稿日期:2020-11-16 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 徐根玖 E-mail:xugenjiu@nwpu.edu.cn
作者简介:徐根玖 xugenjiu@nwpu.edu.cn
基金资助:
国家自然科学基金(71671140);国家自然科学基金(72071159);国家自然科学基金(71871180)

A Shapley solution for bipartite rationing problems and its application to museum pass problems

Doudou GONG¹, Genjiu XU¹^,*(), Dongshuang HOU¹

1. School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an 710072, Shaanxi, China

Received:2020-11-16 Online:2022-06-15 Published:2022-05-27
Contact: Genjiu XU E-mail:xugenjiu@nwpu.edu.cn

摘要/Abstract

摘要：

双边配给问题描述了现实生活中一类带有二部图结构的稀缺资源配置问题, 例如, 在自然灾害期间救援物资的配给; 电力和天然气等自然资源按需分配; 高校引进人才调配等。本文通过求解线性规划, 并从联盟边际贡献的角度出发定义了双边配给问题的一个Shapley解。之后, 通过合作对策模型和解的公理化方法说明新解的合理性。首先, 建立双边配给问题的合作对策模型, 论证了新解与双边配给合作对策的Shapley值一致; 其次, 证明了Shapley解是唯一满足优先一致性的有效配给方案。最后, 将Shapley解应用于博物馆通票问题的研究, 探讨了博物馆合作制定通票后所得单票和通票收益的分配方式。

关键词: 双边配给问题, 合作对策, Shapley值, 公理化, 博物馆通票问题

Abstract:

Bipartite rationing problem was studied to divide a short supply between resource and sink nodes in a bipartite graph. It had been used to deal with numerous issues in the real world, such as, the allocations of aid relief during natural disasters, utilities like electricity and natural gas, and talents of different types to universities, etc. From the view of marginal contribution of coalitions, this paper proposed the Shapley solution of bipartite rationing problems calculated by linear programming, and characterized it by cooperative game and axiomatization. First, we defined the cooperative game of bipartite rationing problems, called the bipartite rationing game, and proved that the Shapley value of the corresponding cooperative game coincides with the solution we propose. Then, we showed that the Shapley solution is the unique feasible allocation satisfying priority-consistency. Finally, we considered the application of the Shapley solution to museum pass problems, and discussed the allocations of the revenue of single tickets and pass tickets of each participating museum.

Key words: bipartite rationing problem, cooperative game, Shapley value, axiomatization, museum pass problem

中图分类号:

O225
F275.4

宫豆豆, 徐根玖, 侯东爽. 双边配给问题的Shapley解及其在博物馆通票问题中的应用[J]. 运筹学学报, 2022, 26(2): 45-54.

Doudou GONG, Genjiu XU, Dongshuang HOU. A Shapley solution for bipartite rationing problems and its application to museum pass problems[J]. Operations Research Transactions, 2022, 26(2): 45-54.

图/表 2

参考文献 18

1	Moulin H , Sethuraman J . The bipartite rationing problem[J]. Operations Research, 2013, 61 (5): 1087- 1100. doi: 10.1287/opre.2013.1199
2	O'Neill B . A problem of rights arbitration from the Talmud[J]. Mathematical Social Sciences, 1982, 2 (4): 345- 371. doi: 10.1016/0165-4896(82)90029-4
3	İllkılıç R , Kayı Ç . Allocation rules on networks[J]. Social Choice and Welfare, 2014, 43 (4): 877- 892. doi: 10.1007/s00355-014-0815-x
4	Moulin H . Entropy, desegregation, and proportional rationing[J]. Journal of Economic Theory, 2016, 162 (6): 1- 20.
5	Moulin H . Consistent bilateral assignment[J]. Mathematical Social Sciences, 2017, 90, 43- 55. doi: 10.1016/j.mathsocsci.2016.09.004
6	Ginsburgh V , Zang I . The museum pass game and its value[J]. Games and Economic Behavior, 2003, 43 (2): 322- 325. doi: 10.1016/S0899-8256(03)00013-7
7	Casas-Méndez B , Fragnelli V , García-Jurado I . Weighted bankruptcy rules and the museum pass problem[J]. European Journal of Operational Research, 2011, 215 (1): 161- 168. doi: 10.1016/j.ejor.2011.05.033
8	Wang Y . A museum cost sharing problem[J]. American Journal of Operations Research, 2011, 1, 51- 56. doi: 10.4236/ajor.2011.12008
9	Casas-Méndez B , Fragnelli V , García-Jurado I . A survey of allocation rules for the museum pass problem[J]. Journal of Cultural Economics, 2014, 38 (2): 191- 205. doi: 10.1007/s10824-013-9202-1
10	Bergantiños G , Moreno-Ternero J D . The axiomatic approach to the problem of sharing the revenue from museum passes[J]. Games and Economic Behavior, 2015, 89, 78- 92. doi: 10.1016/j.geb.2014.12.003
11	Bergantiños G , Moreno-Ternero J D . A new rule for the problem of sharing the revenue from museum passes[J]. Operations Research Letters, 2016, 44 (2): 208- 211. doi: 10.1016/j.orl.2016.01.004
12	于晓辉, 杜志平, 张强, 等. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24 (4): 113- 127.
13	Gillies D B. Some theorems on n-person games[D]. New Jersey: Princeton University, 1953.
14	Shapley L S. A value for n-person games[C]//Contributions to the Theory of Games Ⅱ, Annals of Mathematics Studies, New Jersey: Princeton University Press, 1953: 307-317.
15	Calleja P , Borm P , Hendrickx R . Multi-issue allocation situations[J]. European Journal of Operational Research, 2005, 164 (3): 730- 747. doi: 10.1016/j.ejor.2003.10.042
16	González-Alcón C , Borm P , Hedrickx R . A composite run-to-the-bank rule for multi-issue allocation situations[J]. Mathematical Methods of Operations Research, 2007, 65 (2): 339- 352. doi: 10.1007/s00186-006-0123-z
17	Schaarsberg M C , Reijnierse H , Borm P . On solving mutual liability problems[J]. Mathematical Methods of Operations Research, 2018, 87 (3): 383- 409. doi: 10.1007/s00186-017-0621-1
18	Ketelaars M , Borm P , Quant M . Decentralization and mutual liability rules[J]. Mathematical Methods of Operations Research, 2020, 92 (3): 577- 599. doi: 10.1007/s00186-020-00725-7

[1]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[2]	薛娟, 高红伟, 姜辉, 周允旭. 基于时隙ALOHA协议的数据传输二人随机博弈模型[J]. 运筹学学报, 2019, 23(4): 45-58.
[3]	胡勋锋, 李登峰. Shapley值与Winter值的解析关系[J]. 运筹学学报, 2015, 19(4): 114-120.
[4]	杨靛青, 李登峰. 基于多维线性扩展的模糊联盟合作对策tau值性质与计算方法[J]. 运筹学学报, 2015, 19(2): 61-71.
[5]	吴美容, 孙浩, 陈辉. 双准均衡合作对策\tau值的公理化[J]. 运筹学学报, 2014, 18(2): 119-125.
[6]	王磊, 高红伟, 周长礼. 具有多联盟结构的扩展型部分合作对策[J]. 运筹学学报, 2012, 16(4): 61-68.
[7]	聂翠平, 张强. 模糊联盟合作对策的平均树解[J]. 运筹学学报, 2012, 16(4): 77-85.
[8]	彼得罗相. 微分对策中的联盟解[J]. 运筹学学报, 2012, 16(4): 86-94.
[9]	林健，张强. 具有判断值支付的合作对策的M-S值[J]. 运筹学学报, 2012, 16(4): 41-50.

双边配给问题的Shapley解及其在博物馆通票问题中的应用

A Shapley solution for bipartite rationing problems and its application to museum pass problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 18

相关文章 9

编辑推荐

Metrics

本文评价

T	$ \varnothing $	1	2	3	4	12	13	14	23	24	34	123	124	134	234	N
h(T)	0	7	12	6	9	17	13	16	18	21	15	22	22	22	22	22