钻头
PDF钻头
低频交易中的离线算法
结算组合拍卖
特伦斯·凯利
金钱论
对于能够做出真实世界决策的软件，人们抱有很高的期望，尤其是在金钱攸关的情况下。本期《钻头》 展示了精心设计的软件如何通过发现细微的交易获利机会来有效地创造财富。我们将揭示拍卖与我们学生时代经典问题之间的深刻联系，我们将看到结算拍卖——基于出价分配资源——类似于一场高风险的变异俄罗斯方块游戏，并且我们将学会停止担忧并热爱一个在实践中远非难以处理的NP-hard问题。
我的同事和我为两种情境开发了本专栏的技术：曾经被古雅地称为效用计算（后来更名为网格计算，然后是云计算）4,5的计算资源租赁市场；以及制造商采购实物零件的采购拍卖2。为了避开我不便讨论的细节，本专栏使用了一个不同的示例问题，但其基本原理超越了具体的应用，并且差异是表面的。
实际上，编写高效软件以挖掘每一美元的关键在于，超越现实世界问题中令人分心的细节，并将其映射到一个众所周知的形式化问题上。一旦我们建立了正确的联系，优雅的代码几乎就会自行编写出来。《钻头》本期附带的软件 包括结算拍卖的简洁代码。
办公空间
考虑一栋办公楼，其所有者将其房间和停车位租赁给不同规模的公司。潜在租户的需求在绝对资源需求以及他们需要的房间与停车位比例上有所不同：一些租户公司的员工独自开车上班；其他租户拼车或乘坐公共交通工具。一些租户给他们的员工私人房间；另一些租户则将多名员工挤在一个房间里。需求随费用而变化：如果资源昂贵，租户会少用，但如果资源便宜，则会多用。最重要的是，房间和停车位彼此互补，因此任一资源的效用都取决于获得了多少另一种资源。如果两种资源独立分配，租户最终可能会得到不成比例的组合。消除这种风险需要统一分配房间和停车位。
直接的方法是使用拍卖，如下所示：潜在租户提交包含一个或多个资源捆绑包的出价，并标明报价。例如，一个出价可能会说，“我愿意为正好3个房间和正好6个停车位支付1.8万美元；或为4个房间和8个车位支付2.6万美元；或为5个房间和12个车位支付3.1万美元。”每个出价都包含一个隐含的“零捆绑包”，表示对没有资源出价0美元。每个潜在的租户公司都将从其出价中获得一个资源捆绑包——可能是零捆绑包——并支付该捆绑包的报价。
图1说明了我们两个资源办公室示例中的资源捆绑包和出价。图1a将资源捆绑包表示为一个矩形，其高度和宽度与捆绑包中的房间和停车位数量成比例。图1b描绘了用颜色区分的三个出价。矩形形状——宽、高、正方形——反映了适合不同租户的不同房间与停车位比例。
出价可以包含任意数量的捆绑包。较长的出价迫使投标人计算更多资源捆绑包的报价；好处是需要较长的出价才能表达出抓住机会性交易的意愿。建筑物所有者可以通过设定价格下限（例如，从资源成本中得出）来禁止不可接受的低价出价。
结算我们的拍卖意味着从每个出价中选择正好一个捆绑包，而分配的资源不超过可用资源。图2描绘了一个可行的分配方案：代表从出价中选出的捆绑包的彩色矩形，在代表可用房间和停车位数量的外部虚线矩形内，角对角地排列。在所有可行的拍卖结算方式中，我们寻求最优解，以最大化收入（即，所选捆绑包报价的总和），给定提交的出价。最优解不必分配所有可用资源，并且不同的投标人最终可能会为相似或相同的资源捆绑包支付不同的价格。
我们的示例办公空间拍卖在研究文献中被称为“具有互斥或出价的多单元组合拍卖”：组合是因为它同时分配多种资源类型；多单元是因为每种资源都有相同的副本可用；XOR是因为每个出价都列出了几个资源捆绑包，其中正好一个被授予投标人。
揭开面纱
正确的类比将结算我们的示例拍卖的实际问题与一个众所周知的形式化问题联系起来：将资源捆绑包分配给投标人，以与在容器中放置物理对象减少容器容纳其他对象的能力完全相同的方式，减少可用资源池。结算我们的拍卖是经典背包问题的推广。
对于一个简单的拍卖，拍卖-背包之间的联系最为清晰，该拍卖在一个单一类型的资源——例如，办公楼中的房间——上进行分配，每个出价都包含一个数量/价格对。建筑物中的房间数量对应于背包的重量容量；以规定的报价对指定数量的房间进行出价，对应于具有重量和“利润”的候选对象；而最优地结算这个简单的拍卖，对应于解决经典的二元背包问题，之所以这样命名，是因为每个对象要么被选中，要么不被选中，通过将利润最高的对象子集塞进背包，而不超过其重量限制。鉴于简单拍卖的结算问题与二元背包问题之间的这种对应关系，同时推广这两个问题会产生相当全面的拍卖结算问题和背包问题的分类，这些分类精确对齐，仅在其变量的解释上有所不同。5
最优地结算我们的示例办公空间拍卖的问题，对应于“多维多选背包问题”：4,5背包现在有两个容量方面，重量和体积（对应于房间和停车位）；每个候选对象（定价资源捆绑包）都有重量、体积和利润；对象被分组到类别（出价）中；并且从每个类别中选择一个对象，以在不超过背包的任一容量方面的情况下最大化利润。虽然不如经典的二元背包问题出名，但这种推广是已知的。3
将实际的拍卖结算问题映射到经过充分研究的背包问题会带来重要的好处。最重要的是，建立这种联系使我们能够利用计算机科学家和运筹学研究人员自计算机时代初期以来开发的各种优秀解决方案方法。我们将深入研究最优雅的解决方案，该解决方案在实践中效果非常好。
有利可图地打包租户
拍卖-背包的联系告诫人们不要拼凑临时的结算算法，这些算法无法最大化收入。例如，可以使用“贪婪”启发式算法来结算我们的拍卖，该算法选择报价与捆绑包“大小”之比最大的捆绑包。不幸的是，背包文献表明，贪婪启发式算法可能会留下大量的钱3。
在解决方案质量谱的另一端，是在所有可能的从每个出价中选择一个捆绑包的方式中，选择收益最大化的可行解决方案的蛮力方法。蛮力会找到所有可能的交易收益，包括次优启发式算法忽略的那些，但这需要O(BT)时间，对于T个租户出价，每个出价包含B个资源捆绑包。
最优且高效地结算我们的示例拍卖的挑战似乎令人生畏，因为它似乎涉及关于所有提交的出价的同时相互依赖的决策。驯服问题的一种方法是将问题分解为关于单个出价的序列决策。考虑图1b中出价1的四种可能结果，如图3所示：解决方案必须包括三个非零捆绑包之一或零捆绑包。决定如何处理出价1会留下减少的剩余资源池，并减少一个需要担心的出价——原始拍卖的较小版本。有四种方法可以从出价1中选择一个捆绑包，然后最优地解决剩余的较小的“内部”结算问题；这四种替代方案中的最佳方案最优地解决了原始的“外部”问题。
由于所有最优解都具有这种“嵌套”结构，因此标准动态规划可以找到最优解。我们的双资源示例问题比本科计算机科学课程中的典型动态规划练习要复杂一些，但基本思想是相同的。中心舞台是将最优收入定义为提交的出价和可用资源的子集的递归函数：如果M个房间和S个停车位可用于在编号为1到T的出价中进行拍卖，则从前t ≤ T个出价中拍卖m ≤ M个房间和s ≤ S个停车位的最优收入为F(t, m, s)，如图4所示，其中第三行的最大值取自出价t中的所有捆绑包b，并且b$、bm和bs分别表示捆绑包b的报价、房间数量和停车位数量。F的定义只是形式化了常识：第一行禁止不可行的分配；第二行表示如果没有出价，收入为零；第三行根据“内部”最优解定义“外部”最优解。
评估F(T, M, S)会产生从给定“最外层”拍卖中可获得的最大收入。实现必须跟踪导致最优解的决策（即，由F定义第三行中的最大运算选择的捆绑包）。实现还应缓存先前计算的F 值，以避免冗余工作。我的拍卖结算程序为此目的使用了多维数组。
通过动态规划结算我们的拍卖最多需要O(BTMS)时间和O(TMS)内存。5 从技术上讲，这些界限是伪多项式的（即，在问题大小参数M 和 S 中是多项式的，但在问题实例的长度中不是多项式的）。经典的二元背包问题是NP-hard问题，与结算我们的办公空间拍卖相对应的推广也是如此，因此不要对真正的多项式解抱有希望。幸运的是，背包问题允许伪多项式算法，这些算法在许多实际应用中足够快，从而揭穿了“NP-hard问题是难以处理的”这种广泛的过度概括10。学会识别野外的背包问题，以谨慎的乐观态度对待它们，并考虑基于动态规划的简单解决方案。
深入挖掘
除非采取对策，否则拍卖中的投标人可能会通过提供低于他们从资源中获得的真实价值的价格来寻求优势。例如，在一个简单的单件商品拍卖中，如果您愿意为该商品支付100美元，并且您认为没有人会出价超过50美元，您可能会被诱惑只出价50.01美元——为什么要支付更多？但是，如果您对他人的信念是错误的，您可能会失败——例如，输给报价53美元的竞争对手。单件商品拍卖的经典补救措施，著名的维克里拍卖，将商品授予出价最高者，价格为第二高出价者的出价。可以证明，在维克里拍卖中，最佳策略是提供自己的真实估价14。广义维克里拍卖使用更复杂的重新定价技巧，以激励任何类型的拍卖中的真实出价9。
我们的示例办公空间拍卖仅包括两种类型的资源——房间和停车位——但我们可以定义更多（例如，通过将小型、中型和大型房间区分为不同的资源）。不幸的是，通过动态规划结算拍卖所需的时间，与资源类型的数量成指数关系（这对应于多维背包问题的“维度”）；在最坏的情况下，对于每种已知的解决方案方法，情况也是如此。与大多数其他方法相比，动态规划的优势在于，基于渐近时间和内存需求的简单粗略计算，可以快速揭示动态规划是否可以处理与我们的拍卖类似的任何特定拍卖结算问题的实例5。如果此类计算表明动态规划无法令人满意地处理给定的问题实例，则要考虑的下一个方法是整数规划1。
通用整数规划还具有容纳各种侧约束对解决方案的额外好处。例如，在我们的办公空间拍卖中，建筑物所有者可能会坚持认为，授予租赁权的租户数量必须在指定的范围内。如果所有者无法明确表达侧约束，但“看到好的解决方案时就知道”，她可以使用一种替代方法，该方法生成多个高收入的可行拍卖结算问题解决方案，她可以从中选择自己喜欢的解决方案2。
高频交易与通过组合拍卖进行的“低频交易”提供了几个对比。股票交易所的买卖订单匹配13的计算密集程度低于最优地结算像我们这样的拍卖，但高频交易软件在股票交易所下订单必须收集和分析相关数据，做出决策，并在实时压力下采取行动8。更重要的对比涉及社会效用：最优的拍卖结算软件通过发现次优方法会忽略的交易收益，有效地将计算工作转化为新创造的财富。相比之下，高频交易经常因破坏财富而受到谴责7,12。
对于编程和金融交叉领域的另一个问题，请查看Sedgewick和Wayne的Algorithms中货币套利与图分析之间的联系11。通过研究这样的例子来磨练将现实世界问题映射到形式化问题的技能。
位
本专栏的示例代码位于 https://queue.org.cn/downloads/2020/Drill_Bits_03_sample_code.tar.gz。我的拍卖结算程序基于动态规划；对于小问题实例，它会针对蛮力算法检查其解决方案。我的随机出价生成器可以为结算程序创建输入；我提供了一个将两个程序一起运行的脚本。
演练
拍卖利用从理论到软件工程的全部编程技能，用于高度实际的目的。尝试以下几个练习，大致按难度升序排列。
1. 为了秉承《钻头》 避免不必要工作的宗旨6，我的拍卖结算程序“自上而下”地评估动态程序。虽然“自下而上”的评估会完全填充缓存F 值和记录最优决策的数组，但自上而下的评估仅填充那些有助于解决方案的数组条目。是否有充分的理由使用自下而上的方法？
2. 将结算问题公式化为整数程序5，并将其输入到CPLEX或Gurobi等求解器中。在便利性、灵活性和性能方面与动态规划进行比较。
3. 在背包研究的术语中，我的随机出价生成器创建“不相关”的问题实例，对于某些解决方案方法来说，这些实例相对容易3,5。修改代码以输出更难的“强相关”实例。比较整数规划和动态规划在简单和困难实例上的性能。
4. 为办公空间拍卖实施广义维克里拍卖9。它在多大程度上增加了结算的计算成本？
5. 我的拍卖结算程序支持“正向”拍卖。实施通用双向交换，其中出价可以同时提供买卖资源。
6. 推广我的拍卖结算程序以处理任意数量的资源类型。（提示：哈希表可能比数组更适合跟踪最优决策和缓存。）
7. 实施用于结算拍卖的分支定界算法；避免重复发明轮子1。在困难的问题实例上，将其与整数规划和动态规划进行比较。
8. 在商业房地产拍卖中发大财。竞选总统。
https://xkcd.com/2318/
致谢
加州大学伯克利分校经济学教授兼大学图书馆馆长杰夫·麦基-梅森为早期草稿提供了宝贵的反馈。加州大学圣地亚哥分校的朱诺·金审查了示例软件，消灭了一两个错误。
参考文献
1. Andersson, A., Tenhunen, M., Ygge, F. 2000. 用于组合拍卖获胜者确定的整数规划。在国际多智能体系统会议 (ICMAS) 论文集中； https://doi.ieeecomputersociety.org/10.1109/ICMAS.2000.858429; http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/icmas00.pdf
2. Byde, A., Kelly, T., Zhou, Y., Tarjan, R. 2009. 高效生成采购拍卖的k-最佳解决方案。在信息和管理中的算法方面，A. V. Goldberg 和 Y. Zhou 编辑。计算机科学讲义 5564。施普林格； https://doi.org/10.1007/978-3-642-02158-9_8; http://www.hpl.hp.com/techreports/2009/HPL-2009-163.pdf。另见美国专利 #7,801,769 和 #8,086,520。
3. Kellerer, H., Pferschy, U., Pisinger, D. 2004. 背包问题。施普林格。
4. Kelly, T. 2003. 效用导向分配。在自管理系统（六月）中； https://www.hpl.hp.com/techreports/2003/HPL-2003-115.pdf。另见美国专利 #7,844,967。
5. Kelly, T. 2004. 用于多单元组合拍卖的广义背包求解器。在代理介导的电子商务 VI，P. Faratin 和 J. A. Rodríguez-Aguilar 编辑。计算机科学讲义 3435。施普林格； https://doi.org/10.1007/11575726_6; https://web.eecs.umich.edu/~tpkelly/papers/LNAI_3435_0073_auction_knapsack_connection.pdf
6. Kelly, T. 2020. 高效图搜索。acmqueue 18(4); https://queue.org.cn/detail.cfm?id=3424304
7. Krugman, P. 2009. 奖励不良行为者。纽约时报 (8月2日)； https://www.nytimes.com/2009/08/03/opinion/03krugman.html
8. Loveless, J., Stoikov, S., Waeber, R. 2013. 高频交易中的在线算法。acmqueue 11(8); https://dl.acm.org/doi/10.1145/2523426.2534976
9. MacKie-Mason, J. K., Varian, H. R. 1994. 广义维克里拍卖。密歇根大学经济系技术报告； http://hdl.handle.net/2027.42/41250
10. Papadimitriou, C. H., Steiglitz, K. 1998. 组合优化：算法和复杂性，388。多佛。
11. Sedgewick, R., Wayne, K. 2011. 算法，第4版，679。艾迪生-韦斯利。
12. Stiglitz, J. E. 2014. 轻踩刹车。在亚特兰大联邦储备银行金融市场会议（四月）中； https://www.frbatlanta.org/-/media/Documents/news/conferences/2014/fmc/Stiglitz.pdf
13. Treleaven, P., Galas, M., Lalchand, V. 2013. 算法交易评论。 通讯 56(11), 76-85; https://doi.org/10.1145/2500117
14. Varian, H. R. 2008. 设计完美的拍卖。 通讯 51(8), 9-11; https://cacm.acm.org/magazines/2008/8/5343-designing-the-perfect-auction/fulltext; https://doi.org/10.1145/1378704.1378708
特伦斯·凯利 ([email protected]) 多年来一直致力于拍卖和定价的理论与实践。他在行业中的工作促成了多项与拍卖设计、云资源分配和材料零件采购相关的出版物、专利和技术转让。如果凯利能做出明智的选择，他就会致富。
版权所有 © 2020 归所有者/作者所有。出版权已许可给 。
最初发表于 Queue 第 18 卷，第 6 期—
在 数字图书馆 中评论本文
© 保留所有权利。