最短路博弈群体单调分配方案构造

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

摘要/Abstract

摘要：

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。

关键词: 合作博弈, PMAS, 最短路问题, 线性规划

Abstract:

Population monotonic allocation schemes (PMAS-es for short) are allocation schemes for cooperative games. PMAS-es provide a core allocation for each subgame in a cross monotonic way and hence ensure the dynamic stability of the grand coalition. This paper investigates PMAS-es for cooperative cost games arising from the shortest path problem. We provide a dual-based combinatorial characterization for PMAS-es of shortest path games. Inspired by Maschler scheme for computing the nucleolus, we show that a PMAS can be determined by solving a linear program of exponential size. Moreover, we manage to solve the linear program and derive the same PMAS as the combinatorial method earlier for shortest path games.

Key words: cooperative game theory, population monotonic allocation scheme, shortest path problem, linear programming

中图分类号:

O225

陈泽融, 肖汉. 最短路博弈群体单调分配方案构造[J]. 运筹学学报, 2022, 26(2): 101-110.

Zerong CHEN, Han XIAO. Population monotonic allocation schemes for shortest path games[J]. Operations Research Transactions, 2022, 26(2): 101-110.

图/表 2

图1

表1

1	Fragnelli V , Jurado I G , Naya L M . On shortest path games[J]. Mathematical Methods of Operations Research, 2000, 52 (2): 251- 264. doi: 10.1007/s001860000061
2	Voorneveld M , Grahn S . Cost allocation in shortest path games[J]. Mathematical Methods of Operations Research, 2002, 56 (2): 323- 340. doi: 10.1007/s001860200222
3	Pintér M , Radványi A . The Shapley value for shortest path games: a non-graph-based approach[J]. Central European Journal of Operations Research, 2013, 21 (4): 769- 781. doi: 10.1007/s10100-012-0272-5
4	Rosenthal E C . Shortest path games[J]. European Journal of Operational Research, 2013, 224 (1): 132- 140. doi: 10.1016/j.ejor.2012.06.047
5	Baïou M , Barahona F . An algorithm to compute the nucleolus of shortest path games[J]. Algorithmica, 2019, 81 (8): 3099- 3113. doi: 10.1007/s00453-019-00574-9
6	Sprumont Y . Population monotonic allocation schemes for cooperative games with transferable utility[J]. Academic Press, 1990, 2 (4): 378- 394.
7	Grahn S , Voorneveld M . Population monotonic allocation schemes in bankruptcy games[J]. Annals of Operations Research, 2002, 109 (1-4): 317- 329.
8	Norde H , Moretti S , Tijs S . Minimum cost spanning tree games and population monotonic allocation schemes[J]. European Journal of Operational Research, 2004, 154 (1): 84- 97. doi: 10.1016/S0377-2217(02)00714-2
9	Hamers H , Miquel S , Norde H . Monotonic stable solutions for minimum coloring games[J]. Mathematical Programming, 2014, 145 (1-2): 509- 529. doi: 10.1007/s10107-013-0655-y
10	Chen X , Gao X , Hu Z , et al. Population monotonicity in newsvendor games[J]. Management Science, 2019, 65 (5): 2142- 2160.
11	Curiel I . Cooperative Game Theory and Applications: Cooperative Games Arising from Combinatorial Optimization Problems[M]. Dordrecht: Kluwer Academic Publishers, 1997.
12	Barron E N . Game Theory: An Introduction[M]. New York: Wiley-Interscience, 2013.
13	Biswas A K , Parthasarathy T , Ravindran G . Stability and largeness of the core[J]. Games and Economic Behavior, 2001, 34 (2): 227- 237. doi: 10.1006/game.2000.0804
14	Shapley L S . Cores of convex games[J]. International Journal of Game Theory, 1971, 1 (1): 11- 26. doi: 10.1007/BF01753431
15	Driessen T S H , Tijs S H . The τ-value, the core and semiconvex games[J]. International Journal of Game Theory, 1985, 14 (4): 229- 247. doi: 10.1007/BF01769310
16	Izquierdo J M , Rafels C . Average monotonic cooperative games[J]. Games and Economic Behavior, 2001, 36 (2): 174- 192. doi: 10.1006/game.1999.0820
17	Hokari T , Gellekom A . Population monotonicity and consistency in convex games: Some logical relations[J]. International Journal of Game Theory, 2003, 31 (4): 593- 607. doi: 10.1007/s001820300141
18	Young P . Monotonic solutions of cooperative games[J]. International Journal of Game Theory, 1985, 14 (2): 65- 72. doi: 10.1007/BF01769885
19	Kalai E , Zemel E . Generalized network problems yielding totally balanced games[J]. Operations Research, 1982, 30 (5): 998- 1008. doi: 10.1287/opre.30.5.998
20	Kruś L , Bronisz P . Cooperative game solution concepts to a cost allocation problem[J]. European Journal of Operational Research, 2000, 122 (2): 258- 271. doi: 10.1016/S0377-2217(99)00232-5
21	Taccari L . Integer programming formulations for the elementary shortest path problem[J]. European Journal of Operational Research, 2016, 252 (1): 122- 130. doi: 10.1016/j.ejor.2016.01.003
22	Dutta B , Ray D . A concept of egalitarianism under participation constraints[J]. Econometrica, 1989, 57 (3): 615- 635. doi: 10.2307/1911055
23	田丰, 张运清. 图与网络流理论[M]. 北京: 科学出版社, 2015.
24	谢政, 戴丽, 李建平. 博弈论[M]. 北京: 高等教育出版社, 2018.

联盟$S$	联盟$S$下的最短路	$c(S)$	联盟$S$的成本分配方案
{1}		$M$	$x_{\left\{1\right\}, 1}=M$
{2}		$M$	$x_{\left\{2\right\}, 2}=M$
{3}		$M$	$x_{\left\{3\right\}, 3}=M$
{4}		$M$	$x_{\left\{4\right\}, 4}=M$
{1, 2}		$M$	$x_{\left\{1, 2\right\}, 1}=x_{\left\{1, 2\right\}, 2}=\frac{M}{2}$
{1, 3}		$M$	$x_{\left\{1, 3\right\}, 1}=x_{\left\{1, 3\right\}, 3}=\frac{M}{2}$
{1, 4}		$M$	$x_{\left\{1, 4\right\}, 1}=x_{\left\{1, 4\right\}, 4}=\frac{M}{2}$
{2, 3}	$s \to b \to d \to t$	18	$x_{\left\{2, 3\right\}, 2}=x_{\left\{2, 3\right\}, 3}=9$
{2, 4}	$s \to b \to d \to c \to t$	24	$x_{\left\{2, 4\right\}, 2}=x_{\left\{2, 4\right\}, 4}=12$
{3, 4}		$M$	$x_{\left\{3, 4\right\}, 3}=x_{\left\{3, 4\right\}, 4}=\frac{M}{2}$
{1, 2, 3}	$s \to b \to d \to t$	18	$x_{\left\{1, 2, 3\right\}, 1}=x_{\left\{1, 2, 3\right\}, 2}=x_{\left\{1, 2, 3\right\}, 3}=6$
{1, 2, 4}	$s \to b \to d \to c \to t$	24	$x_{\left\{1, 2, 4\right\}, 1}=x_{\left\{1, 2, 4\right\}, 2}=x_{\left\{1, 2, 4\right\}, 4}=8$
{1, 3, 4}	$s \to a \to c \to t$	12	$x_{\left\{1, 3, 4\right\}, 1}=x_{\left\{1, 3, 4\right\}, 3}=x_{\left\{1, 3, 4\right\}, 4}=4$
{2, 3, 4}	$s \to b \to c \to t$	12	$x_{\left\{2, 3, 4\right\}, 2}=x_{\left\{2, 3, 4\right\}, 3}=x_{\left\{2, 3, 4\right\}, 4}=4$
$N$	$s \to a \to c \to t$, $s \to b \to c \to t$	12	${x_{N, 1}=x}_{N, 2}=x_{N, 3}=x_{N, 4}=3$

[1]	张雪峰, 彭潇, 陈良育, 杨争峰, 曾振柄. 面向混合整数线性规划问题的智能分支定界算法综述[J]. 运筹学学报（中英文）, 2026, 30(2): 237-270.
[2]	于晓辉, 周卫青, 吴优. 不确定需求下服务型制造混合供应链收益分配模型[J]. 运筹学学报（中英文）, 2026, 30(1): 24-40.
[3]	孙文娟, 宫华, 许可, 申爱红. 带有交货期的一类柔性流水车间调度问题的合作博弈[J]. 运筹学学报（中英文）, 2025, 29(4): 83-93.
[4]	陈聪利, 杨辉, 杨光惠, 王春. 不确定参数下n人非合作博弈的逼近定理[J]. 运筹学学报（中英文）, 2025, 29(1): 105-113.
[5]	袁先智. 共识博弈与区块链生态共识均衡[J]. 运筹学学报（中英文）, 2024, 28(3): 1-26.
[6]	李文忠, 徐根玖. 效用可转移合作博弈的Shapley值公理化研究进展综述[J]. 运筹学学报（中英文）, 2024, 28(3): 63-80.
[7]	孙攀飞, 孙浩. 合作博弈两类组合解的社会可接受性[J]. 运筹学学报（中英文）, 2024, 28(3): 121-131.
[8]	张晴, 陈亮, 艾文宝, 寇彩霞. 天然气管网稳态运行优化模型的非线性界增强方法[J]. 运筹学学报（中英文）, 2024, 28(1): 101-111.
[9]	吕亚星, 韩美佳, 黄子麟, 朱文兴. 非负约束稀疏优化问题的一个等价性条件[J]. 运筹学学报, 2022, 26(1): 43-59.
[10]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[11]	张广, 肖文君, 邬冬华. 图博弈的过程比例解[J]. 运筹学学报, 2021, 25(4): 101-110.
[12]	宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.
[13]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[14]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[15]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.