Selling to a Sophisticated No-Regret Buyer

Abstract

Consider a repeated single item auction with a single buyer who has a value for the item randomly drawn from known distribution \(\mathcal{D}\) each round and bids according to an online learning algorithm. "Selling to a No-Regret Buyer" by Braverman et al. presents a strategy for the seller which, whenever the buyer bids according to a mean-based learning algorithm, extracts revenue that is arbitrarily close to the expected welfare. We extend these results to two settings where the bidder does not use a simple mean-based learning algorithm. First, we consider a bidder using a mean-based learning algorithm with recency bias, where the results of recent rounds are weighed more strongly. We show how much revenue the strategy yields as a function of the recency bias factor \(\beta\). Next, we consider a bidder using a \(\textit{k}\)-switching learning algorithm, where what we define as a \(\textit{g-mean-based}\) learning algorithm is given as options all "meta-strategies" which switch bids at most \(\textit{k}\) times. We present a new strategy and show how much revenue it yields as a function of the \(\textit{g}\) for which the learning algorithm is \(\textit{g}\)-mean-based. In both settings, we also determine which parameter values allow the algorithm to be no-regret, and which yield revenue that is arbitrarily close to the welfare.