We consider the problem of finding a competitive equilibrium when agents have budget constraints and items are indivisible. In our model, the utility of an agent is equal to her valuation minus payment when the payment is no more than her budget; otherwise she gets negative utility. In a competitive equilibrium, every item is assigned a non-negative price, and the items are allocated to the agents in such a way that every agent gets her utility-maximizing bundle, and every unallocated item has price zero.
Most previous work on competitive equilibria (with and without budgets) has focused on the {\em Gross Substitutes} case, where a competitive equilibrium is guaranteed to exist modulo tie-breaking. Our work deals with two types of valuation functions that do not satisfy this property in the presence of budget constraints: Additive valuations, and concave combinatorial valuations.
We present some hardness results for deciding the existence of exact competitive equilibria. Next, we develop connections to a related Fisher model of market clearing in order to design poly-time algorithms that compute approximate competitive equilibria. Not only do our algorithms require several new technical ideas, but we also show that this approach sheds new light on algorithms for the Fisher model. In particular, it yields an interpretation of the well-known Eisenberg-Gale convex program as optimizing a measure of social welfare. We also prove strong revenue properties of the equilibria we construct. We thereby improve and extend the recent work on revenue maximizing envy-free multi-unit auctions by Feldman et al. in EC 2012 (joint work with Vincent Conitzer, Kamesh Munagala and Xiaoming Xu).
