Researchers Solve Fair Housing Puzzle When Homes Arrive One at a Time

Imagine a city with a list of people who need housing. Apartments don't all become available on January 1st — they trickle in month by month. Most classic matching methods assume you can see every home and every person upfront, then do the math once. This paper asks what happens when you can't: decisions have to be made on the fly, without knowing what's coming next. The authors call this "online house allocation."

The first result is encouraging. If you're allowed to give small cash subsidies — payments that make someone feel fine about the home they got instead of someone else's — the researchers show you can always keep the group envy-free, no matter what order homes arrive in. The catch is churn. Accepting a newly arrived apartment may mean bumping someone else, who bumps someone else, and so on. In the worst case, those reassignment chains can stretch as long as the entire list of people.

The second result is a genuine downer. If your goal is to spend as little subsidy money as possible, there is essentially no good real-time strategy. The authors prove that with just two people and four houses, no algorithm can reliably stay close to the best possible answer — not even a clever randomized one. There is one bright spot: if there is at most one extra house beyond the number of people, exact online optimization suddenly becomes possible. One extra house, and everything works.

Finally, the team builds "learning-augmented" algorithms — systems that use predictions about future arrivals to reach the ideal offline answer when those predictions are good, while still guaranteeing they won't blow up when predictions are wrong. In plain terms: guess well and you win; guess badly and you're still protected. That balance is what could make this practical for real housing offices and school placement systems.