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.