Nearly Bounded Regret of Re-solving Heuristics in Price-based Revenue Management
share
Price-based revenue management is a class of important questions in operations management. In its simplest form, a retailer sells a single product over T consecutive time periods and is subject to constraints on the initial inventory levels. While the optimal pricing policy over T periods could be obtained via dynamic programming, such an approach is sometimes undesirable because of its enormous computational costs. Approximately optimal policies, such as the re-solving heuristic, is often applied as a computationally tractable alternative. In this paper, we prove the following results: 1. We prove that a popular and commonly used re-solving heuristic attains an O(lnln T) regret compared to the value of the optimal DP pricing policy. This improves the O(ln T) regret upper bound established in the prior work of (Jasin 2014). 2. We prove that there is an Ω(ln T) gap between the value of the optimal DP pricing policy and that of a static LP relaxation. This complements our upper bound results in showing that the static LP relaxation is not an adequate information-relaxed benchmark when analyzing price-based revenue management algorithms.
READ FULL TEXT