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

Haris Aziz, Gergely Csáji, Péter Biró

A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, e…