WWW 2020 | 搜索广告拍卖下的私有数据代理博弈

关键词：sponsored search auction, private data

导读

本文是国际万维网大会（WWW 2020）入选论文《搜索广告拍卖下的私有数据代理博弈（Private Data Manipulation in Optimal Sponsored Search Auction）》的解读。

引言

搜索广告拍卖（sponsored search auction）是搜索引擎向广告主销售搜索结果页上的广告位的一种拍卖活动。用户每搜索一个关键词，网页的顶部和侧面就可以显示一些广告。广告每被点击一次，相应的广告主就需要向搜索引擎支付一笔费用。通常，广告位不止一个，不同位置的广告被用户点击的概率是不一样的，而希望投放广告的商家也不止一位。当多个广告主竞争点击率高的广告位时，一场拍卖就出现了。

一个简化的搜索广告拍卖场景是这样的：卖家（搜索引擎）出售 m 个广告位，广告位点击率从大到小排序为 q₁ ≥ q₂ ≥ ⋯ ≥ q_m（假设点击率与广告的实际内容无关）。有 n 个买家（广告主），每人至多购买一个广告位，他们对每次点击的估值为 v₁, v₂, …, v_n。估值 v_i 只有买家 i 自己清楚，卖家和其他买家都不知道 v_i 的值。买家们向卖家报价 b_i 来代表他们的估值 v_i。b_i 不一定要等于 v_i。卖家根据所有的报价 b₁, b₂, …, b_n 来确定这 m 个广告位如何分配给广告主们以及每个广告主应该为每次点击支付多少费用 p_i。假设买家 i 获得了广告位 j，则他的效用为 v_i q_j – p_i q_j，而卖家的收益即所有 p_i q_j 的和。买家通过调整报价来最大化自己的效用，而卖家希望最大化收益。不同的分配方案 q_j(⋅) 和费用计算方式 p_i(⋅) 会影响买家的报价策略，也给卖家带来不同的收益。

早在40年前，经济学家 Roger B. Myerson 就设计出了卖家收益最优的拍卖方案，称为 Myerson's auction[1]。除了卖家收益最优，Myerson's auction 还具有 truthful 的性质，即买家的报价 b_i 恰好等于估值 v_i 时，他们的效用是最大的。这个贡献是 Myerson 在2007年获得诺贝尔经济学奖的原因之一。

需要强调的是，Myerson's auction 依赖于经济学中的一个经典假设：买家的估值 v_i 服从某个概率分布 F_i，且包括卖家在内的所有人都知道这个分布。Myerson's auction 的分配方案和费用计算方式与分布 F_i 密切相关，也就是说，买家 i 获得的广告位 q_j(⋅) 和他支付的费用 p_i(⋅) 是同时关于报价 (b₁, b₂, …, b_n) 和分布 (F₁, F₂, …, F_n) 的函数。

然而在现实中，“知道买家的估值分布”这一假设并不成立。不成立的原因有：完整的分布无法用计算机储存、估值信息属于广告主的隐私等。因此，搜索引擎无法直接使用 Myerson's auction 来最大化自己的收益。

不过，与传统经济学中的拍卖不同的是，搜索广告拍卖是重复的。关键词每被搜索一次，就产生一场拍卖，这个过程一天能重复成千上万次。如果一个买家参加多场拍卖，搜索引擎就可以通过他的历史报价记录来估计他的估值分布。如果报价数据足够多，则卖家依然能使用 Myerson's auction 来获得近似最优的收益[2]。卖家收益增加通常意味着买家效用减少。换句话说，通过“大数据杀熟”，卖家能从买家身上榨取更多利润。

但是买家甘心被宰吗？大数据杀熟有一个前提：报价数据必须真实刻画买家的估值分布。然而，当报价数据掌控在买家手中时，即使在 Myerson's auction 这样原本满足 truthful 性质的拍卖中，诚实报价 b_i = v_i 也未必是纳什均衡（纳什均衡即每个参与者在其他参与者的策略不变的情况下采用了最优策略的稳定状态）。因为卖家对分配和付费方案的选择与买家的分布有关，所以买家可以修改分布来影响卖家的决策，从而获得更高的效用。这就是我们希望研究的问题：

若搜索引擎使用历史报价来近似估值分布，

买家会采用怎样的报价策略？

卖家的收益又如何？

模型和结果

我们考虑了一个理想化的两阶段模型：首先卖家公布一个拍卖方案 M，比如 Myerson's auction，M 的分配和付费计算方式可以与估值分布有关；然后买家们提交一组分布 F₁^', …, F_n^'，具体来说，买家 i 根据某个报价函数 β_i: R₊ → R₊ 将估值 v_i ∼ F_i 映射到 b_i = β_i (v_i)，使得 b_i 的分布服从 F_i^'。买家 i 获得的广告位 q_j 和支付的费用 p_i 是由 (b₁, …, b_n) 和 (F₁^', …, F_n^') 决定的。卖家的收益是 p_i q_j 的和的期望，买家 i 的效用是 v_i q_j  – p_i q_j 的期望。

在这个模型中，F_i 是买家的私有信息，而 F_i^' 可被视为私有信息的代理。买家可以任意选择代理。在代理和拍卖方式的选择上，买家之间、买家与卖家之间形成了复杂的博弈关系。因此我们称这个模型为“私有数据代理博弈”（论文中为“私有数据操纵博弈，Private Data Manipulation game，PDM”）。

在私有数据代理博弈模型下，我们证明了：

Myerson's auction 与 Generalized First Price auction 等价。

Generalized First Price auction（GFP）是单物品最高价拍卖（first price auction）在搜索广告拍卖场景中的推广：在 GFP 中，卖家将广告主按照报价从高到低排序，不妨记为 b₁ ≥ ⋯ ≥ b_n，广告位也按点击率从高到低排序，q₁ ≥ ⋯ ≥ q_m。分配方案是：广告主1获得广告位1，广告主2获得广告位2，以此类推，广告主 min{n, m} 获得广告位 min{n, m}；每个广告主 i 为每次点击支付的费用 p_i 就等于他的报价 b_i。与 Myerson's auction 不同的是，GFP 本身不 truthful，且它的分配方案和费用计算方式与估值分布无关。所谓“等价”，是说在私有数据代理博弈中，在 Myerson's auction 和 GFP 各自的纳什均衡下，卖家获得相同的期望收益，每个买家的期望效用也相同。换句话说，搜索引擎没有必要从数据中还原分布后再运行所谓“收益最优”的拍卖——运行一个与分布无关的拍卖就足够了。这个等价性意味着：通过巧妙地选取代理分布，广告主挫败了搜索引擎的“剥削”行为，并在某些私有分布 F_i 下提高了自身的效用（比如 F₁, …, F_n 独立同分布时）。

Myerson's auction 与 GFP 等价的结论对任意一组分布 F₁, …, F_n 都成立。进一步地，在给估值分布加一些限制条件（如独立同分布）后，我们得出了 Myerson's auction 与 Generalized Second Price auction（GSP）和 VCG auction 也等价的结论（见Figure 1）。

讨论

技术上，我们在经典的收益等价定理（revenue equivalence theorem）的基础上，透过私有数据代理博弈这个新的视角，考察了 Myerson's auction 和 GFP、VCG、GSP 之间的等价性现象。我们还推广了 Tang & Zeng [3] 的“Myerson's auction 与 GFP 在只有一个广告位的拍卖中等价”的结论。

实际意义上，我们在重复的搜索广告拍卖这个实际场景里，讨论了机器学习中的激励问题（incentives in machine learning）——当机器学习算法的输出涉及训练数据提供方的利益时，数据提供方可通过修改数据来获利。我们相信私有数据代理博弈模型可以应用到其他实际问题。

参考文献

[1]R. B. Myerson, "Optimal Auction Design," Math Oper Res, doi: 10.1287/moor.6.1.58.

[2]C. Guo, Z. Huang, and X. Zhang, "Settling the Sample Complexity of Single-Parameter Revenue Maximization," in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, doi: 10.1145/3313276.3316325.

[3]P. Tang and Y. Zeng, "The Price of Prior Dependence in Auctions," in Proceedings of the 2018 ACM Conference on Economics and Computation, doi: 10.1145/3219166.3219183. 

WWW

国际万维网大会（the Web Conference，原名 WWW conference）是关于万维网（World Wide Web）的年度国际顶级会议（CCF A类），聚焦于万维网的演化、万维网相关技术的标准化，以及这些技术对社会和文化的影响。The Web Conference 2020 计划于4月20-24日在中国台北举行。

图文 | 林涛

EconCS@PKU

近 期 科 研 进 展

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。