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


Marton Benedek

Peter Biro

Xin Ye
PGR Student Doctor of Philosophy


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.


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.

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
Public URL


You might also like

Downloadable Citations