  We prove that the classic problem of finding a competitive equilibrium in an
exchange economy with indivisible goods, money, and unit-demand agents is
PPAD-complete. In this "housing market", agents have preferences over the house
and amount of money they end up with, but can experience income effects. Our
results contrast with the existence of polynomial-time algorithms for related
problems: Top Trading Cycles for the "housing exchange" problem in which there
are no transfers and the Hungarian algorithm for the "housing assignment"
problem in which agents' utilities are linear in money. Along the way, we prove
that the Rainbow-KKM problem, a total search problem based on a generalization
by Gale of the Knaster-Kuratowski-Mazurkiewicz lemma, is PPAD-complete. Our
reductions also imply bounds on the query complexity of finding competitive
equilibrium.
