Part of Advances in Neural Information Processing Systems 28 (NIPS 2015)
Mehryar Mohri, Andres Munoz
We present a revenue optimization algorithm for posted-price auctions when facing a buyer with random valuations who seeks to optimize his $\gamma$-discounted surplus. To analyze this problem, we introduce the notion of epsilon-strategic buyer, a more natural notion of strategic behavior than what has been used in the past. We improve upon the previous state-of-the-art and achieve an optimal regret bound in $O\Big( \log T + \frac{1}{\log(1/\gamma)} \Big)$ when the seller can offer prices from a finite set $\cP$ and provide a regret bound in $\widetilde O \Big(\sqrt{T} + \frac{T^{1/4}}{\log(1/\gamma)} \Big)$ when the buyer is offered prices from the interval $[0, 1]$.