Online Auctions and Multi-scale Online Learning
Authors:
Open Access
- 20 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 497-514
Abstract
We consider revenue maximization in online auctions and pricing. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.Keywords
All Related Versions
Funding Information
- NSF (CCF-1512964)
- RGC (HKU17202115E)
- Google Ph.D. Fellowship
This publication has 13 references indexed in Scilit:
- Making the Most of Your Samples2015
- Dynamic pricing and learning: Historical origins, current research, and new directionsSurveys in Operations Research and Management Science, 2015
- Revenue maximization with a single sampleGames and Economic Behavior, 2015
- Bandits with concave rewards and convex knapsacks2014
- The sample complexity of revenue maximization2014
- Bandits with Knapsacks2013
- Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal AlgorithmsOperations Research, 2009
- Online learning in online auctionsTheoretical Computer Science, 2004
- Optimal Pricing Mechanisms with Unknown DemandAmerican Economic Review, 2003
- Optimal Auction DesignMathematics of Operations Research, 1981