Non-Additive Two-Option Ski Rental

摘要

We consider a generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. There are two "payment plans" or "options," such that the cost of t time units under option i (for i = 1,2) is given by a_it + b_i, where b_i is a one-time cost to start using option i, and a_i is the ongoing cost per time unit. We assume w.l.o.g. that a_1 ＞ a_2 and b_1 ＜ b_2. (The classical version is b_1 = 0 and a_2 = 0, so that option 1 is "pure rent" and option 2 is "pure buy.") We give deterministic and randomized algorithms for the general setting and prove matching lower bounds on the competitive ratios for the problem. This is the first non-trivial result for the non-additive model of ski rental, which models non-refundable one-time costs.