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

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

参考文献 24

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]. 运筹学学报, 2022, 26(1): 43-59.
[2]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[3]	张广, 肖文君, 邬冬华. 图博弈的过程比例解[J]. 运筹学学报, 2021, 25(4): 101-110.
[4]	宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.
[5]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[6]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[7]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.
[8]	孙广磊, 李小申, 尚有林. 基于时变需求的集成多级供应链生产订货策略研究[J]. 运筹学学报, 2019, 23(4): 143-154.
[9]	黄培煌, 朱文兴. 移动传感器网络中的最大价值路径扫描覆盖算法[J]. 运筹学学报, 2019, 23(4): 155-164.
[10]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[11]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[12]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[13]	黄亚魁, 李博, 康阳, 戴彧虹, 柳建军. 天然气稳态运行优化的混合整数模型及其算法[J]. 运筹学学报, 2017, 21(2): 13-23.
[14]	连淑君, 杜爱华, 唐加会. 等式约束优化问题的一类新的简单光滑精确罚函数[J]. 运筹学学报, 2017, 21(1): 33-43.
[15]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.