Sort-cut: A pareto optimal and semi-truthful mechanism for multi-unit auctions with budget-constrained bidders. Unpublished manuscript

Motivated by sponsored search auctions with hard budget constraints given by the adver-tisers, we study multi-unit auctions of a single item. An important example is a sponsored result slot for a keyword, with many units representing its inventory in a month, say. In this single-item multi-unit auction, each bidder has a private value for each unit, and a private bud-get which is the total amount of money she can spend in the auction. A recent impossibility result [Dobzinski et al., FOCS’08] precludes the existence of a truthful mechanism with Pareto-optimal allocations in this important setting. We propose Sort-Cut, a mechanism which does the next best thing from the auctioneer’s point of view, that we term semi-truthful. While we are unable to give a complete characterization of equilibria for our mechanism, we prove that some equilibrium of the proposed mechanism optimizes the revenue over all Pareto-optimal mech-anisms, and that this equilibrium is the unique one resulting from a natural rational bidding strategy (where every losing bidder bids at least her true value). Perhaps even more signifi-cantly, we show that the revenue of every equilibrium of our mechanism differs by at most the budget of one bidder from the optimum revenue (under some mild assumptions).