Chapter 15. The Housing Allocation Problem

Core allocations in housing markets via Gale's Top Trading Cycle and the LLP framework.

This page: LLP forms. View classical forms »

The housing market

There are $n$ agents and $n$ houses. Each agent owns one house and has a strict preference ranking over all houses. A core allocation is an assignment of houses to agents such that no coalition of agents can improve by trading among themselves. Shapley and Scarf (1974) proved that a core allocation always exists and can be found by Gale's Top Trading Cycle (TTC) algorithm.

Gale's Top Trading Cycle

Build a directed graph where each agent points to the owner of her top remaining choice. Since the graph has finitely many nodes and each node has out-degree one, at least one cycle must exist. Every agent in a cycle trades along the cycle (each gets the house she pointed to). Remove those agents, update preference lists, and repeat. The sequential algorithm runs in $O(n^2)$ time.

The LLP perspective

The housing market admits a lattice-linear formulation. The state vector $G[1..n]$ records the current proposal index for each agent: agent $i$ is proposing to house $\mathrm{pref}[i][G[i]]$. The forbidden condition detects agents who are not in the current submatching but whose desired house is held by a submatching member. Advancing increments the proposal index.

LLP-Housing-Market

LLP form on the proposal vector. Forbidden whenever agent $j$ is not part of the largest submatching but wishes for a house owned by a submatching member. Advancing moves agent $j$ to her next preference. At termination, $\mathrm{pref}[i][G[i]]$ gives the house allocated to agent $i$.

Time complexity: $O(n^2)$ via top-trading-cycles, where $n$ is the number of agents.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[j]$ represents and the negation of the forbidden clause from the matching .llp source.