论文标题
Teo和Sethuraman的中位数稳定婚姻定理的概括
A Generalization of Teo and Sethuraman's Median Stable Marriage Theorem
论文作者
论文摘要
令$ l $为任何有限的分布晶格，$ b $是$ l $定义的任何布尔谓词，使满足$ b $的元素集为$ l $的sublattice。考虑任何满足$ b $的$ k $ $ k $的子集$ m $ $ l $。然后，我们表明$ k $从$ m $产生的中位元素也满足$ b $。我们称此结果为有限分布晶格的广义中位定理。当将此结果应用于稳定的匹配中时，我们会得到Teo和Sethuraman的中位数稳定匹配定理。我们的证明要比Teo和Sethuraman简单得多。当将广义的中位定理应用于任务问题时，我们会为市场清算价格提供类似的结果。
Let $L$ be any finite distributive lattice and $B$ be any boolean predicate defined on $L$ such that the set of elements satisfying $B$ is a sublattice of $L$. Consider any subset $M$ of $L$ of size $k$ of elements of $L$ that satisfy $B$. Then, we show that $k$ generalized median elements generated from $M$ also satisfy $B$. We call this result generalized median theorem on finite distributive lattices. When this result is applied to the stable matching, we get Teo and Sethuraman's median stable matching theorem. Our proof is much simpler than that of Teo and Sethuraman. When the generalized median theorem is applied to the assignment problem, we get an analogous result for market clearing price vectors.
