Multi-unit Auctions with Budget LimitsShahar Dobzinski∗Ron Lavi†Noam Nisan‡AbstractWe study multi-unit auctions where the bidders have a budget constraint, a situation very common in prac-tice that has received very little attention in the auction theory literature. Our main result is an impossibility:there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtainsome surprising positive results for certain special cases.∗The School of Computer Science and Engineering, the Hebrew University of Jerusalem. Supported by the Adams Fellow-ship Program of the Israel Academy of Sciences and Humanities, and by a grant from the Israeli Academy of Sciences. Email:[email protected].†IE&M, Technion. This work was done while the author was consulting Google Tel Aviv. Email:[email protected].‡Google Tel-Aviv and Hebrew University. Email: [email protected] IntroductionThe starting point of almost all of auction theory is the set of players’ valuations: how much value (measured insome currency unit) does each of them assign to each possible outcome of the auction1. When attempting actualimplementations of auctions, a mismatch between theory and practice emerges immediately: budgets. Playersoften have a maximum upper bound on their possible payment to the auction – their budget. This budget limitis not adequately expressible in existing auction theory2. As budgets are central elements in most of economictheory (e.g., in the Arrow-Debreu market model), it is quite surprising that so little attention has been paid tothem in auction theory, and in particular in auctions of multiple units or goods. The reason seems to be thatbudgets take us out of the clean “quasi-linear” setting, which changes many of the “rules of the game”. Previouswork on this issue in economic theory mostly focused on comparing classical auctions formats under budgetconstraints (e.g., [2]). We are aware of only two recent papers that have attempted explicitly designing auctionsfor this setting [5, 4].The Inadequacy of the Quasi-linear ModelSome previous papers (e.g. [6, 7]) have attempted modeling the budget limit as an upper bound on the valueobtained by the bidder rather than on his payment. Specifically they model a player with valuation v and budgetB as though having a valuation v0= min(B, v). This model maintains the quasi-linear setting but misses thepoint when the budget limit is a real constraint, i.e. is lower than what the payment would be without it. Atypical case where budgets play a central role is an auction for multiple items (homogenous or heterogenous),where bidders have a value for each unit and a budget limit that constrains the number of units they can obtain,i.e. the budget is significantly smaller than the combined value of all items3. This is in contrast to the unrealisticquasi-linear modeling where the constraint is a fixed demand curve such as an upper bound q on the number ofunits desired by the bidder. In such cases, once a value equalling the budget is reached, the min(v, B)-modelincorrectly models the marginal value of additional goods as being zero. This would lead to several artifacts, inparticular “VCG” payments will be identically zero, loosing not only all revenue but also incentive-compatibilityitself. From an allocation point of view, any allocation in which all bidders’ values reach their budgets wouldbe considered efficient (maximize social-welfare) including those that are not even Pareto-efficient. We thusconclude that addressing budgets properly requires transcending the pure quasi-linear setting, as usually done inthe rest of economic theory.Our ModelIn this paper we study multi-unit auctions with budget limits. Our model is simple: There are m identicalindivisible units for sale, and each bidder i has a private value vifor each unit, as well as a private budget limitbion the total amount he may pay. We also consider the limiting case where m is large by looking at auctions ofa single infinitely-divisible good. Our assumption is that bidders are utility-maximizers, where i’s utility fromacquiring xiunits and paying piis ui= xi· vi− pi, as long as the price is within budget, pi≤ bi, and is negativeinfinity (infeasible) if pi> bi4. As the revelation principle holds in this setting we concentrate on truthful auctionmechanisms. In this paper we concentrate on allocational efficiency, only commenting on revenue aspects,1This “quasi-linear” setting is needed due to the Gibbard-Satterthwaite impossibility theorem for the general setting without money.2The nature of what this budget limit means for the bidders themselves is somewhat of a mystery since it often does not seem to simplyreflect the true liquidity constraints of the bidding firm. There seems to be some risk control element to it, some purely administrativeelement to it, some bounded-rationality element to it, and more. What can not be disputed is that these budget constraints are very realto the bidders, in fact, usually more concrete and real than the rather abstract notion of the valuation.3The original motivation for this work, as well as for [5, 4] came from ad-auctions which are certainly such a case. Auctions forspectrum licences and for pollution permits are natural applications as well.4This model naturally generalizes to combinatorial auctions: bidders have a valuation vi(·) and a budget bi, and their utility fromacquiring a set Siof items and paying pifor them is vi(S) − pias long as pi≤ biand negative infinity if the budget has been exceededpi> bi. It is interesting to note that the “demand-oracle model” (see e.g. [3]) represents such bidders as well. Analyzing combinatorialauctions with budget limits, even in simple setting such as additive valuations is clearly a direction for future research.1and leaving revenue maximization as a future research direction, already initiated in [4]. As our setting is notquasi-linear, allocational efficiency is not uniquely defined since different allocations are preferred by differentplayers5. We thus focus at the weakest efficiency requirement: Pareto-optimality, i.e. allocations where it isimpossible to strictly improve the utility of some players without hurting those of others. This strengthens ournegative results, while the quality of our positive results may be evaluated by other criteria favored by the reader.Impossibility ResultOur main result in this paper is a spoiler: