Generalized Matching Games for International Kidney Exchange

We introduce generalized matching games defined on a graph G = (V , E) with an edge weighting w and a partition V = V 1 ∪ • • • ∪ V n of V. The player set is N = {1,. .. , n}, and player p ∈ N owns the vertices in V p. The value v (S) of coalition S ⊆ N is the maximum weight of a matching in the subgraph of G induced by the vertices owned by players in S. If |V p | = 1 for every player p we obtain the classical matching game. We prove that checking core nonemptiness is polynomial-time solvable if |V p | ≤ 2 for each p and co-NP-hard if |V p | ≤ 3 for each p. We do so via pinpointing a relationship with b-matching games and also settle the complexity classification on testing core non-emptiness for b-matching games. We propose generalized matching games as a suitable model for international kidney exchange programs, where the vertices in V correspond to patient-donor pairs and each V p represents one country. For this setting we prove a number of complexity results.