On consistency of optimal pricing algorithms in repeated posted-price auctions with strategic buyer.

We study revenue optimization learning algorithms for repeated posted-priceauctions where a seller interacts with a single strategic buyer that holds afixed private valuation for a good and seeks to maximize his cumulativediscounted surplus. For this setting, first, we propose a novel algorithm thatnever decreases offered prices and has a tight strategic regret bound in$\Theta(\log\log T)$ under some mild assumptions on the buyer surplusdiscounting. This result closes the open research question on the existence ofa no-regret horizon-independent weakly consistent pricing. The proposedalgorithm is inspired by our observation that a double decrease of offeredprices in a weakly consistent algorithm is enough to cause a linear regret.This motivates us to construct a novel transformation that maps aright-consistent algorithm to a weakly consistent one that never decreasesoffered prices.

Second, we outperform the previously known strategic regret upper bound ofthe algorithm PRRFES, where the improvement is achieved by means of a finerconstant factor $C$ of the principal term $C\log\log T$ in this upper bound.Finally, we generalize results on strategic regret previously known forgeometric discounting of the buyer's surplus to discounting of other types,namely: the optimality of the pricing PRRFES to the case of geometricallyconcave decreasing discounting; and linear lower bound on the strategic regretof a wide range of horizon-independent weakly consistent algorithms to the caseof arbitrary discounts.