Partitioned Matching Games for International Kidney Exchange

Abstract

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 \cdots \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.

Cited by in corpus (1)

• The Complexity of Matching Games: A Survey