Auction Mechanism for Optimally Trading Off Revenue andEfficiency in Multi-unit AuctionsAnton Likhodedov and Tuomas SandholmCarnegie Mellon UniversityComputer Science Department5000 Forbes AvenuePittsburgh, PA 15213{likh,sandholm}@cs.cmu.eduNovember 8, 2003AbstractWe study auctioning multiple units of the same good to potential buyers with single unit demand (i.e. every buyerwants only one unit of the good). Depending on the objective of the seller, different selling mechanisms are desirable.The Vickrey auction with a truthful reserve price is optimal when the objective is efficiency - allocating the units tothe parties who values them the most. The Myerson auction is optimal when the objective is the seller’s expectedutility. These two objectives are generally in conflict, and cannot be maximized with one mechanism. In many real-world settings—such as privatization and competing electronic marketplaces—it is not clear that the objective shouldbe either efficiency or seller’s expected utility. Typically, one of these objectives should weigh more than the other,but both are important. We account for both objectives by designing a new deterministic dominant strategy auctionmechanism that maximizes expected social welfare subject to a minimum constraint on the seller’s expected utility.This way the seller can maximize social welfare subject to doing well enough for himself.The results in this paper are derived under the asymmetric independent private values model, which assumes thatthe distributions of buyers’ valuations are common knowledge. We also describe a prior-free mechanism, which doesnot assume that the distributions are known. When the number of buyers tends to infinity and the number of units onsale is at least two, this auction approaches expected efficiency and expected seller’s utility of the auction, designedwith distributions known upfront.1 IntroductionElectronic commerce has spawned the use of increasingly sophisticated auction mechanisms. There are several pos-sible reasons for this. First, in many ecommerce settings the bidders are automated agents that are programmed toact rationally even in complex situations. Also human users of ecommerce systems are typically quite savvy andable to recognize attractive properties of sophisticated mechanisms. This motivates the analysis of unintuitive auctionmechanisms, which are capable of meeting complicated design objectives.One example is the Vickrey auction [Vi61]. In this auction with q0units of the same good on sale, q0highestbidders win, but only pay the price of the first unsuccessful bid. The Vickrey auction maximizes economic efficiency,aka. social welfare (assuming the reserve price is set to equal the seller’s valuation for a unit of good being sold), thatis, the units end in the hands of the party who values it the most.Another example is the Myerson auction [My81], which maximizes the seller’s expected utility (expected revenuein case the seller does not value the object).1The unintuitive aspect of the Myerson auction is that it sometimesallocates the goods to bidders other than the q0highest bidders.1The formal characterization of the seller’s optimal multi-unit mechanism was given by E.Maskin and J.Riley in [MR89]. However in thesingle-unit demand case, which is considered in this paper, the seller’s optimal multi-unit mechanism can be derived similarly to the seller’s optimalsingle-unit mechanism from [My81]. Therefore we will refer to the seller’s-optimal mechanism as Myerson auction.1Expected social welfare and the seller’s expected utility cannot be maximized with the same auction mechanismin general because these objectives conflict. Furthermore, in many real-world settings it is not clear that the objectiveshould be either of the two.For example, most privatization auctions are motivated by the belief that private companies can make more efficientuse of an asset than the government can. It seems thus reasonable to allocate the asset to the party who can make themost effective use of it, that is, to use efficiency as the auction objective. At the same time, the government would liketo raise as much money from the sale as possible (maximize the seller’s expected utility) because the asset is ownedby the tax payers who prefer to pay for government expenditures out of the auction revenue rather than taxes.As another example, consider electronic auction houses that compete with each other. To attract sellers, an auctionhouse would use an auction mechanism that maximizes the seller’s expected utility. On the other hand, this wouldnot be desirable from the perspective of attracting buyers. Clearly, an auction house needs both buyers and sellers tooperate. Therefore, including some element of social welfare measurement in the objective may be desirable.We account for both objectives by designing a new deterministic auction mechanism that maximizes expectedsocial welfare subject to a minimum constraint on the seller’s expected utility. This way the seller can maximizesocial welfare subject to subject to doing well enough for himself. We show that this auction mechanism belongs toa family of mechanisms, maximizing a linear combination of the seller’s expected utility and expected social welfare,controlled by one free parameter λ.2We then present an algorithm for determining the optimal value for this parameterand constructing an auction with desired characteristics. This approach is different from the traditional mechanismdesign - the mechanism is not completely specified upfront - rather we compute the particular mechanism for everyinstance of the problem (that is, given the constraint on the revenue and the distributions of buyers’ valuations). In away this is similar in spirit to automated mechanism design [CS02].We also present a family of much simpler randomized mechanisms that under some assumptions, which we statelater in the paper achieve the same expected revenue and efficiency. However, in Section 4 we argue, that random-ization is inappropriate for the settings, which motivate the present work. This discourages the use of the randomizedmechanisms even in the cases, when they yield similar expected revenue and social welfare.Although most of the results in this paper are derived under the independent private values model, which assumesthat the distributions of valuations (types) of buyers are common knowledge, it is possible to relax this assumption. InSection 5