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

Problem definition: We study a multiperiod, multiproduct, dynamic pricing problem with price adjustment costs known as “menu costs.” In this setting, decision makers, such as retailers or 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, whereas purchasing decisions are dictated by a time-dependent multinomial logit choice model. Methodology/results: Our first main contribution consists of establishing fundamental hardness results for the dynamic pricing problem of interest, unveiling 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 scheme (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. Managerial implications: Finally, we present two extensive numerical experiments aimed at studying the impacts of menu costs, albeit from distinct vantage points. Both studies make use of a large and diverse test bed of problem instances that we painstakingly construct from a NielsenIQ scanner grocery data set. Given the novelty of incorporating menu costs within dynamic pricing environments, we use the first set of numerical experiments to present what constitutes one of the first close looks at how these price adjustment costs shape pricing patterns and influence optimal gross margins in a multiproduct setting. The second set of experiments is used to evaluate the efficacy of our FPTAS, ultimately showing its mean revenue performance to be within 1%–2% of optimal. In this way, not only do we break ground from a theoretical perspective when it comes to multiproduct dynamic pricing problems in the presence of menu costs, but we also extensively demonstrate the practical viability of our approach. Funding: The work of D. Segev on this project is supported by Israel Science Foundation [Grant 1407/20]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.0832 .