Stable Matching with Approval Preferences Under Partial Information

We study the stable matching problem when agents only submit partial information, where the goal is to compute a matching that has the minimum number of blocking pairs in the worst case. Previous work shows that this problem is NP-hard in general. In this paper, we focus on the simple yet widely used approval preferences, where each agent approves a subset of agents. We provide a comprehensive overview of the computational complexity of different variants of the problem and reveal interesting connections to some graph matching problems, such as Nonlinear Bipartite Matching and Exact Matching.