Tie breaking in unbalanced matching markets--a new paper by Itai Ashlagi and Afshin Nikzad.

What matters in tie-breaking rules? How competition guides design, by Itai Ashlagi  and Afshin Nikzad

August 2015

Abstract

School districts that adopt the Deferred Acceptance (DA) mechanism to assign students to schools face the tradeoff between fairness and efficiency when selecting how to break ties among equivalent students. We analyze a model with with random generated preferences for students and compare two mechanisms differing by their tie-breaking rules: DA with one single lottery (DA-STB) and DA with a separate lottery for each school (DA-MTB). We identify that the balance between supply and demand in the market is a prominent factor when selecting a tie-breaking rule. When there is a surplus of seats, we show that neither random assignments under these mechanisms stochastically dominates each other, and, the variance of student’s assignments is larger under DA-STB. However, we show that there is essentially no tradeoff between fairness and efficiency when there is a shortage of seats: not only that DA-STB (almost) stochastically dominates DA-MTB, it also results in a smaller variance in student’s rankings. We further find that under DA-MTB many pairs of students would benefit from directly exchanging assignments ex post when there is a shortage of seats, while only few such pairs exist when there is a surplus of seats. Our findings suggest that it is more desirable that “popular” schools use a single lottery over a separate lottery in order to break ties, while in other schools there is a real tradeoff.