The Online Reservation Problem
The Online Reservation Problem
复制标题
在线预订问题
作者：
Shashank Goyal;D. Gupta
许多共享经济平台的运作方式如下。所有者列出资源的可用性、价格和合同期限限制。客户建议合同开始时间和长度。业主立即决定是否接受或拒绝每个建议，即使合同是未来的日期。被接受的提案会产生收入。被拒绝的提案将丢失。在任何决策时期，业主都没有关于未来提案的信息。所有者寻求易于实现的算法，以实现最佳竞争比（CR）。我们首先推导出一个下界的CR的任何算法。然后，我们分析所有直观的“贪婪”算法的CR。我们提出了两个新的算法，有显着更好的CR比任何贪婪算法的某些参数值范围。这些算法背后的关键思想是，所有者可以为晚到的更高价值的提案保留一定数量的容量，以提高收入。我们的贡献在于操作这个想法的帮助下，利用阈值的算法。此外，我们表明，如果选择非最佳阈值，那么这些可能会导致不良的CR。我们提供了一个严格的方法，业主可以决定在他们的上下文中通过分析贪婪算法的CR和我们提出的最佳方法。
Many sharing-economy platforms operate as follows. Owners list the availability of resources, prices, and contract-length limits. Customers propose contract start times and lengths. The owners decide immediately whether to accept or decline each proposal, even if the contract is for a future date. Accepted proposals generate revenue. Declined proposals are lost. At any decision epoch, the owner has no information regarding future proposals. The owner seeks easy-to-implement algorithms that achieve the best competitive ratio (CR). We first derive a lower bound on the CR of any algorithm. We then analyze CRs of all intuitive “greedy” algorithms. We propose two new algorithms that have significantly better CRs than that of any greedy algorithm for certain parameter-value ranges. The key idea behind these algorithms is that owners may reserve some amount of capacity for late-arriving higher-value proposals in an attempt to improve revenue. Our contribution lies in operationalizing this idea with the help of algorithms that utilize thresholds. Moreover, we show that if non-optimal thresholds are chosen, then those may lead to poor CRs. We provide a rigorous method by which an owner can decide the best approach in their context by analyzing the CRs of greedy algorithms and those proposed by us.