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

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 inventory 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 Paretooptimal 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).

• Publication year

  2009

• Venue

  arXiv.org

• Publication date

  2009-03-08

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  arXiv 0903.1450
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Single-value combinatorial auctions and algorithmic implementation in undominated strategies

  2009cited by this paper
• Multi-unit Auctions with Budget Limits

  2008influential reference
• A Truthful Mechanism for Offline Ad Slot Scheduling

  2008cited by this paper
• Greedy bidding strategies for keyword auctions

  2007cited by this paper
• Revenue maximization when bidders have budgets

  2006cited by this paper
• Multi-unit auctions with budget-constrained bidders

  2005cited by this paper
• AdWords and generalized on-line matching

  2005cited by this paper
• Auctions with Budget Constraints

  2004cited by this paper
• An Efficient Ascending-Bid Auction for Multiple Objects

  2004cited by this paper
• Expected revenue of all-pay auctions and first-price sealed-bid auctions with budget constraints

  2003cited by this paper
• Auctions, development, and privatization: Efficient auctions with liquidity-constrained buyers

  2000cited by this paper
• Multiple-Object Auctions with Budget Constrained Bidders

  1998cited by this paper
• Strategic Bidding in a Multiunit Auction: An Empirical Analysis of Bids to Supply Electricity in England and Wales

  1998cited by this paper
• Expected revenue of all-pay auctions and first-price sealed-bid auctions with budget constraints

  1996cited by this paper
• Demand Reduction and Inefficiency in Multi-Unit Auctions

  1995cited by this paper
• Optimal bidding in multi-unit auctions with many bidders

  1995cited by this paper
• Implementation in Undominated Strategies: A Look at Bounded Mechanisms

  1992cited by this paper

• Sponsored Search Auctions

  2015cites this paper
• Stochastic Budget Strategies at the Campaign Level: A Preliminary Investigation

  2014cites this paper
• Chapter 2 – Budget Constraints in Sponsored Search Auctions

  2014cites this paper
• Keyword auctions with budget-constrained bidders

  2013influential citation
• STAMP: A Strategy-proof Approximation auction Mechanism for Spatially reusable Items in wireless networks

  2013cites this paper
• Keyword auctions with budget-constrained bidders

  2013influential citation
• Design and Analysis of Sponsored Search Mechanisms

  2013cites this paper
• Polyhedral clinching auctions and the adwords polytope

  2012cites this paper
• Optimal equilibrium bidding strategies for budget constrained bidders in sponsored search auctions

  2012cites this paper
• Sponsored search auctions: an overview of research with emphasis on game theoretic aspects

  2012cites this paper
• Auctions, equilibria, and budgets

  2012cites this paper
• An Approach to VCG-like Approximate Allocation and Pricing for Large-scale Multi-unit Combinatorial Auctions

  2012cites this paper
• Toward a VCG-Like Approximate Mechanism for Large-Scale Multi-unit Combinatorial Auctions

  2011cites this paper
• Offline Ad Slot Scheduling

  2010cites this paper
• Incentive compatible budget elicitation in multi-unit auctions

  2009cites this paper
• Budget constrained auctions with heterogeneous items

  2009cites this paper