论文部分内容阅读
帕累托最优匹配指的是给一群申请人分配房子，其中每个申请人对他们可以接受的房子有一个优先序列。我们称一个匹配是帕累托最优的即不存在任何其它的匹配使得至少有一个申请人更喜欢新的匹配且没有其他申请人更喜欢原来的匹配。在这里“更喜欢”指的是在某个匹配中获得优先级更高的房子。当在动态环境下申请人和房子可以任意地加入或离开系统时，本文给出一个线性的算法对原来的帕累托匹配作出调整，使匹配仍然能够保持帕累托最优且匹配到尽可能多的申请人。此外本文还证明了任意两个帕累托匹配之间可以通过特殊构造的有向图一步转换到达。