  We study markets where a set of indivisible items is sold to bidders with
unit-demand valuations, subject to a hard budget limit. Without financial
constraints and pure quasilinear bidders, this assignment model allows for a
simple ascending auction format that maximizes welfare and is
incentive-compatible and core-stable. Introducing budget constraints, the
ascending auction requires strong additional conditions on the unit-demand
preferences to maintain its properties. We show that, without these conditions,
we cannot hope for an incentive-compatible and core-stable mechanism. We design
an iterative algorithm that depends solely on a trivially verifiable ex-post
condition and demand queries, and with appropriate decisions made by an
auctioneer, always yields a welfare-maximizing and core-stable outcome. If
these conditions do not hold, we cannot hope for incentive-compatibility and
computing welfare-maximizing assignments and core-stable prices is hard: Even
in the presence of value queries, where bidders reveal their valuations and
budgets truthfully, we prove that the problem becomes NP-complete for the
assignment market model. The analysis complements complexity results for
markets with more complex valuations and shows that even with simple
unit-demand bidders the problem becomes intractable. This raises doubts on the
efficiency of simple auction designs as they are used in high-stakes markets,
where budget constraints typically play a role.
