# 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

6 Citations (Scopus)

## 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 language English Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019) Association for Computing Machinery (ACM) 413-421 8 978-1-4503-6309-9 https://doi.org/10.5555/3306127.3331721 Published - 8 May 2019 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 - Montreal, CanadaDuration: 13 May 2019 → 17 May 2019Conference number: 18http://aamas2019.encs.concordia.ca/

### Conference

Conference 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 AAMAS Canada Montreal 13/05/19 → 17/05/19 http://aamas2019.encs.concordia.ca/

## Fingerprint

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