Dynamic Pricing for a Large Inventory of Substitutable Goods

We consider a dynamic pricing problem for a large inventory of substitutable products over a finite planning horizon. Customers arrive sequentially and in each period a single customer randomly chooses at most one unit of a product in-stock. Purchase probabilities depend on product prices and are described by a discrete choice model. Every available product must have a finite price from a set of feasible prices. The goal of the seller is to find a pricing policy that maximizes expected total revenue over the planning horizon. We assume that the seller knows the choice model and the total number of customers at the start of the planning horizon. Our setting generalizes several classic settings in pricing and revenue management with known demand. To the best of our knowledge, prior to our work, efficient algorithms for solving this problem optimally (or approximately) were unknown even in the fundamental special case of Multinomial Logit (MNL) customer choice. To capture the first order effect of demand substitution, we study this problem for large starting inventory. We give an asymptotically optimal pricing policy for MNL choice and show that, in case of MNL, the effect of demand substitution is a monotonically non-decreasing price over time for every product. More generally, we give an approximation framework for all monotone and weakly rational choice models. Our framework uses an $\alpha$ approximate algorithm for the single period (static) pricing problem, to generate a $(1-1/e)\, \alpha$ approximation for the multi-period (dynamic) pricing problem. To analyze the performance of our algorithms, we study the structure of choice polytopes. At a high level, the choice polytope P of a given choice model captures the choice probabilities of all possible (random) subsets of products. We find necessary and sufficient conditions such that, if a choice model satisfies these conditions then every point in P can be represented as a convex combination of vertices that correspond to nested sets. We believe this may be of broader interest in multi-period settings with demand substitution