📊 statistics

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions

本文分析了存在仅操纵反馈而非分配的虚假竞价的第一价格重复拍卖，提出了一种结合鲁棒区间消除与乐观去偏的混合算法，该算法实现了最优的 $\tilde{\mathcal{O}}(\sqrt{T})$ 遗憾，同时证明了此类仅操纵反馈的行为显著增加了学习竞价策略的统计难度。

原作者： Luigi Foscari, Matilde Tullii, Vianney Perchet

发布于 2026-05-22

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Luigi Foscari, Matilde Tullii, Vianney Perchet

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在在线拍卖中购买一件稀有的收藏品。你不知道其他人愿意出多少钱，因此必须通过观察你出价后发生的情况来学习。

通常，如果你输掉了一场拍卖，平台会告诉你击败你的最高出价。这有助于你学习：“哦，下次我需要出得稍高一点。”

但在这篇论文中，作者设想了一种拍卖师有点狡猾的情景。他们称之为“托价”（shilling）。

诡计：“假竞争对手”

想象拍卖师有一个秘密朋友，专门下假价，只是为了让竞争看起来比实际情况更激烈。

如果你赢了：太好了！你得到了物品，那个假朋友无关紧要。
如果你输了：拍卖师会告诉你包含假出价在内的最高出价。

所以，如果真实的最高出价是 50 美元，但假朋友出价 80 美元，拍卖师会告诉你：“你输给了 80 美元！”

问题：你可能会想：“哇，大家都在出 80 美元！下次我最好出 85 美元！”但真实的竞争只有 50 美元。你被诱骗而多付了钱。
转折：有时，假朋友出价非常低（比如 10 美元）。如果真实出价是 50 美元，拍卖师仍然会告诉你最大值，即 50 美元。在这种情况下，你获得了真实的信息。

这篇论文提出了一个问题：当拍卖师有时会对输掉的出价撒谎时，聪明的竞标者如何能学会真实的价格？

双管齐下的策略

作者设计了一种“学习算法”（一套供计算机执行的规则），其作用就像一个谨慎的侦探。它同时使用两种不同的方法，就像既拥有安全网又拥有高速汽车。

1. 安全网（“稳健”分支）

算法的这一部分说：“我完全不信任输掉的出价报告。我要忽略那些虚假数字。”

它只关注自己赢了还是输了。
它将拍卖视为一个简单的“价格标签”游戏（就像买咖啡一样，你只需看看自己是否付得起）。
结果：这既缓慢又安全。它保证你不会损失太多钱，但你不会学得特别快。这就像在黑暗中小心行走。

2. 乐观者（“乐观”分支）

这一部分说：“让我们尝试利用那些虚假数字，但要聪明地利用。”

它了解假出价的模式（例如：“假朋友通常在 10 美元到 20 美元之间出价”）。
当它看到输掉的出价时，它会进行一些数学运算来“减去”虚假部分，并猜测真实出价可能是多少。
关键：只有当假出价足够低，能让真实出价显露出来时，这种方法才有效。
结果：当假出价较低且有帮助时，这种方法比安全网快得多地学习。这就像在畅通的道路上高速驾驶。

3. “竞速”机制

算法事先并不知道哪种方法会更好。因此，它让两者同时进行一场“赛跑”。

它不断检查：“乐观者的判断合理吗？数据可靠吗？”
如果假出价太高，导致乐观者陷入困惑，算法就会切换回安全网。
如果数据看起来干净，它就会依赖乐观者以加快学习速度。

重大发现

这篇论文证明，即使拍卖师在操纵信息，学习者仍然可以表现得出奇地好。

如果假出价总是很高：学习者只能以缓慢的“安全网”速度进行。
如果假出价有时较低：学习者可以利用“乐观者”来加速，比仅仅靠猜测学习得快得多。

作者还证明了一个数学极限：你无法无限快地学习。存在一个“速度限制”，取决于假出价偶然揭示真相的频率。如果假出价非常罕见（概率低），你就被迫慢下来。如果它们经常发生，你就可以快速前进。

简而言之

这篇论文是关于在一个被操纵的游戏中学习如何出价，其中裁判会谎报分数。作者构建了一种策略，在必要时忽略谎言，并在可能时巧妙地利用隐藏在谎言中的真相。他们表明，即使面对一个撒谎的裁判，只要你有办法分辨裁判何时是在提供帮助，何时只是在捣乱，你仍然可以高效地学会市场价格。

技术摘要：在反馈操纵拍卖中学习出价

问题设定
本文研究了重复一级价格拍卖，其中拍卖人（或卖家）参与“托价”（shilling）——即利用虚假出价来操纵学习性出价者所接收的反馈。与传统模型中操纵可能改变分配规则或支付不同，本工作聚焦于反馈操纵拍卖。具体而言，学习者与真实最高竞争出价 $b_t$ 竞争，若其出价 $p_t \geq b_t$ 则获胜。然而，在失败时，学习者无法观察到真实的 $b_t$ 。相反，他们观察到的是托价报告 $o_t = \max\{b_t, s_t\}$ ，其中 $s_t$ 是从已知分布 $S$ 中独立抽取的托价。

这种设定创造了一个独特的学习挑战：分配保持真实（学习者根据现实情况获胜或失败），但信息渠道被扭曲。高托价掩盖了真实的竞争，而低托价则揭示了“后缀信息”（关于高于所出价格的信息）。目标是在存在这种被掩盖的反馈的情况下，最小化相对于实现价值 $v_t$ 的最佳固定出价的遗憾。

方法论
作者提出了一种在价格和值的离散化网格上按阶段运行的算法。核心创新在于双分支方法结合验证与竞赛程序：

鲁棒分支（区间消除）： 该分支完全忽略托价报告，仅依赖二元的输赢结果。它将问题视为具有删失反馈的动态定价任务。该分支保证了 $\tilde{O}(T^{2/3})$ 的遗憾率，在托价严重或托价分布无信息量时充当安全网。
乐观分支（去偏后缀学习）： 该分支试图利用托价报告。由于托价分布 $F_S$ $F_{S}$ 已知，算法利用观测值 $o_t$ $o_{t}$ 构建真实竞争出价分布 $F_B$ $F_{B}$ 的无偏估计器。
- 它利用后缀观测：当 $o_t \leq q$ 时，意味着 $b_t \leq q$ （如果托价足够低）。
- 它采用加权最小二乘框架，将直接的输赢测量与这些后缀差值测量相结合。
- 至关重要的是，它引入了几何不确定性分析。算法不仅估计点值，还利用单个低托价事件揭示整个更高出价范围信息这一事实，构建活跃出价区间的置信界。
二分验证： 算法不假设托价分布的尺度（特别是揭示信息的“低托价”事件的概率 $\gamma$ ）是已知的。它针对托价尺度的一组二分候选值对乐观更新进行验证。如果某个乐观候选值未能通过验证（例如，托价分布过于不规则或尺度过小），算法将回退到鲁棒分支。

主要贡献

带有安全网的鲁棒性： 本文提供了一种鲁棒的区间消除程序，即使在托价使反馈完全失效的情况下，也能实现 $\tilde{O}(T^{2/3})$ 的动态定价速率。
乐观去偏： 开发了一种乐观程序，从托价报告的“噪声路径状”信号中提取结构化信息。通过将后缀观测转化为相邻效用差异的测量，当活跃出价区域规则且覆盖良好时，该算法实现了更快的速率。
适应性： 算法通过二分验证方案适应未知的有效托价水平，无需预先知道托价尺度或反馈几何结构。
紧下界： 作者证明了单活跃区域情况的匹配下界。他们构建了一个“隐藏单元”实例，其中未知区间内存在微小的效用凸起。证明表明，遗憾从根本上受到局部搜索（动态定价机制）与通过失败侧报告进行跨学习之间权衡的限制。

结果
本文确立了以下遗憾界（忽略对数因子）：

上界： 算法实现的遗憾为 $\tilde{O}\left(\min\left\{T^{2/3}, \rho^{1/4}\sqrt{T}\gamma^{-1/4}\right\}\right)$ $\tilde{O} (min {T^{2/3}, ρ^{1/4} T γ^{- 1/4}})$ ，其中 $\rho$ $ρ$ 是活跃出价区域的数量， $\gamma$ $γ$ 是信息性低托价事件的概率。
- 在单活跃区域情况（ $\rho=1$ ）下，该界为 $\tilde{O}\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ 。
- 该速率介于托价严重（ $\gamma \to 0$ ）时的动态定价 $T^{2/3}$ 速率和托价轻微（ $\gamma$ 较大）时标准一级价格拍卖的 $\sqrt{T}$ 速率之间。
下界： 对于单活跃区域情况，本文证明了 $\Omega\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ 的下界。这证实了该算法在忽略对数因子的情况下是极小极大最优的。下界构建强调，即使已知托价分布，如果信息性托价事件罕见，学习者也无法完全恢复 $\sqrt{T}$ 速率，因为“隐藏单元”仍然难以快速识别。

意义与主张
本文主张，即使是仅反馈层面的托价（分配规则未受影响），也会显著改变重复出价的统计难度。这种操纵通过信息渠道起作用，使学习者偏向更高的出价，并部分破坏了通常允许一级价格拍卖实现 $\sqrt{T}$ 遗憾的跨学习结构。

作者将这项工作定位为拍卖反馈操纵理论的第一步。他们明确指出，将这些结果扩展到未知的托价分布、更丰富的托价模型（例如依赖于学习者的出价）以及更通用的活跃区域几何结构仍然是一个开放问题。其意义在于证明，只要操纵遵循特定的结构约束（如已知分布的最大托价），精心利用被操纵反馈的结构就能比纯粹的鲁棒方法恢复更多。