The standard approach to fair rent division assumes that agents have quasi-linear utilities, and seeks allocations that are envy free; it underlies an algorithm that is widely used in practice. However, this approach does not take budget constraints into account, and, therefore, may assign agents to rooms they cannot afford. By contrast, we design a polynomial-time algorithm that takes budget constraints as part of its input; it determines whether there exist envy-free allocations that satisfy the budget constraints, and, if so, computes one that optimizes an additional criterion of justice. In particular, this gives a polynomial-time implementation of the budget-constrained maximin solution, where the maximization objective is the minimum utility of any agent. We show that, like its non-budget-constrained counterpart, this solution is unique in terms of utilities (when it exists), and satisfies additional desirable properties.

We study the problem of allocating a collective endowment of n objects among n agents when monetary compensation is available. We require budget balance and assume complete information. We also assume that money is desirable and that no object is infinitely better than another (in terms of money). Our preference domain contains, but is not restricted to, quasi-linear preferences. Examples are the dissolution of a partnership among partners who know each other well and the allocation of rooms and the division of the rent among housemates who collectively lease a house.