Near-Optimal Bayesian Online Assortment of Reusable Resources

摘要

受租赁服务在电子商务中的应用的激励，我们考虑为不同类型的到达消费者提供可重复使用资源的在线分类的收入最大化。我们针对贝叶斯环境中的最优在线策略设计了具有竞争力的在线算法，其中类型随时间独立于已知的异构分布绘制。在初始库存最小值cmin较大的情况下，我们的主要结果是对于可重用资源的一般情况，近似最优的1−min1 2，p log（cmin）/cmin竞争算法。我们的算法依赖于问题的预期LP基准，解决该LP，并通过独立的随机舍入模拟解决方案。主要挑战是从这些基于仿真的算法中以计算效率高的方式获得逐点库存可行性。为此，我们使用几个技术要素来设计丢弃策略——每个资源一个。这些策略处理可重用性下的库存可行性和每个资源的收入损失之间的权衡。然而，丢弃一个资源单元会改变其他资源的未来消耗。为了应对这一新挑战，我们还引入了后处理分类程序，以帮助设计和分析并行运行的丢弃策略，这可能是独立的兴趣所在。作为一个副作用，通过利用先知不等式文献中的技术，我们进一步展示了针对不可重用资源的特殊情况的改进的近最优1−1/√cmin+3竞争算法。最后，我们使用对合成数据的数值模拟来评估我们算法的性能。

1引言

产品组合规划是指收入最大化的公司决定向消费者展示哪一部分产品。在经典零售应用中，重点主要是销售；然而，随着在线电子商务平台的出现，一些应用程序出现了，其重点是出租可重用资源。可重复使用的资源（也称为租赁产品）在分配给消费者后，会在一段时间内离开库存，一旦重新分配给新的消费者。例如AWS等云计算平台中的虚拟机，Airbnb等度假租赁在线市场中的房屋，以及本地Thumbtack等在线劳动平台的专业服务。为了获取更多收入，一旦新消费者与平台交互，（个性化）分类策略可以决定显示这些资源的不同子集；这种策略的任务是在给定库存限制的情况下长期管理产品组合的顺序。
受上述应用的激励，我们研究了可重用资源的在线分类，其中平台顺序地为到达的消费者流做出不可撤销的分类决策。
每个消费者都有一种类型，该类型决定了她在给定每个可能的产品组合时的选择概率——称为消费者的选择模型。该平台在消费者每次租用产品时收取一次性个性化付款。不同的产品有不同的租金，这取决于消费者的类型。为了对租赁期限的不确定性进行建模，我们考虑了一个随机模型，其中每次租赁产品时，租赁期限都是独立绘制的。
到达消费者的类型也决定了不同产品的租赁期限分布。为了对平台关于其未来消费者的先前信息进行建模，我们采用贝叶斯方法，这些信息通常是基于在线平台中过去消费者的数据形成的。我们假设随着时间的推移，这些类型是从已知的异构分布中独立绘制的。
一旦新消费者到达，平台会从已知的类型分布中观察其已实现的类型，显示新的产品子集，并允许消费者根据其选择模型从该子集随机选择产品。目标是设计一种在线分类算法，以便在决策期内最大化预期收取的总租金（也称为收入）。重要的是，我们考虑每个产品都有初始库存的情况，并且算法应该始终对可用的产品子集进行分类。可用性取决于产品的当前库存水平——数量随着租赁产品的单位而减少，随着返回库存而增加。
给定整个决策层的分布序列，我们问题中的收益基准是任何可行的在线算法作为平台的预期收益的上限，其中预期超过了算法、类型序列和消费者选择的随机性。我们使用竞争比率的概念来衡量在线算法的性能，即在线算法的预期收益与目标收益基准之间的最坏情况比率。
正如在分类优化的文献和实践中常见的那样，我们假设一般的消费者选择模型是弱替代品，即，对一种新产品进行分类只会微弱地降低另一种分类产品的选择概率（见假设1）。如果没有进一步的假设，即使是一次性分类优化也很难计算。为了解决这个问题，我们假设oracle可以访问一个黑箱算法，该算法可以解决一次性分类优化（见假设3）。同样，这是文献中的常见假设当考虑一般消费者选择模型时，与一次性问题相关的计算问题（Golrezaei等人，2014，Rusmevichientong等人，2020）。在oracle访问计算模型中，我们的目标是针对我们的问题设计多项式时间竞争在线算法，以获得适当的收益基准。
在这种情况下，找到使预期总收入最大化的最佳在线策略的问题纯粹是计算问题，指数大小的动态规划（DP）可以制定最佳在线策略。虽然在我们的问题中，没有正式的计算难度来计算最佳在线策略，但据推测，即使在oracle访问模型中，计算难度也很高。1因此，很自然地将最佳在线策略的预期收益作为收益基准，并研究其是否适用于多项式时间竞争在线算法。
更具体地说，我们在本文中提出了以下问题：在预期收益方面，多项式时间在线算法与最优在线策略有多接近？特别是，我们能否获得与最优在线策略相关的恒定或接近最优的竞争在线算法（当初始库存较大时）？
Rusmevichientong等人（2020）的研究结果是在为上述问题提供令人信服的答案方面取得的一项重大进展，该研究为指数大小的最佳在线DP建立了近似动态规划方法。他们表明，使用最优收益函数线性近似的贪婪算法至少获得最优在线预期收益的12。他们进一步研究了租赁期限无限长（即资源不可重复使用）且租赁费用类型独立的情况。在此设置中，他们展示了如何执行简单静态策略的推广，以获得最佳在线策略预期收入的1−min1 2，1 3√cmin分数，其中cmin是不同产品的最小初始库存。2当初始库存较大且资源不可重复使用时，最后一个结果基本上是一个接近最优的竞争算法。注意，大的初始库存制度在分类优化的许多应用中都是相关的，这也是我们论文的主要焦点
注释 1.例如，参见帕帕季米特里乌和Tsitsiklis（1987）了解在部分可观察的马尔可夫决策过程中找到最优策略的PSPACE公司难度，以及Rusmevichientong公司等人（2020）和阿纳里等人（2019）中的相关讨论。
2.如果租赁费取决于类型，Rusmevichientong公司等人（2020）表明，相同的政策获得了1−最小值1 2，R 3√cm的竞争性比率保证，其中R是不同类型的最高和最低租赁费之间的比率。

1.1本文贡献
本文的主要贡献是以下结果。
（主要结果）对于可重用资源的贝叶斯在线分类的一般情况，我们提出了一种多项式时间在线算法，该算法获得了1−min的近似最优竞争比
即使租赁费用、消费者选择和租赁期限分布因类型而异，并且在不同类型之间任意变化，上述竞争性比率保证仍然有效。
为了获得上述结果，我们的工作与Rusmevichientong等人（2020）的不同之处在于考虑了不同的收入基准。特别地，我们考虑最优在线策略的线性规划松弛，称为贝叶斯期望LP。为了定义这个基准，假设一个可行的在线政策知道未来类型的确切实现，但不知道消费者选择和租赁期限的实现。最佳的此类政策，被称为千里眼最佳在线政策，显然提供了一个收入基准。现在考虑放宽这一政策，只要求可重复使用资源的库存可行性约束在类型、消费者选择和租赁期限的随机性上保持预期。给定类型分布序列，该松弛由具有指数数量变量和多项式数量时变包装约束的LP编码，以确保可重用资源在预期中的库存可行性。详见第2.2节。
事实证明，我们可以简单地在多项式时间内求解贝叶斯期望LP，方法是使用椭圆体方法求解其对偶程序——给定离线分类预言机的访问权限。给定LP解，贝叶斯在线优化中一种简单但强大的技术是使用基于模拟的舍入算法来模拟该LP的最优解（有关此方法的示例，请参阅Alaei等人2012、Devanur等人2012、Ma等人2018、Gallego等人2016、Wang等人2018、Dickerson等人2018、Baek和Ma 2019）。在观察到到达消费者的类型后，该算法从LP解决方案中的产品子集的分布中独立地对分类进行采样，忽略库存约束。与LP解决方案相比，该算法在预期收益方面没有损失；然而，它只考虑预期中每种产品的库存约束，而不一定在现有随机性的每个样本路径下。
我们的主要技术贡献是提供在多项式时间内将基于模拟的算法转换为逐点可行的在线算法的技术，在预期收益中具有恒定或可忽略的乘法损失。为此，我们在一段时间内运行一个单独的过程（每个产品一个）以及基于模拟的策略。在每次对产品分类进行抽样后，每个程序决定是否丢弃相应的产品（如果该产品在抽样子集中），以保持该产品的库存可行性。根据LP解决方案进行采样，然后使用产品特定丢弃规则的这种特定架构在过去已经过探索，例如，参见Alaei等人（2012）、Gallego等人（2016）、Wang等人（2018）、Dickerson等人（2018年）、Baek和Ma（2019）。3(注释3具体参见Gallego等人（2016年）第7节中的“原始路由算法”和Wang等人（2018年）第4.2节的“分离算法”。)同样，我们的目标是设计多项式时间在线丢弃策略（和其他必要的算法构造），处理维持库存可行性和放弃每个产品的收入损失之间的权衡。针对我们问题的主要新挑战是：（i）产品是可重复使用的，（ii）产品是弱替代品，因此丢弃产品会增加其他产品的选择概率，以及（iii）丢弃可能是随机的-这与可重用性相结合，在时间上的选择指标随机变量之间创建了复杂的相关结构，并使关于策略的逐点可行性的争论具有挑战性。在下文中，我们概述了我们的主要技术贡献以及他们如何克服这些挑战。
（一） 一般租赁期限分布/近似最优丢弃（第3.2节）：近似最优丢弃程序背后的主要思想是以小概率随机丢弃每个可用的样本产品。这是一种简单而合理的方法（参见Hajiaghayi等人，2007），因为基于模拟的算法考虑了预期中每种产品的库存约束。通过概率γ>0的独立随机丢弃，我们通过确保出租产品的单位数量的预期值在任何时候最多为其初始库存量的（1−γ）倍，在库存可行性约束中留有一定的余地。如果该数量作为独立租金指标随机变量的总和集中在其期望值附近，那么当γ=O p log（cmin）/cmin时，我们将以高概率避免违反库存约束。此外，它只损失了该产品预期收入的γ部分。
然而，上述简单方法不能如所描述的那样工作，因为（i）资源是可重用的，并且库存是有限的，因此，如果时间τ的租赁持续时间至少为t−τ，并且产品的最后一个单位在τ处租赁，则产品在某个时间τ<t处的租赁指标随机变量可以与同一产品在时间t处的租金指标随机变量相关联；4
注释4我们想强调的是，在我们的论文出现在线版本后，通过与Goyal等人（2020a）的作者的个人沟通，我们被告知这篇论文（当时在线上没有）独立并同时发现了一种类似于我们的子分类采样的程序，用于具有对抗性到达和可重复使用资源的设置。
（ii）一旦丢弃程序将产品从抽样分类中删除，其他产品的同类产品将减少，因为消费者的选择是较弱的替代品。这反过来又增加了到达消费者选择其他产品的可能性，因此，与基于模拟的算法的预期数量相比，所得到的算法将增加未来租赁的不同产品的预期数量。
我们通过在独立随机丢弃之后提出后处理步骤来解决上述问题，我们称之为子分类采样。简言之，子分类抽样的目标是找到可用子集上的分布，以便不会丢弃的产品将以与贝叶斯期望LP的最优解完全相同的概率出租。甚至还不清楚这种分布是否存在；然而，我们证明了这一点，并提供了一个多项式时间结构来从这个分布中采样。利用子分类抽样的财产，我们提出了一种耦合技巧，以显示我们期望的浓度，尽管事实上，租金指标随机变量在时间上是相关的。请注意，子分类抽样的任务很一般，在其他应用中可能具有独立的利益。4(注释4我们想强调的是，在我们的论文出现在线版本后，通过与Goyal等人（2020a）的作者的个人沟通，我们被告知这篇论文（当时在线上没有）独立并同时发现了一种类似于我们的子分类采样的程序，用于具有对抗性到达和可重复使用资源的设置。)
（II）一般租赁期限分布/1 2-竞争性丢弃（第3.3节）：作为可重复使用资源的一般情况的替代丢弃策略，考虑一个指数大小的DP，它跟踪产品的每个单元的状态（即，当每个单元返回库存时），并最优地解决丢弃任务。我们介绍了这个DP的近似版本，我们也称之为乐观DP，可以在多项式时间内解决。我们的目标是，当我们每次做出丢弃决定时，通过外部过程自动补充库存时，使产品的单位收入最大化，从而使产品的整个库存始终可用。这种新的DP与库存无关，因此是多项式大小。然后，我们考虑一个丢弃算法，该算法做出与乐观DP相同的决策。结果是一个非自适应阈值丢弃规则，即，只有当可用产品的租金低于某个阈值时，才丢弃该可用产品。这些阈值是预先计算的，仅取决于产品、时间和实现的类型。
为什么上述丢弃算法是合理的近似，其主要直觉如下。我们可以证明，该算法的预期收益是库存水平的凹函数，即库存水平越高，单位预期收益越低。
因此，当实际没有补充时，它获得的单位收入至少与补充后的DP相同。然后，我们使用“因子揭示线性规划”及其对偶，分析该独立于库存的DP的价值与预期LP的单位收入之间的最坏情况比率。该方法为该比率确定了12的下限。
值得注意的是，基于双重拟合的类似证明技术已在文献中用于不可重复使用资源的其他问题（例如，见Zhang和Adelman 2009，Adelman 2007，Alaei等人2012，Gallego等人2016，Wang等人2018）。我们的工作扩展了现有分析，以证明在资源可重用时基于LP的丢弃策略的性能保证。
我们强调，在给定预期LP解决方案的情况下，我们设计上述近似丢弃策略的DP与Rusmevichientong等人（2020）中的近似动态规划方法具有相似但不完全相同的递归结构，用于直接近似最优在线策略；事实上，与他们的方法不同，我们DP的Bellman更新方程使用了预期LP（最佳分类抽样概率）的解。因此，虽然两个DP提供了相同的近似因子12，但我们的是预期LP的更强基准，而他们的是最佳在线策略。这个微妙的结果证明，差异是将第3.2节和第3.3节中两种算法的性能保证结合起来的关键，以便获得一种简单的混合算法，相对于更强的预期LP基准实现理论上的“两全其美”竞争比率保证（正如我们后来观察到的，在数值模拟中提高了性能）。
（三） 基于仿真的混合算法（第3.4节）：通过不同的丢弃规则访问上述基于仿真的算法，我们的目标是定义一种混合算法，该算法可以享受小库存和大库存的竞争比率。为此，我们预先决定每个产品使用哪种丢弃策略。特别是，我们分别使用每个产品的乐观DP的价值函数来计算该产品遵循乐观DP的预期收入与该产品对预期LP目标的贡献之间的比率Ri。然后，我们将该比率与1-ε（ci）（函数ε（·）的定义见（1））进行比较，以将产品划分为大库存（即当Ri+ε（ci）<1时）和小库存（即Ri+ε*（ci）>1时）。对于每个大库存产品，我们在第3.2节中运行随机丢弃策略，对于每个小库存产品，在第3.3节中运行乐观DP丢弃策略。我们还使用子分类抽样程序进行后处理，以纠正由于替代性较弱而导致的非废弃产品选择概率的增加。通过使用以下事实：（i）两种算法的竞争比率分析在产品之间解耦，（ii）两种分析将从每种产品获得的预期收入与该产品对预期LP目标的贡献进行比较，以及（iii）子分类抽样校正了未丢弃产品的选择概率，我们展示了由此产生的混合策略结合了两种竞争比率5
注释5值得注意的是，Rusmevichientong等人（2020）的12竞争近似DP算法不能使用该方法与我们的近似最优丢弃策略相结合，因为该近似DP算法与最优在线策略竞争，而不是与预期LP竞争。
虽然这种混合算法实现了1−min的两个世界的最佳竞争比在实际情况下，它也可能优于这两种政策；第4节中的数值模拟结果从经验上支持了这一主张。我们还提出了使用条件期望方法的第二种混合算法。详见第3.4节。
我们还通过考虑不可重用资源的特殊情况来补充我们的结果。通过利用来自先知不等式文献的杠杆老化技术，并将其扩展到贝叶斯分类优化问题，我们提供了在这种情况下相对于预期LP的1−1√cmin+3的近似最优改进竞争比。更多详情请参见第EC.1节和第EC.5节。

（iii）数值模拟（第4节）： 我们最终为拟议政策的收入表现提供了数字依据。根据Golrezaei等人（2014年）和Rusmevichientong等人（2020年）的数字实验设置，我们将我们提出的政策（即混合算法和无限租赁期限下最优丢弃的模拟）的收入与文献中的其他政策进行了比较。在我们的数值模拟中，我们考虑了一般租赁期限分布和无限租赁期限的情景。在所有这些情况下，我们的政策在预期收入方面明显优于其他政策。
1.2进一步相关工作
近几十年来，收入管理产品组合规划的文献越来越多。我们让读者参考相关的调查和书籍（参见K–ok等人，2008年，兰开斯特，1990年，何和唐，1998年）进行全面研究。van Ryzin和Mahajan（1999）研究了静态模型，该模型在多项logit消费者选择模型下捕捉了库存成本和产品种类之间的权衡。后来的工作考虑了各种消费者选择模型下的分类，例如，需求替代模型（Smith和Agrawal 2000）、多项logit模型（Talluri和van Ryzin 2004，Gallego等人2004，Liu和van Ryjin 2008，Topaloglu 2013）、兰开斯特选择模型（Gaur和Honhon 2006）、排名列表偏好（Honhon等人2010，Goyal等人2016，Aoud等人2018）、，然后考虑选择模型（Aouad等人，2020）和非参数（数据驱动）选择模型（Farias等人，2013）。
最近，在先前的自由/对抗和贝叶斯设置下，对在线分类进行了研究。对于不可重复使用的产品，Bernstein等人（2015）研究了两种产品的模型，即消费者类型和泊松到达率。Chan和Farias（2009）研究了一个具有非平稳消费者类型的模型，并展示了与千里眼最佳在线基准相关的12个性能保证。Golrezaei等人（2014年）引入了“库存平衡”算法——灵感来自Mehta等人（2005年）对在线广告分配的开创性工作——并使用原始对偶方法分析了它们在先前免费设置下的性能保证。Ma和Simchi Levi（2020）后来对这一分析进行了改进和推广。Chen等人（2016）考虑了另一种变体，其中产品组合以折扣价格作为附加产品提供。本文还使用了丢弃以确保逐点库存可行性的思想，由于产品替代，它们面临着类似的挑战。为了克服这一挑战，作者引入了一种针对特定目标的误差抽样程序。相比之下，我们的分类抽样不会产生任何错误，可以用于更一般的目的。
对于可重复使用产品的在线分类，Levi和Radovanovi c（2010）研究了一个模型，该模型假设产品之间存在独立需求，而无限销售范围内的客户没有任何选择行为。Owen和Simchi Levi（2018）的后续工作扩展了这项工作，以纳入客户选择行为和有限的销售范围。Chen等人（2017）研究了单个可重复使用产品的多个单元的模型。他们考虑了随机使用持续时间和提前预订，并获得了与数据相关的性能保证，当产品库存和客户到达率以相同的速度线性增长时，这些性能保证是渐近最优的。
最后，Rusmevichientong等人（2020）研究了贝叶斯设置和Gong等人（2021），Feng等人（2019年、2021）、Goyal等人（2020b）研究了无先验/对抗性环境，其中租金和租期分布都是类型相关的，并且在不同时间段内是相同的。
在贝叶斯环境中，我们的问题类似于“先知不等式”问题的某些方面。这一问题起源于Krengel和Sucheston（1978）在70年代的开创性工作，并已被广泛研究。文献中也研究了这个问题的组合推广。例如，拟阵的预言不等式（Samuel Cahn等人，1984年，Hajiaghayi等人，2007年，Kleinberg和Weinberg 2012年）、匹配（Alaei等人，2012年）和组合拍卖（D–uetting等人，2017年）。在这些概括中，用于计算最佳在线策略的自然动态规划是指数大小的（Niazadeh et al.2018，Anari et al.2019），与我们的问题类似。参见Lucier（2017），了解全面调查。
我们的一些技术类似于先知不等式匹配（Alaei et al.2012）、魔术师问题和在线争用解决方案（Alaei2014、Brubach et al.2021、Feldman et al.2016）、静态日历定价问题（Ma et al.2018）、可重用离线节点的在线二部匹配（Dickerson et al.2018）、，以及志愿者众包问题（Manshadi和Rodilitz 2022）。与我们最接近的是（Baek和Ma 2019）针对可重复使用资源的网络收入管理问题的研究，在该研究中，作者们独立地同时发现了类似于我们针对小库存机制的算法的策略。
其他预期的LP基准在文献中以“事前放松”的名义用于各种随机在线优化和机构设计问题。例如，参见Alaei等人（2012）、D¨uetting等人（2017）、Lee和Singla（2018）、Vera和Banerjee（2021）、Ma等人（2018）和Anari等人（2019）。我们用于分析基于DP的阈值丢弃规则的因子揭示技术类似于Adelman（2007）的LP方法、Alaei（2014）、Wang等人（2018）中的双重拟合方法，以及用于近似动态规划的其他基于LP的方法（参见Si等人（2004）的综合研究）。
我们的一些技术类似于先知不等式匹配（Alaei等人。
2012年）、魔术师的问题（Alaei 2014）、静态日历定价问题（Ma等人。
2018）（该研究还研究了没有可重用资源的静态分类策略）和志愿者众包问题（Manshadi和Rodilitz 2022）。与我们的贝叶斯预期LP相似，其他预期LP基准在文献中以“事前放松”的名义用于各种随机在线优化和机构设计问题。例如，参见Alaei等人。
（2012），Devanur等人（2012）、Feldman等人（2016）、D¨uetting等人（2017）、Chawla等人（2017年）、Lee和Singla（2018年）、Vera和Banerjee（2021）、Ma等人（2018）、Anari等人（2019年）、Dickerson等人（2018年。
另一项与我们相关的有趣工作是维拉和巴纳吉（2021）以及巴纳吉和弗伦德（2020年）的工作。这里的目标是获得改进的（基于附加或遗憾的）近似值具有包装约束的各种随机在线优化问题。这些论文与我们的不同之处在于，采用了不同的技术方法，并考虑了不同的制度（即，当库存随地平线增加时）；然而，将他们的技术应用于可重用资源问题是一个有趣的未来研究方向。

2 准备工作

我们首先将问题、模型和第2.1节中的所有必要假设形式化。然后，我们在第2.2节中简要解释了预期LP基准的各个方面。
2.1模型和问题定义
该平台提供n种不同的租赁产品，按[n]={1，2，…，n}索引。每个租赁产品i具有ci∈Z+的初始库存。有兴趣租用这些产品的消费者在时间t=1、2、…、。，T.消费者T具有类型zt∈zt，其中zt表示时间T时可能类型的（离散）空间。我们假设类型是独立于已知概率分布Ft:zt绘制的→ [0，1]在时间t=1。，T 当消费者t到达时，她的类型zt向平台展示。给定该类型和截至时间t的历史，平台从其库存中提供可用产品的分类St∈S，其中S⊆2[n]是可提供的所有可行分类的集合，忽略库存可用性。给定种类St，消费者选择一个租赁产品，它∈St，向平台支付租赁费，并在随机租赁期限dt∈Z+内保留该产品。
我们考虑了消费者选择行为、不同产品的租赁费用和不同产品的租金持续时间分布取决于每个时间t的类型zt的设置。形式上，消费者类型z定义为元组⟨z，rz，Gz⟩，因此：•具有类型z的消费者的选择由通用选择模型函数进行建模→ [0，1]，其中，z（S，i）是当提供分类集S∈S时，类型为z的消费者选择产品i出租的概率。
•对于类型为z的消费者，r z=（r z 1，rz 2，…，rz n）∈r n，其中ri z表示产品i的租赁费。此外，Gz=（Gz 1，Gz 2，…，Gz n），其中Gz i表示类型为z产品i的租用期限的c.d.f.。我们使用gi z:[T]→ [0，1]表示z型产品i的租赁期限的p.d.f。
此外，设’Gz i（·）≜1−Gz i（·）。
注意，我们假设租赁期限在时间上是独立的，也就是说，如果在时间t，z类型的消费者选择了产品i，则新的样本dt～Gz i被实现为该产品的租赁期限。
我们进一步将以下假设应用于我们的选择模型和可行组合，这在以前的文献中是常见的（参见Golrezaei等人2014，Rusmevichientong等人2014）假设1（弱替代性）。对于所有的t∈[t]，z∈Zt和i∈[n]，⑪z（∅，i）=0。此外，对于所有的S∈S和j∈[n]/{i}
假设2（向下关闭可行性）。如果S∈S和S′⊆S，则S′∈S，即，在移除其提供产品的任何子集后，可行的分类将保持可行。
备注1。在Airbnb等在线酒店服务中，用户在平台向他们展示列表之前，会向平台报告他们的入住时间。在这种变化中，平台通过使用到达类型的当前租赁时间的准确实现来做出分类决策。
事实上，这是我们模型的一个特例，其中租赁时间分布是点质量。
给定类型分布｛Ft｝T T＝1，目标是设计在线算法——扮演平台的角色——最大化从租金中获得的预期收入；这里，期望是算法（如果随机）和环境的随机性，即类型、消费者选择和租赁期限。该问题的收益基准定义为通过任何可行的在线算法获得的预期收益的任何上限（通过可行的在线计算可能实现或可能不实现）。固定一个收益基准，我们通过与该基准的竞争比率来评估任何在线算法的性能。非正式地说，竞争比率是在线算法的预期总收入与基准之间的最坏情况比率，其中最坏情况是所有可能的类型分布。
定义1（竞争比率）。在线算法A与给定revenue基准相比是α-竞争的，如果
（）
其中RevA[·]是算法A的预期收入，OPT[·]为给定的收入基准。
对于一般的消费者选择模型，准确甚至近似的离线分类优化在计算上是困难的（K¨ok等人，2008）。为了在为一般消费者选择模型设计多项式时间在线算法时避免这一障碍，我们假设可以使用解决离线分类问题的算法。为了简单起见，我们假设整个论文中的解算器是精确的，但如果解算器为某个0<β<1的β近似算法，则我们的所有结果仍然适用于竞争比率中β的乘法降级。
假设3（离线预言机）。对于所有的t∈[t]、z∈Zt和∈R∈R n+，我们都可以使用oracle访问一个算法，该算法可以找到子集S∈S，从而：
（）
2.2 贝叶斯预期LP基准
根据关于未来不确定性和所需计算能力的给定信息，考虑以下收入基准层次：
1。最佳离线：最佳离线算法的预期收益，该算法具有关于已实现类型序列｛zt｝T T＝1的完整信息，每种类型zt和产品i的租赁持续时间的精确实现，以及每种可能分类的消费者选择的精确实现。
2.Clairvoyant最佳在线：最佳在线算法的预期收入，该算法具有关于已实现类型序列｛zt｝T T＝1的完整信息，但不知道租赁期限的确切实现，也不知道消费者的选择。
3.非透视最优在线：仅知道类型分布序列的最优在线算法的预期收益｛Ft｝T T＝1
图1 比较了这些基准的预期收入。即使资源不可重复使用，也不存在针对最佳离线的持续竞争在线算法；见第EC2节。最佳（非透视）在线策略是一个较弱的基准，需要解决指数大小的动态规划（Rusmevichientong等人，2020）。Golrezaei等人（2014）针对不可重复使用的产品提出的在线透视优化，Gong等人（2021）将其扩展到可重复使用产品，是预期收入的中间基准；此外，它必须解决指数大小的动态规划，以在给定额外信息{zt}T T＝1（这不提供给正常的在线算法）的情况下计算其分类决策。
我们所有算法中的一个关键组成部分是贝叶斯预期LP基准——这是一个概念，常用于先前关于在线分配、机制设计和分类优化的文献中，以纠正上述基准的问题（例如，参见Chawla等人2010年、Alaei 2014年、Ma等人2018年、Gallego等人2016年、Wang等人2018年和Anari等人2019年）。该基准由预期LP[{Ft}T T=1]表示，使用线性规划来捕获只需要以满足期望中的库存约束，其中期望被视为租赁持续时间和消费者类型的随机性，给定类型分布｛Ft｝T T＝1：
（）
这里，变量{yS，t，zt}t∈[t]，S∈S，zt∈zt对应于给定类型zt被实现时，分类S被提供给消费者的概率，第一个约束表明库存在预期中的可行性。
首先，该LP的最佳目标值是透视最佳在线基准的预期收益上限，因此是较弱的非透视最佳在线（建议1；证据见第EC.3节）。第二，使用离线分类的预言机可以有效地解决预期的LP[{Ft}T T=1]（命题2；证据见EC.3节）。我们在所有算法中使用这个计算块作为预处理步骤。6最后，定理1中的近似最优保证表明，随着初始库存变为无限，最优在线（以及透视在线）和预期LP[{Ft}T T=1]之间的差距缩小到零。
提案1。对于任何类型的分布｛Ft｝T T＝1，千里眼最佳在线基准的预期总收入由预期LP〔｛Ft｝T＝1〕上限。
提案2。给定离线分类的算法（假设3），可以在时间Poly（n，t，P t∈[t]|zt|）中有效地计算期望LP[{Ft}t t=1]的最优分配{yS，t，zt}。此外，{yS，t，zt}不超过Poly（n，t，P t∈[t]|zt|）个非零条目。
注释6事实上，需要使用离线分类求解器作为分离预言器来运行此LP的对偶的椭圆体方法，以便找到最优解。在实践中，为了获得更快的算法，可以使用诸如Vaidya（1996）之类的切割平面方法或甚至更快的几乎线性时间切割平面方法，例如Lee等人（2015），这些方法更有效地使用分离预言。

3 一般租赁期限的近似最优算法

在本节中，我们展示了我们的主要结果——一种基于在线模拟的近似最优算法，其竞争比至少为最大
（1）
设γ*（cmin）为方程（1）中γ的最佳赋值。不难验证ε*（cmin）=O p log（cmin。我们首先在第3.1节中概述了我们的方法。然后，我们在第3.2节中引入了竞争比率为1-ε*（cmin）的基于模拟的算法，并在第3.3节中引入不同的基于模拟算法，以确保竞争比率至少为12（即使是小cmin）。我们最后在第3.4节中提出了两种简单的混合算法，可以获得两种竞争比率中的最佳。
3.1我们方法的高级草图
设{y*S，t，zt}是期望LP[{Ft}t t=1]的最优分配。由于∅∈S，在不丧失一般性的情况下，我们只能考虑最优分配，其中：
（）
本文中所有基于仿真的在线算法都遵循四个步骤：

-在时间t=0（开始之前）：
**（i）预处理：**通过调用假设3中描述的离线预言机，计算预期LP[｛Ft｝t t=1]的最优分配｛yS，t，zt｝。此外，计算算法偶尔需要的任何其他离线参数。
-在每个时间t＝1、2、。，T：
**（ii）模拟：**当在时间T实现消费者类型zt时，外部程序建议通过从S上的分布{yS，T，zt}S∈S中采样S∈进行分类。
**（iii）丢弃：**对于每个产品i∈SÜ，一个单独的内部丢弃程序决定是否将该产品从最终分类中移除，考虑到时间t之前的历史和实现的类型zt。如果手头没有可用的产品i，则会自动丢弃，以保证库存的可行性。否则，产品i的内部程序决定是否丢弃。设S⊆S⊂是未放弃产品的集合。
**（iv）后处理：**给定zt、S和S，在S的所有子集上选择概率分布Fzt，S，S。然后，选择一个产品组合S~~Fzt、S、S并提供给消费者。

在上述四步布局中，步骤（ii）是预期LP[{Ft}T T=1]的最优解的无损失随机舍入；然而，最终的分类只保证了预期中每种产品的库存可行性。步骤（iii）和步骤（iv）的作用是确定这种可行的期望分类的（随机化）子集，不仅保证每个样本路径中的库存可行性，而且还保证由于丢弃产品而造成的预期损失很小。
3.2大型初始库存：接近竞争比率1−ε（cmin）*
本小节算法背后的主要思想是在每个时间t的步骤（iii）中以概率γ=O（p log（cmin）/cmin）随机丢弃每个产品。直观地说，这种丢弃尝试为每个时间t不违反任何库存约束留下足够的概率，如果丢弃一个产品不会改变另一个分类产品的选择概率，则每个产品i在每个时间t的预期不可用单元数为大多数（1−γ）ci–由于步骤（ii）中采样集预期的可行性。现在考虑产品i的租金指标随机变量，即表明该产品是否在每次出租的随机变量。如果这些随机变量在时间上是相互独立的，那么我们可以使用独立随机变量之和的简单集中边界来证明我们的主张。
上述方法存在两个主要问题：（I）在弱可替代性（假设1）下，丢弃产品I会微弱地增加另一个分类产品j的选择概率，如果我们仅模拟期望的LP最优解并以概率γ独立地丢弃每个产品，则这反过来增加了该产品在时间t的不可用单元的预期数量。
（二） 由于资源可重复使用且库存有限，产品i在时间τ<t的租金指标随机变量与同一产品在时间t的租金指数随机变量相关；事实上，当在时间t实现的租赁持续时间dτ不小于t−τ时，第一个指标迫使第二个指标为零，产品的最后一个单位在时间τ租赁，并且在[τ+1，t]期间没有产品的单位返回。
我们通过改变算法来解决第3.2.1节中的第一个问题，并通过修改分析来解决第3.2.2节中的第二个问题。
3.2.1.子分类抽样 为了解决第一个问题，我们提出了子分类抽样程序——步骤（iv）中使用的后处理程序。该程序确保在步骤（ii）中未丢弃的产品被到达的消费者以与预期LP基准的最优解中完全相同的概率出租。更正式地说，子分类抽样在每个时间t在S的子集上诱导分布Fzt，S，S，因此
（2）
目前尚不清楚这种分布Fzt、S、S是否存在，但仅能在多项式时间内采样（乘积n的多项式）；然而，对于满足弱可替代性（假设1）和向下封闭可行性（假设2）的任何一般选择模型，我们表明存在这样的分布Fzt，ûS，S，并且我们引入了在多项式时间内递归地从Fzt中采样集合的过程1。7
注释7值得注意的是，Goyal等人（2020a）独立并同时发现了一种类似于我们针对具有对抗性到达和可重用资源的设置的子分类采样的想法。
命题3。对于任何弱可替代且向下封闭的可行选择模型，任何分类S∈S，以及任何目标概率{pi}i∈S使得所有i∈S的pi≤⑪（S，i），过程1输出满足（i）S～8838S的随机分类S～；（ii）对于所有i∈S，ES _h（S，i）i=pi。
此外，它在时间上运行Poly（n）
算法1
备注2。为了保证在步骤（iv）中给定任何（zt，⑪S，S）的方程（2），我们通过设置← ⑪zt，S← S和pi← 对于所有i∈S´。请注意，对于所有i∈S，pi=⑪zt（⑪S，i）≤ύzt。
命题3的证明。在不丧失一般性的情况下，我们假设σ是恒等置换，即，对于i∈[m]，σ（i）=i。为了显示多项式运行时间，观察（a）每个递归中的运行时间是Poly（n）；和（b）此递归算法的迭代次数最多为n，因为开始时|S|≤n，并且作为下一递归调用的输入的S′的大小在每次迭代时缩小1，即|S′|≤|S|−1。
建筑持有的财产（i）。我们通过对m=|S|的归纳来展示性质（ii），即分类S的大小。在这个归纳中，我们使用了另一个简单的性质（iii），即对所有i∈S而言，对所有i，i）Pmj=iqj=pi，这通过构造立即成立。
基本情况（m=1）。在这种情况下，程序1随机输出∅或S。根据属性（iii），归纳陈述成立。
感应步长（m>1）。固定任意乘积i∈S。请注意，通过构造ES_h⑪（S，i）|j*<ii=0，并且ES_h⇔（S，i）| j*=m i=（S，i）。对于任何实现值j*=i。，m−1及其对应的S′={1，…，j*}，我们可以使用分类S′的归纳假设，对于每个i∈S′，概率p′i=（S，i）。这是真的，因为|S′|≤m−1，并且对于每个i∈S′，作为选择模型的（S，i）≤⑪（S′，i）是弱替代。通过调用归纳法假设当我们在下一个递归调用中使用S′时，对于所有j=i。，m−1。因此调用属性（iii），
（）
其完成感应步骤并完成验证。
3.2.2 算法与分析
现在，我们提出了第一个基于仿真的算法（算法2）及其竞争比率保证（定理1）。
算法2
定理1。通过设置γ=γ*（cmin），算法2与贝叶斯预期LP基准预期LP的竞争比率[｛Ft｝T T=1]至少为1-ε*（cmn）=1−O p log（cmin，cmin）/cmin。更重要的是，它在时间上运行Poly（n，T，P T∈[T]|Zt|），给定oracle对分类优化离线算法的访问权限（假设3）。
为了解决本节前面提到的第二个问题，我们在对算法2的分析中使用了一个谨慎的耦合论证，该论证将我们算法的租金指标随机变量与另一个假设算法相耦合。该假设算法忽略了所有产品的库存约束，仅模拟了预期LP的最优解以概率γ丢弃每个产品。该算法生成租金指标随机变量的独立序列，允许我们使用简单的集中边界。重要的是，这种耦合技巧只有在方程（2）中的子分类抽样程序的保证下才有可能实现，这将在稍后的证明中明确。
在证明定理1之前，我们回顾了证明中使用的Chernoff浓度边界的乘法形式（Chernoff等人，1952）。
引理1（乘性Chernoff界）。假设X1，X2。，Xt是取｛0，1｝中值的独立随机变量。X表示它们的和，µ=E[X]表示和的期望值。那么对于任何δ>0，
（）
定理1的证明。命题2和命题3很容易证明运行时间。为了证明竞争比，我们首先声称，对于任何时间段t和产品i，存在产品i的可用单位的概率至少为1−exp−γ2 2 c−min，定义了以下指标随机变量及其相应事件：γ。为了证明这一点，Ii，t：在时间t分配产品i的单位的事件；I（1）I，t：产品I在产品组合Sût中的事件；I（2）I，t：在算法2的第6行中，产品I未从分类S中删除的事件；I（3）I，t：在时间t开始时库存中有单位产品I可用的事件；I（4）I，t：产品I在S～t分类中并由消费者t选择的事件；Ii，τ，t：产品i在时间τ的租赁持续时间至少为t−τ的事件。
注意，根据定义，Ii，t=I（1）I，t·I（2）I，t·I（3）I。现在，我们的索赔相当于
（3）
对于任何时间t和乘积i。为了显示不等式（3），一个问题是{Ii，t}在t上不是独立的。为了解决这个问题，考虑一个假设场景，其中我们在没有库存约束的情况下运行算法2，并定义随机变量n zt†，SÜt†、i†i，t，i（1）i，t†；i（2）i，t†，i（3）i，τ的方式与在具有库存约束的算法2的正常运行中完全相同。注意，根据定义，（i）i（3）i，t†确定等于1；（ii）I†I，t=I（1）I，t†·I（2）I，t†·I（3）I，t†·Ⅰ（4）I，t=I（1 I，t=†·Ⅱ（2）I，t=†·Ⅲ（4）I，t:†；和（iii）{I†I，τ·I†I，τ，t}τ在τ上相互独立。
我们现在使用这个假设场景和算法2的正常运行之间的耦合，其中Pτ<t I†I，τ·I†I，τ，t≥Pτ<tIi，τ·Ii，t，t用于所有I，t。显然，我们可以定义耦合使得zt†← 中兴通讯†← SÜt（因此I（1）I，t†=I（1 I，t），I（2）I，t†← I（2）I，t和I†I，τ，t← Ii、τ、t。
此外，请注意
（）
其中第一等式因命题3中的子分类抽样的保证而成立，第二等式因上述耦合而成立。此外，当I（3）I，t=0时，第三等式自动成立，而当I（2）I，t=1时，由于命题3中的子分类抽样的保证，以及I（1）I，t=I（3，t†的事实，第三个等式自动成立。同样，由于上述耦合，我们得出结论：
（）
因此，我们可以进一步耦合随机变量I（4）I，t†·I（3）I，t← I（4）I，t·I（3）I，t。因此，I（4）I，t†·I（3）I，t†≥I（4（I），t†.·I（2）I，t=I（4。因此，足以证明
（）
为了显示上述界限，我们首先将期望值E I†I，τ·I†I，τ，t重写如下：，
（）
其中我们使用命题3中的E h I（4）I，t†|I（1）I，t†，I（2）I，t†I=⑪zt†（Sût†，I）·I（1（1）†I，t·I（2（I），t†）这一事实；E h I（2）I，t†| I（1）I，t†I=（1−γ；随机变量I†I，τ和I†I，τ，t独立于zτ。因此
（）
通过对独立随机变量序列i†i，τ·i†i，τ，t t−1τ=1应用Chernoff界（引理1）的乘法形式，我们完成了对我们主张的证明，即（3）中的尾界
图2
现在，固定任意时间t和乘积i。考虑乘积i在时间段t对算法2的收益的预期贡献。根据定义，它等于
（）
其中第三个等式由命题3成立；最后一个不等式成立，因为I（3）I，t与ri zt、I（1）I，t、I（2）I、t和SÜt相互独立，并且通过我们在（3）中的尾部约束，我们有
（）
因此，对于任何γ∈[0，1]，算法2至少（1−γ）1−exp−γ2 cmin 2–γ-与贝叶斯预期LP基准相比具有竞争力。最后，设置γ=γ*（cmin）完成验证。□ 备注3。我们在本节中的分析主要集中于cmin较大的渐近状态；然而，通过使用方程（1）对ε*（cmin）进行数值计算，我们仍然可以绘制算法2的竞争比1−ε*（cm in）。参见图2中的黑色实心曲线。
3.3小型初始库存：达到竞争比率1/2
在本小节中，我们提出了第二个基于仿真的算法。该算法与算法2的主要区别在于丢弃步骤：如果手头没有可用的产品i单位，则自动丢弃以保证库存可行性；否则，只有当ri zt≥P zt i，t时，才在最终分类中选择，其中P zt i，t是由算法计算的非自适应阈值前面（稍后将讨论）。这一丢弃程序的目的是确保只有具有足够高租赁费的可用产品被分类。
从技术上讲，对于每种产品，人们可以考虑一个单独的DP，以最佳地做出分类决策。考虑到步骤（ii）的随机建议（召回第3.1节），该DP将在有限的时间范围内使产品i的分类单位的单位收入最大化[1:T]。缺点是需要一个高维状态变量来跟踪现有产品库存，以及正在使用的产品单位的库存（并将在不同时间返回库存）。我们算法的一个主要组成部分是用一个与库存无关的简单DP来代替这个高维DP，并在Bellman方程中使用实际库存的ci的乐观上界来更新产品的最优单位收入
3.3.1 与补货配合的单位收入动态规划
在本小节的其余部分中，对于每个S、t和zt，设XS、t、zt≜yS、t、zt Ft（zt）。假设在每个时间t，实现一个新的独立消费者类型zt～Ft。设Sû～XS，t，zt表示在步骤（ii）（模拟步骤）中采样的随机化子集。固定产品i∈[n]，初始库存为ci单位。现在，考虑一个假设情景，即一个外生过程每次都会补充库存，以确保我们手头始终有ci个产品单元，无论当前有多少个单元处于租赁状态。在这个新问题中，目标是设计一个在线策略，一旦在步骤（ii）中建议，就丢弃或接受可重复使用的产品单元，以便最大化租赁该产品的单位收入。我们可以使用一个简单的动态规划来表述这个问题，其中Vi，t是在时间间隔[t:t]内产品i的最佳单位收益。与用于解决最优丢弃的原始高维DP相比，该DP是乐观的，因为它“想象”了每一个周期都会补充库存中的不足。
按照惯例，设Vi，T+1=0。为了使用后向归纳法在时间t编写乐观DP的贝尔曼更新方程，假设实现了类型zt，并且SÜ=S（这发生在p.XS，t，zt）。
如果最优策略决定放弃产品i，则单位收益将为Vi，t+1。如果最优策略决定不丢弃i，那么在概率为（1−⑪zt（S，i））的情况下，单位收益仍将为Vi，t+1。8
注释8在这个假设场景中，我们假设消费者选择产品i的概率等于⑪zt（S，i），而不管是否从S中丢弃了另一个产品i′。
然而，在概率为⑪zt（S，i）的情况下，消费者租用了其中一个ci单元（请记住，库存将始终是满的），因此产生的总收入为（ci−1）Vi，t+1（即，由于在时间t未租用的单元的贡献；这些单元将在时间t+1转移到库存中）加上ri zt+Vi，t+d在实现租赁时间d～G z i t时（即，由于租赁单位的贡献）。
总之，我们将使用以下Bellman更新公式：
（4）
注意，可以通过重新排列术语来简化上述动态编程的更新规则；有趣的是，规则将独立于ci和⑪zt（S，i），因为它们抵消了
（5）
备注4。稍后在EC.1和EC.5节中，我们将用一个稍微修改过的DP替换这个简单的DP，该DP具有库存依赖状态，但在租赁时间无限时仍然是低维的。
这使我们能够获得（几乎）这种特殊情况下的最佳竞争比率。
3.3.2 算法与分析
现在，我们提出了第二个基于仿真的算法（算法3），其竞争比率保证（定理2）。9
注释9定理2中的竞争比率是最优的，即使租赁时间是无限的。考虑以下示例：有一个具有单个单元的不可重用产品。有两个时间段T=2。消费者1具有一种确定性类型，即以1美元的价格确定购买该商品。在概率为ε的情况下，消费者2的类型决定以1/ε的费用购买该商品。否则（即，概率为1-ε），消费者2的类型是什么都不买的。
在本例中，贝叶斯预期LP基准以及透视策略的预期收益为2-ε，而任何在线策略的预期收入最多为1。
算法3
定理2。算法3与离线贝叶斯预期LP基准（即，预期LP[{Ft}T T=1]）的竞争比至少为1/2。此外，它在时间上运行Poly（n，T，P T∈[T]|Zt|），给定oracle对分类优化离线算法的访问权限（假设3）。
定理2的证明草图。命题2证明了运行时间，第3.3.1节中的简单DP可以在多项式时间内求解。竞争比率的分析可以在产品之间解耦。对于每个固定产品i，我们分两个部分进行分析，每个部分如下所示（参见第EC.4节中的完整细节）：•第（i）部分–第EC.4.1节：我们首先将算法3与第3.3.1节中描述的简单乐观动态规划进行比较，并显示出算法3由于产品i的租金而产生的总预期收入至少为ciVi，1。我们使用归纳法证明了这一说法，并且事实上，显示采样分类SÜt的子集仅能增加遵循乐观DP阈值的丢弃策略的收益（如在算法中）。
•第（ii）部分–第EC.4.2节：然后我们将这个简单的动态规划与预期LP基准进行比较，并表明对于每个产品i，ciVi，1至少是产品i对预期LP的最佳目标值的贡献的1/2[｛Ft｝T T=1]（第（ii）部分）。为了证明这一部分，我们使用了第3.3.1节中的乐观DP与描述乐观DP竞争比率的相关因素之间的联系。这种联系导致我们应用对偶论证，以找到ciVi，1的比率和乘积i对预期LP[{Ft}T T=1]的最优目标值的贡献的下限。
3.4 算法2和算法3的混合
两全其美的丢弃 在算法2和算法3中，我们都有相互独立运行的丢弃策略（每个产品一个）。此外，两种竞争比率分析在不同产品之间基本上是解耦的，因为我们分别分析了每个产品的这些丢弃策略的收益表现。此外，在这两种分析中，我们将每个产品i的预期收入与该产品在预期LP中的贡献进行比较。
考虑到我们两种算法的所有上述设计和分析方面，我们可以提出一种混合算法，在该算法中，我们基于每个产品i的初始库存ci来决定丢弃策略的选择。一旦我们完成了这些选择，我们就在最终混合算法的丢弃步骤中，为不同的产品并行和单独运行（可能不同）丢弃算法。为了实现小型和大型库存制度的最佳收益绩效保证，我们在一开始就将这组产品划分为初始库存较大的产品和初始库存较小的产品（稍后将正式定义）。
给定此分区，如果ci较大，我们分配一个“随机丢弃”策略（如算法2中所述），以在时间t∈[t]上做出产品i的丢弃决策，如果ci较小，我们使用“具有单位收入阈值的丢弃”（如算法3中所述）。为了区分大ci和小ci，我们首先通过使用其Bellman更新方程（如方程（4）所述）来解决第3.3节中每个产品i∈[n]的乐观DP丢弃策略的动态规划。然后，我们使用产品i的乐观DP的值函数Vi，1将该产品标记为大库存或小库存。特别地，将Ri定义为产品i的乐观DP的预期收益与该产品对预期LP目标的贡献之间的比率，即。，
（）
注意定理2中的Ri∈[0.5，1]。还应注意，ε（c）在c中是连续单调递增的，ε*（0）=1，且ε*（+∞）=0-关于ε*（·）的定义，请参见方程（1）。接下来，我们将比率Ri与1-ε*（ci）进行比较。事实上，如果Ri+ε*（ci）<1，我们将随机丢弃的竞争比率排除在外，使其不小于乐观DP的竞争比率，因此我们将该产品标记为“大库存”。否则，我们期望乐观的DP在竞争比方面击败随机丢弃，因此我们将产品标记为“小投资”。最后，我们执行子分类抽样作为后处理步骤，以纠正未丢弃产品的选择概率（可能由于替代性较弱而增加，其他产品要么被丢弃，要么甚至没有在分类中被选择，因为它们最初不可用）。我们用Sim+Hybrid（i）表示得到的算法。
定理3。Sim+Hybrid（i）与离线贝叶斯预期LP基准的竞争比，即预期LP[{Ft}T T=1]，至少为1−min
蒙特卡洛模拟有帮助 原则上，给定类型分布序列｛Ft｝T T＝1，可以模拟算法2和算法3，并使用蒙特卡洛模拟来估计它们的预期未来收入，从任何时间T∈[T]开始（给定直到时间T的任何历史）。现在，一个简单的混合算法可以切换到具有更高预期收入的算法，并在给定当前租赁产品历史的下一个时间步骤中运行该算法。通过在给定到目前为止的历史的每个时间t重复应用该方法（一种称为条件期望方法的技术），我们最终得到了一种替代的混合算法，该算法本质上是在两项政策中，每次都要成为领导者政策，这意味着其每次的预期未来收入至少是两项政策的预期未来收益（可以使用归纳法证明）。因此，该混合算法明显地获得了1−min的两个世界的最佳竞争比
备注5。我们想强调的是，虽然Sim+Hybrid（i）和Sim+Hyatt（ii）都达到了前面提到的理论上的两全其美的竞争比率，正如我们在第4节的数值模拟中看到的那样，它们在我们问题的实际场景中都优于其他现有策略，但它们在计算要求方面有所不同。事实上，Sim+Hybrid（i）可以很容易地为每个产品i的丢弃策略的选择做出预先决定，与算法2和算法3相比几乎没有额外的计算；然而，Sim+Hybrid（ii）需要通过从未来类型中进行采样来多次运行蒙特卡洛模拟（取决于切换频率），这使得它在实际中不那么吸引人。

4 数值实验

实验设置。在我们的测试问题中，我们有六个由{1，2，3，4，5，6}索引的产品。每个产品的初始库存ci=30。我们考虑从自己的“考虑集”中选择的消费者（Howard和Sheth 1969，Aouad等人，2020）。考虑到消费者的考虑集，我们假设她基于多项Logit（MNL）选择模型从该集中选择产品。更具体地说，我们有六类消费者。类型j∈{1，2，3，4，5，6}的消费者考虑产品[1:j]。给定分类集S，她选择产品i∈S，其概率为⑪j（S，i）=αj i/（α0 j+P l∈Sαj l）。对于类型为j的消费者，αj i=0表示i>j（即，她不会选择超出其考虑范围的产品）。每个非零的αj i都是从区间[0.9，1.1]随机独立且均匀地绘制的。为了给消费者选择外部选项的可能性，我们将α0 j设置为α0 j/（α0 j+P l∈[1:j]αj l）=0.1。注意，类型1的消费者是最挑剔的（思想单一），而类型6的消费者是最少挑剔的。对于类型为j的消费者，产品i的租赁费r j i是从区间[10·η（j，κ），25·η（j，κ）]中随机抽取的，其中η（j、κ）≜1+2κ·6−j 5，且κ≥0是在我们的模拟案例中变化的参数（将在后面详细说明）。在为j类消费者生成租赁费rj=（r1j，…，r6j）后，我们重新排序，使r1j≥r2j≥…≥r6 j中。
我们考虑了长度T=300的离散时间销售/租赁期限，以及以与Rusmevichientong等人（2020）类似的方式针对不同类型到达的非平稳模型。粗略地说，为了得到最坏的类型分布顺序，我们打算有一个到货订单，在那里挑剔的消费者会在销售期晚些时候到达。通过这种方式，政策需要为这些消费者谨慎地保留足够的库存（如果没有租赁），或者考虑产品的有限租赁期限，并谨慎地管理，以便在挑剔的消费者到达时（如果有租赁）有足够的物品返回库存。为了捕捉这种到达方式，我们将销售范围划分为长度相等的块τ=T/6。设τj=（6−j）τ+1，对于j=1，2。，6.
在每个时间t，j型消费者以与e−0.001κ| t−τj|成比例的概率到达，即。，
（6）
注意，κ=0对应于来自均匀分布的类型的i.i.d.到达。随着κ的增加，到达变得更加异质（以类型的降序向确定性到达收敛）。
我们考虑两类场景：第一类场景没有租金（见图3），第二类场景有租金（见图4）。对于每个类别，我们考虑与κ∈{0，1，2，3}相对应的四个测试场景。
在第一种情况下，我们为每种产品i设置初始库存ci=30。类型j的消费者的产品i的租赁持续时间被设置为随机变量T/10+Xj，
其中Xj是几何分布的，其平均值从模拟开始时的间隔[20·η（7−j，κ），20·η。
为了衡量每个场景中不同策略的预期收益，我们考虑通过进行50次蒙特卡洛模拟迭代，在输入的独立样本路径（包括类型实现、消费者选择和租赁持续时间）上运行目标策略。然后，我们记录所有运行/样本路径的产生收入，并使用“盒和须”图来证明这些数量的中值收入和由此产生的置信区间（图3和图4）。
此外，我们计算所有运行/样本路径的平均收入，作为每个策略的预期收入的估计（表1和表2）。
政策。在我们的数值实验中，我们比较了本文或之前工作中提出的八种不同策略/基准的预期收益：1。库存平衡（IB）：Golrezaei等人（2014）通过跟踪可重复使用产品的库存水平，对库存平衡算法进行了调整。对于我们的实验，我们考虑使用指数惩罚函数Ψ（x）=e1−x−e1−e的变体。
2.近视贪婪策略（GR）：给定每个时间段的可用产品，GR此时提供（近视）最佳分类。当Ψ（x）=✶｛x＞0｝。
3.贪婪与价值的线性近似（GR APXLinValue）：该政策是Rusmevichientong等人（2020）提出的近似DP政策，本质上是一种贪婪的近视政策，与最优收益函数的线性近似有关。更多详情请参见Rusmevichientong等人（2020）的第3节。
4.推出政策（推出）：该政策通过对Rusmevichientong等人（2020）第4节中提出的静态政策应用推出10获得。
注释10在这种情况下，静态策略的推出是通过首先使用bakward归纳法计算静态策略的收益-收益函数来计算的，然后在假设未来收益等于静态策略的计算收益-收益值的情况下，贪婪地选择每次的最佳分类。
5.分解（Deco）：该策略是Liu和van Ryzin（2008）提出的另一种近似DP策略，它首先分解产品中的原始DP，然后通过求解每个产品的单独DP来构建价值函数近似值。该策略在实践中被广泛使用，但没有理论性能保证。
6.具有混合丢弃规则的基于仿真的策略（Sim+hybrid（i））：该策略是第3.4节中讨论的第一类基于仿真的混合策略。具体而言，对于每种产品，它比较了不同丢弃策略的近似保证，即算法2中的随机丢弃和算法3中的每单位收入阈值（以及算法4中无租金场景的库存相关收入阈值）。然后分别为每个产品选择具有更高近似保证的丢弃策略
7.基于模拟的策略，通过蒙特卡洛模拟进行混合（Sim+hybrid（ii））：该策略是第3.4节中讨论的第二类基于模拟的混合策略。具体而言，在每10个周期之后，它通过进行20次蒙特卡洛模拟迭代来估计算法2和算法3（以及无租金场景的算法4）的预期未来收入；并转向具有更高估计未来收入的政策。
8.贝叶斯预期LP：该基准是第2节中定义的贝叶斯LP基准预期LP[{Ft}T T=1]。它提供了任何可行在线政策的预期收入上限（当预期被接管类型、消费者选择和租赁期限的随机性以及政策的内部随机性时）。
表1表2
后果为了总结我们在本节中运行的模拟结果，我们分别考虑了上面提到的两个类别：1。无租金：在这种情况下，从表1和图3可以明显看出，Sim+Hybrid（i）和Sim+Hyatt（ii）在所有κ方面的性能明显优于其他产品。具体来说，通过对场景κ∈{0，1，2，3}进行平均，将其他策略与我们的混合策略进行比较：
Sim+Hybrid（ii）的平均性能比GR（分别为Deco、GR+APXInValue、Rollout、IB、Sim+Hybrid（i））高33.2%（分别为26.0%、30.8%、28.4%、15.3%、0.3%）。值得注意的是，Sim+Hybrid（i）和Sim+Hybrid（ii）之间的差距很小。
注释11值得一提的一点是，Rusmevichientong等人（2020）报告了在非常相似的模拟设置中，与IB相比，推出的性能更好。虽然这在表面上看起来是矛盾的，但我们验证了这种差异背后的原因是，他们每100个时间段重新计算Rollout使用的近似值，这提高了其性能。为了进行公平比较，我们没有重新计算任何参数。
随机和有限租金：在这种情况下，从表2和图4可以清楚地看出，Sim+Hybrid（i）和Sim+Hyatt（ii）在所有κ方面的表现明显优于其他政策。
具体而言，Sim+Hybrid（ii）的平均性能比GR（分别为Deco、GR+APXLinValue、Rollout、IB、Sim+Hybrid（i））高24.8%（分别为21.8%、42.9%、34.8%、8.3%、5.5%）。
图4当存在具有随机持续时间的依赖于类型的租金时，不同政策在预期收入方面的盒和胡须比较。结果基于蒙特卡洛模拟的50次迭代。

5 结论

我们研究了在贝叶斯环境中为可重用资源的在线分类设计近乎最优的算法。我们提出了一个基于四个模块化步骤的算法框架：（i）解决预期的LP，（ii）模拟解决方案，（iii）为每种产品运行单独的丢弃程序，以保持逐点库存的可行性（同时仅损失每种产品收入的可忽略部分），以及（iv）执行后处理步骤以调整未丢弃项目的选择概率。使用该框架，我们设计了一个在一般租赁持续时间分布下为1−min1 2，O p log（cmin）/cmin的算法，以及在无限租赁持续时间下具有竞争比1−1/p（cmin+3）的改进的近最优算法。不仅如此我们的算法在理论上优于文献中的现有算法，我们通过数值模拟进一步验证了它们的收益性能优势。
作为未来的路线图，研究现实世界分类问题中除可重用资源之外的其他实际方面可以建模，以及数学编程技术可以在多大程度上用于设计有竞争力的算法，是很有意思的。在技术方面，我们工作中最直接的公开问题是找到一般租赁期限分配情况下的最佳竞争比率。特别是，我们可以在我们的竞争比率中去除对数因子，获得1−O（1/√cmin）竞争算法，类似于不可重复使用情况下的最佳已知竞争比率吗？作为一个不同但更具雄心的未来方向，进一步研究类似于贝叶斯在线分类的随机在线优化类将是有趣的，以便发现计算的计算难度或近似最佳在线策略，即DP策略。这里一个有趣的发现是，通过多项式时间策略，获得针对最佳在线基准与预期LP基准的改进近似值，`a la Anari等人（2019），或证明其不可能

EC.1讨论和辅助结果

EC.1.1。静态与动态替代和子分类抽样。
在本节中，我们讨论了文献中研究的静态替代和动态替代的子分类抽样与分类优化之间的联系（参见。
Ma等人2018）。我们首先介绍了静态替代和动态替代的定义，然后讨论了它们与离线（单镜头）分类问题中的子分类抽样的联系，最后我们将讨论扩展到本文所考虑的在线（多时段）分类问题。
在我们的模型中，平台只能形成可用产品的组合。另一种模式假设是，无论产品的可用性如何，平台都可以形成产品组合。
在这个替代模型中，我们区分了消费者如何根据显示的产品种类和可用性做出决定的两种设置。
•静态替代：给定所有产品的分类S和可用性状态，选择模型为的消费者选择项目i的概率为（S，i），只有当所选产品i可用时，销售才是最终的。
•动态替代：给定产品类别S和所有产品的可用性状态，具有选择模型的消费者选择项目i，其概率为（S，i），其中产品类别S包括S中的所有可用产品。根据定义，消费者从不选择不可用产品。
值得注意的是，在离线（单镜头）分类问题中，子分类抽样在静态替代和动态替代之间建立了以下联系。
提案EC.1。对于任何弱可替代和向下封闭的可行选择模型⑪、任何分类S∈S和任何可能的产品可用性，存在一个随机分类S，使得对于每个产品i∈[n]，产品i在静态替代中被分配在类别S下的概率等于产品i在动态替代中被配置在类别S～下的预期概率（在S～的随机性上）。
证据通过设置⑪调用命题3← ⑪，秒← S和pi← 对于所有i∈S，（S，i）完成证明。□ 在在线（多周期）分类问题中，我们基于模拟的算法首先基于贝叶斯期望LP期望LP的最优分配对分类SÜt进行采样[｛Ft｝t t=1]，然后通过移除不可用的产品以及丢弃程序建议丢弃的产品来构建分类S´t。我们将静态替换的定义调整如下。
•带取消的静态替代：给定产品组合S，选择模型为的消费者选择产品i的概率为（S，i）。观察消费者的实际选择后平台可以立即收回该产品i，而无需为丢弃或因不可用而支付任何费用。
在带抵消的静态替换下，我们可以简化基于模拟的算法（算法2和算法3），并通过如下修改后处理步骤来保持相同的竞争比率保证（定理1和定理2）：向消费者t提供分类SÜt，如果i̸∈SÜt，则收回消费者t选择的产品i。上述修改算法3的竞争比率保证遵循与之前完全相同的论点。为了了解为什么上述修改的算法2保持了竞争比，请注意，与定理1中算法2的论点类似的论点仍然成立。特别地，我们可以考虑一个假设场景，其中我们在没有库存约束的情况下运行修改后的算法2，并且正常运行修改后算法2；有趣的是，在带抵消的静态替换下，这一次两种场景之间的耦合变得微不足道，然后假设场景的集中度论证结束了论证。
另一方面，具有动态替代的在线（多周期）分类问题本质上是正文中考虑的确切问题。在这个意义上，定理1的证明中的子分类抽样和耦合论证可以被解释为从具有动态替换的在线分类问题到具有静态替换（具有取消）的在线分类

EC.1.2.提高了不可重复使用案例的竞争比率。
作为一个副作用，主要是为了我们的数值模拟，我们在第EC.5节中考虑了不可重用资源的贝叶斯在线分类的特殊情况，Rusmevichientong等人（2020）对此进行了研究。
我们遵循基于模拟的方法，然后类似于第3.3.1节，我们使用动态规划来捕获该产品的最佳丢弃策略的预期收益，当产品从基于仿真的外部算法接收到（概率）建议以放入分类时。12(注释12此动态规划是Alaei等人（2012）中先知不等式匹配动态规划的推广这一次的主要区别在于，我们实际上可以计算并运行精确的最佳丢弃DP。)为此，固定乘积i∈[n]。注意，在无限租赁期的情况下，当前库存水平起着状态的作用（这是一个单调递减的数量，因为产品的单位永远不会返回库存）；因此DP具有多项式大小的状态空间，并且原则上可以有效地计算，即在多项式时间内。
事实证明，解决这个DP与Alaei（2014）中介绍和研究的“魔术师问题”密切相关，这本身就是一个在线竞争解决方案的特例简单均匀拟阵环境（Feldman等人，2016）。通过利用本文中介绍的技术并将其扩展到贝叶斯在线分类优化问题，我们表明，遵循最优DP的丢弃算法损失的LP预期收入不超过1√cmin+3（这与魔术师问题中的近似因子相同）。
具体而言，假设E I I，t表示当I是时间t的剩余库存时，产品I在[t，t]期间从最优丢弃策略中获得的预期收入。类似于第3.3.1节中关于单位收入阈值的讨论，假设在时间t对分类Sû～XS，t，zt进行采样。
如果DP丢弃策略丢弃来自抽样分类S的产品i，则预期收益变为E i i，t+1；否则，消费者选择产品i的概率为⑪zt（⑪S，i）13，(注释13与第3.3.1节相似，这里我们考虑一个假设场景，其中消费者选择产品i等于⑪zt（⑪S，i）的概率，而不管是否从S中丢弃了另一个产品i′。)预期收益为E i−1 i，t+1+ri zt。在剩余概率下，产品i未被选择，预期收益为E i i，t+1。因此，我们可以使用动态编程（即反向诱导），使用以下Bellman方程计算E I I，t：
(EC.1)
重新排列术语后，很容易观察到DP决策是由依赖于库存的收入阈值规则做出的（这独立于{⑪zt（S，i）}，因为这些术语抵消了）：
()
现在，我们已经准备好用一个新的丢弃规则来呈现我们完善的基于模拟的策略。该规则使用上述依赖于库存的阈值，其中这些阈值是预先计算的，但它们取决于产品、时间和产品的当前剩余库存水平。详见算法4。
定理EC.1。设cmin=mini∈[n]ci为最小库存。算法4与离线贝叶斯预期LP基准（即，预期LP[{Ft}T T=1]）的竞争比至少为1−1√cmin+3。此外，它在时间上运行Poly（n，T，P T∈[T]|Zt|），给定oracle访问离线算法进行分类优化（假设3）。
该证明遵循与定理2的证明类似的结构。详见第EC.5节

EC2.最佳离线的无限竞争力

在本节中，我们构建了一个简单的例子，表明贝叶斯期望LP期望LP[{Ft}T T=1]至多是最优离线的O（1/T）近似。结合命题1，这意味着任何在线算法都不能实现与最优离线相比的（T无关）有界竞争比。
算法4
定理EC2。贝叶斯期望LP期望LP[{Ft}T T=1]至多是最佳离线的O（1/T）近似。
推论EC.1。没有一种在线算法能够实现与最优离线相比的（不依赖于T的）有界竞争比。
定理EC.2的证明。考虑以下实例，其中有一种产品和一种消费者类型。对于该产品，其初始库存为1，奖励为1。一旦分配了该产品，实现的租赁期限为一（即，在下一时间段内可用），概率为1/2，否则为无限。在每个时间段t∈[t]，具有这种单一消费者类型的消费者以概率1到达平台。消费者选择该产品（如果有）的概率为1。
首先，我们声称最佳离线的预期收入至少为T/2。请注意，最佳离线观察产品在分类前每个时间段的租赁持续时间实现情况，因此它可以在该时间段内实现租赁持续时间时对产品进行分类周期是一。由于此类时间段的预期数量为T/2，因此最佳离线的预期收入至少为T/2。
接下来，我们考虑贝叶斯期望LP期望LP[{Ft}T T=1]及其对偶程序：
（）
考虑双重方案中目标值为2的以下可行双重方案：
（）
调用上述原始对偶线性程序之间的弱对偶完成证明

EC.3第2节提案1中省略的证据。

对于任何类型的分布｛Ft｝T T＝1，千里眼最佳在线基准的预期总收入由预期LP〔｛Ft｝T＝1〕上限。
证据设IS，t（z）∈｛0，1｝是透视最佳在线基准在给定类型序列z＝｛zt｝t＝1的时间t提供集合S的指示符。由于透视最佳在线基准对于租赁持续时间d＝｛dt｝T＝1的任何样本路径都是可行的，因此对于所有i∈[n]，T∈[T]，我们有：
（）
现在，请注意，随机变量dτ独立于随机变量is，τ（z），因为透视最佳在线基准在时间τ对集合进行分类时无法看到dτ。因此，设置yS，t，zt＝E IS，t（z）zt导致在对应的线性程序中对任何类型分布序列｛Ft｝t t＝1的期望LP[{Ft}t t＝1]的可行赋值；要看到这一点，首先考虑到租赁期限上的上述不平等的LHS，然后考虑到类型是独立的，考虑到z。此外，此任务下预期LP[{Ft}T T=1]的目标值将等于千里眼最佳在线基准的预期收益，该基准完成了证明。□ 提案2。给定离线分类的算法（假设3），可以在时间Poly（n，t，P t∈[t]|Zt|）中有效地计算期望LP[{Ft}t t=1]的最优分配{yS，t，z{t}。此外，yS，t，zt}不超过Poly（n，t，P t∈[t]|zt|）个非零条目。
在证明上述命题之前，我们首先陈述了一个关于椭球算法的技术引理，并简要说明了其证明（参见Gr¨otschel等人1981年的详细证明）。
引理EC.1。假设一个原始线性规划是有界且可行的。此外，假设其对偶具有运行时间最多为τ的分离预言。然后primal接受一个最优解，该最优解具有Poly（τ，m）非零项，并且可以在Poly（σ，m）时间内计算，其中m是对偶变量的数量（原始约束）。
引理EC.1的证明草图。因为原始LP是可行且有界的，所以对偶也是可行且有边界的。现在考虑使用分离预言运行椭球算法来解决对偶问题。
椭球可以在Poly（τ，m）时间内解对偶。现在，通过观察椭球体的运行，并仅考虑椭球体返回为违反的对偶约束，我们可以在对偶中找到Poly（τ，m）许多约束，使得如果我们丢弃剩余的约束，对偶值不会改变。
注意，对偶中的约束对应于原始中的变量。因此，我们可以丢弃原始变量中的所有变量，除了与分离预言要求我们保留的对偶约束相对应的变量，LP值不变。现在我们在原始中有一个紧凑的LP，我们可以再次求解，以获得具有Poly（τ，m）非零项和时间Poly（t，m）的简洁原始解。□ 命题2的证明。给定引理EC.1，我们已经准备好证明离线预言机可以有效地解决预期的LP。预期的LP[{Ft}T T=1]具有指数级的变量和（nT+T）约束。因此，它的对偶只有（nT+T）个变量和指数多个约束。
这里是对偶LP，具有对偶变量θi、t和λt：
（）
现在，固定t∈[t]，zt∈zt，并考虑对应于t和zt的对偶约束组。为了获得这组约束的分离预言，给定λt，zt和{θi，τ}，需要找到一个集合Sû∈arg max S∈S X n i=1ûRiězt（S，i），其中
（）
那么，如果λt，zt≥X n i=1⑪Ri⑪zt（⑪S，i），则满足这些约束，如果不满足，则对应于t，zt，S的约束是分离超平面。注意，由于S的向下接近性，即假设2，以及⑪zt（S，i）的弱可替代性，即假定1，我们可以丢弃其中Ri<0的产品，因此在不丧失一般性的情况下，假设Ri≥0。因此，多亏了假设3，只需调用一次预言就可以找到这样的子集Sû。通过对所有可能的t和zt进行多项式时间搜索，对偶将得到一个运行时间为Poly（n，t，P t∈[t|zt|）的分离预言。调用引理EC.1完成证明。□

EC.4.第3.3节（小库存）省略的技术细节

在本节中，我们对定理2中所述的算法3的竞争比进行了详细分析。如定理2的证明草图所述，分析由两个主要部分组成。我们首先将算法3与第3.3.1节中描述的简单动态规划进行比较，并显示由于产品i的租金，算法3的总预期收入至少为ciVi，1（第（i）部分，附录EC.4.1）。然后，我们将该简单动态规划与预期线性规划基准进行比较，1至少是产品i对预期LP[{Ft}T T=1]的最优目标值的贡献的1/2（第（ii）部分，附录EC.4.2）。将这两部分结合起来，就完成了定理2的证明。
EC.4.1.证明的第（i）部分：与乐观DP相比
在这一部分中，我们使用向量变量J=（J1，…，JT）来跟踪固定产品i的库存状态，其中JT是在时间t将返回库存的产品i的副本数量。注意，在每个时间t，可能的状态J具有以下形式
（）
其中P Tτ=T Jt=ci。现在假设Qi，t（J）表示当算法在时间t从初始状态J开始时，算法3从时间t到t产生的产品i的单位收入。
14（注释14等价地，Qi，t（J）等于[t:t]中产生的产品i的总收入除以Jt，Jt是开始时间t时产品i的现有单位数。）按照惯例，设Qi，T+1（J）=0。我们证明了以下更强的引理，这也表明产品i产生的总收入不低于ciVi，1。Lemma EC.2背后的直觉如下：Vi，t是通过乐观DP计算的，该DP“想象”库存的不足在每一个时期都会得到补充，预期收益是库存水平的凹函数——即库存水平越高，单位预期收益越低。
引理EC2。对于时间t处的每个t∈[t]和每个可能的库存状态J，Qi，t（J）≥Vi，t。
证据为了简化证明，我们首先假设算法不执行作为后处理步骤的子分类采样（因此S ~t与S ~t相同）。在这个简化假设下，我们首先完成了证明。然后，我们将证明中的分类集S？t替换为S？t⊆S？t时，证明仍然保持完整，这是在算法3的后处理步骤中使用子分类抽样程序时的相关情况。
该证明基于对t的反向归纳。对于归纳的基础，Qi，t+1（J）=Vi，t+1=0。
现在假设在[t+1:t]和可能状态J中的任何时间，引理的陈述成立。我们可以只需为Qi，t（J）编写以下更新方程（遵循与方程（4）中动态编程的更新规则完全相同的逻辑，但考虑到手头只有Jt产品）：
（EC.2）
其中S⊆S是丢弃步骤后算法3中为消费者t提供的分类，J′≜（0，…，0，0，Jt+Jt+1，Jt+2，…，Jt）是时间t+1的下一个状态，如果在时间t没有发生出租，如果出租发生在时间t，出租持续时间为d（其中该状态的随机性来自未来时间[t+1：t+d−1]期间的所有类型实现和消费者选择），则J￣（τ，d）是算法3在时间t+τ的（随机化）状态。现在，通过将我们的归纳假设应用于等式（EC.2）和弱替代（即，对于所有i∈S，i而言，（S，i）≤⑪（´S，i）），我们得到：
（EC.3）
还应注意，上述不等式的RHS作为Jt的函数是不增加的，这仅仅是因为如果1Jt增加了加性ε>0，则RHS增加了
（）
因此，当Jt≤ci时，我们有
（）
现在假设我们在后处理步骤中使用子分类采样（步骤1）。执行此后处理步骤不会降低算法3中“每单位收入阈值”P zt i，t丢弃的收入保证。事实上，显示S的任何子集（例如，每次子分类抽样程序的输出S⊆S）只能增加遵循乐观DP阈值的保单的单位收入。更准确地说，在某个时间t，查看上述证明中的归纳步骤。当ri zt≥P zt i，t时，等式（EC.3）中第一个不等式的右手边只能增加，如果我们用S⊆S⊂代替S，简单地说，因为由于弱替代，所以，当ri zt≥P zt i，t时，方程（EC.3）中第一个不等式右手边的系数为非负，因此。其余的归纳法类似于简化的案例，完成最终的证明。
EC.4.2.第（ii）部分：比较乐观DP与预期LP
为了证明这一部分，我们使用了第3.3.1节DP与相关LP之间的联系。
这种联系导致我们应用简单的对偶论证来找到ciVi，1的比率和乘积i对期望LP的最佳目标值的贡献的下限[{Ft}T T=1]。
注意，缩放{ri-zt}不会改变比率。因此，在不丧失一般性的情况下，我们将乘积i对期望LP[{Ft}T T=1]的最优目标值的贡献归一化，即。，
（）
鉴于上述观察结果和（4）中的Bellman更新，考虑以下给出比率最坏情况值下限的原始线性程序：
（EC.4）
其中我们允许V={Vi，t}t t=1和r={ri-zt}t∈[t]，zt∈zt都是变量（这是该技术的一个重要特征）。我们首先通过切换第一个约束的RHS中的外部求和和最大算子来放松和简化这个程序（这只会使RHS变小，因此是放松）。还应注意：
（）
现在，通过将新的约束Vi，t≥max{A，B}替换为两个约束Vi、t≥A和Vi，t≥B，我们得到以下最终原始线性规划：
（Primal-LP1）
现在，我们用对偶变量{αt}、{βt}和µ编写其对偶程序如下：
（Dual-LP1）
现在，我们尝试猜测对偶程序的可行解，以获得最优原始目标的期望下界。为此，让∀t:αt=µci（因此，第一组约束将自动满足），并让所有其他约束都严格。特别地，β1=ci-α1=ci（1-µ），并且对于所有t∈[2:t]：
（）
其中（1）可以通过改变求和的顺序并重新排列项来获得，并且（2）由于{y*S，t，zt}在预期LP[{Ft}t t=1]中的库存可行性而成立。现在，设置µ=1/2可以保证双重可行性，因为∀t:αt≥0，βt≥0。通过应用弱对偶，期望的比率至少为µ=1/2，这完成了证明。

EC.5.无限租赁持续时间特例的省略细节

在本节中，我们考虑了租赁时间无限的情况，即一旦消费者购买了产品，他们就再也不会返回平台。在这种情况下，每种产品的库存水平随着时间的推移逐渐降低。这使我们能够使用动态规划在多项式时间内开发依赖于库存的丢弃策略。这些丢弃政策比第3.3.1节中讨论的单位收入阈值政策更为精细，并实现了更好的竞争比率（即1−1√cmin+3），这在库存较大时接近最佳。
定理EC.1。设cmin=mini∈[n]ci为最小库存。算法4与离线贝叶斯预期LP基准（即，预期LP[{Ft}T T=1]）的竞争比至少为1−1√cmin+3。此外，它在时间上运行Poly（n，T，P T∈[T]|Zt|），给定oracle访问离线算法进行分类优化（假设3）。
定理EC.1的证明遵循与定理2类似的结构：我们首先使用归纳法来证明{EI i，t}是算法4的未来收益的下限（第（i）部分），然后引入线性程序来证明E ci i，1至少是乘积i对预期LP的目标值的贡献的1−1/√ci+3（第（ii）部分）。
定理EC.1的证明。命题2证明了运行时间，第3.3.1节中的简单DP可以在多项式时间内求解。竞争性证明分为两部分：第一部分。在这里，我们显示了对于任何产品i、时间t和库存i，算法4中的产品i和当前库存i在时间t的未来预期收入至少为E i i，t，通过时间t从t+1到1的归纳。由于我们的边界假设E I I，t+1=0，所以满足基本情况t=t+1。
现在，假设从时间t+1到t+1，诱导假说成立。考虑时间t的算法。以概率XS，t，zt对分类Sû进行采样。让S⊆S⊂是丢弃后在时间t提供给消费者的产品组合。对于库存为i的任何产品i，如果E i−1 i，t+1+ri zt<E i i，t+1，则算法将其丢弃。通过在时间t+1的诱导假设，它保证获得未来预期效用至少最大值{EI i，t+1，⑪zt（´S，i）（ri zt+E i−1 i，t+1）+（1-⑪zt（´S，i））E i i，t+1，}。由于选择模型满足可替代性（假设1），因此对于所有i∈S∈，zt（⑪S，i）≤⑪zt。因此，通过与引理EC2的证明类似的计算，归纳假设在时间t时成立，即e i i，t下界为产品i的未来预期收入和时间t的库存i。因此，算法4从时间1开始的产品i的预期收入至少为e ci i，1。
第（ii）部分。这里我们显示E ci i，1至少是产品i对预期LP目标值的贡献的1−√c 1 i+3分数[｛Ft｝T T=1]。注意，缩放{ri-zt}不会改变比率。
因此，在不丧失一般性的情况下，我们将乘积i对期望LP[{Ft}T T=1]的最优目标值的贡献归一化，即。，
（）
鉴于上述观察结果和（EC.1）中的Bellman更新，考虑以下给出比率最坏情况值下限的原始线性程序：
（EC.5）
其中变量是{ri zt}和{EI i，t}。为了证明我们的结果，足以证明对于所有可行的库存{XS，t，zt}（即，P t，zt，S XS，t，zt⑪zt（S，i）≤ci），程序（EC.5）的值至少为1−√c 1 i+3。为了看到这一点，我们通过切换外部求和和最大算子来放松（EC.5）中的第一个约束，这提供了如下放松的线性程序：，
（）
我们用双变量αt I、βt I和γ编写其对偶程序如下
（）
通过弱对偶，任何可行的对偶解都提供了原始解的下界。
设qt≜P zt∈zt P S∈S XS，t，zt⑪zt（S，i）。根据定义，P T T=1 qt≤ci。现在，假设我们有兴趣生成一个可行的对偶赋值，其中对应的所有约束都是紧的，即以下程序的解决方案分配（EC.6）
注意，下面的引理EC.3足以完成定理EC.1的证明。
引理EC.3。对于任何非负序列｛qt｝T T=1，使得P T T=1 qt≤ci，程序（EC.6）的目标值至少为1−√c 1 i+3。
为了显示引理EC.3，我们使用了在Alaei（2014）中开发的技术引理（定义EC.1，引理EC.4），如下所述。
定义EC.1（砂/屏障工艺，Alaei 2014）。考虑一条无限长的胶带，在位置0处有一个单位的无限可分割的沙子，在位置1处有一道屏障。q1。，qT（所有qT∈[0，1]）和参数γ∈（0，1）作为输入。沙子和障碍物在T轮中逐渐向右移动。在第t轮，发生以下情况。
选择磁带上最左侧的砂的γ分数，并将该砂的qt分数向右移动一个位置。这可以正式定义如下。设s j t表示t轮开始时位置j处的砂量，设yt j∈[0，1]表示t轮期间从位置j处选择的砂分数。选择yt j，使得P i s j tyt j=γ，并且对于某个整数θt，对于任何j<θt，yt j=1，对于任何j>θt，yt j=0。因此，在第t轮期间，一定数量的沙子从每个位置j移动到位置j+1。当障碍物位置的沙子总量超过1−γ时，障碍物在任何一轮结束时向右移动一个位置。我们将使用λt表示在t轮开始时屏障的位置。
引理EC.4（砂/屏障过程，Alaei 2014）。对于任何γ和任何序列q1。，qn，在整个砂/障壁过程中，第t轮开始时障壁的位置，即λt，满足
（）
引理EC.3的证明。我们现在通过使用沙子/屏障论点来构造程序（EC.6）的这种可行的解决方案。设｛s j t｝、｛yt j｝和｛λt｝为定义EC.1的沙/屏障过程中定义的变量，参数为t，｛qt｝t∈[t]，γ=1−√c1 i+3。将不同的库存水平视为砂带上的不同位置，但顺序相反。换句话说，位置ci−I对应于库存水平I（基本上，沙子从较高的库存水平移动到较低的库存水平）。我们有T轮沙子/屏障过程。在该过程的第t轮，对于i∈[ci]，在每个位置ci−i处总共有s c t i−i个沙子单位。沙子st ci−I的量分为决定αt I的选定沙子s c t I−I yt ci−I和决定βt I的未选定沙子st ci–I（1−yt ci–I）。总之，我们如下构造对偶解，
（）
注意，程序（EC.6）中的所有约束都通过上述双重构造得到满足。根据定义EC.1中对砂/屏障过程的描述，如果屏障从未通过位置ci，即λT+1≤ci，则只有胶带的ci位置才会有砂（因此该结构定义明确）。调用引理EC.4并重新排列术语完成证明。□