## 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 | Canada |

City | Montreal |

Period | 13/05/19 → 17/05/19 |

Internet address |