On random sampling auctions for digital goods

ABSTRACT

In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is a popular approach for auctions that aims to maximize the seller's revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is 15-competitive in the worst case -- which is substantially better than the previously proved bounds but still far from the conjectured competitive ratio of 4. In this paper, we prove that RSOP is indeed 4-competitive for a large class of instances in which the number λ of bidders receiving the item at the optimal uniform price, is at least 6. We also show that it is 4.68 competitive for the small class of remaining instances thus leaving a negligible gap between the lower and upper bound. Furthermore, we develop a robust version of RSOP -- one in which the seller's revenue is, with high probability, not much below its mean -- when the above parameter λ grows large. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.

REFERENCES

• 1: Maria-Florina Balcan , Avrim Blum, Mechanism Design via Machine Learning, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.605-614, October 23-25, 2005 [doi>10.1109/SFCS.2005.50]
• 2: S. Baliga and R. Vohra. Market research and market design. Advances in Theoretical Economics, 3(1):1059--1059, 2003.
• 3: U. Feige, A. Flaxman, J.D. Hartline, and R.D. Kleinberg. On the competitive ratio of the random sampling auction. In WINE, pages 878--886, 2005.
• 4: C.M. Fortuin, P.W. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics, 22:89--103, June 1971.
• 5: Andrew V. Goldberg , Jason D. Hartline, Competitive Auctions for Multiple Digital Goods, Proceedings of the 9th Annual European Symposium on Algorithms, p.416-427, August 28-31, 2001
• 6: 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
• 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: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 9: J.D. Hartline and T. Roughgarden. Optimal mechansim design and money burning. CoRR, abs/0804.2097, 2008.
• 10: W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13--30, 1963.
• 11: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 12: I. Segal. Optimal pricing mechanisms with unknown demand. American Economic Review, 93(3):509--529, June 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
auction, mechanism design, random sampling