Journal article by Péter BIRÓ [et al.] in Games and Economic Behavior

We consider multiple partners matching games (G,b,w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite, these games are called multiple partners assignment games. We give a polynomial-time algorithm that either finds that a given multiple partners matching game has no stable solution, or obtains a stable solution. We characterize the set of stable solutions of a multiple partners matching game in two different ways and show how this leads to simple proofs for a number of results of Sotomayor, 1992, Sotomayor, 1999, Sotomayor, 2007 for multiple partners assignment games and to generalizations of some of these results to multiple partners matching games. We also perform a study on the core of multiple partners matching games. We prove that the problem of deciding if an allocation belongs to the core jumps from being polynomial-time solvable for b≤2 to NP-complete for b≡3.