Selling to No-Regret Buyers

Abstract

We consider the problem of optimizing a seller's revenue in an opaque auction where bidders are using a no-regret learning algorithm. In such auctions, we assume a single item and multiple bidders drawing their values from a known distribution D. The seller is able to set the price and allocation probability for each possible bid value independently for each round. We extend results from "Selling to a No-Regret Buyer" by Braverman et. al to the multiple bidder setting by taking a Lagrangian relaxation of the original linear program presented in the paper. We provide three properties of a solution to the Lagrangian relaxation in the single bidder setting and show why one does not hold for the multiple bidder setting. We then present two greedy algorithms for solving the multiple bidder Lagrangian relaxation and show why they do not output an optimal solution. Finally, we present a subset of distributions for which the techniques for solving the single bidder Lagrangian relaxation can be extended to the multiple bidder setting.