Generalized matching games for international kidney exchange

Walter Kern, Péter Biró, Dömötör Pálvölgyi, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
6 Downloads (Pure)

Abstract

We introduce generalized matching games defined on a graph $G=(V,E)$ with an edge weighting $w$ and a partition $V=V_1 \cup \dots \cup V_n$ of~$V$. The player set is $N = \{ 1, \dots, n\}$, and player $p \in N$ owns the vertices in $V_p$. The value $v(S)$ of coalition $S \subseteq N$ is the maximum weight of a matching in the subgraph of $G$ induced by the vertices owned by players in $S$. If $|V_p|=1$ for every player~$p$ we obtain the classical matching game. We prove that checking core non-emptiness is polynomial-time solvable if $|V_p|\leq 2$ for each $p$ and co-\NP-hard if $|V_p|\leq 3$ for each $p$. We do so via pinpointing a relationship with $b$-matching games and also settle the complexity classification on testing core non-emptiness for $b$-matching games. We propose generalized matching games as a suitable model for international kidney exchange programs, where the vertices in $V$ correspond to patient-donor pairs and each $V_p$ represents one country. For this setting we prove a number of complexity
results.
Original languageEnglish
Title of host publicationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)
PublisherAssociation for Computing Machinery (ACM)
Pages413-421
Number of pages8
ISBN (Print)978-1-4503-6309-9
DOIs
Publication statusPublished - 8 May 2019
Event18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 - Montreal, Canada
Duration: 13 May 201917 May 2019
Conference number: 18
http://aamas2019.encs.concordia.ca/

Conference

Conference18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
Abbreviated titleAAMAS
CountryCanada
CityMontreal
Period13/05/1917/05/19
Internet address

Fingerprint Dive into the research topics of 'Generalized matching games for international kidney exchange'. Together they form a unique fingerprint.

  • Cite this

    Kern, W., Biró, P., Pálvölgyi, D., & Paulusma, D. (2019). Generalized matching games for international kidney exchange. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019) (pp. 413-421). Association for Computing Machinery (ACM). https://doi.org/10.5555/3306127.3331721