{"ID":2893306,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12733","arxiv_id":"2507.12733","title":"The Query Complexity of Uniform Pricing","abstract":"Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \\textit{pricing query complexity} problem in Mechanism Design. The previous work [LSTW23] studies the \\textit{single-distribution} case, with tight bounds of $\\widetildeΘ(\\varepsilon^{-3})$ for a \\textit{general} distribution and $\\widetildeΘ(\\varepsilon^{-2})$ for either a \\textit{regular} or \\textit{monotone-hazard-rate (MHR)} distribution, where $\\varepsilon \\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 \\textsf{Uniform Pricing}} mechanism, in the \\textit{single-distribution} case''. Yet in the \\textit{multi-distribution} case, can the regularity and MHR conditions still lead to improvements over the tight bound $\\widetildeΘ(\\varepsilon^{-3})$ for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound $Ω(\\varepsilon^{-3})$ for either \\textit{two regular distributions} or \\textit{three MHR distributions}. We also address the \\textit{regret minimization} problem and, in comparison with the folklore upper bound $\\widetilde{O}(T^{2 / 3})$ for general distributions (see, e.g., [SW24]), establish a (near-)matching lower bound $Ω(T^{2 / 3})$ for either \\textit{two regular distributions} or \\textit{three MHR distributions}, via a black-box reduction. Again, this is in stark contrast to the tight bound $\\widetildeΘ(T^{1 / 2})$ for a single regular or MHR distribution.","short_abstract":"Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \\textit{pricing query complexity} problem in Mechanism Design. The previous work [LSTW23] studies the \\textit{single-distribution} case, with tight bounds of $\\widetildeΘ(\\varepsilon^{-3})$ for a \\textit{general} d...","url_abs":"https://arxiv.org/abs/2507.12733","url_pdf":"https://arxiv.org/pdf/2507.12733v3","authors":"[\"Houshuang Chen\",\"Yaonan Jin\",\"Pinyan Lu\",\"Chihao Zhang\"]","published":"2025-07-17T02:31:01Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}