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

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

Abstract

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

CLC Number:

O225

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

Figures/Tables 2

References 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]	Yaxing LYU, Meijia HAN, Zilin HUANG, Wenxing ZHU. An equivalence condition for sparse optimization problem with non-negative constraints [J]. Operations Research Transactions, 2022, 26(1): 43-59.
[2]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[3]	Yindong SHEN, Zhuang QIAN, Yuanyuan LI. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[4]	SUN Guanglei, LI Xiaoshen, SHANG Youlin. Optimal production ordering policy for an integrated supply chain with time varying demand [J]. Operations Research Transactions, 2019, 23(4): 143-154.
[5]	HUANG Peihuang, ZHU Wenxing. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks [J]. Operations Research Transactions, 2019, 23(4): 155-164.
[6]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[7]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[8]	LIAN Shujun, DU Aihua, TANG Jiahui. A new class of simple smooth exact penalty functions for equality constrained optimization problems [J]. Operations Research Transactions, 2017, 21(1): 33-43.
[9]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[10]	GUAN Meigu. A historical review on the research and development [J]. Operations Research Transactions, 2015, 19(3): 1-7.
[11]	PAN Pingqi. On “An efficient implementation of the face algorithm for linear programming” [J]. Operations Research Transactions, 2015, 19(3): 78-84.
[12]	HE Shengxue. Determining optimal routes for transit vehicles in no-notice emergency evacuation [J]. Operations Research Transactions, 2014, 18(3): 47-59.
[13]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[14]	Shu-jun Lian. On the Smoothing of the Lower Order Exact Penalty Function for Inequality Constrained Optimization [J]. Operations Research Transactions, 2012, 16(2): 51-64.
[15]	ZHOU Kang, CHEN Jin, QIU Jiang, JIE Zhi. Matrix Algorithm for LP Problem Based on Partial Basic Variables [J]. Operations Research Transactions, 2012, 16(2): 121-126.

Population monotonic allocation schemes for shortest path games

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 24

Related Articles 15

Recommended Articles

Metrics

Comments