We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph \(G=(V,E)\) with an edge weighting w and a partition \(V=V_1 \cup \dots \cup V_n\) . The player set is \(N = \{ 1, \dots , n\}\) , and player \(p \in N\) owns the vertices in \(V_p\) . The value v(S) of a coalition \(S \subseteq N\) is the maximum weight of a matching in the subgraph of G induced by the vertices owned by the players in S. If \(|V_p|=1\) for all \(p\in N\) , then we obtain the classical matching game. Let \(c=\max \{|V_p| \; |\; 1\le p\le n\}\) be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if \(c\le 2\) but co-NP-hard if \(c\le 3\) . We do this via pinpointing a relationship with the known class of b-matching games and completing the complexity classification on testing core non-emptiness for b-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.
