Selling to a No-Regret Buyer
Selling to a No-Regret Buyer
复制标题
DOI：
10.1145/3219166.3219233
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
M. Braverman;Jieming Mao;Jon Schneider;Matt Weinberg
中科院分区：
文献类型：
--
作者：
M. Braverman;Jieming Mao;Jon Schneider;Matt Weinberg
我们考虑一个单一卖家反复向单一买家出售单一商品的问题（具体来说，买家在每一轮中都从已知分布D中获得新鲜的价值）。先前的研究假设买方是完全理性的，并且会完全推理出他们今天的出价如何影响卖方明天的决定。在这项工作中，我们启动了一个不同的方向：买家简单地运行一个不后悔的学习算法对可能的出价。我们提供了一个相当完整的表征最优拍卖的卖方在这个领域。具体来说：-如果买方根据EXP3（或任何“基于均值的”学习算法）出价，那么卖方可以任意提取接近预期福利的预期收入。这次拍卖独立于买家的估价，但有些不自然，因为有时出价过高符合买家的利益。-存在一种学习算法a，如果买方根据a出价，那么卖方的最优策略就是每轮为D发布迈尔森保留。-如果买方根据EXP3（或任何“基于均值的”学习算法）出价，但卖方仅限于“自然”拍卖形式，其中超竞价占主导地位（例如广义第一价格或广义第二价格），那么卖方的最佳策略是支付你的出价格式，并随着时间的推移减少储备。此外，卖方的最优可实现收益具有线性规划的特征，可以无限地优于最优真实拍卖，但同时也无限地低于预期福利。
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.