Multidimensional Dynamic Pricing for Welfare Maximization
| Autor: | Jonathan Ullman, Aleksandrs Slivkins, Zhiwei Steven Wu, Aaron Roth |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Computer Science::Computer Science and Game Theory Economics and Econometrics Mathematical optimization Distribution (number theory) Computer science media_common.quotation_subject 0211 other engineering and technologies Hölder condition 0102 computer and information sciences 02 engineering and technology 01 natural sciences Machine Learning (cs.LG) Computer Science - Computer Science and Game Theory Computer Science - Data Structures and Algorithms 0502 economics and business 0202 electrical engineering electronic engineering information engineering Economics Computer Science (miscellaneous) Data Structures and Algorithms (cs.DS) 050207 economics Valuation (finance) media_common Marketing 021103 operations research Concave function Online learning 05 social sciences TheoryofComputation_GENERAL Maximization Computer Science::Multiagent Systems Computer Science - Learning Computational Mathematics 010201 computation theory & mathematics Bundle Convex optimization Dynamic pricing 020201 artificial intelligence & image processing Mathematical economics Welfare Computer Science and Game Theory (cs.GT) |
| Zdroj: | EC |
| ISSN: | 2167-8383 2167-8375 |
| Popis: | 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. To apply our general technique, we introduce a novel price randomization procedure that 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 supply of each good cannot be replenished. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|