Markdown Pricing Under an Unknown Parametric Demand Model

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(n2/3) for the Lipschitz demand family and tilde O(n1/2) for a general class of parametric demand models. With monotonicity, the minimax regret is tilde O(n3/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 Theta(log2 n) regret for families with crossing number k=0, and (ii) another policy with an optimal tilde Theta(nk/(k+1)) regret when k≥ 1. These bounds are asymptotically higher than the tilde O(log n) and tilde Theta(√ n) minimax regret for the same families without the monotonicity constraint.