The NTU Partitioned Matching Game for International Kidney Exchange Programs

Motivated by the real-world problem of international kidney exchange programs (IKEPs), recent literature introduced a generalized transferable utility matching game featuring a partition of the vertex set of a graph into players, and analyzed its complexity. We explore the nontransferable utility (NTU) variant of the game, where the utility of players is given by the number of their matched vertices. Our motivation for studying this problem is twofold. First, the NTU version is arguably a more natural model of the international kidney exchange program, as the utility of a participating country mostly depends on how many of its patients receive a kidney, which is nontransferable by nature. Second, the special case where each player has two vertices, which we call the NTU matching game with couples, is interesting in its own right and has intriguing structural properties. We study the core of the NTU game, which suitably captures the notion of stability of an IKEP, as it precludes incentives to deviate from the proposed solution for any possible coalition of the players. We prove computational complexity results about the weak and strong cores under various assumptions on the players. In particular, we show that if every player has two vertices, then the weak core is always nonempty, and the existence of a strong core solution can be decided in polynomial time. Moreover, one can efficiently optimize on the strong core. In contrast, it is NP-hard to decide whether the strong core is empty when each player has three vertices. We also show that if the number of players is constant, then the nonemptiness of the weak and strong cores is polynomial-time decidable, and we can find a minimum cost core solution in polynomial time.

History: This paper has been accepted for the Mathematics of Operations Research Special Issue on Market Design.

Funding: G. Csáji is supported by the Hungarian Scientific Research Fund [ADVANCED Grant 150556], by the Lendület Programme of the Hungarian Academy of Sciences [Grant LP2021-2/2021], and by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme [Grant C2258525]. T. Király is supported by the Lendület Programme of the Hungarian Academy of Sciences [Grant LP2021-1/2021] and by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund [ELTE TKP Grant 2021-NKTA-62 and ADVANCED Grant 150556].