OpenAlex ·
Online House Allocation with Subsidy
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.29691
- Original
- Read it at the publisher
- Topics
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.
More in Artificial Intelligence
Metaorder modelling and identification from public data
Deterministic Leave-One-Cluster-Out Cross-Validation for Multilevel Bayesian Structural Equation Models
Computing Equilibria in Simulation-Based Insurance Markets with Discontinuous Demand
How outside options are incorporated into payoff distributions
Tight Maximin Share Guarantees of EFX and PMMS
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.