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 \cup \dots \cup V_n$ of~$V$. The player set is $N = \{ 1, \dots, n\}$, and player $p \in N$ owns the vertices in $V_p$. The value $v(S)$ of coalition $S \subseteq 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 non-emptiness is polynomial-time solvable if $|V_p|\leq 2$ for each $p$ and co-\NP-hard if $|V_p|\leq 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.