ИСТИНА

In this talk, we discuss our recent findings on revenue optimization learning algorithms for repeated posted-price auctions where a seller interacts with a single strategic buyer that holds a fixed private valuation for a good and seeks to maximize his cumulative discounted surplus. Two setups are considered: asymptotic minimization of strategic cumulative regret for the worst-case buyer valuation and exact maximization of expected cumulative discounted revenue over a given distribution of valuations. In the first setup, a thorough theoretical analysis of some broad families of consistent algorithms is provided. For some of these families, we show that there does not exist a no-regret horizon-independent algorithm. For the class of right-consistent algorithms, we introduce a novel deterministic pricing that, on the one hand, is independent of the time horizon~$T$ and, on the other hand, has an optimal strategic regret upper bound in $O(\log \log T)$. We also propose a novel transformation of algorithms that makes a right-consistent algorithm to never decrease offered prices. The transformation of the optimal algorithm above is shown to be optimal as well. This result closes the open research question on the existence of a no-regret horizon-independent weakly consistent pricing, while the property of non-decreasing prices is proven to be nearly necessary for a weakly consistent algorithm to be a no-regret one. In the second setup, in the case when the participants equally discount their cumulative utilities, we show that the seller cannot advantageously use the ability to change prices in dynamic fashion: the constant offering of the Myerson price is optimal. When there is an imbalance between the seller and the buyer in the patience to wait for utility, we find that the constant pricing, surprisingly, is no longer optimal. For the case of more patient seller, we also propose a novel multidimensional optimization functional to numerically search for optimal algorithms. Our results are supported by a numerical experimentation for a variety of discount rates.