# The Query Complexity of Uniform Pricing

arXiv: https://arxiv.org/abs/2507.12733 · HTML: https://mlsanity.com/paper/2507.12733/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)

## Abstract (arXiv)

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.