Computing solutions for matching games (Q662281)

This paper studies matching games. A matching game is a cooperative game \((N, v)\) defined on a graph \(G = (N, E)\) with \(n=|N|\) vertices, \(m=|E|\) edges, and an edge weighting \(w : E \rightarrow {\mathbb R}_+\). The player set is \(N\) and the value of a coalition \(S\subseteq N\) is defined as the maximum weight of a matching in the subgraph induced by \(S\). As is usual in cooperative game theory, it is assumed that the grand coalition \(N\) is formed. Then, the central problem is how to allocate the total value \(v(N)\) to the individual players in \(N\). An allocation is a vector \(x\in {\mathbb R}^N\) with \(\sum_{i\in N}{x_i} = v(N)\). The authors focus on two sets of allocations for matching games: (a) the core, i.e., the set of allocations with \(\sum_{i\in S}{x_i} \geq v(S)\) for all coalitions \(S\), and (b) the nucleolus, which is a singleton contained in the core if the latter is non-empty [\textit{D. Schmeidler}, SIAM J. Appl. Math. 17, 1163--1170 (1969; Zbl 0191.49502)]. Regarding the core, the authors provide a necessary and sufficient condition for the non-emptiness of the core of a matching game, connecting the maximum weight of matchings with the maximum weight of half-matchings (Proposition 1). Since a maximum weight matching and a maximum weight half-matching can be found in \(O(nm + n^2 \log n)\) time, it follows that there exists an \(O(nm + n^2 \log n)\) time algorithm that tests if the core of a matching game is non-empty and that computes a core allocation in the case that the core is non-empty (Theorem 5). Regarding the nucleolus, the authors show that the nucleolus of a matching game with a non-empty core can be computed in \(O(n^4)\) time (Theorem 6). This result generalizes the corresponding result of \textit{T. Solymosi} and \textit{T. E. S. Raghavan} [Int. J. Game Theory 23, No. 2, 119--143 (1994; Zbl 0811.90128)] for assignment games, which are matching games based on bipartite graphs. Finally, the authors prove that it is NP-hard to determine an imputation (i.e., an allocation \(x\) such that \(x_i \geq v(\{i\})\) for all singletons \(\{i\}\)) with a minimum number of blocking pairs, even for matching games with unit edge weights (Theorem 7). The problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games (Proposition 2).