Abstract
We consider the online auction problem in which an auctioneer is selling an identical item each time when a new bidder arrives. It is known that results from online prediction can be applied and achieve a constant competitive ratio with respect to the best fixed price profit. These algorithms work on a predetermined set of price levels. We take into account the property that the rewards for the price levels are not independent and cast the problem as a more refined model of online prediction. We then use Vovk’s Aggregating Strategy to derive a new algorithm. We give a general form of competitive ratio in terms of the price levels. The optimality of the Aggregating Strategy gives an evidence that our algorithm performs at least as well as the previously proposed ones.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, A., Kumar, V., Rudra, A., Wu, F.: Online Learning in Online Auctions. In: Proc. 14th SODA (2003)
Blum, A., Hartline, J.D.: Near-Optimal Online Auctions. In: Proc. 16th SODA, pp. 1156–1163 (2005)
Bar-Yossef, Z., Hildrum, K., Wu, F.: Incentive-Compatible Online Auctions for Digital Goods. In: Proc. SODA 2002, pp. 964–970 (2002)
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D.P., Schapire, R.E., Warmuth, M.K.: How to use expert advice. J. ACM 44(3), 427–485 (1997)
Freund, Y., Schapire, R.E.: A decision-theoretic generalization of on-line learning and an application to boosting. JCSS 55(1), 119–139 (1997)
Hutter, M., Poland, J.: Prediction with expert advice by following the perturbed leader for general weights. In: Ben-David, S., Case, J., Maruoka, A. (eds.) ALT 2004. LNCS (LNAI), vol. 3244, pp. 279–293. Springer, Heidelberg (2004)
Harada, S., Takimoto, E., Maruoka, A.: Online Allocation with Risk Information. In: Jain, S., Simon, H.U., Tomita, E. (eds.) ALT 2005. LNCS (LNAI), vol. 3734, pp. 343–355. Springer, Heidelberg (2005)
Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 26–40. Springer, Heidelberg (2003)
Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Inform. Comput. 108(2), 212–261 (1994)
Vovk, V.: A game of prediction with expert advice. JCSS 56(2), 153–173 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harada, S., Takimoto, E., Maruoka, A. (2006). Aggregating Strategy for Online Auctions. In: Chen, D.Z., Lee, D.T. (eds) Computing and Combinatorics. COCOON 2006. Lecture Notes in Computer Science, vol 4112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11809678_6
Download citation
DOI: https://doi.org/10.1007/11809678_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36925-7
Online ISBN: 978-3-540-36926-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
