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

作者：陈泽融; 肖汉^*

来源：运筹学学报, 2022, 26(02): 101-110.

DOI：10.15960/j.cnki.issn.1007-6093.2022.02.009

• 合作博弈
• PMAS
• 最短路问题
• 线性规划

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

• 单位
  中国海洋大学