2025/07/17 by Chen, Houshuang, Jin, Yaonan, Lu, Pinyan +1
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.12733
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 (LSTW23, SODA) studies the single-distribution case, with tight bounds of \widetildeΘ(ε-3) for a general distribution and \widetildeΘ(ε-2) for either a regular or monotone-hazard-rate (MHR) distribution. This can be directly interpreted as ''the query complexity of the \textsfUniform Pricing mechanism, in the single-distribution case''. Yet in the multi-distribution case, can the regularity and MHR conditions still lead to improvements over the tight bound \widetildeΘ(ε-3) for general distributions? We answer this question in the negative, by establishing a (near-)matching lower bound Ω(ε-3) for either two regular distributions or three MHR distributions. We also address the regret minimization problem and, in comparison with the folklore upper bound \widetildeO(T2 / 3) for general distributions (see, e.g., SW24, EC), establish a (near-)matching lower bound Ω(T2 / 3) for either two regular distributions or three MHR distributions, via a black-box reduction. Again, this is in stark contrast to the tight bound \widetildeΘ(T1 / 2) for a single regular or MHR distribution.