Worst- and Average-Case Robustness of Stable Matchings: (Counting) Complexity and Experiments

Kimon Boehmer, Niclas Boehmer

Focusing on the bipartite Stable Marriage problem, we investigate different robustness measures related to stable matchings. We analyze the computational complexity of computing th…