具有事后投资回报率（ROI）约束的拍卖设计

《Artificial Intelligence》：Auction Design with Ex Post ROI Constraints

　　洪涛·吕 | 肖辉·贝 | 郑振哲 | 方武
山东大学与南洋理工大学的联合人工智能研究中心（C-FAIR），中国济南

**摘要**
受在线广告实际限制的启发，我们研究了对投资回报率（ROI）有约束的投标人的单参数拍卖设计——即获得价值与支付之间的目标最小比率。我们关注的是事后的ROI约束，这要求每个实现的价值配置都必须满足ROI条件。对于有ROI约束的投标人，我们首先提供了符合占优策略激励相容（DSIC）拍卖的分配和支付规则的全貌。特别是，我们表明，给定任何单调的分配规则，相应的DSIC支付应该是Myerson支付，并为每个投标人提供回扣以满足其ROI约束。此外，我们在一个温和的规则条件下，还确定了当物品出售给单个投标人时的最优拍卖结构。该结构包括一个随机分配方案和一口价支付规则，这与确定性的Myerson拍卖以及之前关于事前ROI约束的研究不同。最后，对于多个有ROI约束的投标人，我们研究了简单的拍卖设计，特别是确定性拍卖设计以及它们如何应用于赞助搜索拍卖。

**引言**
在线广告拍卖是许多IT公司的重要收入来源。近年来，每天都有数千万次广告拍卖实时进行，这个大规模且复杂的市场促使现代在线广告平台开发了自动竞价服务，允许广告商为他们的广告活动设定高级营销目标，然后代表广告商进行出价。在这些自动竞价场景中，广告商的财务约束（如预算和投资回报率（ROI）约束）在拍卖设计中变得至关重要。虽然针对预算受限投标人的拍卖在文献中已经被广泛研究[1][2][3]，但针对有ROI约束的投标人的拍卖设计仍处于起步阶段。广告商的ROI约束要求支付不能超过所获得广告价值的某个特定比例。换句话说，有ROI约束的投标人对获得的价值和支付之间有一个目标最小比率。与设置支付上限的预算约束不同，ROI约束建立了一个与分配价值线性相关的支付上限。先前的研究[4][5]已经证明，ROI约束比预算约束更符合现实世界的经验数据，本文旨在探索如何为有ROI约束的投标人设计具有良好激励和收入保障的拍卖。

现有关于有ROI约束的投标人拍卖设计的文献主要关注事前的ROI约束，这要求根据投标人的事先价值分布来期望ROI[4][6]。这种方法适用于每天参与大量拍卖且只关心每单位价值平均支出的广告商。然而，实际上，大多数广告活动都经历了“长尾现象”[7]，这意味着他们每天只收到几十次或更少的点击量。在这些条件下，具有事前ROI保障的拍卖可能会在一天内有不可忽视的概率违反这些广告活动的ROI约束。因此，在这项工作中，我们关注的是事后的或硬性的ROI约束，这确保了拍卖在任何实现的价值配置下都尊重投标人的ROI约束。这比事前的ROI约束要求更严格，也解决了当前拍卖设计方法的局限性。

在这项工作中，我们研究了针对事后ROI约束的投标人的真实和最优拍卖设计。我们沿用了经典的单参数机制设计设定，将投标人的价值视为私有信息，将目标ROI视为公共信息。在这个单参数环境中，ROI约束可以整合到目标函数中（详见第2节），从而得到一个转变后的效用模型：ui=Mivixi?pi，其中ui代表投标人i的效用，vi是价值，xi是分配数量，pi是支付金额。这里Mi≥1是目标ROI比率，这使得该模型与传统的准线性效用模型不同。我们展示了这个新效用模型与近年来出现的传统效用最大化模型和价值最大化模型[8][9]相关，后者将分配价值作为目标，而不减去支付金额。

我们首先研究了有ROI约束的投标人的真实拍卖的特征。与Myerson在单参数环境中对真实拍卖的特征描述相比，我们表明分配规则的单调性要求对于事后ROI约束的投标人仍然成立，但[10]中唯一的支付规则需要通过减去一个max项来进行修改，这可以解释为对所有较低估值的Myerson支付超过ROI约束部分的“回扣”。这是一个完整的特征描述，完全涵盖了所有有ROI约束的投标人的真实拍卖。这个结果可以使用与Myerson分析类似的技术来证明。它也可以从以下对支付规则的另一种解释中得出（我们稍后会详细说明）：注意，有ROI约束的投标人会为从分配中获得的值vixi分配一个权重Mi≥1，因此一个简单的方法是向投标人收取Mi倍的Myerson支付。然而，为了不违反个体理性（IR）条件，我们必须以小间隔逐步应用Myerson支付增量（乘以Mi），并在必要时在获得的价值处“限制”或截断支付金额。

接下来，我们转向最优（即收入最大化）拍卖设计。我们支付规则中的额外max项对最优拍卖设计提出了显著挑战，因为尚不清楚如何将其纳入之前文献中看到的修改后的虚拟价值函数。相反，我们专注于将单个物品出售给单个投标人的情况。我们的主要结果表明，在一个称为边际收益递减（DMR）1的温和规则假设下，向单个事后ROI约束的投标人出售物品的最优拍卖采用了一种随机方案。更具体地说，分配规则x(·)从一个一口价区间开始，其中支付始终与获得的价值相匹配，直到达到最高分配，之后x(·)变得固定。这一发现与经典的Myerson拍卖[10]以及之前针对有事先ROI约束的投标人的结果相反，在那些情况下，最优拍卖始终是确定性的。这意味着与许多关于多参数设置和某些单参数环境（包括公共预算[11]和风险厌恶[12][13]的最优机制设计的文献类似，包含Mi项的轻微泛化也可以导致随机最优拍卖。

然后我们关注多投标人的场景。对于单投标人的随机分配意味着任何扩展都可能非常技术性；因此，我们主要关注简单的拍卖，并展示了之前文献中为传统投标人建立的简单和近似最优拍卖也对有ROI约束的投标人具有近似保证。此外，对于在在线广告等实际应用中通常更受欢迎的确定性拍卖，我们发现，当有一个物品和多个有ROI约束的投标人时，最优确定性拍卖等同于Myerson拍卖。

最后，我们将我们的结果应用于在线赞助搜索拍卖的特定背景。在我们对有ROI约束的投标人的真实确定性赞助搜索拍卖的特征描述中，支付金额可以通过取阶梯式支付和临界价格支付中的最小值来确定。此外，我们还展示了当只有一个有限估值空间的有ROI约束的投标人时，可以使用动态规划算法高效计算最优确定性拍卖。

关于有ROI约束的投标人的拍卖研究主要有两个方向。第一个方向研究的是投标人的出价策略如何受到经典VCG或广义第二价格（GSP）拍卖[14][15][16][17][18][19][20]中ROI约束的影响。第二个方向，也是我们论文所遵循的，专注于有ROI约束的投标人的拍卖设计，这对许多在线广告平台[4][6][16][21][22][23][24][25][26]具有实际意义。在这条研究线中，与我们工作最相关的是[4]，该研究通过实证表明，在线广告中确实有一部分买家受到ROI约束。他们还迈出了朝向具有贝叶斯激励相容性（BIC）和事前ROI约束的投标人收入最大化拍卖设计的第一步，这些约束只要求预期满足ROI条件，这比事后ROI约束要宽松得多。他们证明了分配规则与Myerson拍卖非常相似，但是使用了修改后的虚拟价值函数。支付规则与ROI约束相关：如果ROI约束较低，以至于不具约束力，那么修改后的虚拟值就回到了传统虚拟值；如果ROI约束适中，那么机制就使用修改后的虚拟值；如果ROI约束较高，那么机制需要补贴投标人以确保他们的参与。值得注意的是，这种机制是确定性的。另一项最近的研究[6]考虑了价值或ROI约束是投标人私有信息的情况。他们还考虑了事前的ROI，但他们使用了不同的事前IC约束。对于公共ROI和私有估值的设置，他们发现尽管事前IC导致了比BIC更大的可行集，但最优机制正是上述[4]中所述的那一个。与这些工作不同，我们关注的是事后ROI约束，为每个可能的价值实现提供硬性的ROI保障。在[27][28]中，作者考虑了多阶段的事后ROI约束，并假设每个投标人在不同阶段保持固定的出价倍数，这与我们的问题完全不同。

一个特定的研究方向关注事后ROI约束的真实性的要求。Cavalllo等人在[22, Appendix A]中研究了与我们相同的效用函数，并研究了相应的支付规则。主要区别在于他们仅关注具有相同ROI约束的投标人的确定性机制，而我们考虑了随机机制领域中更一般的单参数设置。他们表明，确定性赞助搜索拍卖的真实支付规则是经典VCG和GSP机制的推广。我们在第5节中关于确定性拍卖的结果也将他们的结果推广到了非相同ROI约束的情况。Li等人[21]提出了一个关于ROI信息真实性的条件，基于此他们使用控制论工具提供了一个机制框架。他们将ROI约束作为私有信息，而不是价值，这导致了与我们的问题完全不同的问题。

我们在最优拍卖特征描述中使用的DMR假设在拍卖和动态定价文献[29][30][31][32]中得到了广泛讨论。这意味着函数ψ(v)?vf(v)+F(v)?1是非递减的，或者等价地，v·(1?F(v))是以价格p出售物品的预期收入，这是这个条件名称的来源。直观地说，许多常用的分布函数满足这个假设，例如均匀分布，以及任何具有有限支持和单调非递减密度的分布。DMR条件首次在[29]中为有预算约束的投标人提出。在[31]中，作者发现DMR条件在他们的情况下比传统使用的规则性概念[10]更为自然，因为DMR精确地消除了在价值空间中的熨平要求，而不是在分位数空间中。在[30]中，DMR得到了全面讨论，作者展示了在具有私人需求的多人设置下，DMR条件下的最优机制是确定性的。我们建议读者参考他们的工作以获取具体示例和更多讨论。

**初步**
我们考虑一个一般性的单参数拍卖环境，其中包含一个卖家和n个投标人N={1,2,...,n}。每位投标者i对每单位商品都有一个私人估值ti。我们用xi表示分配给投标者i的商品数量，用pi表示投标者i的支付金额。不失一般性，我们假设最大可能的分配量是ximax=1，并且该商品是不可分割的，即xi表示投标者i收到商品的概率。除了分配的价值外，每位投标者...

**DSIC拍卖的结构描述**
在本节中，我们介绍了具有事后ROI约束的DSIC拍卖的特性。这些结果推广了经典的Myerson引理[10]（对于传统效用模型，即Mi=1），该引理指出，在单参数环境中，一个机制是DSIC当且仅当其分配规则是单调的，并且支付方案遵循一个唯一规则。
**引理1 Myerson引理[10]**
对于Mi=1的传统投标者，一个单参数机制是DSIC当且仅当：
- **分配规则是单调的**

**单个投标者的最优拍卖设计**
在获得了具有ROI约束的设置下分配规则和支付函数的确切描述后，我们现在转向收益最大化拍卖设计。回想一下，在Myerson拍卖[10]以及之前的先验ROI约束设置[4],[6]中的工作，收益最大化问题被简化为最大化（修改后的）虚拟福利问题。不幸的是，具有事后ROI约束时，支付函数的描述（4）涉及...

**多投标者的拍卖设计**
正如我们所讨论的，具有ROI约束的投标者的最优拍卖可能涉及将单一物品出售给单一投标者的简单设置中的部分分配。换句话说，当物品不可分割时，需要概率分配来实现最优拍卖。一方面，这意味着任何扩展都可能非常技术性；另一方面，不幸的是，这在实际场景中（如在线广告）通常是不希望的。

**赞助搜索拍卖**
在本节中，我们研究了具有S个广告位的赞助搜索拍卖。赞助搜索拍卖可以被视为多物品环境的一种特殊情况。在赞助搜索拍卖中，每位投标者出价一个单一的价值bi，这代表了他们的“每次点击价值”vi，拍卖确定这些S个广告位的分配给哪些投标者以及相应的支付金额pi。注意，具有ROI约束的投标者仍然有一个“初始价值”ti=Mi·vi，如我们之前的定义所示。每个广告位s的...

**结论**
在本文中，我们讨论了具有事后ROI约束的投标者的最优拍卖设计。我们提供了DSIC拍卖和这种设置下单个投标者的最优拍卖的特征描述。我们展示了在具有ROI约束的投标者设置下，最优拍卖可能需要随机分配方案。我们还提供了关于多个具有事后ROI约束的投标者的简拍卖设计的几个结果。
在这个模型中还有几个重要的未解决的问题。

**生成式AI和AI辅助技术在写作过程中的声明**
在准备这项工作时，作者使用了GPT-4来改进语言。使用该工具后，作者根据需要对内容进行了审查和编辑，并对出版物的内容负全责。

**作者贡献声明**
- 孔涛（Hongtao Lv）：撰写——原始草稿、方法论、研究、概念化
- 贝晓辉（Xiaohui Bei）：撰写——审阅与编辑、验证、监督、研究
- 郑振哲（Zhenzhe Zheng）：撰写——审阅与编辑、监督、资金获取、概念化
- 吴帆（Fan Wu）：撰写——审阅与编辑、监督、资金获取

**利益冲突声明**
作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：
- 孔涛（Hongtao Lv）、郑振哲（Zhenzhe Zheng）和吴帆（Fan Wu）报告称获得了中华人民共和国科技部的财务支持。
- 孔涛（Hongtao Lv）、郑振哲（Zhenzhe Zheng）和吴帆（Fan Wu）报告称获得了国家自然科学基金的财务支持。
- 孔涛（Hongtao Lv）报告称获得了自然科学基金的财务支持。