Sort-Cut: A Pareto Optimal and Semi-Truthful Mechanism for Multi-Unit Auctions with Budget-Constrained Bidders

Isa Hafalir, Sayedi Amin and R. Ravi

No 2009-E17, GSIA Working Papers from Carnegie Mellon University, Tepper School of Business

Abstract: Motivated by sponsored search auctions with hard budget constraints given by the advertisers, 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 nventory in a month, say. In this single-item multi-unit auction, each bidder has a private value for each unit, and a private budget 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 mechanisms, 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 significantly, 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).

References: Add references at CitEc
Citations:

Downloads: (external link)
https://student-3k.tepper.cmu.edu/gsiadoc/wp/2009-E17.pdf
Our link check indicates that this URL is bad, the error code is: 401 Unauthorized

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cmu:gsiawp:996030656

Ordering information: This working paper can be ordered from
https://student-3k.t ... /gsiadoc/GSIA_WP.asp

Access Statistics for this paper

More papers in GSIA Working Papers from Carnegie Mellon University, Tepper School of Business Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3890.
Bibliographic data for series maintained by Steve Spear ().