@article{hosseini2024houseallocationidentical,
author = {Hosseini, Hadi and McGregor, Andrew and Payan, Justin and Sengupta, Rik and Vaish, Rohit and Viswanathan, Vignesh},
title = {Graphical house allocation with identical valuations},
year = {2024},
issue_date = {Dec 2024},
publisher = {Kluwer Academic Publishers},
address = {USA},
volume = {38},
number = {2},
issn = {1387-2532},
url = {https://doi.org/10.1007/s10458-024-09672-7},
doi = {10.1007/s10458-024-09672-7},
abstract = {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, called Graphical House Allocation, 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 the envy value over all edges in a social graph. We focus on graphical house allocation with identical valuations. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied Minimum Linear Arrangement. 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, cliques, and complete bipartite graphs; we also obtain fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, complete bipartite graphs, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call splittability, which results in efficient parameterized algorithms for finding optimal allocations.},
journal = {Autonomous Agents and Multi-Agent Systems},
month = aug,
numpages = {47},
keywords = {Fair allocation, House allocation, Envy minimization, Local envy}
}