ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月延迟差异化云服务宋佳宜和罗奇·格林，华盛顿大学圣路易斯分校。Louis，USA8我们考虑一个云提供商，它通过提供在成本和作业完成的及时性之间具有不同权衡的服务来寻求其收入的最大化。Spot实例和可抢占实例是此类服务的示例，在这两种情况下，可能的服务中断会延迟作业的完成。我们的重点是在价值和对执行延迟的敏感性方面利用作业之间的异质性，并通过联合分布来确定它们在用户群体中的关系。我们的特点是最佳（收入最大化）的定价策略，并在现场的情况下，最佳的投标策略，以及确定条件下，在一个固定的价格投标是最佳的。我们表明，延迟敏感性和工作价值之间的相关性对供应商有利。我们进一步评估结果CCS概念：·社会和专业主题→定价和资源分配;·计算理论→计算定价和拍卖;·网络→云计算;附加关键词和短语：定价、延迟敏感度、服务差异化ACM参考格式：宋嘉仪和罗克·盖林。2020年。延迟差异化云服务的定价（和投标）策略ACM Trans.经济Comput. 8，2，第8条（2020年5月），58页。https://doi.org/10.1145/33815311介绍1.1背景和动机云计算经历了爆炸式增长，并成为越来越多的用户选择的计算平台。云提供商通过提供不同类型的服务来应对这种日益增长的多样性，每种服务都有自己的定价方案。例如，最大的云提供商亚马逊[11]提供多种定价选项，从1到ac，协调客户的异质性，即，在这些选项中，按需实例和点实例与这项工作最相关，因为它们体现了服务成本和特性之间的不同权衡。[1]2019年3月1日检索，来自https://aws.amazon.com/ec2/pricing。这项工作得到了NSF Grant No.CNS-1514254。作者地址：J. Song和R. Guerin，圣路易斯华盛顿大学计算机科学工程系，布鲁金斯大道一号，CB 1045，圣路易斯。Louis，MO，63130，USA;电子邮件：{jiayisong，guerin}@ wustl.edu.允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2020/05-ART8 $15.00https://doi.org/10.1145/3381531ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月八：2J. 宋河盖兰按需实例和现货实例都允许用户一次动态请求一小时（或Linux实例2的一秒）的计算能力首先，虽然按需实例的价格是固定的，但现货实例的价格可能会随着时间的推移而变化。第二个也是更重要的一点是，spot实例可能会意外终止。具体来说，现货价格每小时更新一次，尽管亚马逊当用户的出价低于现货价格时作为对终止可能性的交换，与按需实例相比，现货实例的价格有很大的折扣，亚马逊因此，对于那些能够或已经被检测为容忍中断的作业来说，Spot实例是一个潜在的有吸引力的选择，并且愿意以较低的成本来换取完成其执行的可能延迟。在这篇文章中，我们重点关注属于这一类的工作。除了亚马逊，阿里云6和Packet7也提供类似于现货实例的服务（分别称为可抢占实例和现货市场），客户为指定的实例类型指定每小时的最高价格（出价）。如果出价不低于当前市场价格，则实例按当前市场价格计费;否则实例自动释放，直到出价再次超过市场价格才重新启动。此外，微软Azure和谷歌云，亚马逊之后的两个最大的云提供商[11]，提供的服务可以被视为提供了类似的权衡（参考文献[22]提出了类似的主张，认为亚马逊具体来说，低优先级VM8（微软）和可抢占实例9（谷歌）的价格低于标准的按需实例，尽管现在价格是固定的（这两种服务都不存在投标方面）。与现货实例一样，这种较低的价格是通过抢占来交换服务中断的可能性。为了简单起见，在本文的其余部分，我们将Google和Microsoft提供的服务称为可抢占实例或VM。本文关注的是一个云计算产品，它考虑了这样一个服务组合恶习，并旨在更好地了解何时以及为什么它们可能对云提供商有益，即，帮助它最大限度地提高收入，并为定价策略，然后可以实现这些好处，在存在的多样性工作的个人具体而言，我们的主要目标是消除云提供商可以通过提供服务来增加其收入的条件，这些服务允许用户在服务中断的可能性以及因此延迟作业完成的情况下权衡较低的成本此外，当涉及竞标时，就像spot实例的情况一样，我们还寻求设计有效的（针对云用户）竞标策略。如第3节所述，我们的重点主要是后一种情况，即，现货实例的可变价格（至少其原始价格）22019年3月1日从https://aws.amazon.com/blogs/aws/new-per-second-billing-for-ec2-instances-and-ebs-volumes/检索。3引自[4]：不太频繁”。[4]2019年3月1日从https://aws.amazon.com/ec2/spot/instance-advisor/检索。[5]我们还注意到，现货实例对于在现货价格更新之前完成的短期作业可能很有吸引力，从而造成中断。[6]2019年3月1日从https://www.alibabacloud.com/help/doc-detail/52088.htm检索。[7] 2019年3月1日从https://support.packet.com/kb/articles/spot-market检索。[8]2019年3月1日从https://azure.microsoft.com/en-us/blog/low-priority-scale-sets/检索。[9]2019年3月1日从https://cloud.google.com/compute/docs/instances/preemptible检索。延迟差异化云服务的定价策略八：3ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月版本）。这是因为这样的系统更通用，并且如参考文献[22]所述，提供了更大的好处，包括用户，他们通过投标可以选择最适合其应用程序配置文件的价格和性能之间的权衡1.2假设和限制1.2.1职位简介。工作的多样性显然有许多不同的形式，我们专注于两个核心方面，直接影响用户的支付意愿，即工作价值和工作完成的及时性或对服务中断造成的延迟的敏感性。我们承认，许多其他因素影响用户和提供商的决策，例如，地理约束、计算实例类型、调度选项等。然而，作业计算作业的价值显然与确定用户愿意为执行它支付多少钱有关在现场服务的上下文中可能更有趣，或者更一般地，在作业的执行可以被中断的任何服务中通过先发制人，是工作的敏感性，这种敏感性可以预期影响用户较高出价可确保立即执行，而较低出价则更有可能被多次打断，并导致大量的完成延迟。在这样的环境中，对于寻求收入最大化的提供商来说，一个重要的问题是在决定提供什么服务以及如何定价时，如何考虑用户之间的工作价值和延迟敏感度的差异。解决这些差异的第一步显然是让云提供商了解它们。作业配置文件通常是私有信息，但是云提供商可以获取配置文件在用户群体中的分布的知识。这些信息可以通过市场研究方法获得[31]，例如，客户访谈、调查和问题清单[12]。例如，用于沿着多个维度引出客户偏好的常见方法，例如，价值和延迟敏感性，是联合分析[7，18，36]，它依赖于调查和统计技术来评估客户在购买决策中对不同属性的评价。我们的作业概要模型的细节可以在第3节中找到，但它允许不同大小的作业（总执行时间），每单位执行时间生成的值，以及对执行完成延迟的敏感性。通过使这些数量成为具有不同分布的随机变量，更重要的是通过引入它们之间的相关性，来捕获作业之间的异质性。为了保持分析易处理，相关性只存在于作业价值和对延迟的敏感性之间，并且我们假设两者都独立于作业的大小。这仍然允许短作业比大作业更有价值，即，通过具有更高的单位值，并且对于大的作业来说，与短的作业相比，对服务中断的敏感性更高或更低。然而，它不允许的情况下，大型作业系统地与更高（或更低）的单位价值比短的工作，也不适应的情况下，大型作业更（或更少）的中断比短的工作敏感。尽管存在这些限制，该模型仍然允许对工作（单位）价值的异质性和对中断的敏感性如何影响云提供商从不同服务中获得的收入以及如何定价进行有意义的调查1.2.2定价策略。定价通常是报价（供应商的能力）和需求（用户）的函数。在这篇文章中，我们假设定价对需求没有反应。我们断言这一假设的论据是双重的，但两者都依赖于托管现代云服务的设施的规模。八：4J. 宋河盖兰ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月首先，我们假设，正如其他人所做的那样[25]，提供商的容量足够大（接近无限），以满足大多数需求。特别是，有经验证据表明，云提供商知道如何配置其资源以适应激增。事实上，云计算的这种更一般地说，考虑到现代云计算设施的规模，以及在需要时可以快速将断电的服务器联机的事实，接近无限容量的假设并非不合理[27，29，32]。更具体地说，现代数据中心通常有50，000到80，000台服务器，10这种庞大的规模意味着新的典型请求找到“完整”系统的几率例如，为了简单起见，假设所有实例都需要整个服务器（这可能是保守的，因为大多数实例只消耗典型服务器的一小部分），并根据泊松过程到达，对于80，000服务器系统的简单近似[20]，负载因子为90%，阻塞概率上限为10−4。在实践中，并且尽管负载中有大的瞬时尖峰，云系统通常以远低于90%的平均利用率操作65%的量级，12这转化为甚至更小的阻塞概率。此外，云提供商通常运行多个地理上分布的数据中心，例如，目前，亚马逊在美国拥有50多个数据中心和100多国际吧13尽管云提供商强加的数据托管要求甚至限制可能会影响作业跨多个数据中心运行的能力，但这种选项的可用性可以使作业在没有此类限制的情况下可访问的服务器数量增加两个这反过来又以近似相同的因子降低了它们的阻塞概率我们支持定价不响应需求的第二个论点是规模和云资源分配和计费（重新调用EC2 Linux实例的每秒计费）的更精细（时间）粒度的组合，预计这一趋势将继续[9]。这使得有需求意识的短期价格调整变得越来越复杂。至于阿玛，在现货实例中，早期的实证研究[8，41]暗示定价往往不响应需求。最近对亚马逊现货服务的改变[5]指出了更小的可变性，因此响应能力（对需求变化），现货价格反映了“EC2备用产能供需的长期趋势”。14与亚马逊一样，阿里云也为自己的现货服务提供历史定价数据，虽然我们没有对其变化进行详细调查，但基于一个月窗口（2019年2月23日至2019年3月23日）的观察相对规则的小变化模式，偶尔有较大的变化可能由供应决策引起。很明显，Google可抢占实例和Microsoft低优先级VM的固定价格对需求的短期波动没有反应。总而言之，我们假设基础设施的规模以及在此规模下实施和管理需求响应定价的复杂性相结合，创造了一个云服务定价不响应短期需求变化的环境。换句话说，基础设施很少耗尽资源，以至于需求响应定价的潜在好处无法证明增加的成本是合理的。相反，定价反映了服务特性的差异，[10]2019年3月1日从https://www.forbes.com/sites/johnsonpierr/2017/06/15/with-the-public-clouds-of-amazon-microsoft-and-google-big-data-is-the-proverbial-big-deal/#7c225a482ac3检索。11谷歌云可能是一个例外，因为它的云计算产品运行在谷歌使用的相同基础设施内部运行自己的最终用户产品。后者往往会吸收大量可用的闲置产能[12]2019年3月4日检索，来自https://aws.amazon.com/about-aws/sustainability/。[13]2019年3月1日从https://www.sdxcentral.com/articles/news/wikileaks-publishes-the-location-of-amazons-data-centers/2018/10/检索。142019年3月1日从https://docs.aws.amazon.com/aws-technical-content/latest/cost-optimization-leveraging-检索ec2-spot-instances/how-spot-instances-work.html。延迟差异化云服务的定价策略八：5ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月特别是这些特征如何影响服务完成的及时性，例如，因为spot实例（Amazon、Alibaba和Packet）和可抢占实例（Google和Microsoft）可能会捕获服务中断。请注意，我们并不意味着云需求永远不会超过容量。特别是，云计算的一些我们的主要论点是，这种情况很少发生，不会反映在短期价格变化中。如前所述，在这些假设下，我们的重点是探索云提供商应该如何选择和定价其提供的服务，以实现利润最大化，并提供潜在工作的信息。具体而言，给定关于市场细分的信息，沿着工作正在考虑的服务系列涉及增加有关资源可用性的不确定性，例如，通过在现货服务中定价的变化或通过直接抢占来换取较低的价格，这可能类似于IBM最初在其高速打印机产品中使用的在探索定价策略时，我们还利用云的规模，忽略了换句话说，给定关于工作简档的信息，价格被设置为最大化提供给云的需求，即，在给定云提供的服务及其定价的情况下，从使用云获得价值的一组工作。我们要解决的问题是，引入一种“较低质量”（因为可能会中断）但价格较低的服务是否我们在第3节中使这一点更加正式，但假设服务的特征是价格和中断概率，即，由于不能在给定的“槽”中运行，因此定价策略涉及选择两者。在现货实例的情况下，供应商选择现货价格以及何时更改它们。这些因素共同决定了与给定服务成本相关的中断概率，更昂贵的服务（出价更高）具有更低的中断概率。然后，历史定价数据可以让用户根据他们的个人资料选择最佳的投标策略，我们将在第4节中看到。在具有固定价格的可抢占实例的简单情况下，提供者再次设置价格并控制抢占决策。无论是微软还是谷歌都没有明确说明抢占的几率和时间，也没有明确说明被抢占的实例通常可以多快重新启动，尽管有一些机制，至少对于谷歌来说，可以让用户从经验数据中估计它们，从而评估服务的好处，即，估计完成作业需要多长时间。在探索提供这种服务组合的好处时，我们的调查揭示了几个有趣的特征。特别是，我们确定引入在执行的成本和及时性之间提供权衡的服务，如spot实例和可抢占实例，是有益的，即，只有当作业的价值和它们对执行延迟的敏感度之间的相关性超过某个阈值时，才能增加提供商此外，在许多情况下（见5.2节），一种定价策略可以成功地从市场中提取大部分价值。在定价和投标都相关的现货服务的情况下，在简化假设下，投标的作业一直这样做直到完成，并且具有15Google 提 到 ， 可 抢 占 实 例 每 24 小 时 至 少 被 抢 占 一 次 ， 在 此 期 间 的 抢 占 率 在 5% 到 15% 之 间 变 化（https://cloud.google.com/compute/docs/instances/preemptible#preemption_process，2019年7月24日检索）。162019年7月24日从https://gatkforums.broadinstitute.org/firecloud/discussion/10513/preemptible-instances-检索historical-data-of-google-compute-engine-vm-running-time-before-preemption.八：6J. 宋河盖兰ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月线性下降作为其执行延迟的函数，我们还发现，一个固定的投标策略，即，以相同的固定价值重复出价的策略对于决定出价的用户来说是最优的，并且出价与否的决定仅仅是作业价值的函数在更一般的条件下，包括允许工作完成前终止和简单形式的凸和凹延迟罚款的结果的鲁棒性进行工作价值和延迟敏感性之间的强烈相关性的需求为云提供商提供了有用的洞察力，说明了多价格系统的部署何时可以实现有效的市场细分并增加收入。相反，当这样的多价格报价是通过多个（随机17）变化的价格提供的，如在现货服务中，我们的研究提供了直观的简单投标策略下的不同组合的工作价值和延迟的敏感性，包括当投标在一个恒定的价格是有效的，相反，当和为什么改变一个人文章的其余部分结构如下。第二节简要回顾了以往的相关作品。第3节更正式地介绍了我们的模型。第四节研究了用户在在更一般的假设下，数值检验了结果的鲁棒性在第6节。第7节总结了文章的研究结果，并确定了未来的潜在方向。附录A中提供了一个词汇表，总结了文章主体中使用的符号2相关作品在本节中，我们简要回顾了大量的文献定价在计算系统中，并强调了一些最近的相关工作，包括明确的目标是开发一个更好地了解现货定价及其好处的工作。在具有在价值或对延迟的敏感性方面异构的作业的计算系统中使用资源分配的定价的想法并不新鲜。它可以追溯到20世纪60年代，为共享计算时间定价，例如，参考文献[15，38]。在这个早期的背景下，计算资源通常是受约束的，定价用于实现跨异构用户的全局效用函数最大化的资源分配有限资源的假设很自然地使其本身成为一种与本文非常不同的生产系统表述1990年Mendelson和Whang的论文[30]提供了一个代表性的例子。它考虑了一个M/M/1排队与多个类别的工作具有不同的估值和延迟的敏感性，并研究定价政策，最大限度地提高效用（社会福利）跨类。相反，参考文献[3]考虑了供应商然而，虽然定价的想法经常出现在学术计算文献中，但它们在实践中的使用是有限的[37]，因为定价对于大型计算系统的持续开发和运行从来都不是真正必要大多数这样的系统是集中控制的，例如，这使得定义使用策略变得容易，因此，为资源定价的机制的复杂性和认知开销是不合理的。因此，研究集中在调度算法，以最大限度地利用共享资源，而不是定价政策，以实现明确的社会目标[37]。云计算作为一种实用工具的出现改变了这一点，定价成为一个主要的控制旋钮，例如，参见参考文献[26，28]了解相关定价方案的最新调查，参见参考文献[23]了解有关定价在云计算中的作用的讨论。用户开始习惯于考虑为个人工作付费，及时性是他们评估的一部分17、至少从用户延迟差异化云服务的定价策略八：7ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月在这方面，与本文最相关的作品是参考文献[1，16，21，25，35，42，43]（参考文献[1]的更新和扩展版本也见参考文献[2]）和参考文献[13]。参考文献[42，43]集中于导出最优（现货）投标策略，使用户为服务支付的总价格最小化。然而，没有明确考虑到与不同策略相关的延迟惩罚对作业效用的影响。具体来说，参考文献[43]针对无限容量市场中的固定投标策略，当作业每次中断时都会产生恢复成本。太多的中断可能会导致作业永远无法完成，如果恢复每次中断的开销超过了每轮执行的平均工作量。本文确定了一个最优的投标策略，最大限度地减少成本，同时保证有限的执行时间。参考文献[42]最接近于通过探索作业有截止日期时的投标策略来结合延迟敏感性的某些方面（截止日期约束是我们在第6.3节中研究的凸延迟惩罚的特殊情况）。在这种情况下，它设计了一个动态的投标策略，最大限度地减少工作的成本，同时满足其最后期限。参考文献[1，25]的工作明确地针对（大多数）无限容量设置下的云计算服务，同时试图了解作业价值和延迟敏感性如何影响云服务产品。参考文献[16]与参考文献[1]密切相关，因为两者都依赖于共享理论框架，但它假设有限的云容量，并考虑了提供商侧的运营成本和客户侧的抢占成本两者都提供了有趣的初步见解，特别是在哪些条件下，现场服务可以或不能优于按需服务，但留下了几个问题没有答案，特别是关于工作的价值和延迟的敏感性之间的相关性的正如我们将看到的，这在确定现场服务在多大程度上可以为按需服务提供增值方面起着重要作用参考文献[35]本质上更定性，但其主要观察结果是，简单的固定报价策略在实践中是有用的，这与我们在第4节中的结果相呼应。参考文献[21]研究了具有单位需求、风险规避投标人的云市场，并表明具有按需和现货服务的市场比仅具有现货服务的系统产生更高的收入和更高的福利。然而，它并没有明确地将延迟纳入其效用函数。参考文献[13]的设置是不同的，因为它考虑了客户寻求购买单一类型产品的库存管理系统，例如，家具，但是产品估价和对交付延迟的敏感性的耦合与云计算用户在竞标现货实例时面临的权衡相似，即，以换取更低的执行延迟。然而，两种环境之间存在足够的差异，例如，由于存在库存成本和要求用户的延迟负效用率与她的估价完全正相关，参考文献[ 13 ]的结果不容易适用于我们的3模型配方由于其更大的普遍性，我们的调查是在现货服务的主持下进行的，其中定价（由供应商）和投标（由用户）都是相关的。具体来说，我们考虑一个单一云提供商的设置，即，垄断环境，其中，如前所述，假定提供商可以访问换句话说，我们假设供应商提供了一个即使到今天（2019年）亚马逊不再像以前那样主导云市场，它仍然比接下来的四个最大竞争对手更大。此外，从一个提供商迁移到另一个提供商的转换成本，即，移动数据、学习不同的API等等，仍然相对较高，因此对现有客户的垄断假设并非不合理。八：8J. 宋河盖兰ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月···具有从一组n个价格p=（p1，p2，.，p n），p1
0，其每单位计算时间的值v，即，长度为t的作业的值是Vt，并且其对计算延迟的敏感性的度量，如参数κ所捕获的。例如，κ=0的值对应于对执行延迟完全不敏感的作业，例如，用于在后台运行的批处理作业，而随着κ的增加，作业对延迟的敏感性也会增加。换句话说，κ决定了当作业的由于中断而增加。假设用户知道所有作业的t、v和κ。出于符号的目的，作业通过其三元组（t，v，κ）来表示，其中（v，κ）表示简档所有具有单位值v和延迟敏感度κ的工件。假设工作长度与v无关和κ，并且从具有密度函数21f（t）的概率分布中得出。注意v和t的独立性意味着一个v小的长作业可能比一个v大的短作业价值更低。相反，工作联合密度函数q（v，κ）。因此，我们允许v和κ之间的相关性，例如，高价值作业对延迟更敏感（正相关）。然而，t与v和κ无关的假设意味着，正如1.2.1节所指出的，我们无法捕捉到作业大小影响其单位值或对延迟的敏感性的情况将调查扩展到包括更复杂的相关性，例如这些将是有意义的。[19]我们注意到，亚马逊在2015年推出了一项名为Spot Blocks的服务，用户可以指定最长6小时的时间，在此期间保证不被打断。然而，该服务的定价与标准现货实例的定价不同，即，以相对于按需定价的折扣的形式。我们把研究这一额外的选择作为未来的工作。[20]然而，在实践中，最高现货价格将被设定为超过按需价格，即使只是为了避免提供一个信号，类似的服务（无中断），但（平均）成本较低[21]该描述假设t、v和κ是连续随机变量。对于离散随机变量，类似的表达式是容易得到的。延迟差异化云服务的定价策略八：9ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月用户知道p和π，例如，从云提供商发布的数据（如亚马逊或阿里巴巴现货实例），并使用此信息来选择新工作的投标策略投标策略rp，π（t，v，κ）（当不明确时简单地表示为r或r（t，v，κ））是p和π以及（t，v，κ）的函数，并且指定第一投标价格以及后续投标时期的投标，可能作为现货价格实现的函数这使得一个复杂的战略空间，虽然它包括简单的战略。例如，r可以是状态依赖策略，其下一步仅取决于先前获胜投标的数量，或者r可以简单到以相同价格投标直到作业完成，即，固定的投标策略。给定投标策略Γ和现货价格p>r的实现，已完成作业的效用（t，v，κ）具有以下形式：r）= vt-pr（ t， v， κ，Γ，p>r）- dr（ t， v， κ，Γ，p>r），<<<其中Vt是完成时实现的作业pr（t，v，κ，Γ，p>r）是在策略Γ和现货价格实现下作业支付的总价格<r，且dr（t，v，κ，Γ，p>r）是作业在给定其延迟敏感性的情况下引起的延迟惩罚<κ、策略Γ的使用以及现货价格的实现p>r。<直观地，延迟惩罚dr（t，v，k，r，p>r）应该是k和作业22在其执行时间t之后所经历的执行延迟tr（t，v，k，r，p>r）的增函数（当以pn投标时，延迟为0，当以p1投标时，延迟为最大）。<<这样的函数有很多可能的选择，在6.3节中，我们用凹增函数和凸增函数进行了实验然而，为了便于分析，我们在这里假设形式为κtr（t，v，κ，Γ，p>r）的线性函数，使得r）=vt-pr（t，v，κ，Γ，
r）-κt r（t，v，κ，Γ，
r）.请注意，线性延迟惩罚意味着线性递减的效用函数（当作业不执行时），这隐含地假设客户是风险中性的。这忽略了风险厌恶客户的可能性（具有严格凹效用函数），如参考文献[21]所介绍的6.3节的扩展在某种程度上解决了这个问题，其中包括考虑凸延迟惩罚（映射到凹效用函数）。回到我们的模型，给定p，π和工作配置文件（t，v，κ），用户在投标策略中进行选择，最大化作业的预期效用的策略，其中期望是在现货价格实现上计算的。当最大期望效用为负时，用户会避免出价。在这种情况下，期望效用取为零。否则，作业将继续根据使其期望效用最大化的策略我们对投标策略做了两个假设。第一个是一旦投标开始，它就一直持续到作业完成，即，不允许提前终止[23]第二个是，投标策略被限制为总是在p1投标（最低价格或更高。低于p1的投标相当于不投标，因此可以绕过我们的要求，投标持续到工作完成。我们把满足这两个假设的策略称为持久策略。这些假设的部分动机是这样一个事实，即一个战略在所有可能的现货价格实现。因此，在给定的实现下，即使是最好的战略也不需要总是实现给定工作的非负效用，例如，现货价格的不幸序列很容易产生负效用。这反过来又会产生（动态的）策略，在某个时候决定最好的选择是停止出价（或不断出价低于p1）。这将导致某些作业无法运行完成，从而显著增加了复杂性[22]我们只在已完成的工件上定义tr（t，v，κ，Γ，p>r）<23考虑到与部署和启动一项工作有关的沉没成本，这并非不合理八：10J. 宋河盖兰ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月策略预期效用的推导上述两个假设使我们能够绕过这些复杂性，我们将在6.2节中进行数值探讨，该节考虑了当继续投标的预期剩余效用不再为正时允许终止作业的策略。24在这些假设下，投标策略Γ下的工作Up，π（t，v，κ，Γ）=vt-Pp，π（t，v，κ，Γ）-κTp，π（t，v，κ，Γ），（1）其中Pp，π（t，v，κ，Γ）是投标策略Γ下的作业的期望执行价格，并且Tp，π（t，v，κ，Γ）是在Γ下超过作业执行时间t的预期延迟。给定一个定价配置（p，π），对一个工件选择一个最优投标策略Γp∈，π（t，v，κ）因此，（t，v，κ）包含解决以下问题：Γpπ，π（t，v，κ）=argmaxUp，π（t，v，κ，Γ），（2）Γ在用户期望出价的情况下，π（t，v，k）产生非可预测的期望利用率。虽然用户有兴趣知道如何在给定p，π和（t，v，κ）的情况下选择最优投标策略，但云提供商试图在给定关于作业简档和策略的一些知识的情况下选择p和π，以最大化其预期的每作业收入Rf，q（r_（p，π）），即，解决（p∈，π∈）=arg maxRf，q（r∈（p，π）），（3）p，π其中，符号Γ（p，π）试图指示用户策略对p和π的依赖性，并且Rf，q（Γ（p，π））由下式Rf，q（r（p，π））= f（t）q（v，κ）P p，π（t，v，κ，r）dt dv dκ.t，v，κ在求解方程（3）的优化时，我们假设三元组（t，v，k）是私有信息，但是云提供商知道f（t）和q（v，t），例如，通过第1节中提到的方法。在接下来的两节中，我们首先刻画了在上述假设下的Γπ，然后刻画了（pπ，π）。请注意，这可以被视为标准的Stackelberg博弈：服务提供商基于用户的行为选择并宣布（p，π）以最大化其收入，并且这之后是用户选择向r p，π出价以最大化其利用率。4最优报价策略在这一节中，我们证明了，给定我们之前的假设，最优固定投标策略，即，一个在任务完成之前以相同价值出价的策略总是存在的，并且只取决于κ。由于开始投标的作业不会被终止，因此从等式（1）来看，效用最大化等价于总期望成本最小化：C p，π（t，v，κ，Γ）= P p ，π（t，v，κ，Γ）+ κT p，π（t，v，κ，Γ）。（四）为了便于演示，我们还假设作业长度是槽长度的整数倍，并且w.l.o.g.假设时隙长度为1。 我们将策略空间缩小到出价值在{p1，. ，pn}，根据附录C中的引理12，这不影响最优策略。[24]在这种情况下，终止作业贡献的（非正）效用仅包括终止前的执行付款，即，对于作业的未完成执行，既没有部分值，也没有延迟惩罚延迟差异化云服务的定价策略八：11ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月..- 是的−Σα（ b）4.1最优投标策略的刻画最优策略的推导涉及许多技术步骤，从单时隙长度的工作开始，我们建立了最优策略是固定的投标策略，即，在作业完成之前以相同价值出价的策略。我们把这些技术步骤附录C，并继续陈述我们的主要结果，确定了任意长度工件的最优投标策略的结构。具体地说，我在1号线。[OPT给定定价策略（p，π）和作业执行延迟的线性惩罚函数，在持久策略中，在每个时隙中出价b（v，κ）的策略是作业（t，v，κ）的最优出价策略，其中b（v，κ）是作业（1，v，κ）的最优出价。命题1的证明见附录D。它不仅证明了固定的投标策略是最优的，而且还证明了最优投标b（v，κ）与工件长度t无关。这在一定程度上是因为，假设投标一旦开始就不会终止，使期望效用最大化的决策不受先前投标结果的影响。此外，这种给定命题1的结果，下一步是刻画b（v，κ），或者更准确地说，b（κ），因为正如我们将看到的，最优出价仅取决于作业然而，工作v不影响出价值，但它有助于决定是否出价（或不）。注意，b（κ）可以超过v，因为任何出价值b>p1的预期支付都小于b。在描述b（κ）时，我们还证明了它可以使用简单的线性搜索来计算如果用户使用具有投标价格b的固定投标策略投标作业（t，v，k），则作业处于活动状态的预期时间分数或概率，即，赢得了它的出价，0<α（b）=π i≤ 1。（五）pi≤b假设作业处于活动状态，则单位时间的期望报酬为：b=pi≤bπipi，（6）α（ b）所以预期的付款是P（t，v，κ，b）=bt，（7）平均作业完成时间为不t+ T（ t， v， κ， b）=、α（b）T（t，v，κ，b） =t11.（八）α（ b）将等式（7）和（8）代入等式（4），在b出价的策略的预期总成本（支付加上延迟惩罚）C（t，v，κ，b）由下式给出：C（t，v，κ，b）=t.b+κ。 1-1秒（九）注意，对于给定的b，C（t，v，κ，b）与t成比例（U（t，v，κ，b）也是如此）。还要注意的是，最优投标价格不需要是唯一的。W.l.o.g，假设用户以最低的最优价格出价八：12J. 宋河盖兰ACM Transactions on Economics and Computation，卷。号8第二条第八款。出版日期：2020年5月~≥∞∈~i−1~i~。~回想一下，p1p2···pn，则最优固定投标价格为<<
