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

Aziz, Haris and Biró, Péter and Csáji, Gergely Kál and Pourmiri, Ali (2026) Ex-post Stability under Two-Sided Matching : Complexity and Characterization. ALGORITHMICA, 88 (3). No. -45. ISSN 0178-4617

Preview

Text s00453-026-01388-2.pdf - Published Version Available under License Creative Commons Attribution. Download (466kB) | Preview

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.

Actions (login required)

Edit Item