The Complexity of Matching Games: A Survey
Abstract
Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of matching games and extensions, such as b-matching games and partitioned matching games; the latter originating from the emerging area of international kidney exchange. In this survey we focus on computational complexity aspects of various game-theoretical solution concepts, such as the core, nucleolus and Shapley value, when the input is restricted to a matching game or one of its variants.
Cite
Text
Benedek et al. "The Complexity of Matching Games: A Survey." Journal of Artificial Intelligence Research, 2023. doi:10.1613/JAIR.1.14281Markdown
[Benedek et al. "The Complexity of Matching Games: A Survey." Journal of Artificial Intelligence Research, 2023.](https://mlanthology.org/jair/2023/benedek2023jair-complexity/) doi:10.1613/JAIR.1.14281BibTeX
@article{benedek2023jair-complexity,
title = {{The Complexity of Matching Games: A Survey}},
author = {Benedek, Márton and Biró, Péter and Johnson, Matthew and Paulusma, Daniël and Ye, Xin},
journal = {Journal of Artificial Intelligence Research},
year = {2023},
pages = {459-485},
doi = {10.1613/JAIR.1.14281},
volume = {77},
url = {https://mlanthology.org/jair/2023/benedek2023jair-complexity/}
}