Multi-Apartment Rent Division

Rent division is the well-studied problem of fairly assigning rooms and dividing rent among a set of roommates within a single apartment. A shortcoming of existing solutions is that renters are assumed to be considering apartments in isolation, whereas in reality, renters can choose among multiple apartments. In this paper, we generalize the rent division problem to the multi-apartment setting, where the goal is to both fairly choose an apartment among a set of alternatives and fairly assign rooms and rents within the chosen apartment. Our main contribution is a generalization of envy-freeness called negotiated envy-freeness. We show that a solution satisfying negotiated envy-freeness is guaranteed to exist and that it is possible to optimize over all negotiated envy-free solutions in polynomial time. We also define an even stronger fairness notion called universal envy-freeness and study its existence when values are drawn randomly.