The Query Complexity of Uniform Pricing

Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the pricing query complexity problem in Mechanism Design. The previous work [11] studies the single-distribution case1, with tight bounds of Θ (ε-3 ) for a general distribution and Θ (ε-2 ) for either a regular or monotone-hazard-rate (MHR) distribution, where ε ∈ (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 Uniform Pricing mechanism, in the single-distribution case''. Yet in the multi-distribution case, can the regularity and MHR conditions still lead to improvements over the tight bound Θ (ε-3) for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound Ømega(ε-3) for either two regular distributions or three MHR distributions. We also address the regret minimization problem and, in comparison with the folklore upper bound O(T2/3 ) for general distributions (see, e.g., [13]), establish a (near-)matching lower bound Ømega(T2/3 ) for either two regular distributions or three MHR distributions, via a black-box reduction. Again, this is in stark contrast to the tight bound Θ(T1/2 ) for a single regular or MHR distribution.