On Solution Concepts for Matching Games

摘要

A matching game is a cooperative game (N, v) defined on a graph G = (N,E) with an edge weighting w : E → R_+. The player set is N and the value of a coalition S ≤ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n~2 log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core allocation if the core is nonempty. This improves previous work based on the ellipsoid method. Second we show that the nucleolus of an n-player matching game with nonempty core can be computed in O(n~4) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we show that determining an imputation with minimum number of blocking pairs is an NP-hard problem, even for matching games with unit edge weights.