Pricing Query Complexity of Multiplicative Revenue Approximation

Wei Tang; Yifan Wang; Mengxiao Zhang

doi:10.48550/arxiv.2602.10483

Back

Pricing Query Complexity of Multiplicative Revenue Approximation

Preprint

Open access

Pricing Query Complexity of Multiplicative Revenue Approximation

Wei Tang, Yifan Wang and Mengxiao Zhang

ArXiv.org

Cornell University

02/11/2026

DOI: 10.48550/arxiv.2602.10483

Files and links (1)

url

https://doi.org/10.48550/arxiv.2602.10483View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

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ε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-ε)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.

Computer Science - Computer Science and Game Theory

Computer Science - Learning

Details

Title: Subtitle: Pricing Query Complexity of Multiplicative Revenue Approximation
Creators: Wei Tang - Chinese University of Hong Kong
Yifan Wang - Georgia Institute of Technology
Mengxiao Zhang - University of Iowa
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2602.10483
ISSN: 2331-8422
Publisher: Cornell University; Ithaca, New York
Language: English
Date posted: 02/11/2026
Academic Unit: Business Analytics
Record Identifier: 9985139476402771

Metrics

4 Record Views