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

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

Population monotonic allocation schemes for shortest path games

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.