Computing solutions for matching games
Computing solutions for matching games
复制标题
DOI：
10.1007/s00182-011-0273-y
复制
发表时间：
2011-03
影响因子：
0.6
通讯作者：
P. Biró;W. Kern;D. Paulusma
中科院分区：
文献类型：
--
作者：
P. Biró;W. Kern;D. Paulusma
匹配游戏是在具有边缘权重的图G=（N，E）上定义的合作游戏（N，v）。玩家集合为N，联盟的值定义为S所导出的子图中匹配的最大权重。首先，我们提出一个 O(nm+n2logn) 算法，该算法测试在具有 n 个顶点和边的加权图上定义的匹配游戏的核心是否为非空，并在核心非空时计算核心成员。该算法改进了之前基于椭球法的工作，也可用于计算稳定室友支付问题实例的稳定解。其次，我们证明具有非空核心的 ANN 玩家匹配游戏的核仁可以在 O(n4) 时间内计算出来。这概括了 Solymosi 和 Raghavan 对于作业游戏的相应结果。第三，我们证明，即使对于具有单位边缘权重的匹配游戏，确定具有最小数量的阻塞对的插补也是NP-hard的，而确定具有最小总阻塞值的插补的问题对于一般匹配游戏来说是多项式时间可解决的。
A matching game is a cooperative game (N,v) defined on a graphG= (N,E) with an edge weighting. The player set isNand the value of a coalitionis defined as the maximum weight of a matching in the subgraph induced byS. First we present anO(nm+n2logn) algorithm that tests if the core of a matching game defined on a weighted graph withnvertices andmedges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of ann-player matching game with a nonempty core can be computed inO(n4) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that isNP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.