To refer to this page use:
|Abstract:||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 A such that if the buyer bids according to 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.|
|Citation:||Braverman, Mark, Jieming Mao, Jon Schneider, and Matt Weinberg. "Selling to a no-regret buyer." In Proceedings of the 2018 ACM Conference on Economics and Computation (2018): pp. 523-538. doi:10.1145/3219166.3219233|
|Pages:||523 - 538|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of the 2018 ACM Conference on Economics and Computation|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.