论文标题
在非真实拍卖中学习实用程序和平衡
Learning Utilities and Equilibria in Non-Truthful Auctions
论文作者
论文摘要
在非真实的拍卖中，代理商的战略效用取决于对手的策略以及对私人类型的先前分布；一组贝叶斯纳什平衡通常对先验具有复杂的依赖性。使用第一个价格拍卖作为我们的主要演示示例，我们表明$ \ tilde o（n /ε^2）$样本$ n $ agents的算法足以学习所有单调竞标策略的临时公用事业。结果，这一数量的样本足以学习所有近似平衡。我们在学习公用事业的样本复杂性上几乎具有匹配的（超过各种因素）。我们还考虑了代理商必须支付搜索成本才能发现自己类型的设置。利用Kleinberg等人最近发现的此设置和第一个价格拍卖之间的连接。 （2016年），我们表明$ \ tilde o（n /ε^2）$样本足以容纳公用事业，在这种情况下，在近乎福利 - 最佳的下降拍卖中估算了平衡。在途中，我们改善了Guo等人最近获得的样品复杂性结合。 （2021），对于Pandora的盒子问题，这是用于顺序消费者搜索的经典模型。
In non-truthful auctions, agents' utility for a strategy depends on the strategies of the opponents and also the prior distribution over their private types; the set of Bayes Nash equilibria generally has an intricate dependence on the prior. Using the First Price Auction as our main demonstrating example, we show that $\tilde O(n / ε^2)$ samples from the prior with $n$ agents suffice for an algorithm to learn the interim utilities for all monotone bidding strategies. As a consequence, this number of samples suffice for learning all approximate equilibria. We give almost matching (up to polylog factors) lower bound on the sample complexity for learning utilities. We also consider a setting where agents must pay a search cost to discover their own types. Drawing on a connection between this setting and the first price auction, discovered recently by Kleinberg et al. (2016), we show that $\tilde O(n / ε^2)$ samples suffice for utilities and equilibria to be estimated in a near welfare-optimal descending auction in this setting. En route, we improve the sample complexity bound, recently obtained by Guo et al. (2021), for the Pandora's Box problem, which is a classical model for sequential consumer search.
