Adaptive limited-supply online auctions

ABSTRACT

We study a limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically. We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive auction that is nevertheless value- andtime-strategy proof. For the k=1 problem we have a strategyproof variant on the classic secretary problem. We present a 4-competitive (e-competitive) strategyproof online algorithm with respect to offline Vickrey for revenue (efficiency). We also show (in a model that slightly generalizes the assumption of independent valuations) that no mechanism can be better than 3/2-competitive (2-competitive) for revenue (efficiency). Our general approach considers a learning phase followed by an accepting phase, and is careful to handle incentive issues for agents that span the two phases. We extend to the k›1 case, by deriving strategyproof mechanisms which are constant-competitive for revenue and efficiency. Finally, we present some strategyproof competitive algorithms for the case in which adversary uses a distribution known to the mechanism.

REFERENCES

• 1: Miklos Ajtai , Nimrod Megiddo , Orli Waarts, Improved Algorithms and Analysis for Secretary Problems and Generalizations, SIAM Journal on Discrete Mathematics, v.14 n.1, p.1-27, 2001 [doi>10.1137/S0895480195290017]
• 2: Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780616]
• 3: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: E. B. DYNKIN, The optimum choice of the instant for stopping a markov process, Sov. Math. Dokl., 4 (1963), pp. 627--629.
• 5: Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779978]
• 6: J. GALLIEN, Dynamic mechanism design for online commerce, tech. rep., Sloan School of Management, MIT, 2002.
• 7: J. P. GILBERT AND F. MOSTELLER, Recognizing the maximum of a sequence, J. Amer. Statist. Assoc., 61 (1966), pp. 35--73.
• 8: K. S. GLASSER, R. HOLZSAGER, AND A. BARRON, The d choice secretary problem, Comm. Statist. C--Sequential Anal., 2 (1983), pp. 177--199.
• 9: 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
• 10: Robert Kleinberg , Tom Leighton, The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.594, October 11-14, 2003
• 11: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 12: D. C. PARKES AND S. SINGH, An MDP-based approach to online mechanism design. In Proc. 17th Annual Conference on Neural Information Processing Systems, 2003.
• 13: R. J. VANDERBEI, The optimal choice of a subset of a population, Math. Oper. Res., 5 (1980), pp. 481--486.
• 14: W. VICKREY, Counterspeculations, auctions, and competitive sealed tenders, Journal of Finance, 16 (1961), pp. 8--37.
• 15: J. G. WILSON, Optimal choice and assignment of the best m of n randomly arriving items, Stochastic Process. Appl., 39 (1991), pp. 325--343.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics

Keywords:
auctions, online, pricing