Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We study auctions for selling a limited supply of a single commodity in the case where the supply is known in advance and the case it is unknown and must be instead allocated in an online fashion. The latter variant was proposed by Mahdian and Saberi [12] as a model of an important phenomena in auctions for selling Internet advertising: advertising impressions must be allocated as they arrive and the total quantity available is unknown in advance. We describe the Bayesian optimal mechanism for these variants and extend the random sampling auction of Goldberg et al. [8] to address the prior-free case.

REFERENCES

• 1: Saeed Alaei , Azarakhsh Malekian , Aravind Srinivasan, On random sampling auctions for digital goods, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA [doi>10.1145/1566374.1566402]
• 2: M. Babaioff, L. Blumrosen, and A. Roth. Auctions with online supply. Working paper.
• 3: S. Baliga and R. Vohra. Market research and market design. Advances in Theoretical Economics, 3, 2003.
• 4: S. Chakraborty and N. Devanur. An Online Multi-unit Auction with Improved Competitive Ratio. ArXiv e-prints, January 2009.
• 5: U. Feige, A. Flaxman, J. Hartline, and R. Kleinberg. On the Competitive Ratio of the Random Sampling Auction. In Proc. 1st Workshop on Internet and Network Economics, pages 878--886, 2005.
• 6: 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]
• 7: A.V. Goldberg, J.D. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 55:242--269, 2006.
• 8: 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
• 9: J. Hartline and A. Karlin. Profit maximization in mechanism design. In N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 13, pages 331--362. Cambridge University Press, 2007.
• 10: Jason D. Hartline , Robert McGrew, From optimal limited to unlimited supply auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.175-182, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064028]
• 11: Jason D. Hartline , Tim Roughgarden, Optimal mechanism design and money burning, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374390]
• 12: Mohammad Mahdian , Amin Saberi, Multi-unit auctions with unknown supply, Proceedings of the 7th ACM conference on Electronic commerce, p.243-249, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134734]
• 13: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Economics

Keywords:
auction, limited supply, mechanism design, online, prior-free