Reasoning about optimal stable matchings under partial information
Reasoning about optimal stable matchings under partial information
复制标题
部分信息下最优稳定匹配的推理
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Kevin Leyton
中科院分区：
文献类型：
--
作者：
Baharak Rastegari;A. Condon;Nicole Immorlica;Robert W. Irving;Kevin Leyton
我们研究了双边匹配市场，其中参与者最初被赋予部分偏好排序，缺乏关于他们真实的、严格排序的偏好列表的精确信息。我们希望推理出相对于代理人的真实偏好而言是稳定的匹配，并且对于给定的市场一方来说是进一步优化的匹配。我们提出了三个主要结果。首先，我们可以在多项式时间内确定是否存在一个在所有严格偏好阶下稳定且最优的匹配，如果存在，我们可以在多项式时间内构造这个匹配。然而，我们表明，即使在相当严格的偏好限制下，决定给定的一对代理是否在所有这种最优稳定匹配中匹配还是没有匹配是共同np完全的。最后，我们描述了一个多项式时间算法，该算法决定给定一个在部分偏好排序下稳定的匹配，在部分排序的某些细化下，该匹配对于市场的一侧是否稳定和最优。
We study two-sided matching markets in which participants are initially endowed with partial preference orderings, lacking precise information about their true, strictly ordered list of preferences. We wish to reason about matchings that are stable with respect to agents' true preferences, and which are furthermore optimal for one given side of the market. We present three main results. First, one can decide in polynomial time whether there exists a matching that is stable and optimal under all strict preference orders that refine the given partial orders, and can construct this matching in polynomial time if it does exist. We show, however, that deciding whether a given pair of agents are matched in all or no such optimal stable matchings is co-NP-complete, even under quite severe restrictions on preferences. Finally, we describe a polynomial-time algorithm that decides, given a matching that is stable under the partial preference orderings, whether that matching is stable and optimal for one side of the market under some refinement of the partial orders.