Ski Rental 问题

确定阈值 ​

Ski rental 的问题本身只给出未知停止时间下的租／买选择；确定性阈值是第一条基线，随机购买时刻属于后续解法扩展。在竞争分析公理库竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。中，设日租 1、购买价 (B)、季节长 (T)。离线最优 (OPT(T)=\min(T,B))。算法先租 (B-1) 天，若仍继续则第 (B) 天购买，得到竞争比 (2-1/B)。

若提前一天买，对手可在买后立即结束；若永不买，长季节比率无界。这个二难给确定性下界图像。

随机与边界 ​

随机购买时刻可对 oblivious 对手达到 (e/(e-1)) 量级；若 adaptive 对手观察购买决定后再选择结束，保证会改变。取消、残值、非恒定租金或预测信息都会形成新模型。

买入日的 off-by-one 必须与“当天先租还是先买”约定一致。

离散日与连续时间的随机常数和归一化略有差别。引用竞争比时必须同时标明时间模型、购买发生在当天何时，以及对手能观察哪些随机动作。

确定阈值的逐日成本 ​

约定前 $B-1$ 天租，第 $B$ 天若仍滑雪则先买。若 $T=B-1$，ALG=OPT=$B-1$；若 $T=B$，ALG=$2B-1$、OPT=$B$；若更长，ALG 不再增加。最坏比率 $2-1/B$ 正出现在购买当天附近。

任意确定算法等价于某个首次购买日 $d$（或永不买）。对手若在 $d$ 天结束，使算法既付此前租金又购买；若 $d$ 太晚则让季节很长。平衡两类损失得到阈值约 $B$，形成接近 2 的下界。

随机购买时间 ​

连续版本选择购买时间分布，使 survival function 按指数衰减；对每个固定停止时间，期望成本与 OPT 的比率被平衡到 $e/(e-1)$。离散天需要归一化和 off-by-one 修正。每天独立固定概率购买对应几何分布，未必是有限截断模型的最优分布。

保证面对 oblivious 停止时间。若对手观察是否已买再决定当天结束，可专门在购买后停止，随机优势可能消失。

模型变化 ​

有二手残值、购买可取消、每日租金变化或可靠使用期预测时，OPT 与阈值都改变。Prediction-augmented ski rental 会在预测准时改善、预测错时保持鲁棒比；不能仍引用原始 $e/(e-1)$ 当完整结论。

参考资料

• Karlin et al., “Competitive Randomized Algorithms for Nonuniform Problems,” Algorithmica, 1994.
• Borodin, El-Yaniv, 1998.