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.

本研究在经典的分配问题基础上，研究了基于社交网络的分配问题，目标是通过最小化代理人之间的嫉妒程度来实现公平分配；同时，该研究还贡献了基于图结构的问题结构与计算结果，提出了一个名为 “可分离性” 的概念，可以在某些图结构中实现高效的最优分配算法。