December 25, 2015

"Rental Harmony: Sperner's Lemma in Fair Division"

I recently stumbled on the paper "Rental Harmony: Sperner's Lemma in Fair Division" by Francis Su. It describes an application of a pure combinatorial lemma by Sperner from 1928 to the problem of dividing rent among a number of housemates in a fair manner. Last year, the New York Times published an article together with a rent calculator that is based on this paper.

I am not a mathematician, but the approach is to me very elegant and intuitive and -- at the same time -- solves a practical problem in a way that you wouldn't expect. I think it is not the contribution of this paper but the inductive proof of Sperner's Lemma itself using a "trap-door" argument is very neat. The application to fair division, and particularly to the rent division problem is just beautiful.

It does not make any sense to repeat the details here. The paper itself together with the rent calculator on Su' homepage or the one at the New York Times website are a great source for understanding the problem and its solution.