  The classical house allocation problem involves assigning $n$ houses (or
items) to $n$ agents according to their preferences. A key criterion in such
problems is satisfying some fairness constraints such as envy-freeness. We
consider a generalization of this problem wherein the agents are placed along
the vertices of a graph (corresponding to a social network), and each agent can
only experience envy towards its neighbors. Our goal is to minimize the
aggregate envy among the agents as a natural fairness objective, i.e., the sum
of all pairwise envy values over all edges in a social graph.
  When agents have identical and evenly-spaced valuations, our problem reduces
to the well-studied problem of linear arrangements. For identical valuations
with possibly uneven spacing, we show a number of deep and surprising ways in
which our setting is a departure from this classical problem. More broadly, we
contribute several structural and computational results for various classes of
graphs, including NP-hardness results for disjoint unions of paths, cycles,
stars, or cliques, and fixed-parameter tractable (and, in some cases,
polynomial-time) algorithms for paths, cycles, stars, cliques, and their
disjoint unions. Additionally, a conceptual contribution of our work is the
formulation of a structural property for disconnected graphs that we call
separability which results in efficient parameterized algorithms for finding
optimal allocations.
