Optimal Regret Minimization in Posted-Price Auctions with Strategic Buyers

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 im-provement 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 pre-vious state of the art and show a consistent exponential improvement in several different scenarios.