skip to main content
10.1145/3033274.3085106acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article
Public Access

Multidimensional Dynamic Pricing for Welfare Maximization

Published: 20 June 2017 Publication History

Abstract

We study the problem of a seller dynamically pricing d 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's valuation function. Our main result is a dynamic pricing algorithm for optimizing welfare (including the seller's cost of production) that runs in time and a number of rounds that are polynomial in d 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.
We derive this result as an application of a general technique for optimizing welfare over divisible goods, which is of independent interest. When buyers have strongly concave, Hölder continuous valuation functions over d 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. In order to apply our general technique, we introduce a novel price randomization procedure which has the effect of implicitly inducing buyers to "regularize'' their valuations with a strongly concave function. Finally, we also extend our results to a limited-supply setting in which the number of copies of each good cannot be replenished.

Supplementary Material

MP4 File (07a_04roth.mp4)

References

[1]
Sydney Afriat. 1967. The Construction of Utility Functions from Expenditure Data. International Economic Review 8, 1 (1967), 67--77.
[2]
Alekh Agarwal, Dean P. Foster, Daniel J. Hsu, Sham M. Kakade, and Alexander Rakhlin. 2013. Stochastic Convex Optimization with Bandit Feedback. SIAM Journal on Optimization 23, 1 (2013), 213--240.
[3]
Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth. 2015. Online Learning and Profit Maximization from Revealed Preferences. In Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15).
[4]
Moshe Babaio., Shaddin Dughmi, Robert D. Kleinberg, and Aleksandrs Slivkins. 2015. Dynamic Pricing with Limited Supply. ACM Trans. on Economics and Computation 3, 1 (2015), 4. Special issue for 13th ACM EC, 2012.
[5]
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. 2013. Bandits with Knapsacks. In 54th IEEE Symp. on Foundations of Computer Science (FOCS).
[6]
Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. 2008. Item pricing for revenue maximization. In 9th ACM Conf. on Electronic Commerce (EC). 50--59.
[7]
Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. 2012. Learning Valuation Functions. In 23rd.
[8]
Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V Vazirani. 2014. Learning Economic Parameters from Revealed Preferences. In Web and Internet Economics. Springer, 338--353.
[9]
Eyal Beigman and Rakesh Vohra. 2006. Learning from revealed preference. In Proceedings of the 7th ACM Conference on Electronic Commerce. ACM, 36--42.
[10]
Omar Besbes and Assaf Zeevi. 2009. Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms. Operations Research 57 (2009), 1407--1420. Issue 6.
[11]
Omar Besbes and Assaf J. Zeevi. 2012. Blind Network Revenue Management. Operations Research 60, 6 (2012), 1537--1550.
[12]
Avrim Blum, Anupam Gupta, Yishay Mansour, and Ankit Sharma. 2011. Welfare and Profit Maximization with Production Costs. In 52nd IEEE Symp. on Foundations of Computer Science (FOCS). 77--86.
[13]
Arnoud V. Den Boer. 2015. Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys in Operations Research and Management Science 20, 1 (June 2015).
[14]
Josef Broder and Paat Rusmevichientong. 2012. Dynamic Pricing Under a General Parametric Choice Model. Operations Research 60, 4 (2012), 965--980.
[15]
Sébastien Bubeck. 2015. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning 8, 3--4 (2015), 231--357.
[16]
Sébastien Bubeck and Nicolo Cesa-Bianchi. 2012. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Foundations and Trends in Machine Learning 5, 1 (2012).
[17]
Sébastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. 2015. Bandit Convex Optimization: n(nsqrtfTgn) Regret in One Dimension. In 28th Conf. on Learning Theory (COLT). 266--278.
[18]
Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna. 2013. Dynamic and Nonuniform Pricing Strategies for Revenue Maximization. SIAM J. on Computing (SICOMP) 42, 6 (2013), 2424--2451. Preliminary version in IEEE FOCS 2009.
[19]
Arnoud V. den Boer and Bert Zwart. 2014. Simultaneously Learning and Optimizing Using Controlled Variance Pricing. Management Science 60, 3 (2014), 770--783.
[20]
Nikhil R. Devanur, Balasubramanian Sivan, and Yossi Azar. 2012. Asymptotically optimal algorithm for stochastic adwords. In ACM Conference on Electronic Commerce, EC '12, Valencia, Spain, June 4--8, 2012. 388--404.
[21]
Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial Auctions via Posted Prices. In 26th ACM-SIAM Symp. on Discrete Algorithms (SODA). 123--135.
[22]
Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. 2005. Online Convex Optimization in the Bandit Seeing: Gradient Descent without a Gradient. In 16th ACM-SIAM Symp. on Discrete Algorithms (SODA). 385--394.
[23]
J. C. Gittins. 1989. Multi-Armed Bandit Allocation Indices. John Wiley & Sons.
[24]
Elad Hazan and Kfir Y. Levy. 2014. Bandit Convex Optimization: Towards Tight Bounds. In 27th Advances in Neural Information Processing Systems (NIPS). 784--792.
[25]
Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra. 2016. Do prices coordinate markets?. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 440--453.
[26]
N. Bora Keskin and Assaf J. Zeevi. 2014. Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies. Operations Research 62, 5 (2014), 1142--1167.
[27]
Robert Kleinberg and Tom Leighton. 2003. .e Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. In 44th IEEE Symp. on Foundations of Computer Science (FOCS). 594--605.
[28]
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press.
[29]
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. 2016. Watch and learn: optimizing from revealed preferences feedback. In Proc. of the 48th Annual ACM SIGACT Symp. on Theory of Computing, STOC 2016.
[30]
Ariel Rubinstein. 2012. Lecture notes in microeconomic theory: the economic agent. Princeton University Press.
[31]
Paul A. Samuelson. 1938. A Note on the Pure Theory of Consumers' Behavior. Economica 5, 17 (1938), 61--71.
[32]
Hal R. Varian. 2006. Revealed preference. In Samuelsonian economics and the twenty-first century, Michael Szenberg, Lall Ramra.an, and Aron A. Go.esman (Eds.). Oxford University Press, 99--115.
[33]
Zizhuo Wang, Shiming Deng, and Yinyu Ye. 2014. Close the Gaps: A Learning-While-Doing Algorithm for Single-Product Revenue Management Problems. Operations Research 62, 2 (2014), 318--331.
[34]
Manfred Warmuth. 2009. A perturbation that makes "Follow the leader" equivalent to "Randomized weighted majority". (2009).
[35]
Morteza Zadimoghaddam and Aaron Roth. 2012. Efficiently Learning from Revealed Preference. In Internet and Network Economics - 8th International Workshop, WINE 2012 (Lecture Notes in Computer Science), Vol. 7695. Springer, 114--127.
[36]
Martin Zinkevich. 2003. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21--24, 2003, Washington, DC, USA. 928--936.

Cited By

View all
  • (2020)Learning the valuations of a k-demand agentProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525964(11066-11075)Online publication date: 13-Jul-2020
  • (2020)Feature-Based Dynamic PricingManagement Science10.1287/mnsc.2019.348566:11(4921-4943)Online publication date: 1-Nov-2020
  • (2019)Adversarial Bandits with Knapsacks2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00022(202-219)Online publication date: Nov-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation
June 2017
740 pages
ISBN:9781450345279
DOI:10.1145/3033274
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2017

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dynamic pricing
  2. learning
  3. revealed preferences
  4. welfare maximization

Qualifiers

  • Research-article

Funding Sources

Conference

EC '17
Sponsor:
EC '17: ACM Conference on Economics and Computation
June 26 - 30, 2017
Massachusetts, Cambridge, USA

Acceptance Rates

EC '17 Paper Acceptance Rate 75 of 257 submissions, 29%;
Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)125
  • Downloads (Last 6 weeks)54
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Learning the valuations of a k-demand agentProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525964(11066-11075)Online publication date: 13-Jul-2020
  • (2020)Feature-Based Dynamic PricingManagement Science10.1287/mnsc.2019.348566:11(4921-4943)Online publication date: 1-Nov-2020
  • (2019)Adversarial Bandits with Knapsacks2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00022(202-219)Online publication date: Nov-2019
  • (2018)Strategic Classification from Revealed PreferencesProceedings of the 2018 ACM Conference on Economics and Computation10.1145/3219166.3219193(55-70)Online publication date: 11-Jun-2018
  • (2018)Social Welfare and Profit Maximization from Revealed PreferencesWeb and Internet Economics10.1007/978-3-030-04612-5_18(264-281)Online publication date: 21-Nov-2018

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media