{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:28:45Z","timestamp":1774369725253,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,29]],"date-time":"2020-02-29T00:00:00Z","timestamp":1582934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sloan Foundation Fellowship"},{"name":"NSF","award":["CNS-1253345"],"award-info":[{"award-number":["CNS-1253345"]}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>\n            We study the problem of a seller dynamically pricing\n            <jats:italic>d<\/jats:italic>\n            distinct types of indivisible goods, when faced with the online arrival of unit-demand buyers drawn independently from an unknown distribution. The goods are not in limited supply, but can only be produced at a limited rate and are costly to produce. The seller observes only the bundle of goods purchased at each day, but nothing else about the buyer\u2019s valuation function. Our main result is a dynamic pricing algorithm for optimizing welfare (including the seller\u2019s cost of production) that runs in time and a number of rounds that are polynomial in\n            <jats:italic>d<\/jats:italic>\n            and the approximation parameter. We are able to do this despite the fact that (i) the price-response function is not continuous, and even its fractional relaxation is a non-concave function of the prices, and (ii) the welfare is not observable to the seller.\n          <\/jats:p>\n          <jats:p>\n            We derive this result as an application of a general technique for optimizing welfare over\n            <jats:italic>divisible<\/jats:italic>\n            goods, which is of independent interest. When buyers have strongly concave, H\u00f6lder continuous valuation functions over\n            <jats:italic>d<\/jats:italic>\n            divisible goods, we give a general polynomial time dynamic pricing technique. We are able to apply this technique to the setting of unit-demand buyers despite the fact that in that setting the goods are not divisible, and the natural fractional relaxation of a unit-demand valuation is not strongly concave. To apply our general technique, we introduce a novel price randomization procedure that has the effect of implicitly inducing buyers to \u201cregularize\u201d their valuations with a strongly concave function. Finally, we also extend our results to a limited-supply setting in which the supply of each good cannot be replenished.\n          <\/jats:p>","DOI":"10.1145\/3381527","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T07:46:59Z","timestamp":1588578419000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Multidimensional Dynamic Pricing for Welfare Maximization"],"prefix":"10.1145","volume":"8","author":[{"given":"Aaron","family":"Roth","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwei Steven","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Minnesota, Minneapolis, MN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2525382"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/110850827"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Amin Kareem","year":"2015","unstructured":"Kareem Amin , Rachel Cummings , Lili Dworkin , Michael Kearns , and Aaron Roth . 2015 . Online learning and profit maximization from revealed preferences . In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915) . Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth. 2015. Online learning and profit maximization from revealed preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559152"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.30"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386802"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912)","author":"Balcan Maria-Florina","year":"2012","unstructured":"Maria-Florina Balcan , Florin Constantin , Satoru Iwata , and Lei Wang . 2012 . Learning valuation functions . In Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912) . Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. 2012. Learning valuation functions. In Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912)."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 10th International Conference on Web and Internet Economics (WINE\u201914)","author":"Balcan Maria-Florina","unstructured":"Maria-Florina Balcan , Amit Daniely , Ruta Mehta , Ruth Urner , and Vijay V. Vazirani . 2014. Learning economic parameters from revealed preferences . In Proceedings of the 10th International Conference on Web and Internet Economics (WINE\u201914) . Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V. Vazirani. 2014. Learning economic parameters from revealed preferences. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE\u201914)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134712"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0640"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2448473.2448483"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.68"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2015.03.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1057"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601986276"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 28th Conference on Learning Theory (COLT\u201915)","author":"Bubeck S\u00e9bastien","year":"2015","unstructured":"S\u00e9bastien Bubeck , Ofer Dekel , Tomer Koren , and Yuval Peres . 2015 . Bandit convex optimization: regret in one dimension . In Proceedings of the 28th Conference on Learning Theory (COLT\u201915) . 266--278. S\u00e9bastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. 2015. Bandit convex optimization: regret in one dimension. In Proceedings of the 28th Conference on Learning Theory (COLT\u201915). 266--278."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/100787799"},{"key":"e_1_2_1_19_1","first-page":"770","article-title":"Simultaneously learning and optimizing using controlled variance pricing. Manage","volume":"60","author":"den Boer Arnoud V.","year":"2014","unstructured":"Arnoud V. den Boer and Bert Zwart . 2014 . Simultaneously learning and optimizing using controlled variance pricing. Manage . Sci. 60 , 3 (2014), 770 -- 783 . Arnoud V. den Boer and Bert Zwart. 2014. Simultaneously learning and optimizing using controlled variance pricing. Manage. Sci. 60, 3 (2014), 770--783.","journal-title":"Sci."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.10"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201905)","author":"Flaxman Abraham","year":"2005","unstructured":"Abraham Flaxman , Adam Kalai , and H. Brendan McMahan . 2005 . Online convex optimization in the bandit setting: Gradient descent without a gradient . In Proceedings of the 16th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201905) . 385--394. Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. 2005. Online convex optimization in the bandit setting: Gradient descent without a gradient. In Proceedings of the 16th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201905). 385--394."},{"key":"e_1_2_1_22_1","volume-title":"Multi-Armed Bandit Allocation Indices","author":"Gittins J. C.","unstructured":"J. C. Gittins . 1989. Multi-Armed Bandit Allocation Indices . John Wiley 8 Sons. J. C. Gittins. 1989. Multi-Armed Bandit Allocation Indices. John Wiley 8 Sons."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 27th Advances in Neural Information Processing Systems (NIPS\u201914)","author":"Hazan Elad","unstructured":"Elad Hazan and Kfir Y. Levy . 2014. Bandit convex optimization: Towards tight bounds . In Proceedings of the 27th Advances in Neural Information Processing Systems (NIPS\u201914) . 784--792. Elad Hazan and Kfir Y. Levy. 2014. Bandit convex optimization: Towards tight bounds. In Proceedings of the 27th Advances in Neural Information Processing Systems (NIPS\u201914). 784--792."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897559"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1294"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238232"},{"key":"e_1_2_1_27_1","volume-title":"Green","author":"Mas-Colell Andreu","year":"1995","unstructured":"Andreu Mas-Colell , Michael D. Whinston , and Jerry R . Green . 1995 . Microeconomic Theory. Oxford University Press . Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897579"},{"key":"e_1_2_1_29_1","volume-title":"Lecture Notes in Microeconomic Theory: The Economic Agent","author":"Rubinstein Ariel","unstructured":"Ariel Rubinstein . 2012. Lecture Notes in Microeconomic Theory: The Economic Agent . Princeton University Press . Ariel Rubinstein. 2012. Lecture Notes in Microeconomic Theory: The Economic Agent. Princeton University Press."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2548836"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2124410"},{"key":"e_1_2_1_32_1","volume-title":"Samuelsonian Economics and the Twenty-first Century, Michael Szenberg, Lall Ramrattan, and Aron A","author":"Varian Hal R.","unstructured":"Hal R. Varian . 2006. Revealed preference . In Samuelsonian Economics and the Twenty-first Century, Michael Szenberg, Lall Ramrattan, and Aron A . Gottesman (Eds.). Oxford University Press , 99--115. Hal R. Varian. 2006. Revealed preference. In Samuelsonian Economics and the Twenty-first Century, Michael Szenberg, Lall Ramrattan, and Aron A. Gottesman (Eds.). Oxford University Press, 99--115."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2770678.2770686"},{"key":"e_1_2_1_34_1","volume-title":"\u201cFollow the leader","author":"Warmuth Manfred","year":"2016","unstructured":"Manfred Warmuth . 2009. A perturbation that makes \u201cFollow the leader \u201d equivalent to \u201cRandomized weighted majority.\u201d Retrieved on 19 March , 2016 from http:\/\/classes.soe.ucsc.edu\/cmps290c\/%0DSpring09\/lect\/10\/wmkalai-rewrite.pdf. Manfred Warmuth. 2009. A perturbation that makes \u201cFollow the leader\u201d equivalent to \u201cRandomized weighted majority.\u201d Retrieved on 19 March, 2016 from http:\/\/classes.soe.ucsc.edu\/cmps290c\/%0DSpring09\/lect\/10\/wmkalai-rewrite.pdf."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_9"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML\u201903)","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich . 2003 . Online convex programming and generalized infinitesimal gradient ascent . In Proceedings of the 20th International Conference on Machine Learning (ICML\u201903) . Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML\u201903)."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381527","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,29]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3381527"],"URL":"https:\/\/doi.org\/10.1145\/3381527","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,29]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}