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.