Selling to Multiple No-Regret Buyers

Understand

We consider the problem of repeatedly auctioning a single item to multiple i.i.d buyers who each use a no-regret learning algorithm to bid over time.

• In particular, we study the seller's optimal revenue, if they know that the buyers are no-regret learners (but only that their behavior satisfies some no-regret property -- they do not know the precise algorithm/heuristic used).
• Our main result designs an auction that extracts revenue equal to the full expected welfare whenever the buyers are "mean-based" (a property satisfied by standard no-regret learning algorithms such as Multiplicative Weights, Follow-the-Perturbed-Leader, etc.).
• This extends a main result of [BMSW18] which held only for a single buyer.