The Query Complexity of Uniform Pricing

Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the textitpricing query complexity problem in Mechanism Design. The previous work [LSTW23] studies the textitsingle-distribution case, with tight bounds of widetildeTheta(varepsilon-3) for a textitgeneral distribution and widetildeTheta(varepsilon-2) for either a textitregular or textitmonotone-hazard-rate (MHR) distribution, where varepsilon ∈ (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 textsfUniform Pricing mechanism, in the textitsingle-distribution case''. Yet in the textitmulti-distribution case, can the regularity and MHR conditions still lead to improvements over the tight bound widetildeTheta(varepsilon-3) for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound Omega(varepsilon-3) for either textittwo regular distributions or textitthree MHR distributions. We also address the textitregret minimization problem and, in comparison with the folklore upper bound widetildeO(T2 / 3) for general distributions (see, e.g., [SW24]), establish a (near-)matching lower bound Omega(T2 / 3) for either textittwo regular distributions or textitthree MHR distributions, via a black-box reduction. Again, this is in stark contrast to the tight bound widetildeTheta(T1 / 2) for a single regular or MHR distribution.