English

运筹学学报 >

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

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

 

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

展开
  • 1. 中国海洋大学数学科学学院, 山东青岛 266100
肖汉  E-mail: hxiao@ouc.edu.cn

收稿日期: 2020-07-29

  网络出版日期: 2022-05-27

基金资助

山东省自然科学基金(ZR2020QA024);国家自然科学基金(12001507)

收起

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

摘要

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

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

本文引用格式

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

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

参考文献

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
文章导航

/

〈 〉