Partitioned matching games for international kidney exchange

• 成果类型: Article
• 署名作者: Benedek, Marton; Biro, Peter; Kern, Walter; Palvolgyi, Domotor; Paulusma, Daniel
• 署名单位: Corvinus University Budapest; University of Twente; Eotvos Lorand University; Durham University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02200-9
• 发表日期: 2025-11
• 页码: 723-758
• 关键词: Partitioned matching game; b-Matching games; Complexity classification; 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 = V-1 boolean OR center dot center dot center dot boolean OR V-n. The player set is N = {1,..., n}, and player p is an element of N owns the vertices in V-p. 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 |V-p| = 1 for all p is an element of N, then we obtain the classical matching game. Let c = max{|V-p| | 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.