Selling to a No-Regret Buyer
  We consider the problem of a single seller repeatedly selling a single item
to a single buyer (specifically, the buyer has a value drawn fresh from known
distribution $D$ in every round). Prior work assumes that the buyer is fully
rational and will perfectly reason about how their bids today affect the
seller's decisions tomorrow. In this work we initiate a different direction:
the buyer simply runs a no-regret learning algorithm over possible bids. We
provide a fairly complete characterization of optimal auctions for the seller
in this domain. Specifically:
  - If the buyer bids according to EXP3 (or any "mean-based" learning
algorithm), then the seller can extract expected revenue arbitrarily close to
the expected welfare. This auction is independent of the buyer's valuation $D$,
but somewhat unnatural as it is sometimes in the buyer's interest to overbid. -
There exists a learning algorithm $\mathcal{A}$ such that if the buyer bids
according to $\mathcal{A}$ then the optimal strategy for the seller is simply
to post the Myerson reserve for $D$ every round. - If the buyer bids according
to EXP3 (or any "mean-based" learning algorithm), but the seller is restricted
to "natural" auction formats where overbidding is dominated (e.g. Generalized
First-Price or Generalized Second-Price), then the optimal strategy for the
seller is a pay-your-bid format with decreasing reserves over time. Moreover,
the seller's optimal achievable revenue is characterized by a linear program,
and can be unboundedly better than the best truthful auction yet simultaneously
unboundedly worse than the expected welfare.
