The Complexity of Matching Games: A Survey

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\)-matchi...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Benedek, Márton, Biró, Péter, Johnson, Matthew, Paulusma, Daniël, Ye, Xin
Format: Article
Language:English
Subjects:
Complexity
Games
Matching
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 if its variants.
ISSN:2331-8422
DOI:10.48550/arxiv.2202.06898