Approximately Stable Matching

Many allocation and matching problems (e.g., student-school assignments, job allocation, organ donation) involve coupling agents based on mutual preferences. A central requirement in matching problems is that of stability, that is classically defined as follows: a matching is stable if no blocking pair exists, where a blocking pair is a pair of agents preferring each other over their assigned partners. We assume that matchings are constrained by a given undirected acceptability graph: two agents may be matched only if they are connected by an edge. While stable matchings are guaranteed for specific graph topologies, such as bipartite graphs, stability is not always achievable in more general scenarios. In this paper, we introduce a relaxed notion of stability, yielding to the study of approximately stable matching. Specifically, we define a matching as approximately stable if there exists no k-blocking pair, i.e., no pair of agents who could both improve their assigned partners by at least k positions in their respective preference rankings, by forming a new match together. This refinement captures the idea that small agent gains may not justify a deviation. We provide some theoretical results about the existence and computability of approximately stable matchings, revealing their strengths as well as their inherent limitations. We believe that the introduced notion of approximate stability, along with our foundational findings, constitute a solid basis for future research on matching problems.