Revenue maximization when bidders have budgets

ABSTRACT

We study the problem of maximizing revenue for auctions with multiple units of a good where bidders have hard budget constraints, first considered in [2]. The revenue obtained by an auction is compared with the optimal omniscient auction had the auctioneer known the private information of all the bidders, as in competitive analysis [7]. We show that the revenue of the optimal omniscient auction that sells items at many different prices is within a factor of 2 of the optimal omniscient auction that sells all the items at a single price, implying that our results will carry over to multiple price auctions. We give the first auction for this problem, to the best of our knowledge, that is known to obtain a constant fraction of the optimal revenue when the bidder dominance (the ratio between the maximum contribution of a single bidder in the optimal solution and the revenue of that optimal solution) is large (as high as 1/2). Our auction is also shown to remain truthful if canceled upon not meeting certain criteria. On the negative side, we show that no auction can achieve a guarantee of 1/2-ε the revenue of the optimal omniscient multi-price auction. Finally, if the bidder dominance is known in advance and is less than 1/5.828, we give an auction mechanism that raises a large constant fraction of the optimal revenue when the bidder dominance is large and is asymptotically close to the optimal omniscient auction as the bidder dominance decreases. We discuss the relevance of these results for related applications.

REFERENCES

• 1: Gagan Aggarwal , Jason D. Hartline, Knapsack auctions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1083-1092, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109677]
• 2: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 3: Y. Che and J. Gale. Expected revenue of the all-pay auctions and first-price sealed-bid auctions with budget constraints. Economics Letters, 50:373--380, 1996.
• 4: Y. Che and J. Gale. The optimal mechanism for selling to a budget-constrained buyer. Journal of Economic Theory, 92:198--233, 2000.
• 5: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 6: A. Goldberg, J. Hartline, A. Karlin, A. Wright, and M. Saks. Competitive Auctions. Games and Economic Behavior, 2002.
• 7: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 8: Jason Daniel Hartline , Anna R. Karlin, Optimization in the private value model: competitive analysis applied to auction design, 2003
• 9: J.-J. Laffont and J. Robert. Optimal auctions with financially constrained buyers. Economics Letters, 52:181--186, 1996.
• 10: E.S. Maskin. Auctions, development and privatization: Efficient auctions with liquidity-constrained buyers. European Economic Review, 44:667--681, 2000.
• 11: H. Moulin, and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance vs. Efficiency. Economic Theory, 18:511--533, 2001.
• 12: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 13: Federal Communications Commission. Auctions. http://wireless.fcc.gov/auctions 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory