通过少量采样学习协调竞标者策略，提升非诚实拍卖效果。
Learning to Coordinate Bidders in Non-Truthful Auctions
- 从竞标者估值样本中学习协调策略，实现贝叶斯相关均衡
- 仅需约 $\tilde O(\frac{n}{\varepsilon^2})$ 个样本即可学习成功
- 适用于缺乏估值分布信息的现实拍卖场景
在第一价格拍卖和全付拍卖等非诚实拍卖中，竞标者的独立策略行为难以刻画，常导致次优结果。一种改进方式是协调竞标者：由中介向竞标者推荐相关竞标策略，以实现贝叶斯相关均衡（BCE）。然而，实现BCE通常需要知晓竞标者私有价值分布，而该信息往往不可得。本文首次研究了在非诚实拍卖中学习贝叶斯相关均衡的样本复杂度。证明在一大类非诚实拍卖（包括第一价格和全付拍卖）中，战略形式的BCE可被学习，所需样本数为 $\tilde O(\frac{n}{\varepsilon^2})$，数量级合理，表明学习协调策略在统计上是可行的。技术上，将问题归约为从样本估计竞标者期望效用，并分析了所有单调竞标策略类的伪维数。
原文摘要 · Abstract (English)
In non-truthful auctions such as first-price and all-pay auctions, the independent strategic behaviors of bidders, with the corresponding Bayes-Nash equilibrium notion, are notoriously difficult to characterize and can cause undesirable outcomes. An alternative approach to achieve better outcomes in non-truthful auctions is to coordinate the bidders: let a mediator make incentive-compatible recommendations of correlated bidding strategies to the bidders, namely, implementing a Bayes correlated equilibrium (BCE). The implementation of BCE, however, requires knowledge of the distributions of bidders' private valuations, which is often unavailable. We initiate the study of the sample complexity of learning Bayes correlated equilibria in non-truthful auctions. We prove that the set of strategic-form BCEs in a large class of non-truthful auctions, including first-price and all-pay auctions, can be learned with a polynomial number $\tilde O(\frac{n}{\varepsilon^2})$ of samples of bidders' values. This moderate number of samples demonstrates the statistical feasibility of learning to coordinate bidders. Our technique is a reduction to the problem of estimating bidders' expected utility from samples, combined with an analysis of the pseudo-dimension of the class of all monotone bidding strategies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。