Spliddit's rent calculator helps roommates to fairly share rent when moving into a new house or apartment. This is especially useful when bedrooms differ in size, closet space, bathrooms, and more. You begin by providing a list of roommates, a list of bedrooms, and the monthly rent. We then send everyone a link where they specify how much they would pay to live in each bedroom. Our algorithm uses these evaluations to determine who should live in which room, and how much each housemate should contribute to the monthly rent.
Fairness Properties
Envy-freeness
Our algorithm assigns rooms in such a way that each roommate feels that they got the best deal. In other words, no roommate would want to swap places with another.
This property is guaranteed, assuming that each roommate wishes to maximize the difference between what she thinks her room is worth and how much rent she has to pay.
Efficiency
Our algorithm divides the rent and assigns rooms in such a way that it would be impossible to find another assignment that benefits a roommate without making another roommate worse off.
This property is guaranteed, assuming that each roommate wishes to maximize the difference between what she thinks her room is worth and how much rent she has to pay.
Algorithm Overview
We assume that the benefit a participant derives from getting a room she values at x for rent y is x minus y. We first match the participants to rooms in a way that maximizes the sum of values participants derive from their assigned rooms. We then compute prices for the rooms that maximize the minimum benefit derived by any player (this is the objective function), subject to envy-freeness, by solving a linear program. Envy-free prices are guaranteed to exist, and, moreover, the overall allocation of rooms and rent is guaranteed to be optimal in terms of the above objective function among all envy-free allocations. Envy-freeness also implies efficiency and individual rationality.
References: "Which Is the Fairest (Rent Division) of Them All?", by Ya'akov Gal, Moshe Mash, Ariel D. Procaccia, and Yair Zick.