Dynamic Pricing with Menu Costs : Approximation Schemes and Applications to Grocery Retail

We study a multi-period, multi-product, dynamic pricing problem with price adjustment costs known as menu costs. In this setting, we assume that decision makers (e.g., retailers, online platforms) incur a fixed menu cost whenever prices are updated between periods, as well as a variable menu cost that linearly scales with the number of between-period price changes. From a demand standpoint, the random number of customers arriving in each period is assumed to be arbitrarily distributed, while purchasing decisions are dictated by a time-dependent Multinonomial Logit choice model. Our first main contribution consists of establishing fundamental hardness results for the dynamic pricing problem of interest, which jointly reveal inherent computational hurdles even when stripped down to its simplest form. On the positive side, we identify grocery retail as a particular application domain whose distinguishing features allow us to develop a fully polynomial time approximation schemes (FPTAS), through which optimal expected revenues are shown to be approachable within any degree of accuracy. In this context, our methodology synthesizes compact enumeration ideas, novel coupling arguments, and approximate dynamic programming techniques. Finally, with respect to a Nielsen scanner grocery data set, we conduct an extensive set of numerical experiments where the aforementioned FPTAS is employed to measure the extent to which dynamic pricing policies can improve upon their static counterparts. Surprisingly, we find these improvements to be rather modest on average, which we interpret to be suggestive of certain limitations of dynamic pricing in a grocery retail setting. These findings may carry important practical implications related to the future adoption of digital price tags and inventory tracking technology in grocery retail