[译者按]在复杂的环境中，要充分了解交易的潜在特征，从而设计出最好的机制来有效地从交易中获得收益是很具有挑战性的。近年来，人工智能已经成为一个重要的工具，它可以帮助市场设计者揭示重要的市场基本面，并更好地预测可能导致市场摩擦的波动。本文提供了一些人工智能如何帮助市场设计者改善市场运作的例子，并概述了人工智能将如何继续形塑和影响市场设计的方向。
[关键词]人工智能机器学习激励拍卖市场设计
一、导言
几千年来，市场在为个人和企业提供从贸易中获益的机会方面发挥了关键作用。市场往往需要结构和各种机制支持才能有效运作。例如，当价格发现(pricediscovery)成为一种必需，拍卖就成为了一种常用的从贸易中获得收益的机制。这一领域的研究现在通常被称为市场设计(marketdesign)——最早由威廉•维克瑞(WilliamVickrey)于1961年在《反投机、拍卖和竞争密封投标》(Counterspeculation,Auctions,andCompetitiveSealedTenders)一文中提出——这表明，为了取得有效的结果，更广泛地设计拍卖和市场机构是至关重要的。任何市场设计师者都需要了解预期完成的交易的一些基本细节，以便设计最有效果且最有效率的市场结构来支持这些交易。例如，将医生与住院医生相匹配的国家，住院医生匹配项目最初设计的时候，几乎所有的医生都是男性，而他们的妻子往往跟随他们到所驻医院。到了20世纪90年代，这一项目就需要重新设计，以满足双方都是医生的夫妇的需要，因为男女医生不能被分配到不同的城市。即使是像农民死亡后出售农场这样稀松平常的事情，也需要掌握关于结构和决策的知识，究竟是将农场作为整体出售;还是房子作为周末度假别墅单独出售，同时将土地出售给邻近的农民;还是将森林单独出售给野生动物保护基金。
在复杂的环境中，理解交易的基本特征可能是不容易的，更不用说充分了解它们，以便设计出最好的机制，有效地从贸易中获得收益，这是很有挑战性的。例如，最近互联网广告交易平台快速发展，许多广告代理被使用实时拍卖的广告商获得。但是，出版商应该如何设计这些拍卖，以充分利用他们的广告空间，以及他们如何最大限度地提高他们的回报?罗杰•迈尔森(RogerB.Myerson)的早期理论拍卖设计研究，以及迈克尔•奥斯特洛夫斯基(MichaelOstrovsky)和迈克尔•施瓦茨(MichaelSchwartz)近年对互联网广告定价的研究都已经表明，只要在市场设计时对起拍价设定稍作优化，就可以对在线广告平台的盈利产生戏剧性的影响。
但是，市场设计者如何能获知设定最优或至少更好的起拍价所必需的交易特征呢?或者更广泛地说，市场设计者如何才能更好地了解其市场环境?针对这些挑战，人工智能和机器学习正日益成为市场设计的重要工具。零售商和交易平台，如eBay、淘宝、亚马逊、优步和许多其他企业，都在进行海量数据挖掘，以建立更优化的市场模式，帮助他们为客户创造更好的体验，并提高他们的市场效率。通过更好的预测工具，这些公司可以预测，并更好地管理复杂和动态的市场环境。人工智能和机器学习算法改进了预测效度，有助于市场和零售商更好地预测消费者需求和生产商供应，并帮助产品和服务能够进入到更细分的市场。
回到在线广告的市场，像谷歌这样的双边市场(two-sidedmarket)，它将广告商与消费者相匹配，不仅使用人工智能来设置起拍价，还将消费者细分，进行广告定位，而且他们还开发了基于人工智能的工具来帮助广告商进行广告竞价。在2017年4月，谷歌推出了“智能竞价”，这是一项基于人工智能和机器学习的产品，帮助广告商根据广告转化率自动出价，以便他们能够更好地确定他们的最优出价。谷歌解释说，这些算法使用了大量的数据，并不断地完善用户转化模型，以便使广告商的投入都能用在刀刃上，给他们带来最高的转化率。
二、机器学习与激励拍卖
在20世纪上半叶，美国最重要的基础设施项目都在运输和能源领域。然而，到21世纪初，需要大量运输的不仅仅是人员和货物，还有信息。移动设备、无线网络、视频点播、物联网、云服务以及更多新技术新事物的出现，已经创造了对通信网络进行重大投资的需求。随着5G技术的发展，更多的技术将纷至沓来。
然而，无线通信依赖于基础设施和其他资源。无线通信速率取决于信道容量，而信道容量又取决于所使用的通信技术和专用于无线电频谱带宽的数量。为了鼓励带宽的增长和新用途的快速发展，奥巴马政府于2010年发布了《国家宽带计划》(NationalBroadbandPlan)。该计划目标将大量带宽从旧的、生产力较低的用途中解放出来，投入到现代数据高速公路系统中。
2016—2017年，美国联邦通信委员会(FCC)设计并召开拍卖来完成上述计划的部分工作。那次拍卖的频率使用许可总金额高达200亿美元。为了优化频率资源，给新许可证腾出空间，FCC先以100亿美元的价格向广播电视运营商购买了转播权，又支付了近30亿美元将其他广播公司转移到新频道。最终，共提供约84MHz频率资源，其中70MHz作为授权频率，另外14MHz作无牌用途。本节将详细描述这一过程，以及人工智能和机器学习在改进这一市场的基本算法方面所起的作用。
总体而言，重新分配频率资源，无论是规划还是实施都不容易，也没有直截了当的方法。这一计划的规划过程就遭遇到前所未有的计算困难，实施阶段则需要各部门的高度协调。特别是重新分配的一部分频率资源是用于超高频广播电视的频谱带，需要预先设定要清理多少个原有频道;暂停哪些电台电视台(为新的用途腾出频率空间);哪些频道会继续留给原有电台电视台使用;何时进行频道切换，以避免信号干扰。这一极为复杂的市场设计问题涉及多了个计算难题，其中最主要的就是非确定性多项式时间(NP)。这一过程中最关键的算法之一——“可行性检查器”(feasibilitychecker)，已经借助机器学习的方法被开发出来。
那么，为什么要重新分配频率资源呢?电视转播技术在20世纪末发生了巨大的变化。早期都是通过模拟技术传播;其后几十年里，有线电视和卫星服务不断扩展，到2010年，90%以上的美国人都获得了这些替代服务。标清电视信号被高清信号和4K信号所取代。数字电视和调谐器的出现降低了频道资源分配的重要性，因此消费者/观众使用的频道不需要与广播电视公司所使用的频道相匹配。数字编码能够更有效地利用波段，它使多路复用成为可能，因此曾经只能加载单一标清信号的频道现在可以加载多个高清频道，边际谱(marginalspectrum)的价值有所下降。
相关知识推荐：人工智能的核心期刊都有哪些
然而，频道资源的重新分配是一项困难重重的项目，并非普通市场机制可实现的。美国有数以千计的电视广播塔，它们发射出信号能够造成半径为200英里的干扰范围，所以这些频率中的广播内容需要清理干净，以用于新用途。这一过程不仅需要美国不同地区间的协调，还需要协调与美国接壤的加拿大和墨西哥边境地区。由于任一频率只能在所有相关广播公司停止运作之后才能使用，因此及时协调各方弃用频率方可保证效率，也即要求同步操作。
需要解决的问题很多，其中之一是如何确定哪些电台将在频道资源重新分配后继续保留。如果目标是效率，那么解决方案就是在拍卖后，使这些得以保留的频道的价值最大化。设N是所有当前电台电视台的集合，SN，设为这些电台电视台的一个子集。设集合C为拍卖后可分配给电台电视台的频道，代表不再能继续广播的电台电视台所获得的零分配空集。频道分配是映射A:N→C∪{}。可供分配的频道都是有条件的，即排除了电台电视台之间的相互干扰，采用公式：A(n1)=c1A(n2)≠c2，(c1，c2)∈C2。每一个限制条件都可由一个四元组合来描述：(N1，c1n2，c2)。FCC面临的问题中，这样的限制条件超过百万。如果能满足所有抗干扰条件，那么频道分配即是可行的，此时A代表可行的分配集合;设集合A为可行的分配。集合S为可继续广播的电台电视台，S∈F(C)，如果A∈A，则∈A(S)。
大多抗干扰条件采取了特殊形式，即地理位置临近的两个电台电视台无法共用同一频道，这类电台电视台被称为“链接台”，它们之间的关系设为(n1，n2)∈L。对这样一对“链接台”，限制条件可设为A(N1)=A(N2)A(N1)=。这些就是同信道干扰条件。(N,L)则构成一个节点N与弧L组成的图谱。如果同信道干扰是唯一限制条件，那么确定S∈F是否成立，就决定了能否将集合C中的频道分配给集合N中的电台电视台，以便保证没有两个链接节点被分配到同一频道上。
图1显示了美国和加拿大的同信道干扰图。图显示，美国东部地区和太平洋沿岸干扰最为最密集。问题是能否正确地将颜色(通道)分配给图中的每个节点(电台电视台)，保证两个链接节点被分配到不同的颜色。图着色是NP完全问题(NP-completeproblem)的一类，对于这种问题，没有已知的算法能够快速解决，并且通常假设最坏情况下的求解时间与问题大小呈指数增长关系。由于一般的站点分配问题包括图着色问题，因此它也是NP完全问题，并且因为FCC的问题体量，其求解难度会变得极为棘手。
这样一封信会让许多电台电视台感到不悦，更加犹豫是否参拍。因此FCC决定使用另一种设计，即广播公司只需要决定是同意出售其广播权，还是拒绝FCC的出价保留其广播权，继续使用原频率广播。所有广播公司都很满意这一拍卖设计，即便还有其他的选项(例如变更保留广播权，但变更频率)，也不予以考虑。
在这一简化了的拍卖中，每位参拍者i在拍卖轮次t时的出价为pi(t)，这一价格每一轮递减。每一轮中，参拍者都可以选择“退出”，拒绝当前出价，并保留自己的广播权;或者选择接受当前出价。t轮结束后，所有参拍台被同时进行算法处理。在处理电视台t时，考虑到有些台已经选择退出，因此必须有空余频道供再分配，这时拍卖软件会使用“可行性检查器”校验电视台t能否继续保留其广播权。这就是上述提到的广义图着色问题。如果软件运行超时，或计算结果为无法分配该电视台，则这家电视台即成为本轮拍卖赢家，成交价为pi(t–1)。否则，出价将降至pi(t)，它可以根据规则选择退出或者继续。因此，对于电台电视台而言，无论定价算法和软件如何设定运行，在pi(t)
这种针对难解计算问题(hardcomputation)的时钟拍卖理论是由保罗•米尔格罗姆和厄尔文•塞加尔(IrvingSegal)提出的，他们模拟出超低成本且高效的电视广播权购买实例。
这种下降式拍卖设计的表现在很大程度上取决于“可行性检查器”的质量。根据早期的模拟，我们粗略估计，每1%的可行性检查失败将增加约1.5%，即约1.5亿美元的广播权购买成本。因此，快速解决大部分问题成为拍卖设计团队的当务之急。
作为一个理论命题，对于频道打包1问题中的可行性检查，任何已知的算法都会随着问题的体量增大而增加。然而，如果我们知道可能的问题的分布，仍然可以大概率地找到快速算法。但是我们如何知道问题的分布，又如何找到这样的算法呢?
FCC拍卖使用了由凯文•莱顿-布朗(KevinLeyton-Brown)教授领导的不列颠哥伦比亚大学拍卖经济学研究团队研发的可行性检查器。研发过程包含许多步骤，但在这里我们聚焦其中机器学习的作用。拍卖经济学的目标是能够在一分钟或更短的时间内解决99%的问题。
研发工作首先是模拟拍卖产生可行性问题，如在实际拍卖中可能遇到的问题。模拟产生了大约140万个问题，可用于训练和测试可行性检查算法。分析的第一步是将问题描述为混合整数规划(mixedintegerprograms)，并测试标准商业软件CPLEX和Gurobi，以判断实验结果与实验目标相距几何。结论却是，相去甚远。每100秒时间段内，Gurobi只能解决大约10%的问题，而CPLEX只能解决大约25%。对于实时拍卖，这一结果是不尽人意的。
接下来，同样的问题被描述为布尔可满足性问题(Booleansatisfiabilityproblem，SAT)，并测试了近期参与SAT求解大赛的17个求解器。这次结果差强人意，但是100秒内仍没有哪个求解器的解决能力能超过2/3。而实验目标是在60秒内，解决99%的问题。
下一步是使用自动算法配置(automatedalgorithmconfiguration)，这是由弗兰克•亨特(FrankHutter)、霍格•胡斯(HolgerH.Hoos)和凯文•莱顿-布朗2011年开发的程序，并由莱顿-布朗和他的学生在实验中进行应用测试。首先使用解决可满足性问题的高度参数化算法，训练随机森林算法模型(randomforestmodel)。为了做到这一点，我们首先进行模拟拍卖，假设参拍者作出理性行为，以产生大量具有代表性的数据。然后，使用大量不同参数组合，来确定每个参数向量的求解时间分布，最终解决问题。这一过程产生了一个带有参数和测量指标的数据集。运行过程中最有趣的两点是，中位运行时间和在一分钟内解决问题的比例。然后，通过使用贝叶斯模型，我们加入了不确定性，实验者“相信”结果呈正态分布，随机森林算法所决定的平均值，和取决于参数向量与数据集最近点的距离的方差。接下来，参考先验的均值和方差以及已知最佳参数向量的结果，系统识别能最大限度地提高预期结果改进的参数向量。最后，系统测试实际运行，识别参数并将其作为对数据集的观察。系统迭代处理，识别出更多的参数进行测试、校验，并将它们添加到数据中，以提高模型的精度，直到预算时间耗尽。——论文作者：保罗•米尔格罗姆史蒂文•泰迪里斯刘佳平
