在反馈被操纵的拍卖中,如何学会正确出价?
Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions
- 设计双分支算法,分别应对干扰性报价和可靠信息
- 实现近似最优的 $\tilde{\mathcal{O}}(\sqrt{T})$ 误差率
- 适用于在线广告等受控反馈环境下的竞价学习
刷单是通过虚假出价制造竞争假象以推高价格的行为。本文研究重复的一阶拍卖中,刷单仅影响反馈而不限制分配:学习者无论胜负,失败后观测到的是真实竞标价与独立刷单价的最大值。这种操纵改变了学习者所见信息,从而影响其出价策略,但不改变当前拍卖结果。我们分析相对于最优出价基准的遗憾度,假设刷单价分布已知。即使如此,刷单仍可掩盖真实报价,仅在少数低刷单事件中出现有用旁证。提出算法结合鲁棒区间剔除分支(忽略刷单报告,达到动态定价率 $\tilde{\mathcal{O}}(T^{2/3})$)与乐观分支(去偏失败侧报告,利用可靠后缀信息,实现一阶拍卖最优率 $\tilde{\mathcal{O}}(\sqrt{T})$)。验证与竞速机制使算法无需预知尺度或反馈结构即可使用乐观更新。上界与下界匹配,仅差对数因子,在单活跃区域情形下成立。结果表明,仅反馈层面的刷单即可显著提升重复竞价的统计难度。
原文摘要 · Abstract (English)
Shilling is the use of artificial bids to make competition appear stronger and push prices upward. We study repeated first-price auctions in which shilling affects feedback but not allocation: the learner wins or loses against the real competing bid, but after a loss observes the maximum of the real bid and an independent shill bid. Thus the manipulation changes what the learner observes and hence how it learns to bid, without changing the outcome of the current auction. We analyze regret with respect to the best bid benchmark, assuming that the shill-bid distribution is known. Even then, shilling can mask the real bid, while useful side information appears only through intermittent low-shill events. Our algorithm combines a robust interval-elimination branch, which ignores the shilled report and achieves the dynamic-pricing rate $\tilde{\mathcal{O}}(T^{2/3})$, with an optimistic branch that debiases losing-side reports and exploits the resulting suffix information when it is reliable and achieves the first-price auctions rate $\tilde{\mathcal{O}}(\sqrt{T})$. A validation and racing procedure lets the algorithm use these optimistic updates without knowing the right scale or feedback geometry in advance. We complement the upper bounds with a matching lower bound, up to logarithmic factors, in the single-active-region case. Overall, the results show that even feedback-only shilling can sharply alter the statistical difficulty of repeated bidding.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。