中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 2: 101 - 110

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.02.009

Population monotonic allocation schemes for shortest path games

Expand
  • 1. School of Mathematical Sciences, Ocean University of China, Qingdao 266100, Shandong, China

Received date: 2020-07-29

  Online published: 2022-05-27

Fold

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

Cite this article

Zerong CHEN, Han XIAO . Population monotonic allocation schemes for shortest path games[J]. Operations Research Transactions, 2022 , 26(2) : 101 -110 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.009

References

1 Fragnelli V , Jurado I G , Naya L M . On shortest path games[J]. Mathematical Methods of Operations Research, 2000, 52 (2): 251- 264.
2 Voorneveld M , Grahn S . Cost allocation in shortest path games[J]. Mathematical Methods of Operations Research, 2002, 56 (2): 323- 340.
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.
4 Rosenthal E C . Shortest path games[J]. European Journal of Operational Research, 2013, 224 (1): 132- 140.
5 Ba?ou M , Barahona F . An algorithm to compute the nucleolus of shortest path games[J]. Algorithmica, 2019, 81 (8): 3099- 3113.
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.
9 Hamers H , Miquel S , Norde H . Monotonic stable solutions for minimum coloring games[J]. Mathematical Programming, 2014, 145 (1-2): 509- 529.
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.
14 Shapley L S . Cores of convex games[J]. International Journal of Game Theory, 1971, 1 (1): 11- 26.
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.
16 Izquierdo J M , Rafels C . Average monotonic cooperative games[J]. Games and Economic Behavior, 2001, 36 (2): 174- 192.
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.
18 Young P . Monotonic solutions of cooperative games[J]. International Journal of Game Theory, 1985, 14 (2): 65- 72.
19 Kalai E , Zemel E . Generalized network problems yielding totally balanced games[J]. Operations Research, 1982, 30 (5): 998- 1008.
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.
21 Taccari L . Integer programming formulations for the elementary shortest path problem[J]. European Journal of Operational Research, 2016, 252 (1): 122- 130.
22 Dutta B , Ray D . A concept of egalitarianism under participation constraints[J]. Econometrica, 1989, 57 (3): 615- 635.
23 田丰, 张运清. 图与网络流理论[M]. 北京: 科学出版社, 2015.
24 谢政, 戴丽, 李建平. 博弈论[M]. 北京: 高等教育出版社, 2018.
Options
Outlines

/

〈 〉