Scholarlink

<p>We investigate the stable matching problem under partial preference information, where the objective is to find a matching that minimizes the maximum number of blocking pairs in the worst case. While previous work has shown that this problem is NP-hard in general, we focus on a simple yet widely studied and practical model of approval preferences, where each agent approves a subset of acceptable partners. We provides a comprehensive characterization of the computational complexity for various problem variants, identifying cases that allow (randomized) polynomial-time solutions as well as those that remain NP-complete. Furthermore, we uncover interesting links between our problem and well-known graph matching problems, including <span>Nonlinear Bipartite Matching</span> and <span>Exact Matching</span>.</p>

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

Stable matching with approval preferences under partial information

  • 期刊论文

  • 发表日期：

    2026年2月9日

查看全文
  • Yaqin Chu,
  • Junjie Luo,
  • Tianyang Zheng

摘要

We investigate the stable matching problem under partial preference information, where the objective is to find a matching that minimizes the maximum number of blocking pairs in the worst case. While previous work has shown that this problem is NP-hard in general, we focus on a simple yet widely studied and practical model of approval preferences, where each agent approves a subset of acceptable partners. We provides a comprehensive characterization of the computational complexity for various problem variants, identifying cases that allow (randomized) polynomial-time solutions as well as those that remain NP-complete. Furthermore, we uncover interesting links between our problem and well-known graph matching problems, including Nonlinear Bipartite Matching and Exact Matching.