The Query Complexity of Uniform Pricing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909998446018560 |
|---|---|
| author | Chen, Houshuang Jin, Yaonan Lu, Pinyan Zhang, Chihao |
| author_facet | Chen, Houshuang Jin, Yaonan Lu, Pinyan Zhang, Chihao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12733 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Query Complexity of Uniform Pricing Chen, Houshuang Jin, Yaonan Lu, Pinyan Zhang, Chihao Computer Science and Game Theory 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. |
| title | The Query Complexity of Uniform Pricing |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.12733 |