arXiv preprint ·
Personalised versus Posted Pricing from Samples
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Personalised pricing maximises expected revenue from a market but requires detailed information about individual customers. How much of this revenue can be recovered using a simple posted price based on a finite number of samples from the underlying value distribution? We answer this question by maximising the worst-case ratio between the expected revenues of posted and personalised pricing over the fundamental class of $λ$-regular value distributions. Our results reveal a structural transition as a function of $λ$. For the class of monotone hazard rate (MHR) distributions, corresponding to $λ= 0$, the sample mean is an optimal statistic: the entire sample can be compressed into its average without any loss of revenue. Beyond the MHR class, corresponding to $λ> 0$, this property disappears. We show that the sample mean is no longer optimal, revealing that optimal sample-based pricing rules become substantially more intricate. Nevertheless, we show that a remarkably simple order-statistic based pricing rule is asymptotically optimal as the number of samples $n$ grows, achieving the optimal approximation ratio up to a tight error of order $1/n$. Our analysis combines techniques from probability, approximation theory and optimization, including doubly infinite linear programming, hypergeometric functions, and combinatorial identities involving incomplete Beta functions.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
Precise Convergence Speed of Clipped SGD
Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation
Limiting-Kernel Q($λ$): Bridging Short and Long Horizons
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.