# Graphical House Allocation

arXiv: https://arxiv.org/abs/2301.01323 · HTML: https://mlsanity.com/paper/2301.01323/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 42 references that are in the map.
- First posted on arXiv 3 Jan 2023.

## Builds on (most cited first, 7 of 7)

- [Fair Division via Social Comparison](https://mlsanity.com/paper/1611.06589/) (2016)
- [Envy-Freeness in House Allocation Problems](https://mlsanity.com/paper/1905.00468/) (2019)
- [Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division](https://mlsanity.com/paper/1901.09527/) (2019)
- [Envy-Free Allocations Respecting Social Networks](https://mlsanity.com/paper/2011.11596/) (2020)
- [Graphical One-Sided Markets](https://mlsanity.com/paper/1911.06757/) (2019)
- [On the Complexity of Fair House Allocation](https://mlsanity.com/paper/2106.06925/) (2021)
- [Reforming an Envy-Free Matching](https://mlsanity.com/paper/2207.02641/) (2022)

## Abstract (arXiv)

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.