Multi-unit Auctions with Budget Limits∗Shahar Dobzinski†The School of Computer Science and EngineeringThe Hebrew University of [email protected] Lavi‡Faculty of Industrial Engineering and ManagementThe Technion – Israel Institute of [email protected] NisanThe School of Computer Science and EngineeringThe Hebrew Universit y of JerusalemandGoogle Tel [email protected] study multi-unit auctions where the bidders have a budget constraint, a situation verycommon in practice that has received relatively little attention in the auction theory literature.Our main result is an impossibility: there are no incentive-compatible auctions that alwaysproduce a Pareto-optimal allocation. We also obtain some surprising positive results for certainspecial cases.JEL Classification Numbers: C70, D44, D82Keywords: Multi-Unit Auctions, Budget Constraints, Pareto Optimality.∗A preliminary version appeared in FOCS’08. We thank Peerapong Dhangwatnotai for pointing out an error in aprevious version.†Supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities, and by a grantfrom the Israeli Academy of Sciences.‡This work was done while this author was consulting Google Tel Aviv.11 IntroductionThe starting point of almost all of auction theory is the set of players’ valuations:howmuchvalue (measured in some currency unit) does each of them assigns to each possible outcome ofthe auction. When attempting actual implementations of auctions, a mismatch between theoryand practice emerges immediately: budgets. Players often have a maximum upper bound on theirpossible payment to the auction – their budget. This budget limit is not adequately expressible inexisting auction theory1. Budgets are central elements in most of economic theory, but relativelylittle attention has been paid to them in auction theory. A concrete example is Google’s and Yahoo’sad-auctions, where budgets are an important part of a user’s bid, and are perhaps even more real forthe users than the rather abstract notion of a valuation. Addressing budgets properly breaks downthe usual quasi-linear setting, as is common in the rest of micro-economic theory (e.g., in the Arrow-Debreu market model). Because of this, the VCG mechanism loses its incentive-compatibility, andthe design of incentive-compatible mechanisms becomes significantly more involved.The few relatively recent works in the literature that study this issue focus on four differentdirections. The first branch of works (Che and Gale, 1998; Benot and Krishna, 2001) analyze howbudgets change the classic results on “standard” auction formats, showing for example that first-price auctions raise more revenue than second-price auctions when bidders are budget-constrained,and that the revenue of a sequential auction is higher than the revenue of a simultaneous ascendingauction. A second branch of works (Laffont and Robert, 1996; Pai and Vohra, 2008) constructsingle-item auctions that maximize the seller’s revenue, and a third branch (Maskin, 2000) considersthe problem of “constrained efficiency”: maximizing the expected social welfare under Bayesianincentive compatibility constraints. The forth branch (Borgs et al., 2005; Abrams, 2006), takenby the computer science community, tries to design incentive-compatible multi-unit auctions thatapproximate the optimal revenue.Our model in this paper is simple: There are m identical indivisible units for sale, and eachbidder i has a private value vifor each unit, as well as a budget limit bion the total amount hemay pay. We also consider the limiting case where m is large by looking at auctions of a singleinfinitely-divisible good. Our assumption is that bidders are utility-maximizers, where i’s utilityfrom acquiring xiunits and paying piis ui= xi· vi− pi, as long as the price is within budget,pi≤ bi, and is negative infinity (infeasible) if pi>bi2. As the revelation principle holds in thissetting we concentrate on incentive-compatible (in dominant strategies) mechanisms.In this paper we concentrate on auctions that produce an efficient allocation. As our settingis not quasi-linear, allocational efficiency is not uniquely defined since different allocations are pre-ferred by different players3. We thus focus at the weakest efficiency requirement: pareto-optimality,i.e. allocations where it is impossible to strictly improve the utility of some players without hurtingthose of others.1The nature of what this budget limit means for the bidders themselves is somewhat of a mystery since it oftendoes not seem to simply reflect the true liquidity constraints of the bidding firm. There seems to be some risk controlelement to it, some purely administrative element to it, some bounded-rationality element to it, and more.2This model naturally generalizes to any type of multi-item auctions: bidders have a valuation vi(·) and a budgetbi, and their utility from acquiring a set S of items and paying pifor them is vi(S) − pias long as pi≤ biandnegative infinity if the budget has been exceeded pi>bi. It is interesting to note that the “demand-oracle model”(see e.g. Blumrosen and Nisan (2007)) represents such bidders as well. Analyzing combinatorial auctions with budgetlimits, even in simple settings such as additive valuations, is clearly a direction for future research.3In quasi-linear settings any pareto-optimal allocation must optimize the “social-welfare” – the sum of biddersvaluations – and thus efficiency is justifiably interpreted as maximizing social-welfare.2Our main result is a spoiler: we show that there is no incentive-compatible and pareto-optimalauction for any finite number m>1 of units of an indivisible good with any n ≥ 2numberofplayers.Towards this result, we first analyze the case where budgets are common-knowledge. Under thisassumption, we characterize the unique mechanism that is simultaneously incentive-compatible andpareto-optimal. Quite surprisingly, the revenue properties of this auction are also excellent. Theassumption of public budgets was made by several of the works mentioned above, e.g. by Laffontand Robert (1996) and Maskin (2000), and our characterization for this case may be interestingby itself, in addition to being the cornerstone of our impossibility result. After obtaining thecharacterization for the known-budgets case, enables the impossibility for the private-budgets