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.
results.
Original language | English |
---|---|
Title of host publication | Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019) |
Publisher | Association for Computing Machinery (ACM) |
Pages | 413-421 |
Number of pages | 8 |
ISBN (Print) | 978-1-4503-6309-9 |
DOIs | |
Publication status | Published - 8 May 2019 |
Event | 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 - Montreal, Canada Duration: 13 May 2019 → 17 May 2019 Conference number: 18 http://aamas2019.encs.concordia.ca/ |
Conference
Conference | 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019 |
---|---|
Abbreviated title | AAMAS |
Country/Territory | Canada |
City | Montreal |
Period | 13/05/19 → 17/05/19 |
Internet address |