TR-2019-12

Complexity of the NTU International Matching Game

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



Abstract

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:

@techreport{egres-19-12,
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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-12}
}


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