×

zbMATH — the first resource for mathematics

Online learning in online auctions. (English) Zbl 1091.91028
Summary: We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online learning can be usefully applied in this context, and we derive a new auction for digital goods that achieves a constant competitive ratio with respect to the optimal (offline) fixed price revenue. This substantially improves upon the best previously known competitive ratio for this problem of \(\text{O}(\exp(\sqrt{\log \log h}))\). We also apply our techniques to the related problem of designing online posted price mechanisms, in which the seller declares a price for each of a series of buyers, and each buyer either accepts or rejects the good at that price. Despite the relative lack of information in this setting, we show that online learning techniques can be used to obtain results for online posted price mechanisms which are similar to those obtained for online auctions.

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
68T05 Learning and adaptive systems in artificial intelligence
Software:
AdaBoost.MH
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Auer, N. C-Bianchi, Y. Freund, R.E. Schapire, Gambling in a rigged casino: the adversarial multi-armed bandit problem, in: Proc. 36th Annu. IEEE Symp. Foundations of Computer Science (FOCS), 1995, pp. 322-331. · Zbl 0938.68920
[2] Auer, P.; C-Bianchi, N.; Freund, Y.; Schapire, R.E., The nonstochastic multiarmed bandit problem, SIAM J. comput., 32, 1, 48-77, (2002) · Zbl 1029.68087
[3] A. Bagchi, A. Chaudhary, R. Garg, M.T. Goodrich, V. Kumar, Seller-focused algorithms for online auctioning, in: Proc. 7th Internat. Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, Vol. 2125, Springer, Berlin, 2001. · Zbl 0997.68629
[4] Z. Bar-Yossef, K. Hildrum, F. Wu, Incentive-compatible online auctions for digital goods, in: Proc. 13th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2002, pp. 964-970. · Zbl 1092.91522
[5] A. Blum, V. Kumar, A. Rudra, F. Wu, Online learning in online auctions, in: Proc. 14th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2003, pp. 202-204. · Zbl 1094.68620
[6] Cesa-Bianchi, N.; Freund, Y.; Helmbold, D.P.; Haussler, D.; Schapire, R.E.; Warmuth, M.K., How to use expert advice, J. assoc. comput. Mach., 44, 3, 427-485, (1997) · Zbl 0890.68066
[7] A. Fiat, A. Goldberg, J. Hartline, A. Karlin, Competitive generalized auctions, in: Proc. 34th ACM Symp. Theory of Computing (STOC), 2002, pp. 72-81. · Zbl 1192.91103
[8] Y. Freund, R.E. Schapire, Game theory, on-line prediction and boosting, in: Proc. 9th Annu. Conf. Computational Learning Theory (COLT), 1996, pp. 325-332.
[9] Freund, Y.; Schapire, R.E., A decision-theoretic generalization of on-line learning and an application to boosting, J. comput. system sci., 55, 1, 119-139, (1997) · Zbl 0880.68103
[10] A. Goldberg, J. Hartline, A. Wright, Competitive auctions and digital goods, in: Proc. 12th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2001, pp. 735-744. · Zbl 0988.91024
[11] J. Hartline, Dynamic posted price mechanisms, Personal communication, 2002.
[12] R. Lavi, N. Nisan, Competitive analysis of incentive compatible on-line auctions, in: Proc. 2nd ACM Conf. Electronic Commerce (EC-00), 2000, pp. 233-241. · Zbl 1098.91044
[13] Littlestone, N.; Warmuth, M.K., The weighted majority algorithm, Inform. and comput., 108, 212-261, (1994) · Zbl 0804.68121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.