Online Pricing with Limited Supply and Time-Sensitive Valuations

Many efforts have been devoted to online pricing mechanism design for different settings. In this work, we consider a common but challenging setting where the buyers have private time-sensitive valuations and the seller has limited supply. The seller offers a take-it-or-leave-it posted price for each arriving buyer and aims to maximize the expected total revenue. The unknown distribution of time-sensitive valuations and limited supply significantly increase the difficulty of searching the optimal dynamic posted prices. Given B identical items to sell, when the time-dependent valuations can be estimated with a factor of α, we prove Ω(log(1/α)) lower bound with respect to the optimal fixed distribution over prices and design an algorithm achieving tight O(log(1/α)) competitive ratio. When the seller has no information about the future trends of buyers’ valuations, we prove Ω(log B) lower bound and show that there is an algorithm with tight O(log B) competitive ratio by modeling the problem as adversarial bandits with knapsacks optimization. Extensive simulation studies show that our algorithm outperforms previous mechanisms in various settings.