Partitioned matching games for international kidney exchange

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=V1∪⋯∪Vn. The player set is N={1,…,n}, and player p∈N owns the vertices in Vp. The value v(S) of a coalition S⊆N is the maximum weight of a matching in the subgraph of G induced by the vertices owned by the players in S. If |Vp|=1 for all p∈N, then we obtain the classical matching game. Let c=max{|Vp||1≤p≤n} be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if c≤2 but co-NP-hard if c≤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.

Keywords
Partitioned matching game, b-Matching games, Complexity classification, International kidney exchange