决策智能技术浪潮袭来，数智商业领域如何变革？来听听三位专家怎么说
原创Synced机器之心 2023-01-13 12:41 发表于北京
机器之心报道
机器之心编辑部
近年来，伴随着广告主的需求变化和相关技术发展，计算经济学理论、博弈论和人工智能技术被越来越多地应用到广告拍卖机制、投放策略中。
决策智能在商业场景中的意义逐渐凸显。用户看到的每一次商品展现、商家的每一次广告出价、平台的每一次流量分配，背后都有庞大且复杂的决策智能做支撑。
这些动作的目标在于优化用户购物体验，让广告投放的决策过程更加智能，同时让广告主、媒体在平台实现长期繁荣。广告主希望在有限的资源投入下最大化营销效果，平台希望能够建立更好的生态。然而流量环境、其他参竞广告形成的竞争环境的复杂性、以及广告投放策略中出价、目标人群、资源位、投放时间等变量的巨大组合复杂度，使得最优广告投放策略的计算与执行充满了挑战。
这些问题如何解决？效益最大化的目标具体如何分解？这些有关于决策智能的重要议题，也是领域内的研究者和从业者最关心的。
为了深入探讨「数智商业场景中的决策智能」这一主题，近日，阿里妈妈博见社联合机器之心，邀请到了北京大学邓小铁教授、中科院蔡少伟研究员和阿里妈妈 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 这些方法，求解到相同精度的时间相差十几倍甚至上百倍。
接下来看第二个问题：「图着色问题」。所谓着色是给图的每个点涂一个颜色，相邻两个点不能为同一个颜色，图着色问题讨论的是一个图最少可以用多少种颜色来着色，最少颜色数叫做图的色数。图着色问题有很多应用，特别是在没有冲突情况下分配资源。
