The Complexity of Matching Games: A Survey

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

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.

• 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