Markdown Pricing Under an Unknown Parametric Demand Model
This work solves a fundamental open problem in revenue management for sellers constrained by monotonic pricing, though it is incremental in extending prior regret bounds to parametric models.
The paper tackles the problem of single-product revenue maximization with monotonic price decreases under an unknown parametric demand model, establishing optimal regret bounds of Θ(log² n) for families with crossing number 0 and Θ̃(n^{k/(k+1)}) for families with crossing number k≥1, which are asymptotically higher than without monotonicity.
Consider a single-product revenue-maximization problem where the seller monotonically decreases the price in $n$ rounds with an unknown demand model coming from a given family. Without monotonicity, the minimax regret is $\tilde O(n^{2/3})$ for the Lipschitz demand family and $\tilde O(n^{1/2})$ for a general class of parametric demand models. With monotonicity, the minimax regret is $\tilde O(n^{3/4})$ if the revenue function is Lipschitz and unimodal. However, the minimax regret for parametric families remained open. In this work, we provide a complete settlement for this fundamental problem. We introduce the crossing number to measure the complexity of a family of demand functions. In particular, the family of degree-$k$ polynomials has a crossing number $k$. Based on conservatism under uncertainty, we present (i) a policy with an optimal $Θ(\log^2 n)$ regret for families with crossing number $k=0$, and (ii) another policy with an optimal $\tilde Θ(n^{k/(k+1)})$ regret when $k\ge 1$. These bounds are asymptotically higher than the $\tilde O(\log n)$ and $\tilde Θ(\sqrt n)$ minimax regret for the same families without the monotonicity constraint.