OpenAlex ·

Online House Allocation with Subsidy

Nicholas Teh, Saar Cohen, Karen Frilya Celine, Benjamin Yu and Michael J. Wooldridge

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.29691
Original
Read it at the publisher
Topics
Artificial IntelligenceComputational ComplexityEconometricsGeneral Economics

Abstract

House allocation is a fundamental problem in which each agent is assigned exactly one house. While the classical model assumes that all houses are available before the allocation is computed, many practical settings require decisions to be made as houses become available over time. We introduce the online house allocation problem, where houses arrive sequentially and the algorithm must maintain an allocation without knowledge of future arrivals. Unlike online fair division, the one-house-per-agent constraint makes recourse an inherent part of the problem, as accepting a newly arrived house may require reassigning previously allocated houses. We study online house allocation under subsidy-based fairness, where monetary subsidies eliminate envy among agents. We show that envy-freeability can always be maintained online using bounded recourse and that reassignment chains of length linear in the number of agents are unavoidable in the worst case. In contrast, minimizing the total subsidy is fundamentally harder: no deterministic online algorithm against an adaptive adversary, and no randomized online algorithm against a non-adaptive adversary, admits a bounded competitive ratio, even for two agents and four houses. We complement these impossibilities by showing that exact online subsidy minimization is possible whenever there is at most one extra house beyond the number of agents, and that this guarantee is best possible with respect to the number of extra houses. Finally, we develop learning-augmented algorithms that recover the offline optimum under accurate predictions while providing explicit robustness guarantees when predictions are inaccurate.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics