Ex-post Stability under Two-Sided Matching : Complexity and Characterization

Abstract

We study the problem of determining whether a given random matching can be implemented as a lottery over weakly stable deterministic matchings – a property known as ex-post stability. This concept arises in randomized allocation mechanisms such as school choice, where stability in each realized outcome is essential for fairness. Despite its importance in practice, the computational complexity of verifying ex-post stability has remained unresolved. We settle this question by showing that testing ex-post stability is NP-complete, even under highly restricted conditions – specifically, when both sides have dichotomous preferences or one of the sides has strict preferences. On the positive side, we present an integer programming formulation that finds a decomposition of a random matching with maximum weight on stable matchings. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time.