最优实时报价策略

2022-5-9 13:29:15

最优实时报价策略*Joaquin Fernandez Tapia+，Olivier Guéant，Jean-Michel Lasry§摘要媒体购买机构的广告交易台越来越依赖复杂的算法来购买广告库存。特别是，实时竞价（RTB）算法在购买广告库存的整个过程中响应许多拍卖——通常是Vickrey拍卖——以最大化一个或多个关键性能指标（KPI）为目标。对于应用数学家来说，建立投标策略的公司所面临的优化问题是新的和有趣的。在本文中，我们介绍了一个随机最优控制模型，该模型解决了各种现实情况下的最优投标策略问题：在AudienceStregies框架下，给定现金量的库存最大化，给定现金量的转换/收购数量最大化，等等，拍卖序列由泊松过程建模，每次拍卖的拍价由服从几乎任何概率分布的随机变量建模。我们证明了最优投标是由一个Hamilton-Jacobi-Bellman方程描述的，并且通过使用流体极限可以得到几乎闭式的解。还提供了数值例子。关键词：实时竞价，Vickrey拍卖，随机最优控制，协凸分析，流体极限近似。1简介从一家公司发起广告活动的角度来看，数字广告的目标是通过利用不同的渠道来增加其投资回报，从而实现与潜在客户的互动：桌面显示、移动、社交媒体、电子邮件等。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:18

通常，这是通过品牌推广活动，通过寻找个人来实现的*作者要感谢多米尼克·德尔波特（Havas Media）、朱利安·劳格尔（MFG Labs）、皮埃尔·路易斯·利昂斯（法国学院）和阿尔诺家长（Havas Media）就这一主题进行的讨论。两名匿名裁判也应受到惩罚。+皮埃尔和玛丽·居里大学，概率和模型实验室（LPMA）。巴黎75005号朱西欧4号。Joaquin感谢2015年“经济与管理”主席的支持Ensae Crest，法国马拉科夫塞德斯92245号皮埃尔·拉鲁斯大道3号。哈瓦斯媒体科学顾问委员会成员。本文内容不反映官方观点或哈佛媒体的做法。通讯作者：奥利维尔。gueant@ensae.fr.§路易学士研究所。哈瓦斯传媒科学顾问委员会成员。本文内容并不反映哈瓦斯媒体的官方观点或做法。他们可能与给定的产品/活动有密切关系，或者通过驱使那些已经表现出某种兴趣的人进行最终转换（例如购买）。近年来，广告业经历了许多剧变：大量技术变革、大量新数据、大量广告科技初创公司进入市场等。特别是，新机制的出现，彻底改变了数字广告库存的购买方式。在实践中，投资通常是通过编程方式购买的，而且可以通过算法一个单元一个单元地购买，希望实现广告和媒体购买行业的最初承诺：在正确的时间，在正确的环境下，针对正确的人。在过去五年中，程序性媒体购买激增。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:22

尽管这些数据只能粗略估计，但据估计，2014年欧洲用于程序化桌面显示的净广告收入总额约为29亿欧元。对于程控移动显示和视频显示，图形分别为e 552m和e 205m——参见[15]。总体而言，2013年至2014年间，欧洲与programmaticmedia购买相关的净广告收入总增长率约为70%。IAB Europe在[15]中估计，所有格式的节目媒体购买收入占总收入的比例为两位数：台式显示器占39%，移动显示器占27%，视频显示器占12%。在美国，这一数字甚至更令人震惊，2014年，在台式机/笔记本电脑显示屏上的编程支出为58.9亿美元，在移动设备/平板电脑显示屏上的支出为44.4亿美元（来源：eMarketer.com）。节目媒体购买中最主要、最激动人心的发展之一是实时竞价（RTB）。RTB是购买数字库存的一种新模式：广告商可以通过实时拍卖购买在线库存，以显示横幅（或短视频）。这些实时拍卖使广告商能够以每次访问为目标锁定单个用户。简而言之，每次用户访问一个网站时，出版商（供应方）都会连接到一个虚拟市场，称为广告交换，以触发对每个可分配给广告的可用时段的拍卖。在需求端，广告交易平台接收拍卖请求（有时通过需求端平台——DSP），结合用户信息、网站类型等，选择最适合其策略的出价级别。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:25

一旦不同的出价被处理，该时段将归属于提出最高出价的投标人，支付的价格取决于拍卖的类型。从用户进入网站到显示横幅的整个过程大约需要100毫秒。RTB拍卖通常是Vickrey类型，也称为“二价拍卖”。简而言之，其机制如下：首先，参与者以密封的方式发送投标书，主要通过媒体机构等中介机构，但有时在设置交易台时也会自行发送投标书。然后，将物品（此处为槽）出售给提出最高出价的参与者，该参与者支付的价格对应于次优出价（如果只有一名参与者，则为最低价格）。从结构上看，Vickrey拍卖会鼓励参与者披露他们对该物品的真实估价——见[23]。广告交易台面临的问题是，每次收到参与Vickrey拍卖的请求时，都要选择最佳出价水平。在这里，根据考虑的关键绩效指标（KPI），最优可能有不同的含义。在所有情况下，问题的复杂性都源于需要在每小时、每天或每周的时间尺度上优化依赖于宏观量的函数，通过在每次拍卖的微观尺度上与系统交互，即通过高频/低延迟的出价算法参与每秒数千次拍卖。这种多尺度特性导致需要既真实又易于处理的数学模型，因为在多尺度问题的情况下，数值方法往往很麻烦且耗时。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:28

在这篇文章中，我们依赖于随机最优控制的方法，我们证明了最优投标策略可以用凸优化的经典工具非常精确地近似（并且几乎是封闭的）。除了关于Vickrey拍卖的经典文献（例如[7,17,23]）——与拍卖理论有关，更广泛地说与博弈论有关——之外，关于这类新问题的学术文献真的很少。从买方的角度来看，实时投标优化的一般方法主要可以在计算机科学界的会议记录中找到（例如[21,26]）。我们的方法与Amin等人[1]的工作类似：两者都是马尔可夫决策过程（MDP）方法，处理类似的拍卖问题。然而，除了他们模型的独创性，阿明等人没有将他们的数学发展扩展到基线离散情况之外。另一位作者在会议论文[25]中介绍了MDP方法，但他从出版商的角度关注了这个问题。总的来说，供给侧视角比需求侧视角产生了更多的学术研究（参见袁的博士论文[24]和Balseiro等人[3,4]的文章）。Stavrogiani博士论文[22]从abuyer的角度对RTB拍卖进行了最新研究。我们的随机最优控制方法受到算法阅读[2,13,14]中学术文献的启发，其中，与我们的问题类似，目标是根据算法的终端状态（例如，在一天结束时），通过在高频（即毫秒）的基础上不断做出决策，优化宏观函数。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

2022-5-9 13:29:31

此外，与涉及限价指令的高频交易模型一样，算法s应该对一个或多个受控泊松过程驱动的系统作出反应。在本文中——关于实时竞价的系列文章的第一篇，见[11]和[12]——我们用标记泊松过程对广告交易台收到的拍卖请求序列进行建模：泊松过程对请求的到达时间进行建模，尽管我们的拍卖请求是连续时间的，但标记对应。到独立随机变量（pn）n∈N*模拟要拍的价格，即拍卖中其他参与者提出的最高出价。每次收到拍卖时，算法都会向拍卖服务器发送出价b。对于第n次拍卖，当且仅当算法发送的出价大于吃pn的价格（在这种情况下，为插槽支付的价格为pn）时，通过算法购买库存。考虑这个统计模型而不是更复杂的博弈论模型的理由来自：（i）大多数细分观众的大量拍卖请求（每秒数百次），（ii）我们假设算法仅限于库存的一个同质子集（即，我们假设不同受众和背景的细分已经提前进行，或者换句话说，我们考虑的问题是战术“执行”层面的——另见[9,10]）。在第2节中，我们介绍了我们的建模框架的主要符号，并讨论了一个随机最优控制问题，其中广告交易者的目标是在给定的消费（受众策略）下最大化显示的横幅总数。我们用一个Hamilton-Jacobi-Bellman方程描述了最优投标策略的特征，并证明了最优投标策略可以通过流体极限近似得到almos t-闭形式。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:34

此外，这种近似导致投标策略以最优调度的形式出现新的特征，在实践中可以通过f反馈控制机制进行跟踪。主要结果确实是，预算应在考虑的时间窗口内平均支出。在第3节中，我们提出了模型的几个扩展。特别是，我们通过考虑几种库存来源和类型来推广初始模型，并考虑另一个目标函数来考虑一个非常重要的KPI：转换次数。在这些扩展中，正如在只有一个库存来源的初始模型中一样，我们发现总预算应该在考虑的时间窗口内平均使用——关于考虑在线学习时的不同结论，请参见[12]。然而，我们发现，不同来源的最优投标策略并不一致，而是与指数成正比，在多个来源和转换的一般情况下，指数是（i）每个来源/存货类型的先验利益，（ii）每个转换来源的先验利益，以及（iii）与每个来源相关的转换概率的简单函数。在第3节中，我们还讨论了第一价格拍卖和第二价格拍卖之间的差异、楼面价格的影响，以及更一般的非线性客观标准。特别是，通过假设其他参与者的最佳价格是一个外生变量，我们忽略了所有博弈理论影响，或者，等效地，市场参与者之间的所有战略互动。尽管我们在本论文中没有考虑这些方面，但考虑几个目标不同的因素——或平均场博弈设置中的连续代理人——并在我们模型的核心寻找重复拍卖博弈中的纳什均衡，将是非常有趣的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:37

这对于小部分特定观众的拍卖尤其重要。2受众策略模型在本节中，我们提出了一个模型，其中广告交易者希望在一个时间窗口[0，T]内支付给定数量的资金，以便向阿吉文人群显示最大数量的横幅。他从一个广告交易所随机收到拍卖请求，并且事先不知道他将收到多少拍卖请求。我们提出的模型自然是在连续时间内编写的，auctionrequests的（随机）出现是通过泊松过程的跳跃来建模的。附录中为更习惯离散时间马尔可夫决策过程的读者提供了一个简单的离散时间建模框架。2.1连续时间内的建模框架定义了一个概率空间(Ohm , F、 P）配备过滤（Ft）t∈R+满足通常的条件。我们假设所有随机过程都定义在(Ohm, F、（Ft）t∈R+，P）。拍卖：我们考虑一个与广告交易有关的广告交易商。他收到参加拍卖的请求，以便购买库存，并向他想要瞄准的特定人群展示一些横幅。请求用标记的泊松过程建模：请求的到达由强度λ>0的泊松过程（Nt）两次跳跃触发，标记（pn）n∈N*在每次拍卖中，与其他参与者出价中的最高出价相对应。每次他收到参加拍卖的请求时，广告交易人都可以出价：在时间t，如果他收到请求，那么我们用bt表示他的出价。我们认为广告交易人已经准备好出价（即等于0或0的出价）+∞) 任何时候。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:41

特别是，我们认为（bt）是一个可预测的过程，其值为R+∪ {+∞}.如果在第n次拍卖发生时，本次拍卖的结果如下：o如果bt>pn，则广告交易商赢得拍卖：他支付价格pn并展示横幅。o如果英国电信≤ 请注意，那么广告交易商不会赢得拍卖。特别是，交易者的屏幕没有显示，他不支付任何费用。广告交易者可能与多个广告交易有关，但在第一个模型中，我们假设他对来自不同广告交易的拍卖请求没有任何区别。在本文中，我们只考虑常数强度λ的情况。时间变化的拍卖强度可以通过时间的变化来处理，类似于[10]，其主要思想是从物理时间切换到交易时间。由于我们假设变量（pn）的分布是绝对连续的，因此不单独考虑等式情况——见下文。我们模型的一个重要假设是（pn）n∈N*i.i.d.随机变量是按照绝对连续分布分布的。我们用F表示关联的累积分布函数，用F表示关联的概率密度函数。我们的假设如下：N∈ N*, 这几乎肯定是积极的。特别地，F（0）=0.op>0，f（p）>0.o无力的→+∞pf（p）=0。剩余现金流程：我们用（St）t表示将要花费的现金量建模的流程。其动态为：dSt=-pNt{bt>pNt}dNt，S=\'S.（2.1）库存过程：印象的数量，i。e、显示的横幅数量由库存过程（It）t建模。其动态为：dIt=1{bt>pNt}dNt，I=0。随机最优控制问题：在本节的模型中，交易者的目标是最大化[0，T]上显示的预期横幅数量。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:45

我们应该规定支出不得超过，但出于技术原因，我们更愿意考虑一个宽松的问题，并惩罚额外支出。因此，我们考虑以下标准的最大化：EhIT- K min（ST，0）i，其中K衡量额外支出惩罚的重要性。出于数学原因，我们更愿意把随机最优控制问题写成最小化问题：inf（bt）t∈啊-IT+K min（ST，0）i，其中A是具有R值的可预测过程集+∪ {+∞}.该模型可以很容易（稍微）修改，以涵盖截断函数f的情况，即f等于给定价格水平以上的0。这个过程定义得很好，因为N∈ N*, pn∈ L(Ohm).特别是，我们将考虑极限情况K→ +∞ 作为一种观察当最高总开支被强加时会发生什么的方法。价值函数：为了解决这个随机最优控制模型，我们引入了价值函数u:（t，I，S）∈ [0，T]×N×N(-∞,\'S]7→ inf（bs）s≥T∈吃了-Ib，t，IT+K minSb，t，ST，0,其中Atis是[t，t]上的一组可预测过程，其值为R+∪ {+∞}, 和DSB，t，Ss=-pNs{bs>pNs}dNs，Sb，t，St=S，dIb，t，Is=1{bs>pNs}dNs，Ib，t，It=I.2.2随机最优控制问题的解2。2.1非标准HJB方程的表征为了解决上述随机最优控制问题，我们引入了相关的HamiltonJacobi-Bellman（HJB）方程，该方程对应于从动态规划原理在离散时间推导的Bellman方程（A.2）的连续时间等价物——见附录。这里的HJB方程是：- 图（t，I，S）- λinfb∈R+Zbf（p）（u（t，I+1，S）- p）- u（t，I，S））dp=0，（2.2）终端条件u（t，I，S）=-I+K min（S，0）。式（2.2）是一个非标准的积分微分HJB方程，类似于式。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:48

（A.2）。因为目标函数是变量I中的一个函数，所以可以通过考虑ansatz u（t，I，S）=-I+v（t，S）。有了这个安萨兹，等式（2.2）实际上变成：- 电视（t，S）- λinfb∈R+Zbf（p）（v（t，S）- p）- v（t，S）- 1） dp=0，（2.3），终端条件v（T，S）=K min（S，0）。为了避免本文过于技术化，我们将重点放在应用上，而不是对我们推导的积分微分贝尔曼方程进行数学分析。感兴趣的读者可以通过使用[5]中介绍的高级粘度技术，得出存在性和唯一性结果。值得注意的是，我们将通过流体极限来近似这个问题，经典的弱半凹解方法适用于这个问题——参见[6,8]。等价地，等式（2.3）可以写成-电视（t，S）- λinfb∈R+-F（b）+Zbf（p）（v（t，S）- p）- v（t，S））dp= 0.Eq.（2.3）是另一个非标准积分微分Hamilton-Jacobi-Bellman，但只有一个空间维度，而不是两个。很容易验证它是否对应于以下随机最优控制问题：inf（bt）t∈AE-λZTF（bt）dt+K min（ST，0）, （2.4）其中A是一组可预测的过程，其值以R为单位+∪ {+∞}.变量u（t，I，S）的变化-I+v（t，S）是降低问题维数的关键。为了理解基本原理，让我们注意到-u（t，I，S）是（直到惩罚条款）广告交易者在时间间隔[0，t]内预期购买的印象数量，如果在时间t，他已经购买了相当于I的印象数量，并且在[t，t]上有一个S的最佳花费金额。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-5-9 13:29:52

因为在[t，t]期间购买的印模数量并不取决于已经购买的印模数量，除非通过已经花费的预算——或者，相当于，尚未花费的预算——购买的印模数量-u（t，I，S）- 我应该独立于I.H.encethe ansatz u（t，I，S）=-I+v（t，S）。特别是数量-v（t，S）表示（直到惩罚期限）广告交易者在时间间隔[t，t]内预期购买的印象数量，如果他在时间t有一个S在[t，t]上的最佳花费。2.2.2我们需要超出等式（2.3）的原因从前面的段落中，可以认为问题几乎完全解决了。由于式（2.3）描述了最优投标策略，在系统的每个状态（t，S）中找到最优投标实际上可以归结为执行一个反向（单调）数值格式来近似式（2.3）的解。然而，值得注意的是，广告交易者面临的问题有两个层面：宏观层面是战术层面。这个尺度与时间范围和广告交易员在时间间隔内必须花费的现金量有关[0，T]。实际上，对于盘中战术，数量级在10到10之间- T为10秒（秒），在E10范围内- 10对于S.o微观尺度是每次拍卖的尺度，与强度λ以及变量b和p（在等式（2.3）的积分项中）有关。这些变量的数量级约为10秒-1对于λ，在范围e10内-5.- 10-2每次投标。如果想要在（t，S）中的网格上近似求解等式（2.3），时间步长t和现金/空间步骤S应与微观尺度兼容。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:29:56

如果我们认为广告活动构成了宏观规模，那么采用这种规模可能会被视为中观的。乍一看，这些值似乎很小。我们提醒读者，行业标准是衡量1000次印象（CPM，或每千次成本）的投标水平和价格。例如，对于给定的拍卖，如果一个从业者谈论出价为e1，那么实际上就是e10-3.考虑到拍卖请求的快速到达，自然时间步长是10点左右-4秒。就花费的现金而言，如果想要精确计算每次拍卖的最佳出价，那么S大约在E10左右-7，考虑到之前讨论的投标数量级。考虑到宏观尺度上考虑的数量级，我们需要考虑一个网格上的数值格式，该网格具有10- 10点时间和10点- 在太空中10点，这在计算上非常昂贵。尽管可以建立智能数值方法来避免网格中每个点的计算，但问题的多尺度性质在实践中是一个重要问题。避免使用计算机密集型数值方法的一种方法是寻找近似形式。正如我们将在下面展示的，这种近似可以通过在等式（2.3）的积分项中使用一阶泰勒展开来找到。2.3几乎封闭形式的近似解在本小节中，我们的目标是近似值函数v和由此产生的最优控制函数（t，S）7→ B*（t，S）对应于最优投标策略——后者的特征是V（t，St-- B*（t，圣-)) = v（t，圣-) + 1，（2.5）如果该方程有解，或通过b*（t，圣-) = +∞ 否则，即。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:00

如果我们在limS的案子里→-∞v（t，S）≤ v（t，圣-) + 1.我们在以下段落中获得的近似值的主要思想是替换术语v（t，S）-p）-式（2.3）中v（t，S）的一阶泰勒展开式-PSv（t，S）。因此，我们将等式（2.3）替换为：- 电视（t，S）- λinfb∈R+-Zbf（p）（1+p）Sv（t，S））dp=0。（2.6）终端条件v（T，S）=K min（S，0）。直观地说，由于问题的多尺度性质，该近似值是相关的：b的值范围应比S.2.3.1 A流体极限近似值在以下段落中的值小几个数量级，我们证明，公式（2.6）是与变分问题相关的H amilton-Jacobi方程，该变分问题可以被视为随机变量的流体极限，而不是公式（2.3）的数值解需要更多时间（秒、分钟等）的问题比授权向拍卖服务器发送出价的最长时间（毫秒）计算。实际上，该解决方案可以提前计算，然后嵌入内存中的查找表中，从而允许低延迟请求。在在线估计参数的情况下，这个问题更为关键——见[12]。下面将讨论这一点。我们在上一小节中考虑的最优控制问题。为此，让我们介绍以下优化问题：inf（~bt）t∈阿德特-λZTF（~bt）dt+K min~S~bT，0,式中yenSyenbt=-λG（~bt）dt，G:x∈ R+∪ {+∞} 7.→Zxpf（p）dp，其中Adetis是一组F-可测过程，其值为R+∪ {+∞}.与该问题相关的值函数＠v定义为：＠v（t，S）=inf（＠bs）S≥T∈阿德特-λZTtF（~bs）ds+K min~S~b，t，ST，0,式中dSb，t，Ss=-λG（~bs）ds，~S ~b，t，St=S。我们有以下定理：定理2.1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-5-9 13:30:05

让我们定义（x）=λsupb∈R+Zbf（p）（1+xp）dp=(-λxR-xF（p）dp，x<0λ1+xR∞pf（p）dp, 十、≥ 0.值函数v由以下公式给出：~v（t，S）=supx≤0Sx- （T）- t） H（x）-x4K.这是Hamilton-Jacobi方程（2.6）的唯一弱半凹解。此外，最优控制函数（t，S）7→~b*（t，S）由以下公式给出：o如果S≥ λ（T）- t） R∞pf（p）dp，然后b*（t，S）=+∞.o 如果S<λ（T）- t） R∞pf（p）dp，然后b*（t，S）=-十、*, w在这里x*其特征是s=（T- t） H′（x）*) +十、*2K。（2.7）证据。通过使用变量的变化as=λG（~bs）∈ I=[0，λR∞pf（p）dp]，我们有：~v（t，S）=inf（as）S≥T∈A′detZTtL（as）ds+K minbSa，t，ST，0, （2.8）其中A′det是一组F-可测过程，其值在I中，其中dbsa，t，Ss=-asds、bSa、t、St=S，其中函数L定义为：L:a∈ I 7→ -λFG-1.λ.L在I的内部是连续可微的，带有：L′（a）=G-1.′λF′G-1.λ= -FG-1.λG′G-1.λ= -G-1.λ.特别是，因为G是一个递增函数，所以L′是递增的，因此，L是严格凸的。现在让我们计算L:L的勒让德-芬切尔变换*（x） =苏帕∈伊克萨- L（a）=supb∈R+λxG（b）+λF（b）=λsupb∈R+Zb（1+xp）f（p）dp（2.9）=H（x）。如果x<0，则与等式（2.9）中的上确界相关的一阶条件为f（b*) （1+b）*x） =0。换句话说：x<0=> B*= -x、如果x是非负的，那么b*= +∞.在前一种情况下，我们可以写（通过使用部分积分）：H（x）=λsupb∈R+Zb（1+xp）f（p）dp=λZb*f（p）（1+xp）dp=-λxZ-xF（p）dp。因此L的Legendre-Fenchel变换是H，可以写成：H（x）=(-λxR-xF（p）dp，x<0λ1+xR∞pf（p）dp, 十、≥ 0.很容易检查H是一个两次连续可微凸函数。我们知道，从经典变分演算中，~v由Hopf-Lax公式给出：~v（t，S）=infy∈[S]-λR∞pf（p）dp（T）-t），S]（T）- t） Ls- yT- T+ K min（y，0）.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:08

（2.10）通过使用非理想卷积，我们可以将等式（2.10）转换为：~v（t，S）=supxSx- （T）- t） H（x）- supyyx- K min（y，0）= 好的Sx- （T）- t） H（x）- χR-（十）-x4K= 好的≤0Sx- （T）- t） H（x）-x4K. （2.11）这是该定理的第一个结果。此外，我们知道它是以下Hamilton-Jacobi方程的唯一弱半凹解：-t~v（t，S）+H(当终端条件为最小值K时，Sv（t，S））=0。这个等式与等式（2.6）完全相同，因此是定理的第二个断言。此外，修正问题（2.8）中的最优控制由A给出*（t，S）=H′(v（t，S））。简单的计算给出：H′（x）=（λR-xpf（p）dp=λG-十、, x<0λR∞pf（p）dp，x≥ 特别地，H′（0）=λR∞pf（p）dp。因为跛行→+∞pf（p）=0，函数H′与：H′（x）连续可微=(-λxf-十、, x<00，x≥ 因此，初始问题中的最优控制函数为：~b*（t，S）=(-Sv（t，S），v（t，S）<0+∞, S~v（t，S）≥ 0.如果是≥ （T）- t） H′（0）=λ（t）- t） R∞pf（p）dp，则等式（2.11）中的最大值达到atx*= 0.因此，S~v（t，S）=0和~b*（t，S）=+∞.否则，等式（2.11）中的最大值在x处达到*≤ 0的唯一特征为：S=（T- t） H′（x）*) +十、*2K。特别地，v（t，S）=x*和b*（t，S）=-十、*x在哪里*其特征是等式（2.7）。2.3.2最优投标策略的近似值及其解释定理2.1要求使用v作为v的近似值。然后，最优投标策略（b*t） t可近似为b*（t，圣-), 或者通过求解等式（2.5），其中v被v代替。在下面的内容中，我们考虑前一种方法。此外，我们考虑了K→ +∞.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:13

随后，我们近似得出最优报价b*时间t乘以b*∞（t，圣-), 函数b*∞定义为：o如果≥ λ（T）- t） R∞pf（p）dp，然后b*∞（t，S）=+∞.o 如果S<λ（T）- t） R∞pf（p）dp，然后b*∞（t，S）由以下公式得出：~b*∞（t，S）=-H′-1.装货单-T.为了理解上述结果，值得回顾一下∞pf（p）dp是要击败的平均价格，λ（T）- t）是在时间t和终端时间t之间，广告交易者将参与的预期拍卖次数。因此，λ（T）- t） R∞pf（p）dp是广告交易者为了赢得所有他收到请求的拍卖而出价的预期现金金额。因此，在我们的风险中性设定中，出价b是很自然的*∞（t，圣-) = +∞ 在时间t，如果剩余的花费金额-大于λ（T）- t） R∞pf（p）dp。如果圣-< λ（T）- t） R∞pf（p）dp，然后是近似值b*∞（t，圣-) 最优报价b*tveri fies：考虑到b值非常大，似乎与流体极限近似值相反。然而，事实并非如此，因为与预算S相比，每一次赢得的拍卖最终支付的价格仍然非常小，除非可能接近最终时间T。λ（T）- t） Z~b*∞（t，圣-)pf（p）dp=St-.为了理解这种投标策略，让我们考虑一下从时间t开始的情况，在有趣的情况下，即当-< λ（T）- t） R∞pf（p）dp。如果我们使用上述最优投标策略的近似值，剩余现金的动态为（0≤ T≤ s≤ T）：dSs=-pNs{b*∞（s，Ss）-)>pNs}dNs，St=S。因此：dE[Ss]=-E“λZb*∞（s，Ss）-)pf（p）dp#ds=-E[Ss]T- sds。这就给出了E[Ss]=ST-sT公司-T

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:17

换句话说，最优投标策略的近似值是这样的：平均而言，剩余的现金在[t，t]上平均花费。前面分析的一个主要结果是，最优性不仅体现在最优出价上，还体现在预算支出的速度上。后者在实施方面很有帮助。事实上，通过优化曲线（也称为预算调整，见[10]）定义解决方案，可以通过跟踪目标曲线的反馈控制系统动态控制投标，而不依赖于函数f的形式。从这个角度来看，对最优投标函数的确切了解就不再必要了。然而，该分析基于流体近似。随后，只要拍卖请求的数量足够大，它就有效。对于关注库存小部分的受众策略（例如，仅针对少数客户、将策略限制为优质库存、为非常特定的横幅格式购买慢货等），需要初始随机控制问题解决方案的数值近似值。2.4数值示例我们给出一个数值示例f或一个在100秒内花费e1的算法。由于该算法的高频率特性，考虑到更大的时间框架和更大的预算，从数学角度来看并不会产生重大差异。注意，支出率(~ 考虑到我们的问题，e 500/天——尽管考虑到整体广告预算的规模，它可能很小——是现实的：我们正专注于一种算法，该算法已经局限于特定的频道、观众和库存子集。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:21

实际上，广告交易台通过一系列算法（如本文所示）动态分配一天的总预算。在拍卖请求到达率随时间变化λt的情况下，一个类似的变分问题solvedin[10]表明，最优策略是按λt的比例支出。在这种情况下，网格的大小可以减小，因为λ很小。多个投标算法之间的总体预算优化分配超出了这项工作的范围。然而，我们可以将第3节的扩展视为解决这个问题的一种方式。自然的。4.1 v和b的数值近似*在我们的数值实验中，我们假设要拍的价格分布是参数为u的指数分布，即f（p）=ue-up。我们选择u=2·10e-1，这与e0.5级的CPM一致。我们在图1中表示HJB方程（2.3）解v的数值近似值。如上所述，数量-v（t，S）可以被解释为（直到惩罚时间），当t时的剩余预算为S.S（剩余现金）0.00.20.40.60.81.0t（时间）0204060100-v（t，S）020000400060008000010001200016000018000图1：HJB方程（2.3）的解时，analgorithm按照最佳策略从t时购买的预期印模数。λ=500秒-1，T=100s和‘s=e1。在求解HJB方程（2.3）时，最重要的计算量是最优控制，即最优投标函数（t，S）7→ B*（t，S）。该函数如图2所示。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-5-9 13:30:24

因为当t→ T，我们更喜欢以b的10为底的对数*（t，S）。图2中绘制的最优出价与直觉一致：剩余预算越高，离终点时间越近，最优出价越高。另一种方法是使用[18,19,20]中提出的多武装强盗算法。帕累托分布或极值分布也是相关的选择。为了数值逼近HJB方程（2.3）的解v，我们考虑了（t，S）网格上的一种向后时间显式格式。极小值b*通过使用一阶条件（2.5）（以及连续点之间的精确近似值）在网格的每个点处找到。然后，通过在网格的连续点和f.s（剩余现金）0.00.20.40.60.81.0t（时间）020406080100Log（投标）的指数形式之间使用v的有效近似值，用封闭式公式近似积分-4.-3.-2.-1012图2：日志（b）*（t，S）b的单位*是千分之一欧元）。λ=500秒-1，T=100沙S=e1.2.4.2模拟流体极限近似的一个结果是平均支出率应该是恒定的。一个重要的问题是，当使用通过求解HJB方程（2.3）获得的最优投标策略时，这一特征是否也成立。为了回答这个问题，我们通过绘制拍卖请求发生的时间和每次拍卖的价格（使用与上述相同的参数集）进行了模拟。图3、图4和图5显示了不同时间窗口的结果（我们从100秒放大到10秒，再放大到1秒）：剩余的现金流程绘制在左侧面板中，压缩的数量绘制在右侧面板中。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:28

对于我们考虑的参数的（现实）值，很明显，预算是线性花费的。我们还对较小的λ值（λ=2 s）进行了模拟-1） -也就是说，在流动性较低的市场中，拍卖请求的数量较少-以测试通过流动极限近似获得的定性结果的稳健性。在图6中，我们绘制了HJB方程（2.3）的解v和相关的最优报价（对数）。在图7中，我们绘制了与新参数值对应的模拟结果。如上所述，我们看到支出率会发生变化，但与交易期间的平均支出相对应，仍然保持在一个常数左右。0 20 40 60 80 100次。00.20.40.60.81.0剩余现金0 20 40 60 80 100时间020000400060008000001200014000库存图3：在100秒的时间窗口内，以数字方式计算的最优投标策略的剩余现金流程（左）和库存流程（右）。60 62 64 66 68 70次。320.340.360.380.400.42剩余现金60 62 64 66 68 70时间8000820084008600880090009200库存图4：以数字计算的最佳投标策略的剩余现金流程（左）和库存流程（右）——放大10秒。62.0 62.2 62.4 62.6 62.8 63.0倍。3940.3960.3980.4000.4020.404剩余现金62。0 62.2 62.4 62.6 62.8 63.0时间81808200822082408226082808300库存图5：以数字计算的最优投标策略的剩余现金流程（左）和库存流程（右）——放大1秒。s（剩余现金）0.00.20.40.60.81.0t（时间）020040006008001000V（t，s）050100015002000S（剩余现金）0.00.20.40.60.81.0t（时间）020040006008001000log（投标）-4.-3.-2.-1012图6:HJB方程（2.3）（左面板）和最优投标日志（b）的解*（t，S））（右面板）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:31

λ=2秒-1，T=1000 s和‘s=e1.0 200 400 600 800 1000time0。00.20.40.60.81.0剩余现金0 200 400 600 800 10000Time050100015002000库存图7：以数值计算的最优投标策略的剩余现金过程（左）和库存过程（右）。λ=2秒-1，T=1000 s和¨s=e1.3扩展和关于模型的讨论在本节中，我们介绍了第2节中介绍的模型的两个重要扩展。第一种是多源扩展：我们考虑拍卖请求来自多个广告交换（或来自同一个广告交换，但来自不同类型的受众），具有不同的频率和不同的价格规律的情况。第二个扩展与转换有关：除了购买的印象数量，adtrading交易台通常将转换数量视为KPI，这更符合发起广告活动的品牌或公司的投资回报目标。对于这两种扩展，我们表明问题仍然存在于维度2（变量改变后），即使状态空间的维度随着源的数量成比例增加，并且在考虑转换时几乎翻了一番。除了这两个扩展之外，我们还讨论了该模型的许多特性。特别是，文中讨论了Vickrey拍卖和一价拍卖之间的差异，以及几种类型的底价的存在。最后讨论了关键绩效指标，因为在第2节的模型和下面介绍的两个扩展中，维度降低与目标函数的线性度（直到惩罚项）有关。3.1引入拍卖中的异质性要求我们考虑的第一个扩展侧重于可以从不同来源购买库存的情况，即：。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:35

不同的广告交流，或者只是不同类型的受众。这种异质性来自于拍卖请求到达的频率、与每个来源相关的待拍价格的分布，或目标函数中每种存货类型的相对重要性的差异。一个重要的情况是，在不同的广告交易中，库存是同质的，而差异仅在于拍卖的统计特性。在这种情况下，我们表明——在流体限制的情况下——各场馆的最优出价是相同的，这与[9]中得到的结果一致。然而，当受众是异质的时，我们表明，作为目标函数中对不同类型受众的相对重要性的函数，最优出价从一个来源到下一个来源是不同的。3.1.1模型的设置在下文中，我们仍然考虑希望在一个时间窗口[0，T]内花费给定金额的广告交易员。拍卖：这个广告交易者连接到J>1来源，他从中收到参与拍卖的请求，以便购买库存——我们假设交易者知道每个拍卖请求来自哪个来源。请求用带有J标记的泊松过程建模：来自源J的请求的到达∈ {1，…，J}由强度λJ>0的过程（Njt）上的泊松跃变和标记（pjn）n触发∈N*对于来源j发送的每个拍卖请求，将其对应于其他参与者发送的最高出价。每次他从来源j收到参加拍卖的请求时，广告商人都可以出价：在时间t，如果他收到来源j的请求，那么我们将他的出价表示为bjt。在只有一个来源的模型中，我们假设广告交易者准备好出价（可能是等于0或0的出价）+∞) 任何时候。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:38

特别是，我们假设在这个扩展和下一个扩展中，上标j∈ {1，…，J}指定源，而不是指数。J∈ {1，…，J}，过程（bjt）是一个具有R值的可预测过程+∪ {+∞}.如果在时间t发生与源j相关的第n次拍卖，则该拍卖的结果如下：o如果bjt>pjn，则广告交易商赢得拍卖：他支付价格pjn，并展示其横幅。o如果bjt≤ pjn，然后另一个交易者赢得了拍卖。就像在只有一个源的模型中一样，我们假设∈ {1，…，J}，（pjn）n∈N*i.i.d.随机变量是按照绝对连续分布分布的。我们用fj表示累积分布函数，用fj表示与源j相关的概率密度函数。如上所述，我们假设每个j∈ {1，…，J}，即：N∈ N*, 这几乎肯定是积极的。尤其是Fj（0）=0.op>0，fj（p）>0.o无力的→+∞pfj（p）=0。我们还假设随机变量（pjn）j∈{1，…，J}，n∈N* 他们都是独立的。剩余现金流程：如上所述，我们用（St）t表示将要花费的现金量建模的流程。其动态为：dSt=-JXj=1pjNjt{bjt>pjNjt}dNjt，S=`S。库存流程：针对每个j∈ {1，…，J}，与源J的拍卖请求相关联的印象数量由库存过程（Ijt）t建模∈ {1，…，J}，（Ijt）tis的动力学：dIjt=1{bjt>pjNjt}dNjt，Ij=0。为了简化说明，我们编写它=（It，…，IJt）∈ 我们写下过程的动力学（It）t:dIt=JXj=1{bjt>pjNjt}dNjtej，其中（e，…，eJ）是RJ的规范基础。随机最优控制问题：在模型的第一个扩展中，交易者的目标是最大化αIT+…+形式的指标的期望值αJIJT，α。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:42

，αJ≥ 0.如第2节所述，我们考虑了一个对额外支出进行惩罚的宽松问题：inf（bt，…，bJt）t∈阿杰-JXj=1αjIjT+K min（ST，0）.3.1.2 HJB方程：从尺寸J+2到尺寸2，与该问题相关的值函数为：u:（t，I，S）∈ [0，T]×NJ×(-∞,\'S]7→ inf（bs，…，bJs）s≥T∈阿杰特-JXj=1αjIjTb，t，Ij+K minSb，t，ST，0,其中dsb，t，Ss=-JXj=1pjNjs{bjs>pjNjs}dNjs，Sb，t，St=S，dIjsb，t，Ij=1{bjs>pjNjs}dNjs，Ijtb，t，Ij=Ij，J∈ {1，…，J}。相关的汉密尔顿-雅可比-贝尔曼方程为：- 图（t，I，S）-JXj=1λjinfbj∈R+Zbjfj（p）（u（t，I+ej，S）- p）- u（t，I，S））dp=0，（3.1）终端条件u（t，I，…，IJ，S）=-PJj=1αjIj+K min（S，0）。式（3.1）是一个非标准的J+2维积分微分H-JB方程，它推广了式（2.2）。在只有一个来源的情况下，我们可以考虑ansatz theformu（t，I，…，IJ，S）=-JXj=1αjIj+v（t，S）。有了这个安萨兹，等式（3.1）实际上变成：- 电视（t，S）-JXj=1λjinfbj∈R+Zbjfj（p）（v（t，S）- p）- v（t，S）- αj）dp=0，（3.2），终端条件v（T，S）=K min（S，0）。公式（3.2）是另一个HJB方程，但在维度2中，它推广了公式（2.3）。3.1.3流体极限近似在只有一个源的模型中，可以用数值方法近似求解toEq。（3.2）并随后确定最佳投标策略。然而，有趣的是，考虑替换项v（t，S）所产生的近似值- p）- v（t，S）inEq。（3.2）通过其一阶泰勒展开式-PSv（t，S）。因此，我们将等式（3.2）替换为：- 电视（t，S）-JXj=1λjinfbj∈R+-Zbjfj（p）（αj+p）Sv（t，S））dp=0，（3.3），终端条件v（t，S）=K min（S，0）。情商。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:47

（3.3）与上述随机最优控制问题的流体极限有关，其定义为：inf（~bt，~bJt）t∈阿杰德特-JXj=1λjαjZTFj（~bjt）dt+K min~S~bT，0,式中yenSyenbt=-JXj=1λjGj（~bjt）dt，Gj:x∈ R+∪ {+∞} 7.→Zxpfj（p）dp。与此问题相关的值函数v是：v（t，S）=inf（bs，bJs）S≥T∈阿德特-JXj=1λjαjZTtFj（~bjs）ds+K min~S~b，t，ST，0,式中dSb，t，Ss=-JXj=1λjGj（~bjs）ds，~Sb，t，St=S。使用与定理2.1相同的技术，我们可以证明以下定理：定理3.1。让我们来定义J∈ {1，…，J}，Hj（x）=λjsupbj∈R+Zbjfj（p）αj+xpdp，and H=H+…+HJ。值函数v由以下公式给出：~v（t，S）=supx≤0Sx- （T）- t） H（x）-x4K.这是Hamilton-Jacobi方程（3.3）的唯一弱半凹解。此外，最优控制函数（t，S）7→~b*（t，S）由以下公式给出：o如果S≥PJj=1λj（T- t） R∞pfj（p）dp，然后：J∈ {1，…，J}，~bj*（t，S）=+∞.o 如果S<PJj=1λj（T- t） R∞pfj（p）dp，然后：J∈ {1，…，J}，~bj*（t，S）=-αjx*,x在哪里*其特征是s=（T- t） H′（x）*) +十、*2K。（3.4）证据。通过使用变量的变化ajs=λjGj（~bjs）∈ Ij=[0，λjR∞pfj（p）dp]，我们有：~v（t，S）=inf（as，…，aJs）S≥T∈A\'det，我，。。。，IJZTtJXj=1Ljajsds+K分钟bSa，t，ST，0, （3.5）其中A′det，I，。。。，ij是一组F-可测过程，其值在I×。×IJ，其中dbsa，t，Ss=-as+…+aJsds，bSa，t，St=S，其中，f或所有j∈ {1，…，J}，函数lji定义为：Lj:aj∈ Ij7→ -λjαjFjGj-1.ajλj.一种写Eq的等效方法。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:50

（3.5）is:＠v（t，S）=inf（as）S≥T∈A′detZTtL（as）ds+kminˇSa，t，ST，0, （3.6）其中A′det是一组F-可测过程，其值为I=[0，PJj=1λjR∞pfj（p）dp]，其中Sa，t，Ss=-asds，ˇSa，t，St=S，其中l:a∈ I 7→ inf（a，…，aJ）∈我×。。。×IJ，a++aJ=aJXj=1Ljaj.在定理2.1的证明中，LJI是一个凸函数，在Ij的内部连续可微。现在让我们计算Lj:Lj的勒让德-芬切尔变换*（x） =supaj∈Ijxaj- Lj（aj）=supbj∈R+λjxGj（bj）+λjαjFj（bj）=λjsupbj∈R+Zbj（αj+xp）fj（p）dp（3.7）=Hj（x）。在定理2.1的证明中，我们可以很容易地在等式（3.7）中找到上确界：o如果x<0，那么bj*= -αjx，和hj（x）=λjZ-αjx（αj+xp）fj（p）dp=-λjxZ-αjxFj（p）dp.o如果x是非负的，那么bj*= +∞, andHj（x）=λjαj+xZ∞pfj（p）dp.尤其是，HJ是一个C函数。通过使用非理想卷积，函数L是凸的，其勒让德变换isH=H+…+HJ。从式（3.6）中，由Hopf-Lax公式得出＠v（t，S）=infy∈[S]-PJj=1λjR∞pfj（p）dp（T）-t），S]（T）- t） Ls- yT- T+ K min（y，0）.等价地，通过非理想卷积，我们得到：~v（t，S）=supxSx- （T）- t） H（x）- supyyx- K min（y，0）= 好的≤0Sx- （T）- t） H（x）-x4K. （3.8）这是该定理的第一个结果。此外，我们现在知道v是f Ollowinghilton-Jacobi方程的唯一弱半凹解：-t~v（t，S）+H(当终端条件为最小值K时，Sv（t，S））=0。这个等式与等式（3.3）完全相同，因此是定理的第二个断言。此外，修正问题（3.6）中的最优控制由以下公式给出：*（t，S）=H′(v（t，S））。因此，根据关于非理想卷积的经典结果，修正问题（3.5）中的最优控制如下所示：J∈ {1, . . .

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-9 13:30:55

，J}，aj*（t，S）=Hj′(v（t，S））。我们得出结论，初始问题的最优控制函数为：~bj*（t，S）=(-αjSv（t，S），v（t，S）<0+∞, S~v（t，S）≥ 0.如果是≥ （T）- t） H′（0）=PJj=1λj（t- t） R∞pfj（p）dp，则等式（3.8）中的上确界在x处*= 0.因此，v（t，S）=0和J∈ {1，…，J}，~bj*（t，S）=+∞.否则，等式（3.8）中的最大值在x处达到*≤ 0的唯一特征为：S=（T- t） H′（x）*) +十、*2K。特别地，v（t，S）=x*和J∈ {1，…，J}，~bj*（t，S）=-αjx*x在哪里*由式（3.4）表征。按照与第2节相同的推理，我们近似得出最优报价b1*T北京*通过使用流体极限近似和极限情况下的最优出价，计算时间t→ + ∞ . 换句话说，我们近似于最优出价b1*T北京*t时间t乘以b1*∞（t，圣-), . . . ,~bJ*∞（t，圣-), 其中函数（~bj）*∞)jare定义人：o如果≥PJj=1λj（T- t） R∞pfj（p）dp，然后：J∈ {1，…，J}，~bj*∞（t，S）=+∞.o 如果S<PJj=1λj（T- t） R∞pfj（p）dp，然后：J∈ {1，…，J}，~bj*∞（t，S）=-αjH′-1.装货单-T. （3.9）最优投标策略的这种近似值得注意。首先，案例分析-≥PJj=1λj（T- t） R∞pfj（p）dp与单源情况相同。pjj=1λj（T- t） R∞pfj（p）dp表示如果广告交易者赢得所有参与的拍卖，则在时间t和时间t之间将花费的预期金额。因此，很自然地，如果花费的金额足够大的话，就会发出很高的出价，以确保赢得所有的作品-大于该值。第二，如果圣-<PJj=1λj（T- t） R∞pfj（p）dp，然后我们从等式（3.9）中看到，根据权重（αj）j，投标从一个来源到另一个来源：j、 j′∈ {1，…，J}，~bj*∞（t，S）αj=~bj′*∞（t，S）αj′。特别是，如果一个人只对印象的总数感兴趣，即。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝