Skip to main content

Research Repository

Advanced Search

The Complexity of Matching Games: A Survey

Benedek, Marton; Biro, Peter; Johnson, Matthew; Paulusma, Daniel; Ye, Xin

The Complexity of Matching Games: A Survey Thumbnail


Authors

Marton Benedek

Peter Biro

Xin Ye xin.ye@durham.ac.uk
PGR Student Doctor of Philosophy



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.

Citation

Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281

Journal Article Type Article
Acceptance Date May 3, 2023
Online Publication Date Jun 12, 2023
Publication Date 2023
Deposit Date Dec 30, 2023
Publicly Available Date Jan 2, 2024
Journal Journal of Artificial Intelligence Research
Print ISSN 1076-9757
Publisher AI Access Foundation
Peer Reviewed Peer Reviewed
Volume 77
Pages 459-485
DOI https://doi.org/10.1613/jair.1.14281
Public URL https://durham-repository.worktribe.com/output/2076660

Files




You might also like



Downloadable Citations