Abstract
What is a fair way to assign rooms to several housemates, and divide the rent between them? This is
not just a theoretical question: many people have
used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness,
in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable.
We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness
constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework
that enables the computation of such solutions in
polynomial time. We then study the relations between natural optimization objectives, and identify
the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most
attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms
of our optimization objectives. Finally, a user study
with Spliddit users as subjects demonstrates that
people find the maximin solution to be significantly
fairer than arbitrary envy-free solutions; this user
study is unprecedented in that it asks people about
their real-world rent division instances. Based on
these results, the maximin solution has been deployed on Spliddit since April 2015.