arXiv:2602.10483cs.GTcs.LG2026-02

研究如何用最少的定价查询,逼近最优收益的乘法误差。

Pricing Query Complexity of Multiplicative Revenue Approximation

  • 通过单次采样或范围提示,学习买家估值分布的最优定价。
  • 在MHR、正则等分布下,达到乘法误差的查询复杂度接近最优。
  • 适合关注收益最大化与数据效率的研究者和应用设计者。

我们研究单个买家在估值来自未知分布时的定价查询复杂度问题。卖家只能通过发布价格并观察购买与否的二元反馈来学习最优垄断价格,而无法获得实际估值。已有研究建立了在估值支持于[0,1]区间时,以加法误差ε学习近似最优价格的紧致查询复杂度界限。然而,对于能实现最优收益(1−ε)倍的乘法误差情形,理解仍不充分。本文在多种设定下研究了单买家收益最大化的定价查询复杂度,针对乘法误差保证。注意到,若仅依赖定价查询获取买家分布信息,算法无法实现非平凡近似,因为分布尺度无法仅从定价查询中获知。为此,我们考虑两种自然且动机充分的“尺度提示”模型:(i) 一抽样提示,即算法在定价前可观察一次真实估值;(ii) 估值范围提示,即已知估值支持于[1, H]。对每种提示,我们在包括单调风险率(MHR)、正则分布及一般分布等类别的分布上,建立了紧致至多对数因子的定价查询复杂度界。

原文摘要 · Abstract (English)

We study the pricing query complexity of revenue maximization for a single buyer whose private valuation is drawn from an unknown distribution. In this setting, the seller must learn the optimal monopoly price by posting prices and observing only binary purchase decisions, rather than the realized valuations. Prior work has established tight query complexity bounds for learning a near-optimal price with additive error $\varepsilon$ when the valuation distribution is supported on $[0,1]$. However, our understanding of how to learn a near-optimal price that achieves at least a $(1-\varepsilon)$ fraction of the optimal revenue remains limited. In this paper, we study the pricing query complexity of the single-buyer revenue maximization problem under such multiplicative error guarantees in several settings. Observe that when pricing queries are the only source of information about the buyer's distribution, no algorithm can achieve a non-trivial approximation, since the scale of the distribution cannot be learned from pricing queries alone. Motivated by this fundamental impossibility, we consider two natural and well-motivated models that provide "scale hints": (i) a one-sample hint, in which the algorithm observes a single realized valuation before making pricing queries; and (ii) a value-range hint, in which the valuation support is known to lie within $[1, H]$. For each type of hint, we establish pricing query complexity guarantees that are tight up to polylogarithmic factors for several classes of distributions, including monotone hazard rate (MHR) distributions, regular distributions, and general distributions.

收益最大化定价策略查询复杂度机制设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。