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.

In the consensus halving problem we are given n agents with valuations over the interval $[0,1]$. The goal is to divide the interval into at most $n+1$ pieces (by placing at most n cuts), which may be combined to give a partition of $[0,1]$ into two sets valued equally by all agents. The existence of a solution may be established by the Borsuk-Ulam theorem. We consider the task of computing an approximation of an exact solution of the consensus halving problem, where the valuations are given by distribution functions computed by algebraic circuits. Here approximation refers to computing a point that $\varepsilon$-close to an exact solution, also called strong approximation. We show that this task is polynomial time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem defined by a continuous function that is computed by an algebraic circuit. The Borsuk-Ulam search problem is the defining problem of the complexity class BU. We introduce a new complexity class BBU to also capture an alternative formulation of the Borsuk-Ulam theorem from a computational point of view. We investigate their relationship and prove several structural results for these classes as well as for the complexity class FIXP.