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 $\Theta(\log^2 n)$ regret for families with crossing number
$k=0$, and (ii) another policy with an optimal $\tilde \Theta(n^{k/(k+1)})$
regret when $k\ge 1$. These bounds are asymptotically higher than the $\tilde
O(\log n)$ and $\tilde \Theta(\sqrt n)$ minimax regret for the same families
without the monotonicity constraint.

在这项研究中，我们提供关于收入最大化问题的完整解决方案，引入交叉数量来衡量需求函数族的复杂性，并基于不确定性下的保守性，针对不同的交叉数量提出了衡量函数。