What's the Matter with Tie-Breaking? Improving Efficiency in School Choice
针对美国择校中随机打破平局损害学生福利的问题，提出一种多项式时间算法，通过“稳定改进环”概念找到学生最优的稳定匹配，并分析了该机制的策略性质。
In several school choice districts in the United States, the student proposing deferred acceptance algorithm is applied after indifferences in priority orders are broken in some exogenous way. Although such a tie-breaking procedure preserves stability, it adversely affects the welfare of the students since it introduces artificial stability constraints. Our main finding is a polynomial-time algorithm for the computation of a student-optimal stable matching when priorities are weak. The idea behind our construction relies on a new notion which we call a stable improvement cycle. We also investigate the strategic properties of the student-optimal stable mechanism.