Multidimensional Dynamic Pricing for Welfare Maximization
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 29, 2020
- Source ID
- 10.1145/3381527
Entities
People
- Aaron Roth
- Aleksandrs Slivkins
- Jonathan Ullman
- Zhiwei Steven Wu
Organizations
- Defense Advanced Research Projects Agency
- Microsoft
- National Science Foundation
- Northeastern University
- University of Minnesota
- University of Pennsylvania