Multi-UnitAuctions: Beyond RobertsShahar Dobzinski∗Department of Computer ScienceCornell University, Ithaca NY [email protected] Nisan†School of Computer Science and EngineeringHebrew [email protected] exhibit incentive compatible multi-unit auctions that arenot affine maximizers (i.e., are not of the VCG family) andyet approximate the social welfare to within a factor of 1+².For the case of two-item two-bidder auctions we show thatthese auctions, termed Triage auctions, are the only scal-able ones that give an approximation factor better than 2.“Scalable” means that the allocation does not depend onthe units in which the valuations are measured. We de-duce from this that any scalable computationally-efficientincentive-compatible auction for m items and n ≥ 2 bidderscannot approximate the social welfare to within a factorbetter than 2. This is in contrast to arbitrarily good ap-proximations that can be reached under computational con-straints alone, and in contrast to the existence of incentive-compatible mechanisms that achieve the optimal allocation.Categories and Subject DescriptorsF.2.8 [Analysis of Algorithms and Problem complex-ity]: MiscellaneousGeneral TermsTheoryKeywordsMulti-Unit Auctions, Incentive Compatibility∗Supported by an Alfred P. Sloan Foundation Fellowshipand a Microsoft Research New Faculty Fellowship.†Supported by a grant from the Israeli Science Founda-tion, and by the Google Inter-university center for ElectronicMarkets and Auctions.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.EC’11, June 5–9, 2011, San Jose, California, USA.Copyright 2011 ACM 978-1-4503-0261-6/11/06 ...$10.00.1. INTRODUCTIONBackgroundThe field of Algorithmic Mechanism Design [27] designs mech-anisms for achieving various computational goals, under theassumption of rational selfishness of the involved parties.The notions used are taken from the economic field of Mech-anism Design, and a basic notion is that of incentive com-patibility – where rational players are motivated to act truth-fully. For background and survey see part II of [28]. This pa-per will consider only the simplest and most robust notion ofincentive compatibility, that of dominant strategies in quasi-linear settings with independent private values. The typi-cal question in the field asks for a computationally-efficientincentive compatible mechanism that implements a certaintype of outcome, usually the approximate optimization ofsome target “social” goal. There are two variants of thischallenge, the first considers situations where incentive com-patibility itself is hard to achieve and the computationalefficiency is just an additional burden, with the prime ex-ample being approximate minimization of the makespan inscheduling problems [27]. The second variant focuses oncases where each of the two constraints of incentive compat-ibility and computational efficiency can be achieved sepa-rately, and the challenge is to get them simultaneously, withthe prime example being approximate welfare maximizationin various types of combinatorial auctions [24].While there has been much work and some progress onthese types of challenges, with particular emphasis on theproblems mentioned above of combinatorial auctions (e.g.,[22, 20, 3, 15, 23, 16, 13, 6]) and scheduling (e.g., [7, 21, 2]),the basic challenge remains mostly unanswered. As notedin [22], the main issue turns out to be the richness of thedomain of player’s valuations, i.e., of their private informa-tion. On one extreme are single-dimensional domains wherethe private information of each participant is captured by ascalar (or domains very close to it, e.g., [24]). For these typesof problems, incentive-compatible mechanisms are well char-acterized by a certain monotonicity condition and, in mostcases, the challenge of reconciling incentives with computa-tional efficiency has been met [24, 1, 5, 9, 8]. On the otherextreme are problems which are “fully dimensional” (or closeto fully dimensional, e.g., [29, 17]) where there is no struc-ture on valuations, in which case a key theorem of Roberts[30] characterizes incentive compatible mechanisms as“affinemaximizers”“on a sub-range” – simple generalizations of theVCG mechanism. While such affine maximizers on a sub-range are not completely powerless in polynomial time, in233most cases this characterization implies impossibility of goodcomputationally efficient truthful mechanisms. Most inter-esting problems, including those mentioned above, lie in anintermediate range where the valuation spaces are neithersingle dimensional nor fully dimensional, a range for whichvery little is known. The main problem seems to be thelack of a good characterization of incentive compatibility inthese intermediate ranges1. In particular, the key unknownis whether any useful truthful non-VCG mechanisms existin the intermediate range2.Multi-unit AuctionsAs mentioned, the paradigmatic problems for the reconcilia-tion of computational constraints with incentive constraintsare the various subclasses of combinatorial auctions. In thispaper we consider the simplest variant which exhibits thistension: multi-unit auctions. In this problem there are midentical items for sale among n bidders, where each bidderi has a valuation function vi: {0...m} → <, where vi(k) de-notes player i’s value for receiving k items. The valuations viare assumed to be monotone non-decreasing (free disposal)with vi(0) = 0 (normalization). Key and implicit here isthat there are no externalities: the value of bidder i dependsonly on what he gets rather than also on the allocation tothe others. The optimization goal is to find an allocationof items to the bidders, where bidder i gets siitems, withPisi≤ m, that maximizes social welfarePivi(si).The problem becomes computationally challenging whenthe number of items m is “large”, i.e., when the running timeof the mechanism is not allowed to be polynomial in m butrather just in log m. There are two variant models in thiscase, the first assumes that the valuation functions are givenas “black boxes”that