  We study the problem of fair rent division that entails splitting the rent
and allocating the rooms of an apartment among roommates (agents) in a fair
manner. In this setup, a distribution of the rent and an allocation is said to
be fair if it is envy free, i.e., under the imposed rents, no agent has a
strictly stronger preference for any other agent's room. The cardinal
preferences of the agents are expressed via functions which specify the
utilities of the agents for the rooms at every possible room rent/price. While
envy-free solutions are guaranteed to exist under reasonably general utility
functions, efficient algorithms for finding them were known only for
quasilinear utilities. This work addresses this notable gap and develops
approximation algorithms for fair rent division with minimal assumptions on the
utility functions.
  Specifically, we show that if the agents have continuous, monotone
decreasing, and piecewise-linear utilities, then the fair rent-division problem
admits a fully polynomial-time approximation scheme (FPTAS). That is, we
develop algorithms that find allocations and prices of the rooms such that for
each agent a the utility of the room assigned to it is within a factor of $(1 +
\epsilon)$ of the utility of the room most preferred by a. Here, $\epsilon>0$
is an approximation parameter, and the running time of the algorithms is
polynomial in $1/\epsilon$ and the input size. In addition, we show that the
methods developed in this work provide truthful mechanisms for special cases of
the rent-division problem. Envy-free solutions correspond to equilibria of a
two-sided matching market with monetary transfers; hence, this work also
provides efficient algorithms for finding approximate equilibria in such
markets. We complement the algorithmic results by proving that the fair rent
division problem lies in the intersection of the complexity classes PPAD and
PLS.
