TheWebConf 2024 Oral｜不确信先验下的受预算约束拍卖：策略等价性与结构性质

关键词：不确信先验，受预算约束拍卖，策略等价性

导  读

本文是对 The Web Conference 2024 会议上发表的论文 Budget-Constrained Auctions with Unassured Priors: Strategic Equivalence and Structural Properties 的解读。此工作入选会议的 oral 论文。

本论文由北京大学邓小铁课题组与腾讯广告等合作完成，邓小铁课题组博士生陈炤桦为第一作者。论文探讨了不同的受预算约束的拍卖机制在买家先验不确信时的策略等价性以及各自的结构性质。

← 扫码跳转论文

论文地址：

https://arxiv.org/abs/2203.16816

01

背  景

我们考虑广告商受到预算约束的广告拍卖市场。在这一场景中，站在广告平台的角度，为了最大化平台的收益并保证广告商的花费不超出预算约束，其会对拍卖机制中的参数进行一定程度的调节；而与此同时，广告商则会策略性地出价。值得注意的是，站在机制的角度，其无法看到广告商的真实估价，而只能看到其出价。

在经典的拍卖理论中，解决这一信息壁垒的方式是设计促真的（truthful）拍卖机制，如 Myerson 拍卖。然而，在今天，由于广告商受到多种因素的共同影响（如，受到各类约束、同时在多个平台上竞价、有内在动力不诚实出价等），这一类拍卖机制往往形式过于复杂，且难以获得预想中的效果。所以，必须接受的事实是，广告平台所看到的出价分布和其实际的价值分布很可能并不相同。我们旨在探索在这一前提下不同受到预算约束的拍卖机制之间的关系。

02

模  型

在这一工作中，我们考虑贝叶斯设定，即物品对买家  的价值  独立服从于分布  。同时，我们假设买家  的公开预算为  ，任何买家在期望意义上的花销不能超出其预算。在此限制下，买家的效益（utility）为其获得的物品价值与支付的差。对于卖家而言，我们假设其有一个正的机会成本  。卖家卖出一个物品的收益（revenue）是其从所有买家处获得的支付的和与  的差。同时，我们假设每个买家  拥有一个确定性的将物品价值映射到出价的函数，即将价值  映射为出价   。对于分配规则关于出价单调的拍卖机制而言，我们可以不失一般性地假设这一出价函数也是关于物品价值单调的。这一出价函数将买家的物品价值分布映射为一个出价分布。

在这一模型下，我们要求拍卖机制满足以下两个基本性质：

• 预算可行性（budget-feasibility），即在任何出价分布下，机制均保证每个买家的期望花销不超出预算。当然，机制本身是受到全体买家出价分布和预算的影响的，这一点由下面提到的机制中的参数实现。 

• 个体理性（individual rationality），即当买家诚实出价时，其效益非负。

为了对我们的动机进行建模，我们考虑了以下的介于卖家和全体买家的博弈场景，称为（带预算限制的）不确信先验博弈（unassured prior games with budget constraints）：  

1. 卖家首先确定一个参数化的拍卖机制  ，其中  为待定参数，由全体买家的行为确定。这一机制应保证预算可行性和个体理性。

2. 全体买家汇报其出价分布（策略）以及其真实预算（公开信息），其价值分布为私有信息。

3. 根据买家的汇报相应计算拍卖机制的参数  。

4. 全体买家获得各自的期望效益，卖家获得其期望收益。

03

机  制

在这一工作中，我们考虑了五种拍卖机制，这五种机制均将卖家的机会成本  作为底价。具体机制分别如下： 

1. 折价一价拍卖（bid-discount first-price auction，BDFPA）：其中每个买家  对应一个参数  ，买家  获胜仅当 获胜买家  的支付为  。

2. 配速一价拍卖（pacing first-price auction，PFPA）：其中每个买家  对应一个参数  ，买家  获胜仅当获胜买家  的支付为  。

3. 最优拍卖（Bayesian revenue-optimal auction，BROA）：由 Balseiro et al. (2017) 给出，是满足促真性的拍卖中为卖家带来收益最大的拍卖机制。其中每个买家  对应一个参数  ，买家  获胜仅当 这里  为买家  的虚拟出价函数（virtual bid function）。获胜买家  的支付为   为以下优化的解： 

4. 折价二价拍卖（bid-discount second-price auction，BDSPA）：其中每个买家  对应一个参数  ，买家  获胜仅当 获胜买家  的支付为  。

5. 配速二价拍卖（pacing second-price auction，PSPA）：其中每个买家  对应一个参数  ，买家  获胜仅当 获胜买家  的支付为  。

站在卖家的角度，其当然希望最大化自己的期望收益。为达到这点，一个直觉是，卖家希望在不违反个体理性的前提下尽可能花完每个买家的预算。为此，我们考虑预算抽取性（budget-extracting）条件。这一条件由 Balseiro et al. (2017) 提出，在该文章中被称为市场均衡（market equilibrium）条件，具体如下： 

预算抽取性，即对于任何买家，如下两条件均满足且至少有一个条件为紧：

• 买家的期望支付不超出其预算。

• 买家的参数不超过其上界。

预算抽取性是一个相当理想的性质，事实上，最优拍卖 BROA 是满足这一性质的。此外，我们证明了以下关于预算抽取性存在性和最优性的结果：

• 在一定正则性条件下，BDFPA 和 PFPA 都存在满足预算抽取性的机制。

• 当所有买家均对称时，在上述正则性条件下，BDSPA 和 PSPA 都存在满足预算抽取性的机制。

• 对 BDFPA、PFPA 和对称的 PSPA 而言，在上述正则性条件下，满足预算抽取性的机制均能最大化卖家的收益。

从而，站在卖家的角度，选择满足预算抽取性的机制是比较优的，故我们接下来只考虑满足这一性质的机制，并考虑买家的行为。

04

策略等价性

我们考虑不同机制所对应的不确信先验博弈的关系。为了避免过多的术语，这里仅给出我们得到的最关键结果：

• 在一定的正则性条件下，最优拍卖 BROA 和满足预算抽取性的 BDFPA 所对应的不确信先验博弈拥有相同的纳什均衡结果（Nash equilibrium outcome）集。

• 当所有买家均对称时，在一定的正则性条件下，满足预算抽取性的 BDFPA、PFPA、BDSPA、PSPA 所对应的不确信先验博弈拥有相同的结果集。

其中，第一个结果是重要的。最优拍卖拥有相当复杂的形式，而 BDFPA 的形式相当简单。这一结果说明了，在先验不确定的情况下，选择简单拍卖和复杂的最优拍卖的效果是相同的。从而，在实际场景中，广告平台方并不需要采取复杂的最优拍卖，而只需要采取一价拍卖即可。

05

结构性质

我们进一步考虑了这些机制，特别是一价拍卖机制的结构性质。为了便于理解，我们仅阐述大致结果： 

在一定正则性条件下，对于 BDFPA 而言：

• 所有满足预算可行性的参数向量选择中存在一个每一维都是最大的参数向量。

• 上述最大的参数向量满足预算抽取性。

• 所有满足预算抽取性的机制为买家带来的支付是固定的。

• 满足预算抽取性的参数向量是一个凸函数的全局最小解。

• 此外，我们对全体满足预算抽取性的 BDFPA 参数选择进行了详细的刻画。

在一定正则性条件下，对于 PFPA 而言：

• 所有满足预算可行性的参数向量选择中存在一个每一维都是最大的参数向量。

• 上述最大的参数向量是唯一满足预算抽取性的参数向量。

另外，我们考虑了当所有买家都采取诚实出价时不同机制为卖家带来的收益的比较，结果如下：

• 在一定正则性条件下，满足预算抽取性的 BDFPA 优于最优拍卖 BROA。

• 在一定正则性条件下，满足预算抽取性的 BDFPA 优于满足预算抽取性的 PFPA。

• 在一定正则性条件下，最优拍卖 BROA 优于满足预算抽取性的 BDSPA 和 PSPA。

06

总结及展望

我们的工作探究了在不确信先验下不同受预算约束拍卖机制之间的关系，对这些拍卖机制，尤其是一价拍卖机制提供了比较全面的刻画与理解。我们的工作留下了一些未解决的问题，如：

• 买家是否有动机谎报自己的预算限制，以及此种情况下策略等价性结果是否依然成立。

• 我们的结果是否能延展到非完全贝叶斯的场景下，如有上下文的（contextual）场景中。

• 当要求预算限制事后（ex-post）满足时，能否得到相应的结果。

参考文献：

Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget management strategies in repeated auctions. In Proceedings of the 26th International Conference on World Wide Web, 2017.

图文 | 陈炤桦

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

↑↑扫码转实验室主页↑↑

实验室 PI 简介：邓小铁 讲席教授

实验室相关新闻：#PKU daGAME

daGAME近期动态

• CSR 2024 | 有限正则博弈纳什均衡算法综述

• AAAI 2024 | 重复二价拍卖中的动态预算节流方法

• NeurIPS 2023 Spotlight | 仿射最大化拍卖机制设计的可拓展神经网络方法

• ICML 2023 | 重复二价拍卖下有预算约束的协同竞价在线算法

—   版权声明  —

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

点“阅读原文”转论文链接