The Complexity of Matching Games: A Survey

Matching games naturally generalize assignment games, a well-known class of cooperative games. Over the years, matching games received a growing amount of attention, in particular due to some recent breakthrough results and new applications. This state-of-the-art survey provides an overview of matching games and recent extensions, such as $b$-matching games and generalized matching games. We focus on the computational complexity of various relevant game-theoretical solution concepts, such as the core, nucleolus and Shapley value.