  The classic house allocation problem is primarily concerned with finding a
matching between a set of agents and a set of houses that guarantees some
notion of economic efficiency (e.g. utilitarian welfare). While recent works
have shifted focus on achieving fairness (e.g. minimizing the number of envious
agents), they often come with notable costs on efficiency notions such as
utilitarian or egalitarian welfare. We investigate the trade-offs between these
welfare measures and several natural fairness measures that rely on the number
of envious agents, the total (aggregate) envy of all agents, and maximum total
envy of an agent. In particular, by focusing on envy-free allocations, we first
show that, should one exist, finding an envy-free allocation with maximum
utilitarian or egalitarian welfare is computationally tractable. We highlight a
rather stark contrast between utilitarian and egalitarian welfare by showing
that finding utilitarian welfare maximizing allocations that minimize the
aforementioned fairness measures can be done in polynomial time while their
egalitarian counterparts remain intractable (for the most part) even under
binary valuations. We complement our theoretical findings by giving insights
into the relationship between the different fairness measures and conducting
empirical analysis.
