Neural Information Processing Systems http://nips.cc/

Buyers' valuations for an item depend on the context that describes

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.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

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 previous best known algorithm, and show that no algorithm in that family admits a strategic regret more favorable than $\Omega(\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 best algorithm and show a consistent exponential improvement in several different scenarios.

Neural Information Processing Systems http://nips.cc/

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.

It is quite unclear, since in [Medina & Mohri, 2014], the benchmark is the best possible one, because it is equal exactly to the valuation of the buyer and, hence, generate the maximal revenue each round. So, even any dynamic pricing cannot provide higher revenue than this one. The same issue occurs in Lines 81-83. Comment after rebuttal: I got the answer in general. I hope, the authors will improve clearness in the lines that I have indicated above.