Multidimensional Dynamic Pricing for Welfare Maximization

Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, Steven Wu

[arXiv]

We study the problem of a seller dynamically pricing d distinct types of goods, when faced with the online arrival of buyers drawn independently from an unknown distribution. The seller observes only the bundle of goods purchased at each day, but nothing else about the buyer's valuation function. When buyers have strongly concave, Holder continuous valuation functions, we give a pricing scheme that finds a pricing that optimizes welfare (including the seller's cost of production) in time and number of rounds that are polynomial in d and the accuracy parameter. We are able to do this despite the fact that (i) welfare is a non-concave function of the prices, and (ii) the welfare is not observable to the seller. We also extend our results to a limited-supply setting.