论文标题
Gale-Shapley提案算法的单侧版本及其在随机偏好下的可能行为
One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
论文作者
论文摘要
对于双面（$ n $男性/$ n $女性）稳定的匹配问题）大风和莎普利研究了一种提案算法（男性建议/女性选择，或者相反），这决定了匹配，并未被任何无与伦比的对所阻止。欧文（Irving）将此算法用作其算法的第一阶段，用于与$ n $ agents的单方面（稳定室友）匹配问题。我们分析了Irving提案算法的完全扩展版本，该版本一直运行，直到每个代理商持有提案或代理商优先列表中的每个人都会拒绝代理商。结果表明，终端，定向的合作伙伴关系形成稳定的排列，匹配对剩余的任何其他稳定排列中均保持匹配。假设所有$ n $排名都是独立统一的，则研究了该提案算法的可能行为。事实证明，每个代理商都有一个合作伙伴的概率（W.H.P.），并且长度为$ \ ge 3 $的循环中的代理数量和稳定匹配的总数都以概率为界。 W.H.P.提案的总数渐近至$ 0.5 n^{3/2} $。
For a two-sided ($n$ men/$n$ women) stable matching problem) Gale and Shapley studied a proposal algorithm (men propose/women select, or the other way around), that determines a matching, not blocked by any unmatched pair. Irving used this algorithm as a first phase of his algorithm for one-sided (stable roommates) matching problem with $n$ agents. We analyze a fully extended version of Irving's proposal algorithm that runs all the way until either each agent holds a proposal or an agent gets rejected by everybody on the agent's preference list. It is shown that the terminal, directed, partnerships form a stable permutation with matched pairs remaining matched in any other stable permutation. A likely behavior of the proposal algorithm is studied under assumption that all $n$ rankings are independently uniform. It is proved that with high probability (w.h.p.) every agent has a partner, and that both the number of agents in cycles of length $\ge 3$ and the total number of stable matchings are bounded in probability. W.h.p. the total number of proposals is asymptotic to $0.5 n^{3/2}$.
