The Query Complexity of Uniform Pricing

Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the $\mathit{\text{pricing}}\mathit{\text{query}}\mathit{\text{complexity}}$ problem in Mechanism Design. The previous work [LSTW23] studies the $\mathit{\text{single-distribution}}$ case, with tight bounds of $\tilde{\mathrm{\Theta }}({\epsilon }^{-3})$ for a $\mathit{\text{general}}$ distribution and $\tilde{\mathrm{\Theta }}({\epsilon }^{-2})$ for either a $\mathit{\text{regular}}$ or $\mathit{\text{monotone-hazard-rate}}\mathit{\text{(MHR)}}$ distribution, where $\epsilon \in (0,1)$ denotes the (additive) revenue loss of a learned uniform price relative to the Bayesian-optimal uniform price. This can be directly interpreted as ``the query complexity of the {\em $\mathsf{\text{Uniform}}\mathsf{\text{Pricing}}$} mechanism, in the $\mathit{\text{single-distribution}}$ case’'. Yet in the $\mathit{\text{multi-distribution}}$ case, can the regularity and MHR conditions still lead to improvements over the tight bound $\tilde{\mathrm{\Theta }}({\epsilon }^{-3})$ for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound $\mathrm{\Omega }({\epsilon }^{-3})$ for either $\mathit{\text{two}}\mathit{\text{regular}}\mathit{\text{distributions}}$ or $\mathit{\text{three}}\mathit{\text{MHR}}\mathit{\text{distributions}}$. We also address the $\mathit{\text{regret}}\mathit{\text{minimization}}$ problem and, in comparison with the folklore upper bound $\tilde{O}(T^{2\mathrm{/}3})$ for general distributions (see, e.g., [SW24]), establish a (near-)matching lower bound $\mathrm{\Omega }(T^{2\mathrm{/}3})$ for either $\mathit{\text{two}}\mathit{\text{regular}}\mathit{\text{distributions}}$ or $\mathit{\text{three}}\mathit{\text{MHR}}\mathit{\text{distributions}}$, via a black-box reduction. Again, this is in stark contrast to the tight bound $\tilde{\mathrm{\Theta }}(T^{1\mathrm{/}2})$ for a single regular or MHR distribution.