Sep. 19 (14:30-15:30) room C.714
Péter Biró, Gergely Csáji (HUN-REN KRTK-KTI)
Ex-post stability under two-sided matching: Complexity and characterization
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, ex-post stability is a fundamental stability concept. A prominent open problem is characterizing ex-post stability and establishing its computational complexity. We investigate the computational complexity of testing ex-post stability. Our central result is that when either side has ties in the preferences/priorities, testing ex-post stability is NP-complete. The result even holds if both sides have dichotomous preferences. On the positive side, we give an algorithm using an integer programming approach, that can determine a decomposition with a maximum probability of being weakly stable. 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.
The talk is based on joint work with Haris Aziz és Ali Pourmiri (UNSW Sydney).