非均匀稳定匹配

《ACM Transactions on Economics and Computation》：Non-uniformly Stable Matchings

非均匀稳定匹配的判定算法、凸多面体刻画及其格结构研究。首先证明非均匀稳定匹配存在性可在多项式时间内确定，接着给出该匹配集合的凸多面体刻画，最后证明其构成分配格。

　　

摘要

在存在平局的稳定匹配问题中，超稳定性和强稳定性是匹配的一种属性。在本文中，我们提出了超稳定性和强稳定性的一个通用推广概念，称之为“非均匀稳定性”。首先，我们证明了可以在多项式时间内确定是否存在非均匀稳定的匹配。接着，我们给出了非均匀稳定匹配集合的多面体特征描述。最后，我们证明了非均匀稳定匹配集合构成一个分配格。