Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月15日

查看全文
  • Haris Aziz,
  • Péter Biró,
  • Gergely Csáji,
  • Ali Pourmiri

摘要

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.