Dynamic Pricing with Limited Supply

Abstract

We consider the problem of designing revenue-maximizing online posted-price mechanisms when the seller has limited supply. A seller has k identical items for sale and is facing n potential buyers (“agents”) that are arriving sequentially. Each agent is interested in buying one item. Each agent’s value for an item is an independent sample from some fixed (but unknown) distribution with support [0,1]. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue.

We focus on mechanisms that do not use any information about the distribution; such mechanisms are called detail-free (or prior-independent). They are desirable because knowing the distribution is unrealistic in many practical scenarios. We study how the revenue of such mechanisms compares to the revenue of the optimal offline mechanism that knows the distribution (“offline benchmark”).

We present a detail-free online posted-price mechanism whose revenue is at most O((k log n)2/3) less than the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without any assumptions if the benchmark is relaxed to fixed-price mechanisms. Further, we prove a matching lower bound. The performance guarantee for the same mechanism can be improved to O(√k log n), with a distribution-dependent constant, if the ratio k/n is sufficiently small. We show that, in the worst case over all demand distributions, this is essentially the best rate that can be obtained with a distribution-specific constant.

On a technical level, we exploit the connection to multiarmed bandits (MAB). While dynamic pricing with unlimited supply can easily be seen as an MAB problem, the intuition behind MAB approaches breaks when applied to the setting with limited supply. Our high-level conceptual contribution is that even the limited supply setting can be fruitfully treated as a bandit problem.

References

1. Ittai Abraham, Omar Alonso, Vasilis Kandylas, and Aleksandrs Slivkins. 2013. Adaptive crowd-sourcing algorithms for the bandit survey problem. In Proceedings of the 26th Conference on Learning Theory.
2. Rajeev Agrawal. 1995. The continuum-armed bandit problem. SIAM J. Control Optim. 33, 6, 1926--1951.
3. J. Y. Audibert and S. Bubeck. 2010. Regret bounds and minimax policies under partial monitoring. J. Machine Learn. Res. 11, 2785--2836.
4. Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. 2002a. Finite-time analysis of the multiarmed bandit problem. Machine Learn. 47, 2--3, 235--256.
5. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. 2002b. The nonstochastic multi-armed bandit problem. SIAM J. Comput. 32, 1, 48--77.
6. Peter Auer, Ronald Ortner, and Csaba Szepesvári. 2007. Improved Rates for the Stochastic Continuum-Armed Bandit Problem. In Proceedings of the 20th Conference on Learning Theory. 454--468.
7. Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. 2011. Posting prices with unknown distributions. In Proceedings of the Symposium on Innovations in CS.
8. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. 434--443.
9. Moshe Babaioff, Robert Kleinberg, and Aleksandrs Slivkins. 2010. Truthful mechanisms with implicit payment computation. In Proceedings of the 11th ACM Conference on Electronic Commerce. 43--52.
10. Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. 2009. Characterizing truthful multi-armed bandit mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce. 79--88.
11. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. 2013. Bandits with knapsacks. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science.
12. Z. Bar-Yossef, K. Hildrum, and F. Wu. 2002. Incentive-compatible online auctions for digital goods. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.
13. Omar Besbes and Assaf Zeevi. 2009. Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms. Oper. Res. 57, 6, 1407--1420.
14. Omar Besbes and Assaf Zeevi. 2011. On the minimax complexity of pricing in a changing environment. Oper. Res. 59, 1, 66--79.
15. Avrim Blum and Jason Hartline. 2005. Near-optimal online auctions. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms.
16. Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. 2003. Online learning in online auctions. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. 202--204.
17. Sébastien Bubeck and Nicolo Cesa-Bianchi. 2012. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends in Machine Learn. 5, 1, 1--122.
18. Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. 2011a. Pure exploration in multi-armed bandit problems. Theor. Comput. Sci. 412, 19, 1832--1852.
19. Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvari. 2011b. Online Optimization in X-Armed Bandits. J. Machine Learn. Res. 12, 1587--1627.
20. Nicolò Cesa-Bianchi and Gábor Lugosi. 2006. Prediction, Learning, and Games. Cambridge University Press.
21. Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan. 2010. Approximation schemes for sequential posted pricing in multi-unit auctions. In Proceedings of the Workshop on Internet & Network Economics. 158--169.
22. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the ACM Symposium on Theory of Computing. 311--320.
23. Nikhil Devanur and Jason Hartline. 2009. Limited and online supply and the Bayesian foundations of prior-free mechanism design. In Proceedings of the ACM Conference on Electronic Commerce.
24. Nikhil Devanur and Sham M. Kakade. 2009. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM Conference on Electronic Commerce. 99--106.
25. Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. 2010. Revenue maximization with a single sample. In Proceedings of the ACM Conference on Electronic Commerce. 129--138.
26. Dynkin, E. B. 1963. Eugene B. Dynkin. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4.
27. John Gittins, Kevin Glazebrook, and Richard Weber. 2011. Multi-Armed Bandit Allocation Indices. John Wiley & Sons.
28. J. C. Gittins. 1979. Bandit processes and dynamic allocation indices (with discussion). J. Roy. Statist. Soc. Ser. B 41, 148--177.
29. Ashish Goel, Sanjeev Khanna, and Brad Null. 2009. The ratio index for budgeted learning, with applications. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms. 18--27.
30. Mohammad T. Hajiaghayi, Robert Kleinberg, and David C. Parkes. 2004. Adaptive limited-supply online auctions. In Proceedings of the ACM Conference on Electronic Commerce. 71--80.
31. J. D. Hartline and T. Roughgarden. 2008. Optimal mechanism design and money burning. In Proceedings of the ACM Symposium on Theory of Computing.
32. Robert Kleinberg. 2004. Nearly tight bounds for the continuum-armed bandit problem. In Proceedings of the 18th Advances in Neural Information Processing Systems.
33. Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. 2008. Multi-armed bandits in metric spaces. In Proceedings of the 40th ACM Symposium on Theory of Computing. 681--690.
34. Robert D. Kleinberg and Frank T. Leighton. 2003. The value of knowing a demand curve: bounds on regret for online posted-price auctions. In Proceedings of the IEEE Symp. on Foundations of Computer Science.
35. Tze Leung Lai and Herbert Robbins. 1985. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6, 4--22.
36. Ron Lavi and Noam Nisan. 2000. Competitive analysis of incentive compatible on-line auctions. In Proceedings of the ACM Conference on Electronic Commerce. 233--241.
37. Colin McDiarmid. 1998. Concentration. In Probabilistic Methods for Discrete Mathematics, M. Habib. C. McDiarmid. J. Ramirez and B. Reed (Eds.), Springer, 195--248.
38. Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
39. R. B. Myerson. 1981. Optimal auction design. Math. Operations Res. 6, 1, 58--73.
40. Hamid Nazerzadeh, Amin Saberi, and Rakesh Vohra. 2008. Dynamic cost-per-action mechanisms and applications to online advertising. In Proceedings of the 17th International World Wide Web Conference.
41. Aleksandrs Slivkins. 2011. Contextual bandits with similarity information. In Proceedings of the 24th Conference on Learning Theory.
42. Aleksandrs Slivkins and Eli Upfal. 2008. Adapting to a changing environment: The Brownian restless bandits. In Proceedings of the 21st Conference on Learning Theory. 343--354.
43. Robert B. Wilson. 1989. Efficient and competitive rationing. Econometrica 57, 1--40.
44. Qiqi Yan. 2011. Mechanism design via correlation gap. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms.

Index Terms

• Applied computing

  • Electronic commerce

  • Law, social and behavioral sciences

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Models of computation

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory