近年来，伴随着广告主的需求变化和相关技术发展，计算经济学理论、博弈论和人工智能技术被越来越多地应用到广告拍卖机制、投放策略中。
决策智能在商业场景中的意义逐渐凸显。用户看到的每一次商品展现、商家的每一次广告出价、平台的每一次流量分配，背后都有庞大且复杂的决策智能做支撑。
这些动作的目标在于优化用户购物体验，让广告投放的决策过程更加智能，同时让广告主、媒体在平台实现长期繁荣。广告主希望在有限的资源投入下最大化营销效果，平台希望能够建立更好的生态。然而流量环境、其他参竞广告形成的竞争环境的复杂性、以及广告投放策略中出价、目标人群、资源位、投放时间等变量的巨大组合复杂度，使得最优广告投放策略的计算与执行充满了挑战。
这些问题如何解决？效益最大化的目标具体如何分解？这些有关于决策智能的重要议题，也是领域内的研究者和从业者最关心的。
为了深入探讨「数智商业场景中的决策智能」这一主题，近日，阿里妈妈博见社联合机器之心，邀请到了北京大学邓小铁教授、中科院蔡少伟研究员和阿里妈妈 CTO 郑波老师三位领域内的资深学者和专家，展开了一系列主题分享。
以下为邓小铁教授、蔡少伟研究员、郑波老师的主题分享内容，机器之心在不改变原意的前提下进行了整理。
邓小铁教授：计算经济学的几个最新研究进展
我今天粗糙地介绍一下计算经济学，这是一个很有历史的研究领域，最早可以追溯到 1930 年。后来的计算经济学从另外一个角度出发，将经济学变成计算，之前的计算经济学就是通过计算做经济学研究，这次讲一讲其中的思路。
我们从计算的角度来考虑经济学，有几个主要关键问题：首先是优化，机器学习都是优化，从中可以看到很多优化体系。优化之后，还有一个问题叫做均衡，以前我们做计算经济学是从计划经济的思路去做的，但当时也有一派是从世界银行做发展中国家的发展，他们给发展中国家定计划，从优化投入产出的思路展开。从计算角度算均衡会是很困难的问题，所以出现了一个概念，叫做可计算的一般均衡（Computable general equilibrium）。
最近，我们也越来越多可以看到动力学系统，因为这个世界很多东西并不是均衡的状态，特别突出看到均衡的场景是在数字经济活动中，其中包括经济学层面的东西，比如定价。在数字经济中，每时每秒都可以看到交易数据和价格波动。我们可以清清楚楚看得数据的变化，而不是一年过去之后再把经济数据统计出来。
计算经济学的整个框架下还有很多东西。每一个经济主体都要优化，它们共同博弈的不动点即是均衡。平台也会博弈均衡这件事情，特别是互联网广告平台，做广告的人到平台上来，将广告要通过平台、媒体发放出去。对于媒体，要把广告位置提供出来，利用自身对某一类人群的吸引力。对于平台，要想的是如何将大家的兴趣更好地匹配。阿里妈妈作为国内最大的广告平台，同样面临着博弈均衡的问题，需要安排好各方面利益，以实现社会效益最大化，同时也实现机制设计最大收益。
我们可以从三个角度来谈优化。
首先是经济智能体刻画的问题。很多机器学习的东西都写成优化的问题，比如怎样用机器学习的方法算出来制约的约束条件，包括有些环境中的约束条件。
在非完全信息下，有很多条件是未知的，原来的经济学考虑不了如此复杂的东西，比如博弈对手的效益函数是什么、博弈对手的策略空间是什么、博弈对手都有哪些，非完全信息也是非常重要的对经济活动的刻画。
很多假设可以刻画非完全信息，比如经济人知道对手的效益函数、约束以及其他各种信息。关于彼此的效益函数有一个 common knowledge：我们知道 distribution。但这个 distribution 怎么来的呢？这就走进入机器学习范畴：为什么 player 要告诉彼此、告诉我们它知道什么？针对这些，在计算角度上就有一些很合理的问题。
博弈动力学，这是计算经济学的第三步。从实体经济的经济学来讲，很多活动是经过了 6000 年演化发展过来的，是大家慢慢地博弈，直到均衡。在数字经济中，想一下子到达均衡会是很大的挑战。
广告平台优化是阿里妈妈在做的事情。我们讲了这么多难的计算任务，什么时候能够做好呢？在单参数的情况下，已有的理论能够支撑，但是多参数怎么做到，理论上还没有现成的定义。
很重要的一点是，整个经济学体系已经建好了，但经济学用到互联网中会产生一个很大的缺陷 —— 它是静态的。大家肯定知道，业界的事情不是静态的，比如说「双十一」大促会产生很多挑战，如何设计红包的价格，根据市场已知模型如何建立这些东西，这些成为了今天计算经济学重要的挑战：一是近似求解优化，一是均衡计划，一是平台竞争动力学。
近似计算的难度很大，我们最多知道的均衡的解可以算到三分之一，最多是 33% 的错误率，跟最优相差 33%，所以均衡计算确实挺难的。自动设计方法论、隐藏对手模型学习，是这方面的框架，这里都是跟信息容量相关的东西。
另外就是与市场上的未知对手博弈。我们要考虑至少两个 company，建立一个模型来设计它们之间的博弈，这里都是单调的，并不知道所有的信息。根据已知的信息看市场的波动、价格设计变化，我们基于此设计一个隐函数的优化模型，用机器学习方法做分析。
多方认知次序的先后给我们带来博弈的认知层次。近年来，一些研究讨论了很多一价拍卖为什么比二价拍卖好。Myerson 假设所有人知道所有人的价值分布，发展了一套最优拍卖理论，但我们实际上不知道公共知识。我们自己的研究是从另外一个角度来考虑的，出发点是没有先验的共同知识，把原来用的概率方法建立 Myerson 最优拍卖理论的假设放弃掉。
在没有这套拍卖均衡的基础假设的环境下，最优解可以如何实现均衡？可以发现，泛化一价拍卖收益是跟 Myerson 相等的。这里应对买家以最优效益为目标公布的价值分布，卖家设计的 Myerson 最优收益，等价于它已泛化一价拍卖的期望拍卖收益。
最终的结论是，Myerson 和 GFP 是等价的，它们要比 VCG 要好，但是在 IID 情况下是相等的，Symmetric BNE 和 GSP 也是等价的。
计算经济学用到的另外一个概念是马尔可夫博弈，一种在动态环境下的博弈，特别是无穷轮博弈求解的问题。我们对问题从三个方向进行了处理：一是为计算做了有理化的简化，把目标限制在近似解；二是用时间折现率保证无穷轮收益的收敛性；三是数学上的分阶段求以及将策略不同轮的变化局限在一轮的变化。如此，无穷求和的难点得以克服。
我们进一步在马尔可夫博弈的应用方面简化了计算的难度。对于比特币的共识机制的设计，有清晰的马尔可夫奖励分析，而且讲了一个很好的故事。按照机制设计规定，大多数人支持它就是对。但后面发现，大多数支持并不保证经济学上的安全，有四分之一的人通过自私挖矿攻击就可以推翻多数原则。
远见挖矿策略：「螳螂捕蝉，黄雀在后」
对于数字经济设计环节的问题，我们最新的工作是可以用 Insightful mining Equilibrium 克服，用远见挖矿的策略实现最优，最后是马尔科夫博弈的构架，形成了马尔科夫奖励过程，增加一个认知层级，从诚实矿池、自私矿池，再越过一个层级，达到远见矿池的结果。
同样地，许多互联网公司要处理动态的东西而非静态的东西，如今世界经济学不再是以前的经济学，此外还通过数学使得机器学习方法论和博弈论紧密结合在了一起。我们因此克服了只能处理静态经济学的情形，演进到了能够处理动态的情形。
蔡少伟研究员：一种求解大规模稀疏组合优化问题的高效方法
大家好，今天我分享的题目是大规模稀疏组合优化的高效方法。很多决策问题的核心都涉及组合优化问题，人们很关注如何选择合适的组合方案来达到目标最优化。
求解组合优化主要有两类方法：一类是启发式方法，包括启发式搜索和启发式构造，比如大家经常用的贪心算法就可以看作启发式构造的一种，贪心准则就是启发式（heuristics）；另外一种是分支限界（brand-and-bound）为代表的精确算法。
启发式方法的好处是对规模不敏感，所以可以用近似求解大规模的问题，缺点是往往不知道求出的解离最优解有多大的差距，也可能已经找到最优解了，但是你不知道。Branch And Bound 是完备性的，如果你给它充足时间算到停下来，可以求出最优解并且证明这是最优解。但这个方法是有代价的，会对规模比较敏感，因为这类算法是指数爆炸的，往往不适用于大规模问题。
不管是做搜索还是做构造，启发式算法框架大多很简单，主要是依赖于启发式怎么设计，要根据哪个准则去做。分支限界方法主要在于怎么做「界」，大家看论文也会发现，很多 Branch And Bound 的论文在做 bounding 技术，怎么把这个界做得更紧，可以更好对解空间进行剪枝。
后来我想，可不可以把这两个结合一下？也就是说，既能够保持对规模不敏感，又能把 bounding 技术加进去。大家很容易想到，可以用预处理的方法，或者先做 Heuristics 再做 Branch And Bound，把 Heuristics 结果作为初始解等等。我们在这方面提出了一个新的方法 —— 嵌套地在 Heuristics 和 Branch And Bound 中去迭代。
简单来说，这个方法先粗糙地做一个 Heuristic solving，求一个初步结果。一般来说，做 bounding 需要上下界，Heuristics 会粗糙得到一个下界，接下来通过设计上界的函数。假设这个问题规模比较大，包括很多元素，我们可以淘汰一些，使得问题缩小一圈。之后再精致一点，继续做 Heuristic solving，这样可能改进下界。在这个基础上，算法可以再做一些 bounding，一直嵌套地做下去。于是这个算法就变成半精确算法，有可能可以证明这是最优解的，因为在某一步发现问题空间足够小，不需要 Heuristic solving 而是可以直接精确求解。另外，如果没有求出最优解，也可以知道最优解的区间在哪里。
接下来举两个例子解释这个方法。
第一个是「最大团问题」。团是图论里很经典的概念，在一个图里，点和点之间都有边相连的子图，就称为团，最大团问题是找到最大规模的团。如果给它一个加权，对每个顶点赋予一个权重，这样的最大加权团问题是要找到总权重最大的团。下图这个例子中，分别是四团、三团，三团的权重更大一些，也就是这个图的最大加权团。
按照该框架来做这个事情，我们需要两个子算法，一个做启发式求解，在团里称为 FindClique，另外一个是化简算法，称为 ReduceGraph。我们可以用 FindClique 找到一个团，这个团会比之前找到的要好。当这个更好的团走到 Reduce Graph，我们知道的是：最大团至少有这么大。也是在这一步做化简，如果图经过化简变为空，那么说明找到的团就是最优解；如果没有变为空，那么可以减少一些点，再回去调整找团的算法。这里的算法不一定是固定的算法，可以动态地变化。
我们的一项工作选了「construct and cut」的方法，可以理解为多次贪心的算法。
多次贪心的作用在于，每一次贪心构造可以很快，可以从不同的起点出发，而且如果在某次构造过程中算出来，当前的团再怎么扩展都不可能超过之前找到的团，我们就可以停止。最终目的是希望找到比以前大一些的团，启发式要不要做得更精致以及顺序如何调整，依赖于图的规模，就像剥洋葱一样，剥到某一层再精化，以便有更大精力把更好的团找出来。当图不能再化简的时候，我们可以采取精确的算法，比如 Branch And Bound。找到一个团之后，根据我们的方法，我们要做 bounding 把一些点扔掉，方法在于估计点所能发展出来的团有多大，可以有不同方案去解决。
这两个估界技术是作为例子，大家可以利用不同的技术去做。在实验方面，可以参考下表，对比 FastWClq、LSCC+BMS、MaxWClq 这些方法，求解到相同精度的时间相差十几倍甚至上百倍。
接下来看第二个问题：「图着色问题」。所谓着色是给图的每个点涂一个颜色，相邻两个点不能为同一个颜色，图着色问题讨论的是一个图最少可以用多少种颜色来着色，最少颜色数叫做图的色数。图着色问题有很多应用，特别是在没有冲突情况下分配资源。
这个问题大思路是一样的 —— 启发式求解加一些 bounding 的技术。不同的是，图着色问题并不要求子集合，由于要对整张图进行着色，所以没有「永远扔掉」这个概念，每个点最后都要返回去，这个点一定要有一个颜色。这里的 reduce 是把图分解为 Kernel 和 Margin：
有一个很简单的规则，还是与独立集有关，我如果知道这个图至少需要用多少种颜色，就是颜色下界（记为ℓ），则可以找到ℓ-degree bound 的独立集。这个独立集的点的度数都比ℓ小，所以叫做ℓ-degree bound。如果找到这样的独立集，可以放心移到 Margin 里面。如果把 kernel 的 solution 找出来之后，我们可以很方便把 Margin 合并进来，如果 kernel 是最优解，合起来一定也是最优解，这个规则可以迭代地去使用。
我们看一个例子，这个例子里面灰色的四个点是 kernel，可以看到至少需要 4 种颜色。旁边的三个点放到边缘上，因为三个点的度数都比 4 小，我们放心把这三个点挪到旁边先不管。然后发现剩下这个子图分解不动，已经很硬核了，可以直接求解出来。稀疏图的硬核一般都不大，所以可以考虑精确算法求解。如果把核心找出来，因为已知核心至少用四个颜色，对于边缘中的点，每个点的度数小于 4，怎么样都留有一个颜色给它，走一遍就可以了，线性的时间就可以了。
直到最后，每一次剥离的 Margin 都要保留下来，而且要标记清楚是第几层，这是与第一个问题稍微不同的地方。我们要用额外数据结构把这些边缘图保留下来，最后一个剥不动的 Kernel 精确化解决之后，就可以用倒序的方法，先把最后一个 Margin 给合并进来，根据刚才的规则保留最优性，Kernel 是最优的话，合并一个边缘还会是最优，一路回溯上去，那原图的解也一定是最优的。
当这个问题变成有框架的之后，就只剩下考虑如何找 lower bound 和 upper bound。算法的大致思路是：一开始 kernel 是原图，需要用到最大团算法找一个 lower bound；剥掉边缘之后，可以采取贪心图着色算法，找一个 upper bound。
这里其实用到了三种算法。实践中比较常见组合拳打法，具体到做 kernel 着色，当这个图比较大的时候，我们可能通过某种贪心或者比较快的方法去做，最后有可能变成精确算法去做。整个流程中，lower bound 和 upper bound 都是全局的，如果这两个相等，就可以停下了。
上图是实验结果，可以看出在稀疏大图上面的效果更好，144 个中里有 97 个可以在一分钟内证明最优解。跟同类算法相比，我们的算法对比时间也比较快，在比较稀疏大图上面有特殊方法可以很快求解。大家以前认为，几百万顶点的 NP 难问题肯定要算很久，其实，如果这些图很大但有一定特点的话，我们还是可以在秒级和分钟级的时间内解决的。
阿里妈妈 CTO 郑波：阿里妈妈持续升级的决策智能技术体系
大家好，作为阿里妈妈技术负责人，我将从业界视角分享一下过去几年阿里妈妈在决策智能技术上的进展。
阿里妈妈创立于 2007 年，是阿里巴巴集团的核心商业化部门，也就是在线广告部门。经过了十几年的发展，阿里妈妈打造过「搜索广告淘宝直通车」这样有影响力的产品，2009 年有了展示广告、Ad Exchange 广告交易平台，2014 年又出现了数据管理平台达摩盘，2016 年开始做全域营销。
从技术上看的话，在 2015 年、2016 年前后，阿里妈妈全面拥抱深度学习，从智能营销引擎 OCPX 到自研 CTR 预估核心算法 MLR 模型，都是随着深度学习的方法不断演进的。2018 年，深度学习框架 X-Deep Learning 开源。2019 年，Euler 图学习框架开源，信息流产品超级推荐也上线了，「人找货」进化到了「货找人」。2020 年开始，阿里妈妈针对直播类型的广告上线，同时开始推出互动激励广告，比如大家玩得比较多的互动游戏「双十一」叠猫猫。曲率空间学习框架也在这一年开源。
2022 年，阿里妈妈将整个广告引擎做了重大升级。广告引擎平台 EADS 和多媒体生产与理解平台 MDL 都上线了；在消费者隐私保护上，阿里妈妈的隐私计算技术能力获得了中国信通院认证。回顾阿里妈妈过去十五年的发展，可以看出，我们是一家「根正苗红」做计算广告的公司。
阿里妈妈有什么优势呢？在非常专业的电商场域，我们对用户和电商理解是非常强的，业务场景也非常丰富，除了传统的搜索推荐是传统，在直播推广、互动、新形态等数智业务场景上都有涉猎。此外我们的客户规模属于全球领先，几百万的商家都是阿里妈妈平台的广告客户。这些客户有非常多的需求，除了商家对经营的需求，还有各种各样的生态角色涉及其中，比如主播、达人或者代理商、服务商，他们以不同角色在这个平台里活跃。
我们在 AI 方面也有比较多的研究。这里介绍一下广告场景算法技术的特色。如上图，左边的倒漏斗型结构，很多做搜索或者推荐同学非常熟悉，这一部分广告和搜索推荐非常相似，包括广告召回、粗排序、精排序到机制策略的打分，涉及到信息检索等大量 AI 技术，特别是匹配上的 TDM 等召回模型都用了深度学习的技术。
其中包括决策智能，鉴于平台包含非常多的角色，各有各的博弈的关系，在多方关系和优化平衡之间，决策智能就派上了用场。用户体验、流量成本、预期收益、预算控制、跨域的融合，这些都是需要去博弈平衡的。
在这里我讲讲典型三个博弈 player。平台上博弈方有非常多，主要有三类：媒体、广告主、广告平台。
这三部分的核心技术可以总结为：从媒体角度，关注释放哪些媒体资源能够最好地平衡用户体验和商业化收入；从广告主角度，要优化什么，如何用最小的代价实现营销目标。那么，广告平台的最大目标是什么？长远来说，广告平台更底层的追求目标是让整个平台更加地繁荣，赚钱只是短期的事情，让这个平台长期繁荣才是最终目标，所以平台要平衡各方的关系，让各方的 player 在平台上很好地玩下去。
广告平台所要优化的目标涉及到很多机制设计。我今天会简单讲一下智能拍卖机制设计、智能出价策略、智能商业化策略三个方向，主要以科普的方式讲一讲阿里妈妈在这几年这上面的工作，供大家探讨。
智能拍卖机制设计。
先讲讲智能拍卖机制设计，这是很有趣的课题， 已经好多位前辈、大牛得了诺贝尔经济学奖。我们所谈的经典拍卖机制，从时间来看都是上世纪 70 年代之前出现的，那时候在线广告还没有出现，大家研究了很多关于单次拍卖或者静态拍卖的优化。这些机制通常都是单目标的，而且是针对单次拍卖。
无论是广告平台还是媒体，需要平衡用户体验和广告收入，典型的业界问题都是多目标优化，如果平台上涉及业务比较多，不同业务之间可能有平台策略和意志在里面，这也是多目标的优化。
从最开始用经典拍卖理论，比如用 GSP 或者 UGSP 方式去做流量分发和定价，业界逐渐演进到深度学习去解决这个问题。这些经典算法通过公式去计算平台对某个目标最优化的一些参数，有了深度学习的工具之后，拍卖机制设计本身也是一个可决策问题，其本身是解决决策问题的算法，但生产决策算法也是决策问题。
三年前，我们基于深度学习设计了一个 Deep GSP 拍卖机制，在满足机制良好性质的前提下提升；饿平台的效果，所谓机制性质良好是指激励兼容，广告主不用通过钻牛角尖或者是黑灰产方式获利，真实表达自己的意愿就能够拿到符合出价的流量。保持了激励兼容性质做的 Deep GSP，把原来静态公式换成了可学习的深度网络，这是第一阶段的工作。
到了第二阶段，拍卖机制网络里很多参数，我们通过训练优化的方式算出来。但实际上在整个过程中，除了参数计算还有排序，以及广告分配的过程，是整个系统完整的组成部分。部分模块其实是不可微的，比如排序模块，因此深度学习网络很难模拟它，为了端到端进行拍卖机制设计，我们把拍卖流程可微部分建模到神经网络，这样可以有梯度的反向传导，使得模型训练更加方便。
智能出价策略。
接下来讲一下智能出价策略，这是广告主用来调节效果或者博弈最主要的工具。中心化的分发无法表达诉求，但是在广告场景中这是有办法表达的。出价产品分为三个发展阶段：
最初的经典解法也是最古老的出价，希望预算花得比较平滑，让效果比较有保障，最初的时候业界是通过类似 PID 的控制算法，这是非常简单的算法，效果也比较有限。
等到了 2014、2015 年，再到 AlphaGo 打败人类之后，我们看到了强化学习的强大力量。智能出价是一个非常典型的序列决策问题，在预算周期内，前面花的好不好会影响到后面的出价决策，而这正是强化学习的强项，因此第二阶段我们用了基于强化学习的 bidding，通过 MDP 建模，直接用强化学习做这个事情。
第三个阶段就演进到了 SORL 这个平台，它的特点是针对强化学习中离线仿真环境与在线环境不一致。我们直接在在线环境中进行可交互的学习，这是工程设计和算法设计联合的例子。SORL 上线之后，很大程度上解决了强化学习强依赖于仿真平台的问题。
其他的技术特色还有工程基建部分，包括智能出价模型的训练框架、流批一体调控系统以及多渠道的投放图化在线引擎。工程体系和算法同样重要，离交易中心越近、越实时，越能够得到好的反馈，对于智能出价来说，工程基建部分越先进，越能帮助广告主获得更好的效果。
智能商业化策略。
最后讲讲与媒体相关的智能商业化策略部分。在商业化策略优化上，最初的尝试是把广告结果和自然结果进行加权融合，然后混合起来，根据不同的情况挑选去放。不合理的商业化机制对用户体验伤害很大，大家开始意识到这个问题。最近一两年，动态展现的策略逐渐流行起来了，随着深度学习等技术发展，我们可以通过优化决策算法做到平衡用户体验和商业化收入，在全域流量下去平衡用户的体验。
总体而言，在这三大方面，阿里妈妈形成了一张决策智能体系图，分为三个层面，智能拍卖机制是中间的桥梁，智能商业化策略解决的问题是拿出什么样的资源拍卖最高效，最能平衡好用户体验和商业化收入，智能出价策略是面向流量精细化出价的决策过程，通过出价参数的优化、基于真实环境的强化学习参数寻优，或 Target CPX、Max Return 等建模的范式进行优化。
面对现在的多轮拍卖和高频拍卖，很多基础理论有待进一步突破。说到基础机制理论突破，邓老师是这方面的专家，我们期待与邓老师一起在这方面做出前沿性的研究。从工程实际问题的挑战角度来看，实际环境要求在 200 毫秒返回结果，因此效率和效果上需要通过一些平衡，在工业界做得比较久对这个都有感触。
广告生态的优化是相对独立的，平台的最终目标是希望生态欣欣向荣、和平发展，做好了这几个，生态是否能达到预期呢？我想二者之间未必直接划等号。对于生态优化，仍然有很多理论和实际问题需要解决，这也是希望业界朋友们未来能够一起去探讨和解决的。
过去三年，阿里妈妈决策智能方向在顶级国际会议（NeurIPS、ICML、KDD、WWW 等）共发表近 20 篇论文，并与北京大学、上海交大、中科院、浙江大学等多所高校及研究机构展开合作，相关成果得到了工业界和学术界的广泛关注和跟进，在这个领域实现从跟随到逐步引领行业的技术发展。
相对于深度学习，决策智能在业界和学术界受到关注并没有那么多，所以借这个机会让大家更多了解这个领域，这个领域是非常有趣且有前景的。以上是阿里妈妈在决策智能方面的思考和工作，希望跟业界和学术界朋友一起分享，未来能更多地讨论，争取在决策智能的理论研究和业界实际应用上能够形成一些突破性的发展。
