{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:28:38Z","timestamp":1774369718864,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,27]],"date-time":"2015-03-27T00:00:00Z","timestamp":1427414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-0643934, CCF-0729102"],"award-info":[{"award-number":["CCF-0643934, CCF-0729102"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2015,3,27]]},"abstract":"<jats:p>We consider the problem of designing revenue-maximizing online posted-price mechanisms when the seller has limited supply. A seller has<jats:italic>k<\/jats:italic>identical items for sale and is facing<jats:italic>n<\/jats:italic>potential buyers (\u201cagents\u201d) that are arriving sequentially. Each agent is interested in buying one item. Each agent\u2019s 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.<\/jats:p><jats:p>We focus on mechanisms that do not use any information about the distribution; such mechanisms are called<jats:italic>detail-free<\/jats:italic>(or<jats:italic>prior-independent<\/jats:italic>). 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 (\u201coffline benchmark\u201d).<\/jats:p><jats:p>We present a detail-free online posted-price mechanism whose revenue is at most O((<jats:italic>k<\/jats:italic>log<jats:italic>n<\/jats:italic>)2\/3) less than the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without<jats:italic>any<\/jats:italic>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<jats:italic>O<\/jats:italic>(\u221a<jats:italic>k<\/jats:italic>log<jats:italic>n<\/jats:italic>), with a distribution-dependent constant, if the ratio<jats:italic>k<\/jats:italic>\/<jats:italic>n<\/jats:italic>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.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1145\/2559152","type":"journal-article","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T14:59:12Z","timestamp":1427900352000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Dynamic Pricing with Limited Supply"],"prefix":"10.1145","volume":"3","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Shaddin","family":"Dughmi","sequence":"additional","affiliation":[{"name":"University of Southern California"}]},{"given":"Robert","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2015,3,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 26th Conference on Learning Theory.","author":"Abraham Ittai","year":"2013","unstructured":"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. 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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012992237273"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953023"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768841.1768884"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Symposium on Innovations in CS.","author":"Babaioff Moshe","year":"2011","unstructured":"Moshe Babaioff , Liad Blumrosen , Shaddin Dughmi , and Yaron Singer . 2011 . Posting prices with unknown distributions . In Proceedings of the Symposium on Innovations in CS. Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, and Yaron Singer. 2011. Posting prices with unknown distributions. In Proceedings of the Symposium on Innovations in CS."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. 434--443","author":"Babaioff Moshe","year":"2007","unstructured":"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 . 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807349"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566386"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.30"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Bar-Yossef Z.","unstructured":"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. 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."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0640"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0867"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms.","author":"Blum Avrim","year":"2005","unstructured":"Avrim Blum and Jason Hartline . 2005 . Near-optimal online auctions . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. Avrim Blum and Jason Hartline. 2005. Near-optimal online auctions. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. 202--204","author":"Blum Avrim","year":"2003","unstructured":"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 . 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."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.059"},{"key":"e_1_2_1_19_1","first-page":"1587","article-title":"Online Optimization in X-Armed Bandits","volume":"12","author":"Bubeck S\u00e9bastien","year":"2011","unstructured":"S\u00e9bastien Bubeck , R\u00e9mi Munos , Gilles Stoltz , and Csaba Szepesvari . 2011 b. Online Optimization in X-Armed Bandits . J. Machine Learn. Res. 12 , 1587 -- 1627 . S\u00e9bastien Bubeck, R\u00e9mi Munos, Gilles Stoltz, and Csaba Szepesvari. 2011b. Online Optimization in X-Armed Bandits. J. Machine Learn. Res. 12, 1587--1627.","journal-title":"J. Machine Learn. Res."},{"key":"e_1_2_1_20_1","volume-title":"Prediction, Learning, and Games","author":"Cesa-Bianchi Nicol\u00f2","unstructured":"Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi . 2006. Prediction, Learning, and Games . Cambridge University Press . Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction, Learning, and Games. Cambridge University Press."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Workshop on Internet & Network Economics. 158--169","author":"Chakraborty Tanmoy","unstructured":"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 . 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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566381"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566388"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807364"},{"key":"e_1_2_1_26_1","unstructured":"Dynkin E. B. 1963. Eugene B. Dynkin. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4. Dynkin E. B. 1963. Eugene B. Dynkin. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4."},{"key":"e_1_2_1_27_1","volume-title":"Multi-Armed Bandit Allocation Indices","author":"Gittins John","unstructured":"John Gittins , Kevin Glazebrook , and Richard Weber . 2011. Multi-Armed Bandit Allocation Indices . John Wiley & Sons . John Gittins, Kevin Glazebrook, and Richard Weber. 2011. Multi-Armed Bandit Allocation Indices. John Wiley & Sons."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","article-title":"Bandit processes and dynamic allocation indices (with discussion)","volume":"41","author":"Gittins J. C.","year":"1979","unstructured":"J. C. Gittins . 1979 . Bandit processes and dynamic allocation indices (with discussion) . J. Roy. Statist. Soc. Ser. B 41 , 148 -- 177 . J. C. Gittins. 1979. Bandit processes and dynamic allocation indices (with discussion). J. Roy. Statist. Soc. Ser. B 41, 148--177.","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496773"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988784"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374390"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 18th Advances in Neural Information Processing Systems.","author":"Kleinberg Robert","year":"2004","unstructured":"Robert Kleinberg . 2004 . Nearly tight bounds for the continuum-armed bandit problem . In Proceedings of the 18th Advances in Neural Information Processing Systems. Robert Kleinberg. 2004. Nearly tight bounds for the continuum-armed bandit problem. In Proceedings of the 18th Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE Symp. on Foundations of Computer Science.","author":"Robert","unstructured":"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. 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."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352897"},{"key":"e_1_2_1_37_1","volume-title":"Probabilistic Methods for Discrete Mathematics","author":"McDiarmid Colin","unstructured":"Colin McDiarmid . 1998. Concentration . In Probabilistic Methods for Discrete Mathematics , M. Habib. C. McDiarmid. J. Ramirez and B. Reed (Eds.), Springer , 195--248. Colin McDiarmid. 1998. Concentration. In Probabilistic Methods for Discrete Mathematics, M. Habib. C. McDiarmid. J. Ramirez and B. Reed (Eds.), Springer, 195--248."},{"key":"e_1_2_1_38_1","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367522"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 24th Conference on Learning Theory.","author":"Slivkins Aleksandrs","year":"2011","unstructured":"Aleksandrs Slivkins . 2011 . Contextual bandits with similarity information . In Proceedings of the 24th Conference on Learning Theory. Aleksandrs Slivkins. 2011. Contextual bandits with similarity information. In Proceedings of the 24th Conference on Learning Theory."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 21st Conference on Learning Theory. 343--354","author":"Slivkins Aleksandrs","year":"2008","unstructured":"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 . 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."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912571"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133092"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559152","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:12Z","timestamp":1750230072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,27]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,27]]}},"alternative-id":["10.1145\/2559152"],"URL":"https:\/\/doi.org\/10.1145\/2559152","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,27]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}