Econ Papers Daily / 期刊论文
最小不稳定与优于延迟接受机制的较大改进之间的权衡
The trade-off between minimal instability and larger improvements over deferred acceptance
摘要
The celebrated Efficiency-Adjusted Deferred Acceptance mechanism (EADA) improves the efficiency of the DA algorithm via consented priority violations. Notwithstanding its many merits, we show that EADA can improve only two students when an alternative mechanism that Pareto-dominates DA could benefit all but one student. This shortfall in the number of students improved is not exclusive of EADA but extends to all setwise minimally unstable mechanisms, i.e. those that generate a set of blocking pairs that is never a strict superset of that of another mechanism. The incompatibility between number of students improved and minimal instability disappears when blocking pairs are compared cardinally rather than by set inclusion. In some problems, EADA can be doubly dominated: improving fewer students while generating more blocking pairs.
中文摘要
著名的效率调整延迟接受机制（EADA）通过经同意的优先权违反提升了DA算法的效率。尽管其优点众多，我们表明，当一种帕累托优于DA的替代机制能够使除一名学生之外的所有学生受益时，EADA只能改善两名学生。这种在受改善学生数量上的不足并非EADA所独有，而是扩展到所有集合意义上最小不稳定机制，即那些所产生的阻塞对集合永远不是另一机制阻塞对集合的严格超集的机制。当阻塞对以基数方式而非集合包含方式进行比较时，受改善学生数量与最小不稳定之间的不相容性便消失了。在某些问题中，EADA可能被双重支配：改善更少的学生，同时产生更多的阻塞对。