Von Neumann-Morgenstern stability and internal closedness in matching theory

Abstract

Gale and Shapley’s stability criterion enjoys a rich mathematical structure, which propelled its application in various settings. Although immensely popular, the approach by Gale and Shapley cannot encompass all the different features that arise in applications, motivating the search for alternative solution concepts. We investigate alternatives that rely on the concept of internal stability, a notion introduced for abstract games by von Neumann and Morgenstern and motivated by the need of finding a set of mutually compatible solutions. The set of stable matchings is internally stable. However, the class of internally stable sets is much richer, for an internally stable set of matchings may also include unstable matchings and/or exclude stable ones. In this paper, we focus on two families of internally stable sets of matchings: von Neumann-Morgenstern stable and internally closed. We study algorithmic questions around those concepts in both the marriage and the roommate models. One of our results implies that, in the marriage model, internally closed sets are an alternative to stable matchings that is as tractable as stable matchings themselves, a fairly rare occurrence in the area. Both our positive and negative results rely on new structural insights and extensions of classical algebraic structures associated with sets of matchings, which we believe to be of independent interest.