低频交易中的离线算法

2021年1月27日，第18卷，第6期对做出现实决策的软件的期望很高，尤其是在资金悬而未决时。此版本的钻头展示了精心设计的软件如何通过发现微妙的贸易机会来有效地创造财富。我们将揭示拍卖与上学时期的一个经典问题之间的深层联系，我们会看到清除拍卖（基于出价分配资源）类似于高风险的变形俄罗斯方块游戏，并且；学会停止烦恼，爱上一个在实践中很难解决的NP难题。

我和我的同事在两种情况下开发了本专栏的技术：一度被称为效用计算（后来更名为网格计算，后来称为云）的计算资源租赁市场； 4,5和采购拍卖，从而制造商获得实物零件。 2为了避开我不愿讨论的细节，本专栏使用了一个不同的示例问题，但是基本原理超越了特定的应用程序，并且差异是肤浅的。

的确，编写有效的软件以消除每一个最后的金钱的关键是要超越分散注意力的现实问题，并将其映射到一个众所周知的形式问题上。一旦我们建立了正确的连接，优雅的代码几乎就会编写自己。此批钻头随附的软件包括简洁的代码，可清除拍卖。

考虑一个办公楼，其所有者将其房间和停车位出租给不同规模的公司。准租户的绝对资源需求以及所需的房间与停车位的比例有所不同：一些租户公司＆＃39;员工开车上班其他乘客拼车或乘坐公共交通工具。一些房客给员工提供私人房间；其他人则将几个工人塞进每个房间。需求随费用的不同而变化：如果资源稀缺，租户的收入减少，而如果资源便宜，则租户的收入增加。最重要的是，房间和停车位是相辅相成的，因此，两者的实用性取决于获得的其他数量。如果这两种资源是独立分配的，则租户可能最终会出现偏向组合。消除这种风险需要统一分配房间和停车位。

直接的方法是按以下方式使用拍卖：预期的承租人提交由一个或多个标有报价的资源包组成的投标。例如，出价可能会说，我正好为3个房间和6个停车位支付了$ 18K；或$ 26K用于4个房间和8个空间;或$ 31K的5个房间和12个空间。＆＃34;每个出价都包含一个隐式＆＃34;零捆绑＆＃34 ;；无需资源即可提供$ 0。每个潜在的租户公司将从其投标中获得资源包（可能为零包），并支付该包的要约价。

图1在我们的两个资源的办公室示例中说明了资源包和出价。图1a将资源束表示为高度和宽度的矩形，该矩形的高度和宽度与束中房间和停车位的数量成正比。图1b描绘了按颜色区分的三个出价。矩形形状（宽，高，方形）反映了适合不同租户的房间与停车位的不同比例。

投标可以包含任意数量的捆绑。较长的竞标价格迫使竞标者估算大量资源捆绑的报价。好处是需要更长的出价才能表示愿意机会性地抢购便宜货。建筑物所有者可以通过设置底价（例如，从资源成本中得出）来禁止出价过低。

清除我们的拍卖意味着从每个投标中只选择一个捆绑，而不分配超出可用资源的资源。图2描绘了一种可行的分配方式：表示从投标中选择的捆绑商品的彩色矩形在表示可用房间和停车位数量的外部虚线矩形内的每个角落都适合。在所有可行的清算拍卖方式中，我们都针对给定的出价，寻求一种能够使收益最大化（即所选捆绑商品的总和）的最佳解决方案。最佳解决方案不需要分配所有可用资源，并且不同的竞标者可能最终为相似或相同的资源包支付不同的价格。

我们的示例办公空间拍卖在研究文献中被称为具有“异或”出价的“多单元组合拍卖”：组合是因为它同时分配多种资源类型；多单元，因为每个资源都可以使用相同的副本；和XOR，因为每个出价都列出了几个资源包，其中一个资源包恰好授予了出价人。

正确的类比将清除示例拍卖的实际问题与一个众所周知的形式问题联系在一起：将资源捆绑分配给竞标者会减少可用资源池，其方式与将物理对象放入容器会减少容器的使用方式完全相同。 ＃39;容纳其他物体的能力。清算我们的拍卖是对经典背包问题的概括。

对于一次简单的拍卖，拍卖与背包的连接是最清晰的，该拍卖在投标中分配单一类型的资源（例如，办公楼中的房间），每个投标包含一个数量/价格对。建筑物中的房间数对应于背包的重量。以指定的要约价格对指定数量的房间进行的出价对应于具有权重和＆＃34; profit＆＃34;的候选对象。最佳清除此简单拍卖对应于解决经典的二进制背包问题，之所以如此命名，是因为通过将最有利可图的对象子集塞入背包而不超过其重量限制，从而选择或不选择每个对象。给定清除简单拍卖问题和二元背包问题之间的这种对应关系，将两个问题一并推广，就可以得出拍卖清算问题和背包问题的相当全面的分类法，这些分类精确对齐，仅在变量解释上有所不同。 5

最佳清理我们的示例办公空间拍卖的问题对应于＆＃34;多维选择背包问题＆＃34 ;： 4,5背包现在具有容量，重量和体积两个方面（对应于房间和停车位） ）;每个候选对象（定价资源束）都有权重，数量和利润；对象分为类别（出价）；并且从每个类别中选择一个对象，以在不超过背包容量的任何一个方面的情况下，最大化利润。尽管不如经典的二进制背包问题出名，但是这种概括是已知的。 3

将一个实际的拍卖清算问题映射到一个经过充分研究的背包问题上，将带来重要的好处。最重要的是，建立这种连接使我们能够利用自计算机时代来临以来计算机科学家和运营研究人员开发的各种出色的解决方案方法。我们将深入研究最优雅的解决方案，该解决方案在实践中非常有效。

拍卖背包连接警告不要将特别的清除算法混为一谈，因为这无法使收入最大化。例如，可以通过“贪婪”来结束我们的拍卖。启发式方法，选择要约价格与捆＆＃34;尺寸的比率最大的捆。不幸的是，背包文学表明，贪婪的启发式方法可能会在桌上留下很多钱。 3

Warning: Can only detect less than 5000 characters

通用整数编程的另一个好处是可以在解决方案上适应各种侧约束。例如，在我们的办公空间拍卖中，建筑物所有者可能会坚持要求授予租约的租户数量必须在指定范围内。如果所有者不能明确表达侧约束但当她看到一个约束时知道一个很好的解决方案，她可以采用另一种方法来为拍卖清算问题生成多种高收入可行解决方案，从中可以选择自己喜欢的方法。 2

高频交易与＆＃34;低频交易＆＃34;通过组合拍卖。与像我们这样的最佳清算拍卖相比，在证券交易所13匹配买卖订单的计算强度较小，但是在证券交易所下订单的高频交易软件必须收集和分析相关数据，制定决策并在实时压力下行动。 8一个更重要的对比涉及社会效用：最优的拍卖清算软件通过发现贸易收益被次优方法忽略了，从而有效地将计算工作转化为新创造的财富。相反，高频交易经常因破坏财富而受到谴责。 7,12

对于编程和金融交叉领域的另一个问题，请查看Sedgewick和Wayne的算法中的货币套利与图形分析之间的联系。 11通过研究诸如此类的示例，提高了将现实问题映射到正式问题的技巧。

此列的示例代码位于https://queue.acm.org/downloads/2020/Drill_Bits_03_sample_code.tar.gz。我的拍卖清算程序是基于动态编程的；对于小问题实例，它会根据蛮力算法检查其解决方案。我的随机出价生成器可以为清算程序创建输入；我提供了同时运行两个程序的脚本。

拍卖会运用从理论到软件工程的全部编程技能，以达到高度实用的目的。尝试以下一些练习，大致按难度升序列出。

1.遵循避免不必要工作的钻头宗旨，6我的拍卖清算程序会评估动态程序“自上而下”。而“自下而上”评估将完全填充缓存F值并记录最佳决策的数组，自上而下的评估仅填充那些有助于解决方案的数组条目。是否有充分的理由使用自下而上的方法？

2.将结算问题表述为整数程序5并将其馈送到CPLEX或Gurobi之类的求解器。在便利性，灵活性和性能方面，与动态编程进行比较。

3.在背包研究的术语中，我的随机出价生成器创建＆＃34; unorrelated＆＃34;问题实例，对于某些解决方法来说相对容易。 3,5修改代码以更严格地输出“强关联”。实例。比较简单实例和困难实例上整数编程和动态编程的性能。

4.对办公室空间拍卖实施通用维克雷拍卖。 9它会多少增加清算的计算成本？

5.我的拍卖清算程序支持＆＃34;转发＆＃34;拍卖。实施一般的双向交易，其中出价可以同时提供买卖资源。

6.概括我的拍卖清算程序以处理任意数量的资源类型。 （提示：在跟踪最佳决策和缓存方面，哈希表可能比数组更好。）

7.实施分支定界算法进行拍卖清算；避免重新发明轮子。 1将它与整数编程和对困难问题实例的动态编程进行比较。

https://xkcd.com/2318/加州大学伯克利分校经济学教授兼大学图书馆馆员Jeff MacKie-Mason就早期草案提供了宝贵的反馈意见。加州大学圣地亚哥分校的朱诺·金（Juno Kim）审查了示例软件，发现了一个或两个错误。

1. A. 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-best解决方案。在“信息和管理的算法方面”中，编辑。 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。

4. Kelly，T.2003。实用程序定向分配。自我管理系统（6月）； 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

8. Loveless，J.，Stoikov，S.，Waeber，R.2013。高频交易中的在线算法。队列11（8）; https://dl.acm.org/doi/10.1145/2523426.2534976

9. MacKie-Mason，J. K.，Varian，H. R. 1994年。广义Vickrey拍卖。密歇根大学经济系技术报告； http://hdl.handle.net/2027.42/41250

12. Stiglitz，J. E. 2014年。敲击制动器。在美联储亚特兰大金融市场会议上（4月）； https://www.frbatlanta.org/-/media/Documents/news/conferences/2014/fmc/Stiglitz.pdf

13. Treleaven，P.，Galas，M.，Lalchand，V.2013。算法交易评论。 ACM的通讯56（11），76-85； https://doi.org/10.1145/2500117

14. Varian，H. R.，2008年。设计完美的拍卖。 ACM的通讯51（8），9-11； https://cacm.acm.org/magazines/2008/8/5343-designing-the-perfect-auction/fulltext; https://doi.org/10.1145/1378704.1378708 特伦斯·凯利（Terence Kelly）[受电子邮件保护]致力于拍卖和定价的理论和实践。 他在行业中的工作导致了与拍卖设计，云资源分配和材料零件采购有关的若干出版物，专利和技术转让。 凯利只有明智地选择才能富裕。 最初发表于Queue vol。 18号 6-请参阅ACM数字图书馆中的此项 相关文章：克里斯·诺克伯格（Chris Nokleberg），布拉德·霍克斯（Brad Hawkes）-最佳实践：应用程序框架尽管框架可以是一个功能强大的工具，但它们也有一些缺点，可能对所有组织都没有意义。 框架维护者需要提供标准化和定义明确的行为，同时不要过分规范 ......