On State-Independent Policies in Network Revenue Management

Problem definition: We study the following seminal stochastic multiproduct dynamic-pricing problem, analyzed originally in Gallego and Van Ryzin (1997) – GVR, for short. A firm has a finite inventory of a set of resources needed to produce products that can be sold over a finite horizon. The demand for each product arrives according to a Poisson process for which the rate, at any time, is a function of the current prices of all the products. The firm's goal is to obtain a pricing policy that maximizes its expected revenue over the sales horizon. Results and Managerial implications: GVR's analysis of the above problem implicitly assumes that the demand-price relationship is separable among the products (that is, the demand rate of a product depends only on its own price and is independent of the prices of the other products). However, for pricing problems in many industries, e.g. fashion retail and travel, the separability assumption does not hold (due to, say, substitution or complementarity among the products). In this paper, we derive GVR's results for the more general setting where the demand-price relationship need not be separable. Specifically, we analyze two state-independent policies and show that they are both asymptotically optimal. Similar to GvR, we consider a sequence of scaled versions of the original problem in which the demand-arrival rates of the products and the capacities of the resources are both scaled by a factor $k\in \mathbb{N}$, and show that an upper bound on the optimal revenue scales proportional to $k$, while the optimality gaps of the two policies scale proportional to $\sqrt{k}$. This ''square root effect'' is widely viewed as a cornerstone in Network Revenue Management. Our analysis introduces a bounding technique that uses a Poisson concentration inequality – this technique can potentially be applied to other OM problems