Abstract
We study prior-free revenue maximization for a seller with unlimited supply of n item types facing m myopic buyers present for \(k\!<\!\log n\) days. We show that a certain randomized schedule of posted prices has an approximation factor of \(O(\frac{\log m + \log n}{k})\). This algorithm relies on buyer valuations having hereditary maximizers, a novel natural property satisfied for example by gross substitutes valuations. We obtain a matching lower bound with multi-unit valuations. In light of existing results [2], k days can thus improve the approximation by a Θ(k) factor. We also provide a posted price schedule with the same factor for positive affine allocative externalities, despite an increase in the optimal revenue.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akhlaghpour, H., Ghodsi, M., Haghpanah, N., Mahini, H., Mirrokni, V., Nikzad, A.: Optimal iterative pricing over social networks. In: Fifth Workshop on Ad Auctions (2009)
Balcan, M.-F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: Proc. ACM Conf. on Electronic Commerce, pp. 50–59 (2008)
Bansal, N., Chen, N., Cherniavsky, N., Rudra, A., Schieber, B., Sviridenko, M.: Dynamic pricing for impatient bidders. ACM Trans. Algorithms 6(2), 1–21 (2010)
Bertelsen, A.: Substitutes valuations and \(M^{\natural}\)-concavity. Master’s thesis, Hebrew University of Jerusalem (2004)
Bikhchandani, S., Ostroy, J.M.: Ascending price Vickrey auctions. Games and Economic Behavior 55(2), 215–241 (2006)
David, H., Nagaraja, H.: Order Statistics. Wiley, Chichester (2003)
Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. Journal of Economic Theory 87(1), 95–124 (1999)
Hartline, J., Mirrokni, V., Sundararajan, M.: Optimal marketing over social networks. In: Conference on the World Wide Web, WWW 2008 (2008)
Kleinberg, J.: Cascading behavior in networks: algorithmic and economic issues. Cambridge University Press, Cambridge (2007)
Lien, Y., Yan, J.: On the gross substitutes condition. Working Paper (July 2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balcan, MF., Constantin, F. (2010). Sequential Item Pricing for Unlimited Supply. In: Saberi, A. (eds) Internet and Network Economics. WINE 2010. Lecture Notes in Computer Science, vol 6484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17572-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-17572-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17571-8
Online ISBN: 978-3-642-17572-5
eBook Packages: Computer ScienceComputer Science (R0)