Title: Optimal Regret Minimization in Posted-Price Auctions with Strategic Buyers
Abstract:We study revenue optimization learning algorithms for posted-price auctions with strategic buyers. We analyze a very broad family of monotone regret minimization algorithms for this problem, which inc...We study revenue optimization learning algorithms for posted-price auctions with strategic buyers. We analyze a very broad family of monotone regret minimization algorithms for this problem, which includes the previously best known algorithm, and show that no algorithm in that family admits a strategic regret more favorable than Ω(√T). We then introduce a new algorithm that achieves a strategic regret differing from the lower bound only by a factor in O(log T), an exponential improvement upon the previous best algorithm. Our new algorithm admits a natural analysis and simpler proofs, and the ideas behind its design are general. We also report the results of empirical evaluations comparing our algorithm with the previous state of the art and show a consistent exponential improvement in several different scenarios.Read More
Publication Year: 2014
Publication Date: 2014-12-08
Language: en
Type: article
Access and Citation
Cited By Count: 48
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot