Revenue Optimization in Posted-Price Auctions with Strategic Buyers
This work addresses revenue optimization for auctioneers in online settings with strategic buyers, representing a significant advance over incremental improvements.
The paper tackles revenue optimization in posted-price auctions with strategic buyers by showing that a broad family of algorithms has a lower bound of Ω(√T) strategic regret and introducing a new algorithm that achieves O(log T) strategic regret, an exponential improvement over prior methods, with empirical results confirming this gain.
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 $Ω(\sqrt{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.