Complexity of the NTU International Matching Game

Tamás Király, Zsuzsa Mészáros-Karkus


Motivated by the real-world problem of international kidney exchange, [Biró et al., Generalized Matching Games for International Kidney Exchange, 2019] introduced a generalized transferable utility matching game featuring a partition of the node set into countries, and analyzed its complexity. We explore the non-transferable utility (NTU) variant of the game and prove computational complexity results about the weak and strong cores under various assumptions on the countries.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and M{\'e}sz{\'a}ros-Karkus, Zsuzsa},
TITLE = {Complexity of the NTU International Matching Game},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-12}

Last modification: 29.12.2020. Please email your comments to Tamás Király!