# Envy-Free House Allocation with Minimum Subsidy

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2024.

## Built on by (most cited first, 2 of 2)

- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)

## Abstract (arXiv)

House allocation refers to the problem where m houses are to be allocated to n agents so that each agent receives one house. Since an envy-free house allocation does not always exist, we consider finding such an allocation in the presence of subsidy. We show that computing an envy-free allocation with minimum subsidy is NP-hard in general, but can be done efficiently if m differs from n by an additive constant or if the agents have identical utilities.